Advent of Code

[red marley]

Day 11 (elevator isotope exercises)

That was an exercise in humility for me. By far the toughest puzzle yet of 2016, but satisfying nonetheless.

Part 1:

(click to show/hide)

I spent far to long creating the scaffolding to represent the problem. And stupidly while I had originally encoded the rule that prevented lift movement if no items carried, I somehow managed to delete this. The result was that it reduces the number of moves required (from 11 to 9 in the test case, but many more in the real cases) and therefore generates an incorrect answer. I eventually spotted the error so was able to calculate a correct result.

The depth of the search tree was too much for my implementation so I introduced an arbitrary maximum depth (99 in the first instance). This allowed me to exhaustively search the solution space up to that depth and to find an optimal answer by trimming branches of the tree that deeper than the shortest path solution so far found. This took approach found a solution in about 40 seconds of calculation time.

Not very elegant or efficient, but enough to get the correct answer. It was at this point that I noticed that the lower places on the global leader board were taking 2hrs 45 minutes to find an answer to part 2 (on previous days it was more typically 15-20 minutes)...

Part 2:

(click to show/hide)

I tried running the same brute force algorithm for the 4 extra items, but it soon became clear this would take too long and at that point I had no idea what the depth of optimal answer in the search tree might be.

My first attempt at optimisation was embarrassingly crude: I set the maximum search depth to the depth of part 1 +2, and if no answer found, doubled it and re-searched. This gave me an upper and lower bounds to the correct answer (49 and 98 in my case) after a couple of hours calculation, but honing in on the answer was taking too long.

The second and successful optimisation was to recognise that you should prioritise moving pairs of items up and only single items down. This had a dramatic effect, finding the optimal answer in less than 5 minutes calculation time.

However, looking now at the approaches taken by some on the subreddit, there were plenty of much more elegant approaches that could find the solution in a second or two.

[David Martin]

(click to show/hide)

I think brute forcing even with optimisations is non-optimal. I'm fairly sure that there is a simple calculation that can be done - there are some invalid states so you have to work, where possible from the top upwards.

[red marley]

A tiny modification that knocks the Day 11 part 2 solution down to less than 2 seconds computation time:

(click to show/hide)

When traversing the solution space you obviously need to keep track of previously visited nodes on the graph (to avoid infinite cycling). I had been doing this by generating a hash representing the state of the system (each item and its floor plus the elevator position).

However, the name of the element is unimportant in the 'signature' of the shortest path through the solution graph, only whether it is a generator or microchip (the names are still important for the valid move detection though). So basing the hash only on the generator/microchip status and elevator position prunes all duplicate isomorphic branches of the tree (which is almost all of it).

I have just tested this with a fictitious example with a further 4 items (16 in total) and it finds the shortest path (99 moves) in under 20 seconds. Starting with 20 items in total finds the shortest path (119 moves) in about 3 minutes.

[David Martin]

(click to show/hide)

There are some thoughts that a lower bound for the solution is readily calculated by taking the number of items and taking two items at a time up a floor, coupled with one item down, minus one for each floor. Not valid for all states but close enough to give many folk a very quick response.

I could recode to prune all pairs as a set of homogenous labels and extract as necessary. I'm not sure I can be bothered now. Learned a lot though.

[Ben T]

(click to show/hide)

I used bruteforce but gave each state a score, and always process the 'best' first, and this ran in under 10 seconds for part 1, without jo's optimization above. (Part 1 also worked with it, but didn't require it.)
The score was simply how top-heavy it was, i.e. (4 x count on floor 4) + (3 x count on floor 3) + (2x count on floor 2) + (count on floor 1) etc.

I started off processing all of each depth before moving onto the next depth, and left this going while I went to squash (several hours) and it still hadn't found an answer by the time I got back. Once I switched it to allow it to process e.g. some of depth n+2 before it had processed all of depth n if they had a better score, it found a result in seconds.
I also pruned any branches that had some items on the 1st floor and some on 4th but none on 2nd or 3rd,  as I thought this was no better strategically than with those items on 2nd and 4th, and while this was triggered a few times it didn't seem to make much difference to computation time.

jo's optimization was required (to run in under a minute anyhow) for part 2 however, whether I would have been too thick to figure that out myself I don't know, and whether it would have found a result eventually without it I'm not sure. The only difference between part 1 and 2 seems to be that that optimization is required, so maybe realizing that was what he was getting at with part 2.


