/aocg/ - Advent of Code 2018 General #37

>Incredibly tired
>Understand the problem but fail to implement it for hours because as soon as my head wraps around what I'm trying to solve I forget the context, or get hungry and go eat something
>Guided by the stupidest test case written above, somehow end up with this solution
>Thinking it won't work but check out some test cases
>It actually works
I don't even know. I feel like I'm doing a ton of pointless shit here

Attached: Screenshot from 2018-12-20 05-48-42.png (573x525, 65K)

import sys
from collections import defaultdict
Positions = []
CurPosition = 0 + 0j
DistanceField = defaultdict(int)
for CurChar in sys.stdin.read()[1:-1]:
if CurChar == '(':
Positions.append(CurPosition)
elif CurChar == ')':
CurPosition = Positions.pop()
elif CurChar == '|':
CurPosition = Positions[-1]
elif CurChar in 'NESW':
NewPosition = CurPosition + {'N':-1j,'E':1,'S':1j,'W':-1}[CurChar]
DistanceField[NewPosition] = min(
DistanceField.get(NewPosition,DistanceField[CurPosition]+1),
DistanceField[CurPosition]+1
)
CurPosition = NewPosition

print("Part 1: " + str(max(DistanceField.values())))
print("Part 2: " + str(sum(map(lambda x: x >= 1000, DistanceField.values()))))

Attached: 1424250698924sm.png (64x64, 4K)

do you need to create some kind of graph for part 1? im just making sure im not overthinking this.

it would help you to debug it if you could draw it on the screen
but no you don't need to

can you describe your solution to me?

You don't 'have to' do that, you can use dictionaries of points.

>keep a stack of junctions so you can go backwards and find the last junction when required
>read input from left to right
>anything in "NSEW" means step in that direction
>"(" means we're at a junction, so save this location (add to junction stack)
>"|" means we're done with this branch, go back to the last junction
>")" means we're done with this entire junction, go back to the last junction and pop it off our stack of junctions

I found it simpler to build the graph using this method, and then traverse it afterwards to find the furthest distance away. It's not the most efficient, but this method also let me solve part 2 with only two extra lines of code.

I also finished the hard-branching problem.
If we do not actually have to keep track of positions after branches, why does he explicitly state the opposite?
Regardless of which option is taken, the route continues from the position it is left at after taking those steps

just why?
if you want to make the problem hard, I have no issues with that, but at least make your testcases reflect that...
welp, I whipped out the big guns and wrote a parse grammar.
pastebin.com/ZXNsg6Fw

you still have to describe the connections between those points?

so you don't need to create a graph but you did it anyway?

I'm not that user.

No

You only need to keep track of a given point's shortest path length, so no you don't need connections

the rabbi doing gods work today. I like it

Attached: DeepinScreenshot_select-area_20181220104810.png (657x35, 7K)

I ended up writing the naive stack solution like many other. In retrospect like you say it shouldn't work but the inputs seem to only have relevant branches be detours back to their starting point.

Classic eric.

If there's one thing I've learned about AoC, it's that if it sounds like a hard problem, the data is probably set up to make it an easier problem.

If there's one thing I've learned it's that Eric Wastl is terrible at writing descriptions and coming up with good examples for his puzzles

If there's one thing I learned about AoC it's input parsing AABB collision heat maps stacks queued processes recursion linked lists visualization summed area tables 1d cellular automata finite state machines autism bfs pathfinding assembly pattern skip fluid simulation reverse engineering

hm

Does anyone have the "Chad decompiler vs virgin optimising compiler" calendar image from last year?

Learn networkx instead of shitting around writing code that doesn't work.

Wait you could actually not do all possible branches?
No wonder I didn't understand how people were solving this shit

Here's your (((you))) Mr.rabbi

nope I wish, that's me...

Attached: DeepinScreenshot_select-area_20181220122808.png (595x20, 2K)

I am using C# and i use BFS. I have a node-like structure. It breaks the loop as soon as an elf dies and increases its attack damage

>why doesn't eric spoonfeed me?

Small input that actually branches pastebin.com/V91Y5jB0

It's a shame that he did so poorly early on and he's not higher on the private leaderboard. Hope to see him again next year.

I wasted some time trying to parse the string into a more structured regex type first, in the end I just built an adjacency map from the string directly

Attached: file.png (918x916, 393K)

is 801 / 0 the answer for this?

