Advent of Code

[red marley]

Day 22 (grid computing)

Nice meaty challenge today. First part straightforward but I have to go to work now before getting a solution for second part. Will think about it on way in.

[David Martin]

Likewise. Part 1 was straightforward, almost a one-liner in python.

(click to show/hide)

Code: [Select]

import itertools
len([ x for x in itertools.permutations([y.strip().replace('T','').split() for y in open('day22input.txt').readlines()][2:],2) if int(x[0][2]) >0 and int(x[0][2])<=int(x[1][3])])



[David Martin]

Part 2: Not much coding needed here - easy to do by inspection and simple arithmetic.

(click to show/hide)

Once the data has been parsed it is easy to check that the small disks have the property that none of them hold more data than the smallest can handle, and the large disks just act as walls.
Then you are not so much moving data as moving empty space around. Easy to visualise:

Code: [Select]

.............................
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#0..............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............
.............#...............I have swapped X and Y as the data is listed in column order. I have to get the 0 to the bottom left and then to the top left, bringing the key data with it.
Each step in a data agnostic way is one move. To move the data it is 5 moves per step. Arithmetic then gives the answer.

[Oaky]

(click to show/hide)

I spent too long staring at my logic for part 1 trying to work out why I had the wrong answer before it dawned on me I had forgotten to convert the values from the input to int and so was doing my < comparison on strings instead 

Once that was fixed, I wrote a dumper to print the grid in the format as per the part 2 example, then just solved it by inspection .

I will probably try setting my BFS searcher on it at some point.

[red marley]

^--- Probably a bit of an unhidden spoiler there David.

(click to show/hide)

I mostly liked today's puzzle even though it was a bit of a D'oh! moment in the end. I liked it because it had a deliberate distractor in Part 1 that belied the simplicity of the solution to part 2. The ability to step back and realise a problem is less complex than it first appears is something I admire (and need to improve).

For me I spent too long thinking about a suitable hashing to keep track of previous states of the array and a cost function that could adapt to changing array elements. I was getting a short, but not shortest path to move the empty disk to the top-right so I was getting a credible but wrong answer. In debugging my search I displayed the map of the disks and it was only then that it occurred to me that it might be a simple shortest path with a simple barrier. Given that such a path would not involve self-crossing, it was just a matter of confirming that all disks could potentially swap with their 4 neighbours (accounting for the barrier and edge cells). Shown visually, here are the number of swappable neighbours with my input.


 2  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  G*
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  2
 3  4  4  4  4  4  4  4  4  4  4  4  3 ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
 3  4  4  4  4  4  4  4  4  4  4  4  4  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  2
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  _  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  3
 2  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  2

And then it was just a case of adding the number of steps to move G* from top right to top left (5 moves per shift left).

[David Martin]

I am attempting to fill in the blanks from last years. The lack of a daily deadline doesn't seem to help.

I do think that many of them are harder than this year. The one I am currently toying with is the elves delivering presents. It is obviously some heinous factorial problem, but instead of a straight sum of factors, it is a sum of the product of every permutation.
Wondering about some sort of branch and bound strategy, and being able to set a suitable bound on the number of primes to consider.

[red marley]

I do think that many of them are harder than this year.

We've still got three days to go yet. 

But I agree with you. The average completion time of the top 100 finishers last year was 26 min 50s; this year so far it has been 23 min 25s. One difference (which I like) is that the hardest questions this year (Day 11 lifts; Day 19 elf present stealing; Day 22 grid computing) have all had a trick/heuristic that makes the problem considerably easier to solve.

If you want a gentle clue for the present permutation problem from last year:

(click to show/hide)

subset sum problem

[red marley]

Day 23  (more assembunny)

(click to show/hide)

Be careful what you wish for (although I did greatly enjoy today's challenge).

Day 12

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]

(click to show/hide)

It took me a bit of sitting down with pen and paper to work out what the program was doing.

(click to show/hide)

Calculating factorial eggs and then adding another number to it

