Advent of Code

[Greenbank]

Hoping to sober up enough to be able to do Day 9 tomorrow today.

Hic.

I foresee much keyboard thrashing and grumpiness...

[Ben T]

nothing taxing as long as you don't try and be too fancy.

[Greenbank]

I've written enough stuff that parses input (specifically SQL and CSV) to understand the joy of string parsing with escape characters. Even with a slightly foggy brain from a mild hangover.

(click to show/hide)

I guessed that the garbage characters were going to be significant so part (b) was a simple addition of a counter increment in the appropriate bit of the pre-parser.

Did the parsing in two stages, one to clean the input stream and count the garbage, then a second one to parse the garbage free input into the groups, then a recursive function to score it all.

I'm secretly hoping that someone attempts this with a regex and eventually learns the lesson about regular expressions and context-free grammars. Brings back happy memories of university lectures about the Church-Turing thesis and the Pumping Lemma.

I love state machines; my Comp Sci dissertation was on the use of (non-)deterministic finite state automata in regular expression engines.

[Manotea]

Inspired by Greenbank, I started reading this

Then realised I had something else to do today. 

[Ben T]

I've written enough stuff that parses input (specifically SQL and CSV) to understand the joy of string parsing with escape characters. Even with a slightly foggy brain from a mild hangover.

(click to show/hide)

I guessed that the garbage characters were going to be significant so part (b) was a simple addition of a counter increment in the appropriate bit of the pre-parser.

Did the parsing in two stages, one to clean the input stream and count the garbage, then a second one to parse the garbage free input into the groups, then a recursive function to score it all.

I'm secretly hoping that someone attempts this with a regex and eventually learns the lesson about regular expressions and context-free grammars. Brings back happy memories of university lectures about the Church-Turing thesis and the Pumping Lemma.

I love state machines; my Comp Sci dissertation was on the use of (non-)deterministic finite state automata in regular expression engines.

I'm reasonably au fait with regex but wouldn't attempt to use it to try and count group nesting.... I didn't see any need for recursion but whether it could have made it more elegant I don't know. Mine's a fairly simple literal interpretation of the logic as described https://github.com/bjtaylor1/AoC2017/blob/day09part2/Day09/Program.cs
nothing wrong with recursion if you just like it though

[Pickled Onion]

...then a second one to parse the garbage free input into the groups, then a recursive function to score it all.

The input was well-formed enough that it only required counting the { up and } down

I'm secretly hoping that someone attempts this with a regex and eventually learns the lesson about regular expressions and context-free grammars.

This particular one would be fairly straightforward with a regex, but yes it's the perennial question "how do I parse **ML with a regex?" A: DON'T!!

For a laugh I solved this using regular expressions, it took rather longer to code than doing it with a pencil but the result was quite impressive nonetheless.

[David Martin]

Just plough through and process it as a stream.

(click to show/hide)

Set your initial state. 0 group score, not in garbage.
If the character being evaluated is ! skip the next character.
else, if in garbage, garbage ends or +1
else if { levels go up , add levels to score
else if } levels go down
else nothing
step on to the next character.
 
One pass. I thought it might get more interesting.
My code and input is at https://github.com/davidmam/aoc2017

I did come across an interesting puzzle that was easily solved to a certain state with matrix algebra. I then have to sort a matrix to get the minimum diagonal to get the appropriate order of rows.

[Oaky]

Just plough through and process it as a stream.

(click to show/hide)

Set your initial state. 0 group score, not in garbage.
If the character being evaluated is ! skip the next character.
else, if in garbage, garbage ends or +1
else if { levels go up , add levels to score
else if } levels go down
else nothing
step on to the next character.
 
One pass. I thought it might get more interesting.
My code and input is at https://github.com/davidmam/aoc2017

I did come across an interesting puzzle that was easily solved to a certain state with matrix algebra. I then have to sort a matrix to get the minimum diagonal to get the appropriate order of rows.

I don't think you pushed your day 9 changes to github yet

(click to show/hide)

I also built a very similar state machine.

I decided from the off that garbage and/or cancelled characters might be significant, so I counted them anyway.