>input contains poison tracts to discourage tree length calculations like (WNSE|)
fucking cunts

One of the first paths go 800 steps S and 800 steps W so part 1 should be 1600

> $ time python advent20.py
801
0
python advent20.py 0.23s user 0.01s system 76% cpu 0.324 total

seems right.
it's 800 units not steps

How would you reach a room 1600 steps away passing only 801 doors?

in the examples ascii drawings the rooms and doors are both 1 unit, so probably did the same thing as me and set the step size to 2. now there are 400 steps in each direction totalling 800 steps and 1600 units.

There are 800 S and 800 W, do you honestly believe that SW would only be 1 away?

okay that is what I get for not looking at my input. you are right there are 800 S and 800 W so it should be at leaast 1600 steps. I just assumed there were 400 each

>make retarded class in python to solve expecting to have to wrestle it into usable state for hours
>get amusingly high result and put it in for kicks
>"That's the right answer! You are one gold star closer to fixing the time stream."
>second part is 5 minutes off with a couple of addendums
pastebin.com/NM1Z8fzk
what in the bloody fuck?
why does this even work? why would it ever even work like this?

yeah I fixed my program to handle branches correctly, apparently the puzzle input doesn't require it. Now I run out of memory when I try to run lol

801 doors is the maximum distance from the farthest room, 0 rooms reached with at least 1000 doors traversed, 603 with at least 500 doors, 1403 with at least 100 doors

nice. since the official input never required it, I didn't even find the silly mistake I made.
time python advent20.py
2400
621500
python advent20.py 3.57s user 0.07s system 99% cpu 3.663 total

are you now satisfied with the result?
and pls give bigger boy

and what about now?
1600
391602
python advent20.py 17.35s user 0.50s system 99% cpu 17.993 total

Yes that is correct, Big boy input pastebin.com/1MtdqNnw

Does the number of paths > 1000 fit in a 32-bit integer?

what do you say?
I say that networkx sucks at memory consumption
part2
15420052
part1
9983
python advent20.py 72.42s user 2.63s system 99% cpu 1:15.42 total

I get 9982 for part 1 and same for part 2. Part 1 should be 995*2+999*8 unless I messed up somewhere. What square does your version think is furthest away?

day20 code

`stepfrom` is the part that builds the map. It makes a single pass over the regex, but the "current position" is actually a set of points instead of a single point, representing all the places we could be given the branches traversed so far. So on `N(E|W)S`, after the `N(E|W)` part, `poss` would be `{(1, -1), (-1, -1)}`, since we could have gone either `NE` or `NW`. After `N(E|W)S` it's `{(1, 0), (-1, 0)}` for `NES` or `NWS`. This was inspired by the NFA->DFA conversion where each DFA state corresponds to a set of NFA states that you could be in at this point in the input.

`flood` is just a regular bfs that records the distance of every node, to get the actual answers once the map is built

Attached: aoc18day20.png (622x1194, 76K)

malformed input
one because there's fucking spaces in it
second because the first branch has an empty group that cannot be skipped
Sometimes, a list of options can have an empty option, like (NEWS|WNSE|). This means that routes at this point could effectively skip the options in parentheses and move on immediately.
This regex has one main route which, at three locations, can optionally include additional detours and be valid: (NEWS|), (WNSE|), and (SWEN|). Regardless of which option is taken, the route continues from the position it is left at after taking those steps.
third because (N|E)(N|E) isn't a valid regex for the problem

9982 is right.it was a one-off error in my BFS.
1990 -1998
-1990 1998

are the coordinates of the furthest points
where North is (-1,0) and East is (0,1)

There are no spaces in the input, there is no problem taking the empty path of the first branch and nothing in the description disallow (N|E)(N|E).

operator overloading is fun.
for (auto c: input) switch(c) {
case '^': case '$': break;
case '(': stack > current; visited |= current; break;
default: {
current.go(c);
visited |= current;
bounds.update(current);
} break;
}

that is quite space-filling

curve is white
first 999 steps are red

Attached: lul.png (5000x5000, 87K)

>repeating visited |= current; in every case

can't you put that outside?

So when do we get the hard problems?

>humble bragging