https://github.com/bjtaylor1/AoC_2016/blob/master/Day11/UnitTest1.cs (method Solve())

[red marley]

Comment on BenT's Day 11 solution:

(click to show/hide)

Nice. Effectively an A* type search strategy.  I had initially hoped to do something similar but didn't know how to weight the cost function (your top-heavy metric). I think I was too distracted by the fact that the lift goes down almost as much as it goes up.

My feeling is that with a tuning of that cost function, you may be able to speed up the search considerably.

As for Day 12 - some welcome relief (especially for anyone who did Day 23 last year or the excellent Synacor Challenge) after spending too much of Sunday in front of the computer. I suspect today isn't the last we'll see of assembly language interpreting.

[David Martin]

Day 12 again can be optimised

(click to show/hide)

cpy 5 d
cpy 3 c
inc a
dec c
jnz c -2
jnz d -4


is simply to add c to a d times and set c and d to 0. There are similar multiple loops in the code and teasing out the actual logic would save some time. I bruteforced it.

[red marley]

Day 12 (response to David Martin)

(click to show/hide)

I too just iterated through without any optimisation. What I liked about Day 11 was that part two forced us to consider optimisation, so I was a little disappointed that for Day 12, while possible, wasn't at all necessary.

I like the idea of having to construct higher level operations from the assembly language in order to solve the challenge. Addition as in your example, but also multiplication and exponention would probably be needed for an input that couldn't be processed in a practical time without optimisation.

[David Martin]

Day 12 (response to David Martin)

(click to show/hide)

I too just iterated through without any optimisation. What I liked about Day 11 was that part two forced us to consider optimisation, so I was a little disappointed that for Day 12, while possible, wasn't at all necessary.

I like the idea of having to construct higher level operations from the assembly language in order to solve the challenge. Addition as in your example, but also multiplication and exponention would probably be needed for an input that couldn't be processed in a practical time without optimisation.

But then you would be in 'how to write a compiler 101' territory rather than a short wee puzzle to solve.

[Ben T]

I wonder how difficult it would be to convert the instructions to actual assembly language? If there are equivalents that they would map to on a 1-1 basis.

[David Martin]

And then set each register as a set of binary digits on a front panel display for an arduino for example?

[Ben T]

You can start a C++ program on a normal computer in seconds, and it can include an "asm { ... } " block IIRC. I'm sure one of the instructions is 'mov', which would be similar to their 'jnz', etc. So I was thinking merely output them to the console to then input into the adventofcode site...but if you know a better way knock yourself out

[Oaky]

I fell behind on account of running out of time on the train to work on Friday, and having a surfeit of Real Life stuffs at the weekend.  I've since mostly caught up, but I'm leaving Day 11 until tonight when I can have a proper think about it.  That one looks considerably more difficult than the others so far.

[Diver300]

I converted day 12 into assembly language for a pic24, a 16 bit microcontroller. I ran the code on a simulator on a PC, and found that 32 bit resolution is needed, well more than 16 bits anyhow.

Line numbering went to pot, so I numbered the lines, and therefore the jumps, according to the original input.

Part 2 was then trivial, and took about 10 seconds to run. It would have been <1 second on a real microcontroller.

[David Martin]

Haven't attempted day 13 yet but I know the algorithm

(click to show/hide)

Dynamic programming algorithm, not quite the same as we use in sequence alignment as you have to backtrack occasionally.
Start at 1,1 and calculate the shortest path back to the beginning. This will be a choice of three paths in the classic version. Might have to do the same from the end and find the meeting point.

[red marley]

Or to put it another way (day 13)...

(click to show/hide)

The same as Day 11 but with simpler constraints and a maximum of only 4 out edges per node.

[Tim Hall]

The Boy was still stuck on 11 last night, but very pleased with his solution for 12.  He tried describing to me what he'd done, finishing off with "you don't understand this do you?"  I did manage to grasp he was pleased with the elegance of his solution though.

[David Martin]

A colleague of mine pointed me at a way to simplify day 13.

(click to show/hide)

preprocess a large enough grid to remove all dead ends.
What is left will be the path.

[Oaky]

(click to show/hide)

Day 13 was fairly trivial, given what I'd already learned about Breadth-first searching and had already implemented towards day 11 (which I haven't yet solved!).

The reason day 11 still remains unsolved for me are the intertwined questions of how to represent the state, and how to generate the valid next states.  I keep tying myself up in knots trying to decide on a good way to do these.  I'm currently working on the premise that I'm just going to choose a representation, and will code up the valid move (i.e. neighbouring node) generation routines based on that representation regardless of how ugly/inelegant/inefficient they end up being.

