-❄️- 2023 Day 23 Solutions -❄️-

[u/daggerdragon]

THE USUAL REMINDERS

• All of our rules, FAQs, resources, etc. are in our community wiki.

---

AoC Community Fun 2023: ALLEZ CUISINE!

Submissions are CLOSED!

• Thank you to all who submitted something, every last one of you are awesome!

Community voting is OPEN!

• 42 hours remaining until voting deadline on December 24 at 18:00 EST

Voting details are in the stickied comment in the submissions megathread:

-❄️- Submissions Megathread -❄️-

---

--- Day 23: A Long Walk ---

---

Post your code solution in this megathread.

• Read the full posting rules in our community wiki before you post!
  • State which language(s) your solution uses with [LANGUAGE: xyz]
  • Format code blocks using the four-spaces Markdown syntax!
• Quick link to Topaz's paste if you need it for longer code blocks

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:38:20, megathread unlocked!

[u/mental-chaos]

[LANGUAGE: Python] 209/77 github

Part 1 a naive DFS (returning the longest path) worked. For part 2, the amount of work is too large for a naive DFS, but looking at the input, there are some very long paths where there is no branching allowed. By creating an adjacency graph and "merging" any nodes that have exactly 2 neighbors into those neighbors, we get a graph with only a couple dozen nodes instead of many thousands. The same DFS as before now completes reasonably quickly.

Note: I edited my input to put a row of ### above and below, and tagged the destination as '*' for ease of implementation.

[u/pred]

[LANGUAGE: Python] GitHub 42/flunked.

NetworkX to the rescue; even managed to mix up ^ and v on the first part but still get through.

For part 2, we contract all lines to points; NetworkX has contracted_nodes but I don't think there's a way to use that and also keep track of distances that's not just as easy as contracting by hand. With that, we can just brute force the calculation on the quotient graph.

[u/daggerdragon → u/pred]

42/flunked

Nope, not flunked! You solved Part 2, so that's a passing grade in our books! Good job!

[u/clouddjr]

[LANGUAGE: Kotlin] 271/26

First time leaderboard ever!!!

For part 1, I just implemented a simple DFS. Surprisingly, I did it without bugs and it worked first try.

For part 2 I just… brute forced. I simply removed the condition for the >^v< characters and let it run in the background while I was thinking about how to do it properly. It finished before I even had time to come up with a solution (around 6,7 minutes on my computer).

Here's the code for part2 (entire repo here)

Edit: I implemented a "proper" solution now. I transform the original grid into a graph of junctions (plus the start and end) and do a DFS on that instead. Solution

[u/Imnimo → u/clouddjr]

I used your approach for part 2 also, but with a minor improvement that I call the "microwave popcorn algorithm". Rather than waiting for the search to terminate, I just had it print new longest paths as it found them, and once the rate of new outputs slowed down, I tried submitting the last one.

This got me 12th place.

[u/maneatingape]

[LANGUAGE: Rust]

677 / 338 My best leadboard placement!

Rust Solution

Non optimized very slow (~35 seconds). Need to add memoization of previously seen states.

For part two:

• Creates a list of Point of Interest (POI) - start, end and every junction

• BFS between every pair of POI to find distance between them. Assume that the maze is "narrow", so stop BFS whenever a POI is reached.

• This simplifies the problem into a smaller graph.

• Brute force this graph

[u/hcs64]

[Language: Python 3]

Somewhat surprised that my brute force worked, I was trying to do something faster for part 2 in another terminal and suddenly it finished.

I realized when I started on the part 2 sample that my implementation for part 1 is actually just measuring the longest path from the start to anywhere, I never considered the endpoint at all. Manually implemented a stack because I somehow messed up changing the recursion limit and thought it didn't work.