PASSED: Tested regex, got 3 expected 3
PASSED: Tested regex, got 10 expected 10
PASSED: Tested regex, got 18 expected 18
PASSED: Tested regex, got 23 expected 23
PASSED: Tested regex, got 31 expected 31
PASSED: Tested regex, got 3958 expected 3958
PASSED: Tested regex, got 1600 expected 1600
FAILED: Tested regex, got 9990 expected 9982
FAILED: Tested regex, got 4246 expected 4247
how the fug
In order, those are the five test inputs, this user's from last thread , the smallboi , the bigboi , and my own input. I ended up guessing my answer because my first try was off by +3 and my next one was off by -1

Shows me for trying to be clever I guess, time to build up a dict of points and bfs it instead of trying to do some clever recursive shit while parsing the input, which clearly only sort of works on part 1 and doesn't work at all on part 2.

Maybe you're not accounting for cases in which the path revisits itself or some other corner case

oh fug, didnt notice that.
ix.io/1wsk
made a visualision.

Attached: out.webm (208x208, 1.73M)

Your visualisation made me realize how retarded that whole "no need for a map, i'll just give you a regex dude" thing is retarded
I hate the elfs

don't worry in the future they will be raped by goblins.

I'm pretty sure it's because the approach I attempted doesn't account for shortcuts opening up, and because it's AoC they didn't actually bother requiring that all of the inputs handle that properly (for part 1, anyway):

Before I scrap half of this and rewrite it properly, here's some code from a certified brainlet in case anyone wants to gawk at it:
inp = open("d20.txt").read()

def rparse(s):
o = []
toparse = []
pct = 0
orify = 0
for c in s:
if c in {"N","S","E","W"}:
if pct == 0:
o.append(c)
else:
toparse.append(c)
elif c == "(":
if pct == 0:
None
else:
toparse.append(c)
pct += 1
elif c == ")":
pct -= 1
if pct == 0:
o.append(rparse("".join(toparse)))
toparse = []
else:
toparse.append(c)
else: # |
if pct == 0:
orify = True
o.append(c)
else:
toparse.append(c)
if orify:
o2 = [[]]
for c in o:
if c == "|":
o2.append([])
else:
o2[-1].append(c)
return(o2)
else:
return(o)

def traverse(inp, depth):
depth += 1
longest = 0
stack = []
for move in inp:
if isinstance(move,list):
longest = max(longest, traverse(move,depth))
else:
stack.append(move)
if len(stack) > 1 and {stack[-1], stack[-2]} in reverse:
stack = stack[0:-2]
#print(" "*depth, "longest", length)
return(len(stack) + longest)

def test(inp):
parsed = rparse(inp[0][1:-1])
maxlen = traverse(parsed,-1)
print("PASSED:" if maxlen == inp[1] else "FAILED:", "Tested regex, got", maxlen, "expected", inp[1])

tests = [
("^WNE$", 3),
("^ENWWW(NEEE|SSE(EE|N))$", 10),
("^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$", 18),
("^ESSWWN(E|NNENN(EESS(WNSE|)SSS|WWWSSSSE(SW|NNNE)))$", 23),
("^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$", 31),
(open("d20-e.txt").read(), 3958),
(open("d20-mb.txt").read(), 1600),
(open("d20-bb.txt").read(), 9982),
(inp, 4247),
]

reverse = [{"N","S"}, {"E","W"}]

for t in tests:
test(t)

can you post d20.txt on pastebin?

i want to test this program

Here you go
pastebin.com/jRNwQypB

I'm writing day 10 now. How the fuck am I supposed to deal with a 100.000 pixel-wide image?

you need to close files after opening them.

Hint 1: You're not.

The starting positions are on the range of (-50.000,-50.000) and (50.000,50.000). I shall throw a frame on the middle and hope to get the message?

the vast majority of the image is empty, just keep track of the pixels that aren't empty

>I shall throw a frame on the middle and hope
Why not just draw it around what's there if it gets smaller?

Wait... so all branches are distinct? I thought they could intersect. The description doesn't explicitly forbid regexes such as ^N(EEENWWW|NNES)$.

the description allows more than what was actually required to solve the puzzles

There are no rogue points fucking around going on random directions?

I finally worked our what the fuck is going on in day19 part2. One and a half days analysis fucking outputs for a one liner in python. Fuck this shit.

Why not test it and see for yourself?

if you're using python, why not use a debugger, drop a breakpoint on execution and watch the registers?
It took me like 10 minutes to understand what was going on

because I don't know how to use a debugger nor breakpoints.

