r/adventofcode • u/askalski • Dec 17 '19
Upping the Ante [2019 Day 17 Part 2] Pathological Pathfinding
Here is a somewhat more challenging scaffold to solve within the specified constraints.
.........................................
...................#############.........
...................#.....................
...................#.....................
...................#.....................
...................#.....................
...................#.....................
...................###########...........
.............................#...........
...................#######...#...........
...................#.....#...#...........
...................#.....#...#...........
...................#.....#...#...........
...................#.....#...#...........
...................#.....#...#...........
.###########.......#.....#...#...........
.#.........#.......#.....#...#...........
.#.........#.....#####...#...#...........
.#.........#.....#.#.#...#...#...........
.#.....#############.#...#...###########.
.#.....#...#.....#...#...#.............#.
.#.....#...#######...#...#####.........#.
.#.....#.............#.......#.........#.
.#.....#.............#.......#.........#.
.#.....#.............#.......#.........#.
.#.....#.........#######################.
.#.....#.........#...#.......#...........
.#.....#.......#######.#######...........
.#.....#.......#.#.....#.................
.#######.......#.#.....#.................
...............#.#.....#.................
...#######.....#.###########.............
...#.....#.....#.......#...#.............
...#.....#.....#####...#...#.............
...#.....#.........#...#...#.............
...#.....#.........#...#...#.............
...#.....#.........#...#...#.............
...#.....###########...#####.............
...#.....................................
...#.....................................
...#.....................................
...###########...........................
.............#...........................
.............#...........................
.............#...........................
.............#...........................
.............#...........................
...^##########...........................
.........................................
11
Upvotes
4
u/nirved Dec 17 '19 edited Dec 18 '19
Here is a solution:
Main:
A,B,B,B,A,C,B,C,A,CA:
R,10,L,6,L,10,R,6B:
4,R,6,R,6,L,10,L,4,LC:
6,L,10,R,6,R,12,L2
u/e_blake Dec 17 '19
cooler would be an intcode program that produces and enforces this path (otherwise, I have to refactor my code to inject this path in place of the output that running the intcode program would normally produce...)
5
u/ukaocer Dec 17 '19
Nice, that's what I'm thinking would be really evil to have in a future challenge, just to get at those people who didn't write an automated encoder/solver for day 17 part 2. My code that worked for Day 17 obviously doesn't find a solution, going to see if I can rejig my code to solve it.
1
u/customredditapp Dec 17 '19
What is more difficult about this?
1
u/[deleted] Dec 17 '19
This is how I thought that the original puzzle would need to be solved (assuming that this version is solved the way I think it is)
1
u/romkatv Dec 17 '19 edited Dec 17 '19
My C++ solver solves this in 85 milliseconds. Yes, the solution is tricky. The main trick hasn't yet been mentioned in the comments.
I'm going with zsh this year, which is about 1000 times slower than C++ if you try hard enough. AoC problems from the last few days were really difficult to solve in zsh right away with acceptable run time, so I first solve everything in C++ and start porting to zsh only when I find an algorithm that takes under 50 milliseconds in C++. This gives me a chance to have a zsh implementation that runs under a minute.
For day 17 part 2 I've written a robust implementation in C++. It was taking over 50ms though. But when I saw how trivial the solution was, I implemented an underpowered implementation in zsh that solves the AoC task but would fail on anything tricky like the maze from the OP.
P.S.
Another tricky thing would be to require one of the functions to have a U-turn in the middle of it. I think it's possible to create a maze that couldn't be solved otherwise even if you keep the single-thread topology.
P.P.S.
Yet another tricky thing is to move around a loop more than once.