Solved without code (OK, I did implement it but it would still be running)

[red marley]

(click to show/hide)

For me, the satisfaction is in providing a coded (and therefore more generalisable) solution rather than finding the answer itself. The answer is merely a way of testing the coding.

I also get some satisfaction in moving from an initial naive solution to one that it greatly optimised (by orders of magnitude rather than tinkering with a few percent increase in speed). Today's was a good example:

Initial assembunny code from Day 12 applied to Day 23 took 21 minutes to compute the part 2 answer.
Introducing an 'add' command: took 11 minutes to compute the part 2 answer.
Introducing a 'multiply' command: took 0.06 seconds to compute the part 2 answer.

[David Martin]

Did you put that into the program to generalise from any set of instructions? I had thought about trying that but didn't have time. The challenge means different things to different folks.

[Ben T]

I haven't found a programmatic solution to day 22 or day 23 that will work with anybody's input.

Day 22 is a perfect example of something a human is good at solving based on what they see visually but a computer isn't.

(click to show/hide)

When the 'gap' has to move round the wall, the best path starts off with it actually getting further from the goal data.

With my 'optimized' brute force solution, my outputted visualizations showed it heading towards the wall, getting to it very quickly, but on reaching it, getting 'stuck' in the corner between the 'wall' of big disks and the edge of the matrix. It then just meandered around, as my algorithm had no way of deciding that bouncing off the 'wall' was then actually in a much worse position than having initially headed away from the goal but towards the gap in the wall.
It's not that the algorithm doesn't know where the wall is, it doesn't even know there even IS a wall. Maybe if I could make the assumption that there's a wall, and therefore the best path might actually start going away from the goal, I could maybe use some fuzzy logic to detect the 'bouncing off the wall' phenomenon, it might find the best path. Maybe something along the lines of 'is it impossible to carry on going in any direction without rotating at least 90 degrees'.

 Day 23,

(click to show/hide)

I found it hard to spot the repeating patterns visually let alone programmatically.

[red marley]

I haven't found a programmatic solution to day 22 or day 23 that will work with anybody's input.

Day 22 is a perfect example of something a human is good at solving based on what they see visually but a computer isn't.

(click to show/hide)

When the 'gap' has to move round the wall, the best path starts off with it actually getting further from the goal data.

With my 'optimized' brute force solution, my outputted visualizations showed it heading towards the wall, getting to it very quickly, but on reaching it, getting 'stuck' in the corner between the 'wall' of big disks and the edge of the matrix. It then just meandered around, as my algorithm had no way of deciding that bouncing off the 'wall' was then actually in a much worse position than having initially headed away from the goal but towards the gap in the wall.
It's not that the algorithm doesn't know where the wall is, it doesn't even know there even IS a wall. Maybe if I could make the assumption that there's a wall, and therefore the best path might actually start going away from the goal, I could maybe use some fuzzy logic to detect the 'bouncing off the wall' phenomenon, it might find the best path. Maybe something along the lines of 'is it impossible to carry on going in any direction without rotating at least 90 degrees'.

(click to show/hide)

The shortest path involves no self-crossing lines, so simply keep track of visited locations and make sure your pathfinder can only move to unvisited ones. That should soon rule out dead ends and force the search temporarily to move away from the direct line to the corner.

[David Martin]

I haven't found a programmatic solution to day 22 or day 23 that will work with anybody's input.

Day 22 is a perfect example of something a human is good at solving based on what they see visually but a computer isn't.

(click to show/hide)

When the 'gap' has to move round the wall, the best path starts off with it actually getting further from the goal data.

With my 'optimized' brute force solution, my outputted visualizations showed it heading towards the wall, getting to it very quickly, but on reaching it, getting 'stuck' in the corner between the 'wall' of big disks and the edge of the matrix. It then just meandered around, as my algorithm had no way of deciding that bouncing off the 'wall' was then actually in a much worse position than having initially headed away from the goal but towards the gap in the wall.
It's not that the algorithm doesn't know where the wall is, it doesn't even know there even IS a wall. Maybe if I could make the assumption that there's a wall, and therefore the best path might actually start going away from the goal, I could maybe use some fuzzy logic to detect the 'bouncing off the wall' phenomenon, it might find the best path. Maybe something along the lines of 'is it impossible to carry on going in any direction without rotating at least 90 degrees'.