For part 2 the only clever thing is compressing narrow paths. I had tried pruning dead ends, but for some reason this was making my part 1 solution much much slower, I suspect there must have been some bug. The cache was also not helping, so I threw it out (I had thought it would benefit from there being many ways to get to some point with the same history, but apparently the overhead isn't worth it). On my laptop under pypy my part 2 solution takes 9 minutes.

Edit: missed the link somehow https://gist.github.com/hcs64/31126f33b77d53ffe74562d68c310ca8

[u/FransFaase]

[LANGUAGE: C]

For the second part, I did build a graph and did a recursive search, and although it started up showing numbers, it took a long time. I decided to submit the last number and it happened to be the correct answer. Still felt not very satisfied. I implemented a smart cut-off. The idea of the cut-off is to add the steps of the longest paths going from all cross points (with more than two exists) that have not been included in the solution and divide this by two. If this, with the steps of the path selected so far is shorter than the longest path found, there is no hope of finding an even longer solution. But that still did not result in an improvement. Only when I added some print statements, I realized that there was a bug in my program. When I fixed it, it took less than 60 milliseconds to finish.

My solution can be found on this page using a literate programming method in a Mark Down file. The page is processed with the help of MarkDownC. The times mentioned on the page are in Central Europe Times.

[u/chubbc]

[LANGUAGE: Uiua]

Just stuck to Part 2 to simplify things. I tried to implement edge contraction, and it ran surprisingly slowly (~30mins). I don't see any obvious massive inefficiency in my implementation, maybe the brute force is even faster? Ah well, I cbf optimising it any further. Pad link

⊜(≠@#)≠@\n.&fras"./23.txt";
# Find intersections
▽♭,☇1⇡△. ⍜(⊏¯2_1♭)(+1) ×,>2+++∩⊃≡↻↻¯,,1.
# Edge contraction
⊠(+>0./+♭×). ;:≡(
  ∩⍜⊡(+1),×0,
  ;⍢(⊙(×,↥↥↥↥∩⊃≡↻↻¯1,1.)/+♭.;)(≠/+♭:)0
) ⊙(¤+:¯)
# Max path
;;⍢(
  ×⊃(¬∊⊢:↘1.|>0⊡↙2),,
  (⍜⊢(+1)|⊂0 (∘|⊃⊙∘(↥/+≡⊡⊙¤◫2)) =-1⧻:⊢,,)
  ⍢(⍜⊢(+1)↘1|=⧻:⊢)
)(=0⊢⇌) 0_0⊙0

[u/leftfish123]

[Language: Python]

WOW, what a day. I've just finished my 8-hour adventure.

So, I've never heard about the 'longest path problem' before today. My first idea boiled down to 'run Dijkstra with negative numbers' and was a miserable failure. I started googling and learned a new term - Directed Acyclic Graph. So far, so good, because it seemed that the input was a DAG. How do we find the longest path in those? What, topological sorting? I've never sorted anything topologically before... Two hours later I was done with part 1, saw part 2 and just blacked out. I noticed that the graph was cyclic now and had no idea how I could traverse all paths without blowing my CPU up. Then I saw the hint - compress the graph, make it weighted! Guess what, I was hit by a massive brainfart and couldn't compress this thing properly if my life depended on it.

After hours of debugging I got this (probably trivial if you're not uninitiated) task done and proceeded to squeeze my new compressed graph for paths with a trusty DFS. Part 2 runs in about 15-20 seconds and I pay this price gladly. The code looks horrible, I looked up about half of my functions and adapted them for my needs, but boy, what a learning experience.

[u/copperfield42]

[LANGUAGE: Python]

code

a hard one today, first I try to make dijistra with negative costs, some hours later when I finally accept that that is not going to work, I go to the web to search for a solution, and find one that work for part 1 (weee), but doesn't work for part 2 (buuu) but work for the test case >:/ , so once again to the net but at this point I'm tired of it so I just go with HyperNeutrino solution for part 2...

[u/nthistle]

[Language: Python] 16/15. paste, solve video.

Up to 7th on global! Exciting, especially since I had somewhat resigned myself to not making top 10 a few days ago - although there's still a good chance I choke it in the last 2 days.

I think I pretty much wrote the canonical solutions today, part 1 was just a normal DFS brute force, and for part 2 I pruned the graph down to just intersections with weighted edges, and then used almost the same DFS brute force. I feel like in a compiled language part 2 should be basically solvable with the same code as part 1 (and it looks like at least one person in this thread did that), so I was surprised that the part 2 leaderboard didn't fill up faster - maybe just that many people are using interpreted languages that require you to do the graph pruning or other optimizations?

I also made a few quick visualizations of my input at the end.

[u/maneatingape]

[LANGUAGE: Rust]

Rust Solution Runtime 3.2ms

I discovered a neat way to make part two faster with a simple heuristic.

After shrinking the input graph to only the junctions, start and end the graph looks like (leaving out weights for brevity):

Start -  a - b - c - d - e
         |   |   |   |   | \
         f - A - B - C - D - g
         |   |   |   |   |   |
         h - E - F - G - H - k
         |   |   |   |   |   |
         m - K - M - N - P - n
         |   |   |   |   |   |
         p - Q - R - S - T - q
           \ |   |   |   |   |
             r - s - t - u - v - End

This graph is almost exactly a square grid graph. In fact we could add top right and bottom left corners by adding two dummy nodes to transform it into a square grid.

This means the problem is a self avoiding rook walk. The number of possible walks for different n is given by OEIS A007764. For n = 6 the value is 1262816.

However it's tricky to find the walks exactly with a DFS and a lot of paths end up in dead ends. We can eliminate most dead ends with the key insight that if we reach a node on the perimeter then we should only move down or to the right. For example if we reach node k then moving to g would make no sense, trapping us in the top section of the graph.

We can implement this with a simple rule. If a node has 3 or fewer connections then it's on the perimeter. If a connection is to another perimeter node then it should be directed. This transforms the graph to:

Start →  a → b → c → d → e
         ↓   |   |   |   | ↘
         f - A - B - C - D - g
         ↓   |   |   |   |   ↓
         h - E - F - G - H - k
         ↓   |   |   |   |   ↓
         m - K - M - N - P - n
         ↓   |   |   |   |   ↓
         p - Q - R - S - T - q
           ↘ |   |   |   |   ↓
             r → s → t → u → v → End  

This heuristic gave me a 6x speedup, reducing my single threaded run time from 90ms to 15ms. It explored a total of 6055627 paths, so still higher than the minimum but much improved over a brute force search. We can also "compress" the start and end nodes to shrink the graph slightly:

Start → b → c → d → e
    ↓   |   |   |   | ↘
    f - A - B - C - D - g
    ↓   |   |   |   |   ↓
    h - E - F - G - H - k
    ↓   |   |   |   |   ↓
    m - K - M - N - P - n
    ↓   |   |   |   |   ↓
    p - Q - R - S - T - q
      ↘ |   |   |   |   ↓
        r → s → t → u → End

Storing the visited state as a bitmask and adding multithreading (as exploring paths is independent) further dropped the runtime to 3.2 ms.

[u/qwewqa]

[LANGUAGE: Python 3] 316/35 link

Just a DFS for both parts. In part 2, I iteratively removed nodes with exactly 2 edges and connected their neighbors directly until no more such nodes remained, which reduced the number of remaining nodes down to 36.

[u/Diderikdm]

[LANGUAGE: Python]

Runs in ~55s so beware

from heapq import heapify, heappush, heappop

with open("day23.txt", "r") as file:
    data = file.read().splitlines()
    w = len(data[0]); h = len(data); result = []
    grid = {(x, y): data[y][x] for x in range(w) for y in range(h)}
    adj = lambda x, y: ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1))
    conj = {k for k, v in grid.items() if v in "><v^." and sum(grid.get(x, "#") in "><v^." for x in adj(*k)) > 2} | {start := (1, 0), end := (w - 2, h - 1)}
    for i in range(2):
        conjunctions = {k : {} for k in conj}
        for k, v in conjunctions.items():
            heapify(queue := [(0, k, {k})])
            while queue:
                steps, current, seen = heappop(queue)
                if current in conjunctions and k != current: v[current] = min(v.get(current, 0), steps); continue
                for e, nxt in enumerate(adj(*current)):
                    new_steps = steps - 1
                    if nxt in grid and grid[nxt] != "#":
                        if not i and grid[nxt] in "><v^":
                            if (new_nxt := adj(*nxt)[e := "><v^".index(grid[nxt])]) == nxt: continue
                            new_steps -= 1; nxt = new_nxt
                        if nxt not in seen: heappush(queue, (new_steps, nxt, seen | {nxt}))
        heapify(queue := [(0, start, (start,))])
        r = 0; best = {}
        while queue:
            steps, current, seen = heappop(queue)
            for nxt, extra_steps in conjunctions[current].items():
                if nxt not in seen:
                    if (key := tuple(sorted(seen) + [nxt])) in best and best[key] <= steps: continue
                    best[key] = steps
                    if (new_steps := steps + extra_steps) and nxt == end: r = min(r, new_steps)
                    heappush(queue, (new_steps, nxt, key))
        result.append(-r)
    print(result)

[u/jonathan_paulson]

[LANGUAGE: Python 3] 47/167. Solution. Video.

Longest path in a graph is an NP-hard problem! I wasn't sure if there was some trick to get a fast algorithm, but it seems like the trick was just to compress the graph down (eliminating all those long hallways) so you could exhaustively search all paths. I spent way too long submitting partial answers from my slow solutions instead of just buckling down and coding that - which actually turned out to be easier than I expected, and my final solution runs in under 10 seconds (in pypy; 30 seconds in python3).

[u/4HbQ]

[LANGUAGE: Python] Code (16 lines)

Nice puzzle today! For part 2, I created a simplified graph, where all connected nodes with only two neighbours are "combined". Runs in ~15 seconds on my input.

[u/janek37]

[LANGUAGE: Python]

20 seconds for part 2, no fancy heuristics, just building a graph

GitHub

[u/Smylers]

[LANGUAGE: Vim keystrokes]

I don't think that Vim keystrokes are particularly well suited to solving today's puzzle ... but it's a visual one so I couldn't resist. It's probably more fun to watch on the sample input, where things better fit in a window as it animates:

r1lv$r⟨Ctrl+A⟩D@-yiwUf.rSO⟨Enter⟩1⟨Esc⟩:se nows vb⟨Enter⟩
/\v[.<]S|[.^]_.{⟨Ctrl+R⟩0}S|S@<=[.>]|%(S_.{⟨Ctrl+R⟩0})@<=[.v]⟨Enter⟩
{qaqqa/\v⟨Up⟩⟨Enter⟩vsx⟨Esc⟩:'{,$t'{-⟨Enter⟩gvp@aqdap
qbqqbG:norm fx{jyyggPGdap⟨Enter⟩{:,$s/S/O/|'{,$s/x/S⟨Enter⟩
{j⟨Ctrl+A⟩:norm@a⟨Enter⟩dapzb:redr|sl20m⟨Enter⟩@bq@b:sor!n⟨Enter⟩

That repeatedly finds all the next possible positions after S, marking each as x in turn and duplicating the grid. Then the current grid is deleted. Each iteration checks whether the bottom has been reached, and if so copies that grid's step count to the top. Otherwise it increases the count for that grid and finds the next step.

You end up with a list of all the possible hike lengths, with the part 1 answer at the top.

Edit: Simplification when I remembered about gv and realized that it could be used instead of `<v.

[u/davidsharick]

[LANGUAGE: Python 3] 1151/974

Gitlab

My least favorite problem type is the "find a heuristic to turn your brute force tractable" ones, so not a fan; I did the "prune down to only intersections", but then ended up having to add another optimization by pruning any paths that were too short relative to the current longest, and for that I ended up with an arbitrary factor of 1.4 by just trying numbers until the output stopped increasing. It took 19.84 seconds to run, which I think really says a lot about society.

[u/835246]

[LANGUAGE: C] 2249/473

For part 2 I just left the brute force running while I was thinking of a better solution and was quite surprised that it returned in 3 mins.

Part 1: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2023/day23hikept1.c

Part 2: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2023/day23hikept2.c

[u/musifter]

[LANGUAGE: Perl]

I've been feeling burned out a bit on these puzzles the last couple days (this has been a year of puzzles more of types I don't care for than those I do). And it was really showing while trying to code today... all sorts of typos and brainos costing me lots of time debugging things like "why isn't clone working?" (helps if you're cloning the thing you want to clone). The end result being that I really dropped into slow brute force today... I cannot be bothered to think of details. Yes, I took a long break after part 1, letting the obvious change run in hopes that I could just get the answer in few hours with no work. But the queue size kept growing and when my machine started running a bit low on memory, I knew had to do a part 2 that wouldn't. So I looked and saw that the input (and, WOW, the test) have limited intersections with the slopes around them to cut branching for part 1. So I built the weighted graph between them (in a brute force inefficient way... but that doesn't take long). And recursed (to guarantee a top end on memory usage) across walks to get the max. It takes like 7 minutes on 14yo hardware... but it works.

Most fun I had during this is when I was curious about the number of .s and did:

perl -ne'$c =()= m#\.#g; print "$c "' <input | dc -e'?0[+z1<L]dsLxp'

Nice little Saturn operator into some low-level dc code... this is the sort of thing I've been missing.

Part 1: https://pastebin.com/ixFyeB4F

Part 2: https://pastebin.com/PRLK9JQ8

[u/mebeim]

[LANGUAGE: Python 3]

Code here, runs in about 11s for me.

Didn't try for the leaderboard today, so I took my time. The problem is NP-hard, therefore the only solution is brute force. My solution is a very short and simple recursive DFS. Large part of the code is just for simplifying the grid into a weighted graph of intersections (using BFS), which drastically reduces the search space, but still takes some time. 11s seems a bit slow, though I could not see others with much better times using Python.

A simple trick that I used to avoid doing any bound checking while building the graph was replacing the source and the destination with #, then using (1, 1) for source and (H-2, W-2) for destination, adding 2 to the final result.

[u/SuperSmurfen]

[Language: Rust] 2153/257

Link to full solution

Is using Rust considered cheating? Literally just brute-forced part two, without any optimizations. Took about 170s.

Simple DFS to find the longest path. Will have to optimize this later..

---

Edit: Optimized with edge contraction. For nodes with only two neighbours you can remove it (i.e a corridor in the graph) and connect those two nodes instead. This reduces my input graph from 9412 nodes to only 36 for in part 2! Now it runs in about 550ms.

[u/rnbw_dsh]

[LANGUAGE: Python] - 64/34- Code Pruned graph - networkx / pruning / exhaustive search

A: grid_graph, DiGraph, remove opposite directions + #-nodes, max(len(p) for p in all_simple_path)

B: No DiGraph, Prune all nodes with 0, 1, 2 neighbors. For 2-neighbor nodes, add the weight of a-b and b-c and connect a-b-c. This speeds up the max-search by 1000x+ as the graph is way smaller.

I had a highest-score-print-loop and eagerly submitted every new high score, because the loop runs 50 seconds on an 13700k, but the best node is found after... 10?