/aocg/ - Advent of Code 2018 General #69

nippon banzai edition

Previous thread >Not sure what advents of codings is all about?
fuck off then

>want to joinings the leaderboard?
suck my peanus weanus

Attached: 1534732381071.jpg (640x626, 105K)

Other urls found in this thread:

pastebin.com/84ZtavAc
ghostbin.com/paste/ezecj
paste.ofcode.org/BRJ7pEfzdbdWKSrmmKN3jV
en.wikipedia.org/wiki/Three_utilities_problem
en.wikipedia.org/wiki/Complete_bipartite_graph
pastebin.com/frCLtL3v
twitter.com/NSFWRedditImage

First

Well, since I've linked my AoC profile with Github, I'm not going to join a board with any of you autists, that for sure.

Use a fake reddit account and join the party. We're only 63.

what data structure did you guys use for day 7?

lists and dictionaries

You can go into settings and make your account appear anonymous on AoC.

>he has a public github account
>not gitlab
I bet you commit with your real name and identifying email address, too. Imagine being this desperate for recognition.

Attached: 1419109123514.png (626x683, 265K)

hashtable

A list of tuples of Char, and a list of Char.

I wrote a script that checks the github repos of people in the daily leaderboard, grabs python code, runs it in a vm against my input, and submits the answer

please elaborate

I have a gitlab too, also with my full name and email.

And yes, it helps for getting recognition, among other things by people looking to hire me :^)

how is it doing?

you were completely right; the anomlies are identical between runs. do you feel like i'd be copping out if i'm running into errors due to machine precision?

is it even worth generating the color map like this with these errors... i only have 10gb ram which limits how much i can reasonably memoize, it'd take 7-8 hours to generate and would still have these borked sections

>what causes the dividers
see the prompt for day 6. those dividers are actually bisectors in manhattan geometry.

also i took your advice and hashed for colors for a consistent palette between runs, see pic. now 'random' isn't even imported

a directed adjacency matrix to represent the requirements
a node list to represent units and completion times
and a worker list to represent availability or assignments

Attached: big girl input runs comparison.png (1920x1080, 499K)

dicts = hash tables

IntMap [Int] and IntMap Int

Today was quite the ramp up.
Part 1 was somewhat easy but I found retrofitting the timing simulation quite hard.

Attached: code.png (1240x3480, 410K)

I'm in the global top 60

In an ideal world, anyone stupid enough to use glorified social media would be exempt from being hired in any circumstances. You ruin it for the people who value their privacy.

>being this much of an insecure neet

ok i gave up on part 2 last night but i'm gonna give it another go. any tips from anons?

Attached: notears.png (274x300, 185K)

Not him, but that's my situation too. I'm a undergrad, I NEED to show the things I do, otherwise companies don't even care to call me.

user, in an ideal world, you wouldn't need to hide your privacy because there would be no CIA niggers tracking you, facebooks profiling you for advertisment or Russian slavs stealing your identity

>he didn't use a stack that shuffles the values internally

Attached: 1539294129963.png (820x729, 185K)

I am the original user, and I'm not an undergrad, I have a PhD. I also need to show things I've worked on, because SOMEONE(!!) has successfully spread the meme that fresh grads can't program.

Attached: cs-grad.png (694x801, 116K)

to code my graph
next: hashtable char -> char list, for each vertex it points to next vertices
from: hashtable char -> char list, for each vertex it points to previous vertices

during simulation
reached: a hashtbl for task done (used to know which tasks are available)
current: a hashtbl int -> char list, which is the events list (ie task running and their end time)
available: a string list, for the task that are ready to run (waiting for a free worker).

And why does that require you to use your name instead of just an alias? Hint: it doesn't, you choose to.

god fucking damn, why can't I post my code here? getting 403s all the time

you can rename and refactor a lot to make it a bit nicer: pastebin.com/84ZtavAc

your code is clearly nsfw

are the words "free" and "assemble" banned for Marxist propaganda?

>When you can't be bothered to write elegant code any more.
Time to get fucking mutable.

