Advent of Code

[Oaky]

After day 15's relatively easy problem, what's the betting day 16 is going to be a stinker?

So, day 16 was another easy one.  After this much respite, I'm getting anxious about what Mr Wastl has in store for us next.

(click to show/hide)

I see the Christmas tree in the parking lot got erected once day 16 was complete.

[red marley]

Quite sensibly, our toughest one this year (Day 11) was at the weekend. Last year, arguably the toughest one was Day 19 (molecules), also at the weekend. So perhaps we should brace ourselves for a toughie either tomorrow or the day after. I'm sure he wouldn't be so cruel as to set a time consuming challenge the following weekend given we may have other commitments on Sunday morning.

[Ben T]

Recently went back and did Day 24 of last year and thought that was pretty hard (partitioning).
https://github.com/bjtaylor1/AoC_2015/blob/master/Day24/UnitTest1.cs

[Oaky]

for 2015, day 19 part 2 was the absolute hardest IMO.

[David Martin]

Looking at todays (Just got to it, running part 2), it flips the checksum (almost) with each doubling, so the checksum may be calculable from the starting code without needing to calculate the entire string.

(click to show/hide)

I've done a bit of whiteboarding and I'm pretty sure this is possible, and that it should be feasible to do it in a tiny amount of memory, not much more than a small number of multiples of the initial data input.

No time to play further as I have marking to do and the dept christmas lunch.

[Diver300]

for 2015, day 19 part 2 was the absolute hardest IMO.

That's where I got stuck. This year I've skipped a second part. Maybe I should go back and look at the 2015 ones

[red marley]

I didn't really dig today's (Day 16). Just grinding though some standard string manipulation, which is more or less tedious depending on your language of choice.

I was wrong about this. Looking elsewhere (no links here to avoid obvious spoilers), there are some really elegant ways of processing the input that stop this being such an iterative task. If anyone's feeling like they've done too much proper work today, there's plenty of scope for thinking about some nifty optimisations. I should never have doubted Mr Wastl. What makes these challenges great is their hidden depths.

[Ben T]

I didn't really dig today's (Day 16). Just grinding though some standard string manipulation, which is more or less tedious depending on your language of choice.

I was wrong about this. Looking elsewhere (no links here to avoid obvious spoilers), there are some really elegant ways of processing the input that stop this being such an iterative task. If anyone's feeling like they've done too much proper work today, there's plenty of scope for thinking about some nifty optimisations. I should never have doubted Mr Wastl. What makes these challenges great is their hidden depths.

That's fine, although my viewpoint would be that if iteration works fast enough then any further optimisation is straying from science into art
I was hoping he was going to say that the memory would be something like many GB, not 272.

for 2015, day 19 part 2 was the absolute hardest IMO.

That's where I got stuck. This year I've skipped a second part. Maybe I should go back and look at the 2015 ones

Having done 2016 day 11, 2015 day 19 part 2 wasn't that hard as it's a similar principle:

(click to show/hide)

I got it to run in 1 min 20s using my 'best branch first' algorithm from 2016 day 11, starting from the target molecule and working backwards towards "e", scoring branches first on total length then on 'reducability' (sum of 'reductions' of all replacements contained within, where the reduction of each replacement is the number of characters it will reduce it by)
(without the reducability it churns for ages with no sign of getting hotter)
https://github.com/bjtaylor1/AoC_2015/blob/master/Day19DotNet/UnitTest1.cs#L120

[Diver300]

I didn't really dig today's (Day 16). Just grinding though some standard string manipulation, which is more or less tedious depending on your language of choice.

I was wrong about this. Looking elsewhere (no links here to avoid obvious spoilers), there are some really elegant ways of processing the input that stop this being such an iterative task. If anyone's feeling like they've done too much proper work today, there's plenty of scope for thinking about some nifty optimisations. I should never have doubted Mr Wastl. What makes these challenges great is their hidden depths.

That's fine, although my viewpoint would be that if iteration works fast enough then any further optimisation is straying from science into art
I was hoping he was going to say that the memory would be something like many GB, not 272.

for 2015, day 19 part 2 was the absolute hardest IMO.

That's where I got stuck. This year I've skipped a second part. Maybe I should go back and look at the 2015 ones

Having done 2016 day 11, 2015 day 19 part 2 wasn't that hard as it's a similar principle:

(click to show/hide)

I got it to run in 1 min 20s using my 'best branch first' algorithm from 2016 day 11, starting from the target molecule and working backwards towards "e", scoring branches first on total length then on 'reducability' (sum of 'reductions' of all replacements contained within, where the reduction of each replacement is the number of characters it will reduce it by)
(without the reducability it churns for ages with no sign of getting hotter)
https://github.com/bjtaylor1/AoC_2015/blob/master/Day19DotNet/UnitTest1.cs#L120

(click to show/hide)

Well having failed on 2015 day 19 pt 2, all I could come up with for 2016 day 11 was a swift calculation of the lower limit of the number of moves, which turned out, for my list of objects, to be right.

[David Martin]

And day 17 appears. I may have to think a little.

[Oaky]

(click to show/hide)

Another application for day 11's breadth-first search.

This time I coded a bug into my next-node generation function which instead of checking if (newx, newy) was inside the grid boundary, was instead checking (newx, newx) 

This cause the third part 1 test case to fail, but not the first two.  It also didn't stop my code finding the correct part 1 answer.

I only found it because with that bug in place, running against part 2 turned into an exponential time problem, consuming all the memory in my VM.

I think I'm going to write a library implementation of BFS, using the problems so far as a specification for the required generality. 

[David Martin]