When part 2 was revealed, I just had to slightly adjust my counting rules to match the ones asked for (actually it wasn't strictly necessary as it could be calculated trivially from thecounts I was returning anyway)

https://github.com/MarkNOakden/AdventOfCode/tree/master/17/09

[David Martin]

Good spot. Didn't tick the 'push to origin automatically' box in Sourcetree.

[Oaky]

(click to show/hide)

I realised when reading this:-

https://www.reddit.com/r/adventofcode/comments/7ild5h/2017_day_9_switching_it_up_at_compiletime/

that I didn't read the spec closely enough (not in a way that changes the potential answer to either part of the question, given that the input is well-formed wrt the actual rules (and not those I thought were in place)).

I was looking at the reddit solution and thinking "it doesn't allow for ! cancels except in garbage: what about situations with e.g. "{!<<<<>}" - won't it count those incorrectly?".

It's only going back to the spec in the question that I realised that "!" is described as only appearing within garbage. 

[Diver300]

The instructions for day 10 almost lead you though the programming steps needed. It reads more like a lesson in computing than a puzzle.

[David Martin]

Agreed. Involved but not hard. Bleary eyed typos notwithstanding. Not sure I have the oomph in the morning to test-suite it. I'd have sorted the tests after finding the things that needed to be tested, by which time they would be unnecessary.

[David Martin]

Ouch - my head hurts a bit after trying to sort that one out. Probably an inelegant solution to calculate the total number of steps. I'm sure there must be a better way to resolve the axes than a series of if/else looking at the relevant cases. Possibly something matrixy but my brain isn't functioning.

[Croft]

Day 11

(click to show/hide)

David Martin, you can simply convert each movement into a 3-axis vector:


         x   y   z
N  -> (  0,  1,  1 )
NE -> (  1,  1,  0 )
SE -> (  1,  0, -1 )
S  -> (  0, -1, -1 )
SW -> ( -1, -1,  0 )
NW -> ( -1,  0,  1 )

Then distance is just Σ(abs(x_i) + abs(y_i) + abs(z_i)) / 2

[Greenbank]

(click to show/hide)

Couldn't remember the details of the 3D co-ordinate solution (and am trying to do this from memory and not using google) so did it with a 2D co-ordinate system and a single if/else in the function to calculate the number of moves.

[Croft]

Day 11

(click to show/hide)

I don't think it requires memory or Google. Just sketching it out on paper using some grid lines at 60^o is enough to work out the fairly simple rules for moving in hex space.

[Oaky]

(click to show/hide)

I did this one using pandas again.

I used a 2D coord rep where the origin is at (0, 0) with the neighbours being at

n - (0, 2)
ne - (1, 1)
se - (1, -1)
s - (0, -2)

etc...

the step distance from any point was calculated conceptually by going diagonally in the appropriate direction until either x or y is zero, then adding either the x coord or half the y coord of where you cross the axis.

in practice,  you don't have to care ehat the direction is as the steps are symmetric in the axes, so you can use abs() to map the resulting coordinate into the NE quadrant and work the steps out from there.  the distance to one of the axes is now the smallest coordinate and the remaining steps are either the x-y if x-y is positive or -(x-y)/2 if x-y is negative (or 0 if x=y).

Here's what my path looks like:-



https://github.com/MarkNOakden/AdventOfCode/blob/master/17/11/day11.ipynb

[David Martin]

Day 11

(click to show/hide)

David Martin, you can simply convert each movement into a 3-axis vector:


         x   y   z
N  -> (  0,  1,  1 )
NE -> (  1,  1,  0 )
SE -> (  1,  0, -1 )
S  -> (  0, -1, -1 )
SW -> ( -1, -1,  0 )
NW -> ( -1,  0,  1 )

Then distance is just Σ(abs(x_i) + abs(y_i) + abs(z_i)) / 2

I must admit that trying to sort that at early morning after dealing with a frozen pipe leading to a major water leak in the house was challenging enough - I thought it should be able to be done something like that. Instead I did it the hard way.

[David Martin]

Day 11

(click to show/hide)

David Martin, you can simply convert each movement into a 3-axis vector:


         x   y   z
N  -> (  0,  1,  1 )
NE -> (  1,  1,  0 )
SE -> (  1,  0, -1 )
S  -> (  0, -1, -1 )
SW -> ( -1, -1,  0 )
NW -> ( -1,  0,  1 )

Then distance is just Σ(abs(x_i) + abs(y_i) + abs(z_i)) / 2

I am struggling to see how you come up with that matrix.

[Greenbank]

(click to show/hide)

although you'll need to rotate it for this challenge

[Croft]

Greenbank beat me to it, but..

(click to show/hide)

Just sketch it out and count which axes you cross as you move in each of the 6 directions:

[David Martin]

Doh! I was looking at steps but not in the right directions.

[Greenbank]

(click to show/hide)

Doh! I was looking at steps but not in the right directions.

That's what I did (since I couldn't remember it clearly enough), and when I couldn't figure it out in 20 seconds or so I gave up and continued with a 2D approach using N=[0,-1], NE=[1,-0.5], SE=[1,0.5], and then similar calculations as Oaky above.

At the time I'm not interested in the perfect solution, I'm (personally) only interested in doing it quickly and without looking anything up. Other approaches are available. But afterwards it is interesting to see the other (often better) approaches.

[Greenbank]

Underwhelming today...

Jo's graphs seem to back up my suspicion that 2017 (so far at least) is quite a bit easier than the previous years: https://github.com/jwoLondon/adventOfCode

[Oaky]

(click to show/hide)

It felt like cheating using the networkx library today.

Didn't stop me, though.  Gotta get those quick answers in where you can!

I'll probably revisit later on today and do it in pure python.