Attached: 1503235999787.png (1920x1080, 1.77M)

I use the first letter of my name and my lastname as an alias. The problem is that my lastname is so rare, that when you google it, all the results are my relatives. And I'm the only one whose first name starts with that letter.

fuck, spent way too long fiddling with part 2. it ended up being ugly as fuck so i'm posting part one instead
std::string solve_part_one(std::ifstream& ifs)
{
std::unordered_map node_parents;
std::unordered_map node_children;
for (std::string line; std::getline(ifs, line);) {
char parent = line[5];
char child = line[36];
node_parents[child].insert(parent);
node_children[child];
node_children[parent].insert(child);
node_parents[parent];
}

std::string correct_order;
correct_order.reserve(node_parents.size() + 1);
while (!node_parents.empty()) {
char next_step = 'Z' + 1;
for (const auto&[k, v] : node_parents) {
if (v.size() == 0 && k < next_step)
next_step = k;
}

correct_order.push_back(next_step);
node_parents.erase(next_step);

for (char c : node_children[next_step])
node_parents[c].erase(next_step);
}

return correct_order;
}

ghostbin.com/paste/ezecj

Okay, now THAT was a bit messy. Implementing a priority queue was less readable than I thought.
Here's the elementary operations on pqueues and the main body...

Attached: aoc 2018 day 7 main.png (1222x302, 12K)

can someone explain to a brainlet the logic behind solving part 1, I sorta get it but I'm a bit lost

... here's the implementation of toposort (part 1)...

With hindisight this could have been reimplemented in terms of part 2, but whatever.

Attached: aoc 2018 day 7 toposort.png (561x250, 5K)

... and this is the implementation of schedule (part 2).

This one actually supports any number of workers and different functions for timing purposes.

Attached: aoc 2018 day 7 schedule.png (851x303, 9K)

>pour over part 2 last night
>feel helpless
>go to bed, swear i'm done with this retarded aoc shit
>come back in the afternoon
>start from scratch
>get it in 30 minutes

my fellow brainlets, do not underestimate just how much shit like mood can effect your performance. for now, i'm still /not filtered/

Attached: sundowner.jpg (500x540, 58K)