if you're completely new and don't mind installing some proprietary crap, get vscode and the python extension.
It's what I've been using thus far

>because I don't know how to use a debugger nor breakpoints
excellent learning opportunity for you then
if you learn how to do these things you will instantly be a 10x better programmer
if you take 1 thing away from advent of code, this should be your priority

can anybody beat 150MHz interpreting the VM in day 19?

Attached: threaded_vm.png (520x563, 63K)

Can anyone post their input and solution?

Attached: many doors edboy yes.jpg (480x360, 12K)

I can do 1 billion instructions in 6.7 seconds, which also comes out to about 147 MHz, on a i5-4210M CPU @ 2.60GHz
did you parallelize it?

I'm not sure how to parallelize something as serial as a VM interpreter..

I wrote a simple python interpreter and got ~12MHz with pypy, then converted it to use direct threading in C. I forgot to shutdown the pypy version in the background when I took that screenshot and it's actually averaging ~164MHz.

I've got a i5-3210M at 2.5GHz

>direct threading
Oh I assumed you were talking about threading as in a parallelized program, what do you mean by threading here?

oh, sorry, it's a term that comes from interpreter/vm literature.

threaded code is where your code that implements a given opcode contains the code to jump into the next opcode handler, no dispatch loop necessary.

in gnu C it's realized like this (address of labels is a nonstandard C extension)

typedef struct {
void* opcode_handler;
int a, b, c;
} inst;

inst program[36] = {
{&&addi, 5, 16, 5}, // &&xxyy means take the address of the label 'xxyy'
{&&seti, 1, 9, 1},
{&&seti, 1, 5, 4},
{&&mulr, 1, 4, 3},
...

and below that you have some labels like this

addi:
registers[c] = registers[a] + b;

// usually this chunk is put in a macro call NEXT or something
pc = pc+1; // point to next instruction
a = program[pc].a; // load operands
b = program[pc].b;
c = program[pc].c;
goto *program[pc].opcode_handler; // load pointer and jump to address

addr:
registers[c] = registers[a] + registers[b];
NEXT(); // decode operands and jump to instruction

...

a dispatch loop has two jumps
one of them being a hard-to-predict jump to an opcode handler, and the second being a predictable jump back to the top of the loop

direct threaded code has just one jump per instruction,
and since it's split up, it's easier to predict the jump targets if certain instructions tend to come before other instructions

ah ok that's basically the same I did, expect I used an index into a address table in the struct instead of putting the void* in there directly. I didn't know that's what it's called.
When I read your post I tried putting the void* in the struct, but it actually made my program slower. I also noticed a slowdown when using ints for a,b and c instead of uint8_t, did you try that out?

Solved it the naïve way like everyone else

import qualified Data.Map.Strict as Map
import Data.Map.Strict (Map)

main :: IO ()
main = do
input Int
solve1 = maximum
solve2 :: Map (Int, Int) Int -> Int
solve2 = length . Map.filter (>= 1000)

buildPaths :: String -> Map (Int, Int) Int
buildPaths input = buildPaths' Map.empty [] (0, 0) 0 input
where
buildPaths' paths stack loc steps ('(':ms) = buildPaths' paths ((loc, steps):stack) loc steps ms
buildPaths' paths stack@((loc, steps):_) _ _ ('|':ms) = buildPaths' paths stack loc steps ms
buildPaths' paths ((loc, steps):stack) _ _ (')':ms) = buildPaths' paths stack loc steps ms
buildPaths' paths stack (x, y) steps (m:ms) =
let loc' = case m of
'N' -> (x , y+1)
'E' -> (x+1, y )
'S' -> (x , y-1)
'W' -> (x-1, y )
steps' = steps + 1
paths' = Map.insertWithKey (\_ x x' -> min x x') loc' steps' paths
in buildPaths' paths' stack loc' steps' ms
buildPaths' paths _ _ _ "" = paths

Neither uint8_t's or separating operands and addresses into separate arrays helped. uint8_t's actually made it slower

Prefetching the next instruction after the current one got me up to 170MHz though, and converting modifications to the PC register to branch instructions that know to prefetch the branched-to instruction hits 180MHz occasionally.

>finally get it working after 7 hours of bug-fixing and rethinking the approach
>it's so slow I pretty clearly did it wrong

Attached: Nano_uguu_ep3[1].png (1280x720, 241K)