Finally got round to part 1. Part 2 is running, hopefully without an infinite loop.

ETA: hopes were in vain but infinity was removed and results obtained.

[Ben T]

On Day 17 part 2,

(click to show/hide)

Am I right in thinking you have to actually exhaust all possible branches due to the fact there is no cyclic-ness, as each visit to each square has a different hash and therefore a different set of possibilities for where to go from here, and thus might produce a longer path than the current best. ?

(The same is true for part 1 but for the fact that the best is the shortest, so you can prune all branches that are already as long as the best path to the vault but not reached it yet.)

Or is there actually a possible prune available for part 2?

My part 2 examples, and puzzle, currently run in between 30s and a few (<5) minutes, very slightly quicker (but not critically so) if I don't bother storing visited paths to avoid cyclic-ness (cyclicity?) to save a bit of memory. Part 1 runs in under a second.

Seems to be an exercise in resolving permutations, rather than combinations.

[red marley]

(click to show/hide)

The graph should be acyclic as the MD5 hashes of an accumulated set of path instructions should never repeat. So no need to store previously visited hashes. The search will always terminate when location hits [3,3] and is bounded within a manhattan distance of 6 from the exit so the search space is relatively small and can be accomplished exhaustively to find the longest path.  It only took a couple of seconds to solve with my brute force Java implementation.

Note that if the graph were cyclic (as it was on the 11th), the longest path problem is not easily solvable.

[David Martin]

(click to show/hide)

For the first prt I used a branch and bound strategy to prune any paths longer than the first complete one I found.
I iterated back along that path trying all possible non-taken routes.

For the second part it was much the same except not bounding the search, just checking if the current path was the longest when I reached 3,3 and backing off  to the previous branch when there was nowhere else to go.

ran in a few seconds.

 

[red marley]

I thought I'd do a bit of analysis of challenge difficulty, as measured by leaderboard completion time, to see what we have in store for the rest of 2016 (my guess: a toughie tomorrow and a more challenging final week)

[Ben T]

The times (and thus points) are definitely skewed though because it makes no observation of when you started it.
Did someone finish it early because they're better at coding or just because they could be bothered to get up early...
For instance, I have to be at my desk in the week, so usually start it at 9 am, but didn't even look at today's till at least 4pm.

[red marley]

Except that the leaderboard from which those stats were derived is only the first 100 finishers. Looking at the reddit discussions it is clear that all those who feature in the top 100 will have started the second the day's puzzle was released (with the exception of day 1, 2015 which I excluded).

[red marley]

Day 18 (trapped tiles)

(click to show/hide)

I converted the ^s and .s into 1s and 0s to give a binary representation of each row. Each triplet is then a trap if its decimal is 1 (001), 3 (011), 4 (100) and 6 (110).

However, there is a quicker more elegant way to identify traps, with a bit of a nerdy clue in the symbols used in this challenge:

(click to show/hide)

Arranging the trap configurations in a grid:
001
011
100
110

makes it clearer that it is just an XOR between the left and right bits ('^' being the XOR symbol in several programming languages)

And here's an obvious visual spoiler of the room configuration (highlighted as the central column):

(click to show/hide)

The room is part of larger other seasonal Sierpinski building.



and larger version of the image.

 

(Edited to provide a more seasonal image of the tile layout [and a design for some rather natty Christmas underpants])

[David Martin]

(click to show/hide)

I had thought of doing bitwise manipulations but ended up being really inefficient with pattern matching.

bitstring=int('0b'+bits)
newstring=0
for p in range(100):
    newstring>> ((bitstring <<p ) & 5 ) & ((bitstring << p )& 5 ^5)

or something along those lines (I've probably got that horribly wrong)

[Diver300]

I've just caught up with day 17. Reading the question fully would have save some time.

(click to show/hide)

I found the longest possible path that didn't get to the corner, rather than the longest one that did. The differences were just a few steps for all the examples.

[Ben T]

Did you manage to skip any rows, i.e. avoid having to do every single 400,000 transformations, or doesit just improve the speed at which you can generate each row from the next.
I thought if it repeated at, say, 100,000, then you could simply multiply the result at that point by 4. But it doesn't.

The ones I really like are where an optimization is essential rather than just pretty.

[red marley]

Did you manage to skip any rows, i.e. avoid having to do every single 400,000 transformations, or doesit just improve the speed at which you can generate each row from the next.

(click to show/hide)

Given the relationship between a Sierpinski triangle and the Fibonacci sequence I wouldn't be surprised if there was some algebraic way of calculating the sum up to the nth row without iterating. But my mathematical knowledge isn't good enough to work it out.

However you can achieve some decent processing savings in Java at least by keeping the tiles as character arrays and just comparing L and R values for each new row for equality (which is a faster equivalent of the XOR comparison which is in turn a faster equivalent of the 4 rules specified in the challenge). This reduces the calculation time for part two on my machine from about 3 seconds to 0.15 seconds.

[red marley]

Day 19 (present nabbing)

Great problem today. I like it because it can be tackled from several different angles (with varying degrees of efficiency). A little more challenging in part because if you calculate the wrong result it is not immediately obvious why, so debugging can be more difficult (DAMHIKT).

[David Martin]

Actualy part 1 is analytic

(click to show/hide)

There is a pattern which allows an equation to be written to derive the correct answer. Did that part with pen and paper (and only used a computer to do the calculation).

(click to show/hide)

All n**2-1 are valid (binary all 1s) and are the maxima in the rising pattern. From that you can work back.
Take the next n**2-1, from this subtract twice the difference between your number and this next peak. That is your elf

Part 2 looks more challenging. I will try to find a similar equation.