1. For each step, list the steps which must come after it.
2. Find the steps which can be done now (aren't in any of the lists)
3. sort them and take the first, remove it from your dataset, add it to your results
4. repeat 2-3 until finished

>tfw have already forgotten what last day was about

by last night i mean today's puzzle

That's genius

>Comparing the drop off this year to previous years.

Attached: Brutal.png (325x325, 136K)

Just wish the problems came out at 9 or 10 instead of 12

i'm a brainlet and i remember only having like one question that took me more than 30 minutes in the first week. nothing so far has been like insanely hard, but i definitely thought i remembered the first week being a complete breeze last year. even the knot hash thing people meme about was pretty easy, just slightly hard to conceptualize. there was no real wall for me until day 11 with that hexagon shit

map

basically map each task to an ordered set of its dependencies. literally an in-degree adjacency list of the graph, pre-sorted

Will you be proud or disgusted that I solved it with recursion?

std::map
where Node is a struct { char key; int degree; std::vector edges; }
kind of a minimal graph

Or you can use priority queues you pajeet.

Neat.

Attached: dependencies.png (948x461, 41K)

Sounds neat, why would I be disgusted?

>plebbit visualizations
why? every challenge comes with one

Attached: based ascii.png (536x208, 5K)

Today wasn't brainlet filter since I made it.

beautiful

feels like i'll get filtered tomorrow

Feels dirty, but it works.

const fs = require('fs');

const input = fs
.readFileSync('input.txt')
.toString()
.split('\n');

console.time('Day 7 Pt 1');

let nodes = {};

input.forEach(step => {
let char = step.slice(5, 6);
let target = step.slice(36, 37);
if (!nodes[char]) nodes[char] = [];
nodes[char].push(target);
});

let seq = '';

function traverse(nodes) {
let options = Object.keys(nodes);

if (options.length === 1) {
seq += options[0] + nodes[options[0]];
return;
}

options.forEach(char => {
options = options.filter(x => nodes[char].indexOf(x) === -1)
});
options = options.sort();

if (options.length > 0) {
seq += options[0];
delete nodes[options[0]];
traverse(nodes);
} else {
return;
}
}

traverse(nodes);

console.timeEnd('Day 7 Pt 1');

console.log(seq);

Looks nice, similar to mine but I just used a while loop to keep going until I finished. How long does it take on the standard input?

Just under 1ms, faster than I expected

Similar. Part two takes it up to about 7ms

My shit-tier haskell that I wrote at 3am: paste.ofcode.org/BRJ7pEfzdbdWKSrmmKN3jV
Sorry for link but it was too long for Jow Forums :(

>deep recursion

i'll never be this good

>too long for Jow Forums :
post a screenshot of your code next time

Attached: Code_cBgtTQc5eA.png (838x966, 144K)

>importing Control.Arrow just to use &&& once

have some decency

Attached: dependencies.png (2803x1219, 883K)

post this graph without edges crossing

>two women on the global leaderboard
>one of them is a man
Why is the advent of code so sexist?

>Why is the advent of code so sexist?
what do you mean? can you extrapolate on that?

spot the K3,3

Generators are nifty.

def toporder(adjacency):
indegree = defaultdict(int)
for u, adjacents in adjacency.items():
indegree[u]
for v in adjacents:
indegree[v] += 1

queue = [u for u, d in indegree.items() if not d]
heapq.heapify(queue)

while queue or sum(indegree.values()):
u = yield heapq.heappop(queue) if queue else None
if not u:
continue
for v in adjacency[u]:
indegree[v] -= 1
if not indegree[v]:
heapq.heappush(queue, v)

You can use this to solve both parts. For part 1, just send generated values back into the generator. For part 2, send completed steps into the generator and it will generate new steps if any are available.

>>one of them is a man
transphobia is not tolerated on 4channel

?

Why are these lines all crazy?

>4 off from user's input
>7 off from other user's input

Attached: 1515538295506.jpg (1280x720, 104K)

not them but en.wikipedia.org/wiki/Three_utilities_problem

en.wikipedia.org/wiki/Complete_bipartite_graph

This is my first, so I did a bunch of last year's problem over the weekend. The hex grid one took me a while but it worked out to be a very pretty and simple algorithm; probably the most satisfying of the AoC puzzles so far. They're a lot more fun in general when you're not rushing to type out the first algo that pops into your head, but I'm committed now.

Give 2017 day 23 a shot, part 2 is probably the most fun I've had in aoc

Dictionary for part 1. Each step is a key and the value points to a list containing that step's dependencies.

For part 2 I used this setup which might be a bit over engineered but it works great

class Worker:
def __init__(self, ID):
self.ID = ID
self.current_step = ''
self.time_left = -1

def tick(self):
ret = ''
if(self.current_step != ''):
self.time_left -= 1
if(self.time_left == 0):
#print("Worker "+str(self.ID)+" returning: "+self.current_step)
ret = self.current_step
self.current_step = ''
self.time_left = -1
return ret

def is_free(self):
return self.current_step == ''

def do_step(self, step, time):
self.current_step = step
self.time_left = time
#print("Worker "+str(self.ID)+" now working on: "+self.current_step)

I did it! I have no idea what the HELL was wrong, just rewrote the whole function.
Using recursion was a mistake.

Attached: 1513587546943.jpg (1920x1080, 155K)

Free input and solution 4 u.
pastebin.com/frCLtL3v
A:V
B:
C:E F M N
D:C E F H J R Y
E:B K
F:
G:K
H:A E I O
I:T
J:E F H M O R T Z
K:
L:A F M T
M:R X
N:F G
O:K
P:A C E I M S U Z
Q:C D E L N O P U W
R:G O T X Y Z
S:A C G H J L X Y
T:F V
U:B C D E H I J L M S T V Y
V:
W:B D H L M O P R S T U X Z
X:I
Y:V
Z:K V X

[Part 1] Step Order = BFKEGNOVATIHXYZRMCJDLSUPWQ
[Part 2] Duration = 1020

It's the best that dot can come up with given the input's dependency hell and my constraint that letters must be on the same line if they have as many dependencies.
I have no idea how it decides to bend the edges. I'm glad it's nearly usable, like you can check if there's an edge between M and U. But the twist in Z->F is ridiculous.

And I just realized I should've filtered all edges a->b if there's a path a->...->b. They're completely redundant for the problem but, worse, they clutter the graph.

>Using recursion was a mistake
I don't think Part 2 can really be done using recursion but here's Part 1 using recursion in python:
def get_order(instructions):
#find all steps with no dependencies
no_deps = get_no_dependencies(instructions)
#if the list is empty, return empty string
if not no_deps:
return ''
#put list in alphabetical order
no_deps.sort()
#modify instructions so this step is no longer a dependency in any other step
#also remove the current step entirely from instructions
new_instructions = remove_dependency(no_deps[0], instructions)
#the alphabetical first step is returned, recurse using modified instruction list
return no_deps[0] + get_order(new_instructions)

sure it can

I thought Haskell was supposed to be elegant...

i haven't read one legible haskell program yet

Worker struct and a deque for part 2

for you bb

Attached: ll.png (1001x1373, 253K)

#!/bin/bash
set -e

push() { echo "$1" | grep -o . >"$stack" & }

remainlen()
{
local c prev stack=$(mktemp -u) buf="$1"
local -i changes=-1
mkfifo "$stack"
while ((changes)); do
push "$buf"
changes=0
buf=
prev=
while read -r c; do
if [[ $c != "$prev" ]] && [[ $c == "${prev^^}" || $c == "${prev,,}" ]]; then
changes+=1
prev=
else
buf+=$prev
prev=$c
fi
done "/tmp/aoc${run_num}$RANDOM" &
(( (++n) % j )) || wait
done
wait
echo "part 2: $(cat "/tmp/aoc${run_num}"* | sort -rn | tail -n1)"

$ time bash 5.sh

mad men

just finished part of day 7. I'm working on p2 now
def partOne(relations):
...: dependencies = defaultdict(int)
...: mapping = defaultdict(list)
...: for item in relations:
...: dependencies[item[1]] += 1
...: for item in relations:
...: if dependencies.get(item[0]) is None:
...: dependencies[item[0]] = 0
...: for i in relations:
...: mapping[i[0]].append(i[1])
...: done = []
...: while len(dependencies) > 0:
...: print(dependencies)
...: choose = min([k for k,v in dependencies.items() if v == 0])
...: for i in mapping[choose]:
...: dependencies[i] -= 1
...: done.append(choose)
...: dependencies.pop(choose)
...: return ''.join(done)

- a dict mapping a step to a list of its dependents (i.e. adjacency list)
- a dict mapping a step to the number of remaining prerequisites (i.e. indegree)
- a heapq for the topological sorting queue (popping should be faster than min then remove on any other data structure)
- for part 2, a list of N workers, which in turn are just tuples containing the current step and ETA

It can be nice, but me writing it at 3am is not

I've only done through 18 so far, but unless I get filtered, I'll probably get to it this weekend.

>been an hour with no posts

this shit really is dead. lets have a moment of silence for our filtered brethren

Attached: good_joe.jpg (600x631, 88K)

using job = char
map for dependencies
map to store when a job is finished.

using a vector and using a custom comparason function to sort it would have been cleaner though

It's always dead right before the next puzzle drops

I'm making a list and checking it twice, but I can't quite tell why my code won't play nice.

Just used dicts and sorted lists when I did it in python. Did proper maps, sets and priority_queues when I re-did it in C++.

Does any know a good python priority queue implementation? I just see heapq and queue.PriorityQueue built-in, both of which look pretty lacking. I really want one I can pass a custom comparison function to without going through the make a whole custom class with a priority field they want.