The final feedback was that my coding wasn't good enough. It was a BFS problem, and I didn't think of that at first.
You're given a maze: # is a wall, . is an open path, E is the exit. The only commands are up / down / left / right, and each one moves you one cell. Key rules:
If you hit a wall you stay where you are (that's not a failure, you just stay in place). Execution gives no feedback at all; you only know it's over when you reach E. The starting point is unknown. Find: one fixed sequence of commands such that no matter which open cell you start from, you will pass through E. (The problem guarantees there is a way out.) Example maze:
##########
#..#..E..#
#..#.....#
#..##..#.#
#......#.#
##########
Approach
Insight 1: no feedback => you can't make decisions as you go, you can only generate a "dead sequence" up front. Since you get no information while the commands are executing, you can't do "walk to here, then look at the situation and decide the next step". So the answer has to be one fixed command sequence that works for every starting point.
Insight 2 (the most important one): the state is not "which cell am I in", it's "the set of cells I might be in".
This is the belief state. Don't do BFS on individual cells; do BFS on "sets of possible positions". One BFS state = an entire set (represented as a frozenset).
This is exactly where I got stuck at the time: I assumed by default that "state = one cell", so I felt the BFS had no starting point and couldn't get off the ground, and I wrongly gave up on BFS and switched to thinking about greedy.
Insight 3: hitting a wall is a tool for "collapsing uncertainty", not an obstacle.
Each command is a deterministic mapping on the set: move if you can, stay put if you hit a wall. Because hitting a wall means you don't move, two different cells can land on the same cell in the same step and merge. So the "set of possible positions" only shrinks or stays the same; it never grows. Pushing in one direction over and over = "squeezing" all the possible positions up against that wall, lining them up, and collapsing them together. The goal is to "squeeze" the set all the way down to empty (every starting point has already passed through E).
Discussion
Loading comments…