(click to show/hide)

The shortest path involves no self-crossing lines, so simply keep track of visited locations and make sure your pathfinder can only move to unvisited ones. That should soon rule out dead ends and force the search temporarily to move away from the direct line to the corner.

(click to show/hide)

That depends on what you mean by self crossing lines. If you are talking about the route of the gap then that is explicitly not true as my optimal route crossed itself every step of the desired data towards the goal. For an individual data block it may be true but I haven't checked that.

[Oaky]

(click to show/hide)

I left my unoptimised VM running the code for part 2 while I stared at the assembunny code trying to work out what it did.

By the time I had a prototype translation of it into python running, the original had completed anyway

[David Martin]

Day 24: A bigger challenge

(click to show/hide)

Looks interesting. I will attempt this later but plan to follow this strategy:

(click to show/hide)

1. Build a graph network of all points . and numbers in the chart.
2. Find minimum spanning distance between each pair of numbers.
3. Use minimum spanning distance to solve the travelling salesman problem.

Seems reasonable but it hasn't seen contact with the enemy yet.

[Oaky]

(click to show/hide)

Time to dust off the breadth-first search, with a twist...

(click to show/hide)

Need to do pairwise distances and reduce it to a travelling salesman problem otherwise the search space goes crazy

[red marley]

Oh dear - some stupid mistakes cost me plenty of time which meant with other Christmas stuff going on, I had to leave it a while before resuming.

(click to show/hide)

My initial attempt was to try to find the shortest path through all 7 locations in one go. I recognised it as a possible Travelling Salesperson Problem but thought with only 7 nodes, it could be computed through brute force.

For some stupid reason I thought it sensible to keep track of visited locations with a single 8 bit number holding  the visited status of the search for each of the 7 locations. While this is possible, there's no real saving over resetting the visited flag after each node is found. What it did do was mask a stupid problem in my breadth first search that I failed to spot.

To speed up my search I added a cost function to to the BFS so it prioritised moving towards the goal node. I think in practice this doesn't make much difference as the maze is pretty constrained and the shortest paths can be quite convoluted. What it did do was further mask the problem with my BFS search.

I eventually realised it was more efficient to just compute the shortest path between all pairs of nodes then find the minimum sum of each permutation of the 7 node pairs. This certainly sped up computation time (a fraction of a second rather than a few minutes), but I nevertheless still arrived at a credible but incorrect total for number of steps.

It worked on the test case but was consistently coming up with a path that was a little too long. It was only when I built a slightly more complex test case that I realised long paths were blocking of subsequent shorter candidates and I corrected the bug in my BFS. It then generated the answer in less than a second. Part 2 was a trivial case of adding the start node to the end of the list of 7 permuted nodes.

Lessons learned:

KISS
If your tests are too simple, build some more with edge cases and greater variety
More haste, less speed.

[Ben T]

I haven't found a programmatic solution to day 22 or day 23 that will work with anybody's input.

Day 22 is a perfect example of something a human is good at solving based on what they see visually but a computer isn't.

(click to show/hide)

When the 'gap' has to move round the wall, the best path starts off with it actually getting further from the goal data.

With my 'optimized' brute force solution, my outputted visualizations showed it heading towards the wall, getting to it very quickly, but on reaching it, getting 'stuck' in the corner between the 'wall' of big disks and the edge of the matrix. It then just meandered around, as my algorithm had no way of deciding that bouncing off the 'wall' was then actually in a much worse position than having initially headed away from the goal but towards the gap in the wall.
It's not that the algorithm doesn't know where the wall is, it doesn't even know there even IS a wall. Maybe if I could make the assumption that there's a wall, and therefore the best path might actually start going away from the goal, I could maybe use some fuzzy logic to detect the 'bouncing off the wall' phenomenon, it might find the best path. Maybe something along the lines of 'is it impossible to carry on going in any direction without rotating at least 90 degrees'.

