9
votes

# Day 14: Reflector Dish

## Today's problem description: https://adventofcode.com/2023/day/14

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace `python`

with any of the "short names" listed in this page of supported languages):

```
<details>
<summary>Part 1</summary>
```python
Your code here.
```
</details>
```

I think I came up with an interesting way to solve this.

My first attempt at implementing the idea didn't work, so I gave up and solved it the way everybody else did. Today I had a bit of time to revisit this puzzle, and I managed to make my initial idea work.

## Algorithm

If you think about the problem of applying all the iterations as a walk through a graph with cycles, the natural thing to reach for is a cycle-detection algorithm, such as Brent's. My idea is to instead apply a trick from the pathfinding literature: contractions.

For example, given a path from A to E,

`A -> B -> C -> D -> E`

, we can start by moving from`A`

to`B`

, and then from`B`

to`C`

. Now that we know where the path leads, we can add a shortcut from`A`

to`C`

, skipping`B`

.Short-cuts are themselves subject to being short-cut: When we're at

`A`

again due to the cyclic nature of the problem, we move through the short-cut`A--->C`

. If there is already a short-cut`C--->E`

, we can combine the shortcuts to form a new shortcut`A--->E`

.We also store the length of the path that the shortcut shortcuts in order to be able to track how far along the overall 'path' of applying the required number of iterations we are.

If a shortcut overshoots the target, we clear all shortcuts and continue building new, shorter, shortcuts from the current position until we reach our target number of iterations.

The path length covered by shortcuts increases quickly until we overshoot -- at that point we start again with a small step size (no shortcuts) and build up momentum (increasingly longer shortcuts) until we reach the goal or overshoot again.

## Rust

I'm ridiculously pleased with my solution to part 1. Although I accidentally rolled south first instead of north first & barely missed top 1000, I was able to get top 1000 on part 2, which is pretty much my best-case goal.

## Part 1

## Part 2 comments

For this part, my solution was a bit less elegant in terms of code, basically I didn't want to try and figure out modular math abstractly, so I just returned the list of all possible positions & the index where the loop started. Then I did the manipulation separately.

Since it's split across multiple files, see my repo

Read part2.py then test_fix.py then modular_math.py

Part 1 was a breeze, and I even correctly predicted a good chunk of part 2. I then proceeded to muck about making mistake after mistake with the cycle index until I actually got it working. Oh well, I'm still pleased with how most of my solution turned out, especially tilting in a single line!

## Haskell Solution

Two more languages to

go. And of course it has to beGotoday. I learned Go on the job during my first year. My first large open source contribution was written in Go (dnscontrol), and the maintainer even blogged that he have seen many new contributor mention that it was their first Go code.I thought about pattern detection, but I thought the problem probably can be designed to create very long patterns that is not feasibly storeable, or the pattern might lies in the individual rotations in a cycle. After seeing visualizations on Reddit, I decided to give the simplest solution a

GoGolang solution

Not much to say about the solution -- it was a straightforward simulation. I continue to get a lot of use out of my Grid class when I need to deal with directions in the grid.

I had to stop doing the puzzles at midnight as it was messing up my sleep cycle, but I was able to get the solution in about an hour, which is okay for me. I wish the leaderboard had times on it so I could compare my own start time. I seem to remember this from previous years, but I can't find it now. But I'm not losing much because I haven't come close to breaking the top 1000 yet.

Edit to add:

For grins, I ran an estimate of the time to finish the brute force solution to part 2. Without any attempt to optimize, it was around 108 days.

Forgot to post this last night. I wasn't quite able to get top 1000 on part 2, but thought I did pretty well otherwise. Part 2 was pretty simple once I realized I needed to detect cycles.

## Solution

ElixirFor some reason I have a lot of trouble wrapping my head around the math/logic to extrapolate a repeating sequence of values, not starting at index 0, to the nth element. This time, after working it out again, I actually bothered to write a little function to do it. No more tears on these problems in the future. ðŸ¥²

## New

`Sequence`

moduleThe function itself is short, but I wanted to make sure I'd have an easy time remembering how to use it when the next iteration of this "find the bazillionth iteration of some sequence" problem comes up again.

## Part 1 and part 2

I find it very intuitive to model this kind of "cycle of repeated operations" problem as a stream pipeline.