# 2022 Day 9: Rope Bridge

I think the problem statement was intentionally difficult to parse this time. Those conditionals are a lot simpler than it makes them sound.

I kept the visited positions in a `Hashed_Set` and coming up with a good `Hash` function for a pair of Integers was new for me. I ended up making a lot of assumptions (`Integer'Size = 32 and Hash_Type'Size = 64`) and just shifted one of the integers left 32 bits. A cursory Google search turned up the Cantor Pairing function, but I wasn’t able to make this work with negative integers in a short amount of time. Clearly I need to do more reading.

Part 2 caught me off guard, I hadn’t anticipated I’d need to deal with more elements.

Note: I’m going to stop using the spoiler blur on the daily posts. If you’ve gotten this far, I assume you know that these posts contain spoilers.

1 Like

This is another case where a program that solved the examples solved the puzzle.

My solution is similar to @JeremyGrosser’s, except that…

1. I’m also not that familiar with coming up with a hash function; I seem to remember that multiplying by relatively large primes is a good idea, and of course I didn’t do that my first time through, so after reading his comment here I went back and changed how I was doing things.

2. I had a different approach to the case where one might have to move diagonally. I’ll have to go back and check whether I can simplify what I did, but I like @JeremyGrosser 's `Adjacent` function .

3. While I didn’t this, you could avoid hashing negative numbers by starting at a position far above and to the right of the origin. A scan of the input file should give more than enough buffer for this.

1 Like

I couldn’t be bothered to write a hash so I wrote a lexicographic ordering function and used `Ordered_Set` instead. I spent some time trying to figure out how to move the tail, but I think I ended up with a very elegant solution using some vector math and integer division.

2 Likes

In my opinion, using a `Functional_Map` is easier and more readable.

Used an ordered set, too, but using 2-element arrays as data type instead of records, skipping the need to define the ordering myself. Once again, it was nice to see that solving part 2 required no change of the core logic.

1 Like

It seems my assumption about the size of Hash_Type was wrong, it’s only 32 bits wide. However, this means I can `Unchecked_Conversion (Integer, Hash_Type)`. Shifting 16 bits from there and using `xor` gets us a pretty good hash function for small values of Integer, which is the common case for this problem.

``````   type Position is record
Y, X : Integer;
end record;

function Hash (Element : Position)
is
(Integer, Hash_Type);
begin
return (To_Hash_Type (Element.X) * 2 ** 16) xor To_Hash_Type (Element.Y);
end Hash;
``````

On my Part 1 solution, this hash function drastically improves L1 cache efficiency and results in a 12.3x speedup!

I added a graphical output, both console and again PPM.

Path for second test data for part two:

``````#.....................
#.............###.....
#............#...#....
.#..........#.....#...
..#..........#.....#..
...#........#.......#.
....#......#.........#
.....#..............#.
......#............#..
.......#..........#...
........#........#....
.........########.....
``````

and as PPM (scaled and converted to png using Gimp):

Sadly, the real data is too wide for outputting on console, so here only the PPM (converted to png using Gimp):

2 Likes

In this plot of part 2, circle diameter is proportional to the number of times the tail visited a point (circle’s center):

3 Likes

What is `Functional_Map` BTW?

Good question!

It’s the first time I use `Functional_Maps` container. I used `Hashed_Maps` in the past, and today I discovered this functional version. I noticed three main differences. In `Hashed_Maps`: you must specify the hash function, the API is based on procedures with `in out` parameters and `SPARK_Mode` is off. In `Functional_Maps`: you’re not required to provide the hash function, the API is based on functions that return a new map whenever you modify it (add, remove, set) and `SPARK_Mode` is on.

I don’t know what are the internal differences between them regarding memory requirements and performance. A comparison of both APIs would be also interesting. For today’s puzzle, both containers are good enough, but I think that the functional flavor makes the code more readable.

With respect to SPARK, it exists also the `Formal_Hashed_Maps` container with `SPARK_Mode` which (I suppose) it has been formally verified. I’m not sure if it’s the same for `Functional_Maps`, because is based on `Functional_Base` that has no SPARK support.

Someone with more knowledge on this?

3 Likes

A banana skin I slipped over for part 2 is that there are multiple solutions to the problem.
In the first variant I have applied the rule, for each head-tail pair (be it on part 1’s length 1 rope, or part 2’s length 9 rope): when the new head position is not touching the tail, the tail moves to the former head position.
After my answer was not accepted, I have considered having a glimpse to the the AoC forum.

Below you see the path of part 1’s tail for my input, then the “wrong” solution for part 2 in the middle and the “right” one on the right.

1 Like

Interesting! Mine are very different. The left one is for part 1, the right one for part 2.

1 Like

Almost like the game of
Snake!
L1 is kinda hard to instrument, but the `perf stat` command will give you some info on cache activity. If there’s little or no L2 activity, then you can infer that the data is mostly in L1.