(click to show/hide)

The shortest path involves no self-crossing lines, so simply keep track of visited locations and make sure your pathfinder can only move to unvisited ones. That should soon rule out dead ends and force the search temporarily to move away from the direct line to the corner.

(click to show/hide)

Yeah but my algorithm did this:



The empty space started off in the square marked green, and tried to take the most direct path to the goal (purple).
When it got 'stuck', it spent time buggering about in the corner of doom exploring all the locations that were, yes, still as yet unvisited, but still closer to the goal than the 'apex' (the left end of the wall). This buggering about seemed to waste sufficient time as for me to think the algorithm would not complete in reasonable time (minutes), unless I was being impatient and it would have suddenly 'snapped' towards the apex when the purple path had coloured in the whole corner.

(The light blue path is the optimum path that my algorithm is yet to find but that was obvious on manual visual inspection)

[Ben T]

(That woe is day 24 not day 23... ) but:

(click to show/hide)

I eventually realised it was more efficient to just compute the shortest path between all pairs of nodes then find the minimum sum of each permutation of the 7 node pairs. This certainly sped up computation time (a fraction of a second rather than a few minutes), but I nevertheless still arrived at a credible but incorrect total for number of steps.

That is the best method. (Obviously including caching the distances between each pair.)

Asusming you only have 8 exposed wires to visit (0-7), like i did, there are only 28 different pairs to calculate the distance between so if it takes on average 5s (like mine does about) to calculate the distance between each pair then it still only takes about 2 minutes to pre-compute all the leg lengths.
There are only 5,040 possible distinct tours starting with 0 and once you have pre-cached all the leg lengths then calculating the whole tour length takes hardly any time at all.
In other words, the complexity of a TSP is O(n!), but O is only adding up 7 numbers, not doing routing.

The only slight gotcha for me but that I did realise from the start was that (using the A* algorithm) the shortest distance between each pair was not necessarily the first one found, so I had to sort first by number of steps then by distance to target.

Part 2 didn't add much - I thought he was going to make the problem asymmetrical (i.e., x->y != y->x

[red marley]

^--- (Ben's Day 22) Sure, but with a grid of only c. 30x30 or so cells, shouldn't it soon exhaust that bottom right corner and find a better route past the wall?

(click to show/hide)

Just keeping a single 'visited' grid with the current shortest number of steps required to get to each visited cell is enough to quickly exclude any longer paths.

[Ben T]

^--- (Ben's Day 22) Sure, but with a grid of only c. 30x30 or so cells, shouldn't it soon exhaust that bottom right corner and find a better route past the wall?

(click to show/hide)

Just keeping a single 'visited' grid with the current shortest number of steps required to get to each visited cell is enough to quickly exclude any longer paths.

maybe, yeah - I'll revisit and try and find out why it doesn't. I think the reason may be that the hash is 'too unique', i.e. it cares (too much) about the position of actual data rather than just the position of the space.

[David Martin]

Hmm.. Just got back to this and I think my code is really inefficient compared to the times reported. Still running DFS (maybe BFS would be better?)

[Ben T]

Hmm.. Just got back to this and I think my code is really inefficient compared to the times reported. Still running DFS (maybe BFS would be better?)

(click to show/hide)

Yes I think only BFS will work, because with DFS, once you find any solution, you still need to check all nodes up to that depth because there might be a better (shallower) one, so BFS means that the shallowest (shortest) target is found first.
DFS is the quickest way to find a solution to the length of any given leg (if it doesn't have to be the shortest), but it is not the quickest way to find the shortest.

[David Martin]

(click to show/hide)

I am now intimately aquainted with the joy of BFS vs DFS. And the complete code runs in less than a second.

Mistakes are good, if you learn from them.