[red marley]

In response to David's colleague's heuristic...

(click to show/hide)

But might that not result in more computation? With solutions that find possible routes, you can keep track of the current shortest path so limit all subsequent searches to that shortest path - 1. With the suggested pre-processing heuristic, you can end up searching for dead ends in a greater number steps than the shortest path. To take an extreme case, the following, where S is the start location and D is the destination, would be slower with the heuristic than without it.

####################
#DS................#
####################

[tom_e]

Managed day 12 with only pencil and paper. 

[Oaky]

Managed day 12 with only pencil and paper. 

I feel guilty if I manually encode the input data into my script rather than reading it from a file and parsing it. 

[David Martin]

Code: [Select]

Finally got round to day 13. Easy enough for the first part, second part is giving me a little grief for a reason I cannot fathom.
I've plotted it and worked through by hand but the answer I get appears to be too low for the site. Having checked it exhaustively by hand, I am convinced there is a bug.
[spoiler]
Input is 1350, value I get is 115. This is too low
[/spoiler]

ETA. Read the instructions. The maze bounds are 0,0 not 1,1.
Doh!
[spoiler]
ETA - new answer 122, still wrong.

[code rows=40]#X##X##            ###     ##### ##### 
#X#XXX# ##  ######## # #####   #  ## ##
XX##XX## ## #  #   ### #     #     ## ##
#XX#X# ## #    ##   #  # #### ####   # 
#XX#X## ####### # # #### ## ###   ## # 
##X#XXX#  #    ## #   #    #    #  # # #
##XXX#X#  # ##    #   ## #  #### #   # 
# ##XXX# ## #### ####  ## # #  ## ##  ##
#####XX#     ###  # #   #   #   ###### 
  ####X###      #  #### ## ### #  ## ###
#  ###X##### ##### ## ## #  ##  #   #   
##  #XXXX#X###  ##   # #  # # #  ##   ##
    #XX#XXXXX#     #  ##### #  # # #####
## #### ####X#  ##### ##  # ###  ###  ##
## #XX###XXXX## #  ##  #  ### ###   #  #
#  ##XXXXX##X##      # # #  #     #  # 
### #X######X##### #  ## #  # ###  #   #
XXX##X##  #XXXXXX## #    # ##   ### ####
X#XXXXXX# #XX##X# #  ##  #   ###  # #  #
XX##XX#X# #####X# ############ ####     
## ##XXX###  #XX##    #  #    #  ##### #
 #  ##X#     #X# ####    # ##        ##
######X# ##  #XX#XX####### ##### ## # ##
##XXX#X##### ##XXXXXX#  #   #  #### ## #
 #X#XXXXXX## # ##XX#XX# ##  # #        #
 ## #####X#  ## ### #X#  # ## # ##  ## #
  # #  ##X### ##  ##XX# ##    ## ##### #
  #     ##   # ##  # ##   ## # ##   #   
######    ## ## # ## # ### # ## #   #  #
     #  #  #   ## #  ### # #   ### ####
 ##  ### #   #    #     ##  ##  ## #  #
#####  ## ##  ## ###### # #   # #  #  #
Sorted: There was a hidden sidestep that added two to the path length.
[/spoiler]

[red marley]

Day 14 Hash-mash

People who liked Day 5 will love Day 14.

Hint:

(click to show/hide)

hash-cache (for part two at least)

I like to start each day by making at least one stupid mistake before breakfast. Today's was

(click to show/hide)

to search for instances of triplets and fives that occur anywhere in each hash rather than as three and five consecutive characters (e.g. 12131 would match as a triplet). It soon became obvious that this was giving a very wrong answer, but I did waste too much time writing an efficient frequency counter for my incorrect interpretation of the question.

[Diver300]

(click to show/hide)

I assumed that hashing would take a long time as I coded for part 1, making part 2 easier.

I didn't store the hashes, only a list of indexes and the repeated characters.

(click to show/hide)

I looked for instances of 5 repeats, then looked back in my index for the instances of 3 repeats.

The flaw in that plan is that the index of the 3 repeat can be lower for a higher index 5 repeat.

On mine, the 59th instance of 5 repeats had its character repeat 3 times in hash number 22065,
while the 65th instance of 5 repeats had its character repeat 3 times in hash number 22045