last day (15 days later) » 

9:18 PM
7
Q: Solve all 4x4 mazes simultaneously with least moves

Olavi MustanojaI came across this quite interesting problem, where we have a 4x4 maze and a robot in it trying to get to the goal. The thing is, you have to find a sequence of predefined commands that will always result in the robot reaching the goal. Let's say we have a maze like this: x . . . . # # . . # # ...

 
@גלעדברקן בר Well... for example DRDRDRRR
@גלעדברקן Ah, sorry for not mentioning: moving to blocked squares simply makes the robot not go there.
@above There is no one maze where UP must be used. If we had just a single maze we would only ever need RIGHT and DOWN
See edits. Linked a pastebin.
 
I used some lose reasoning and sketchy diagrams that seem to imply there are a mere 2176 solvable mazes. Using more solid math I can prove it's lower than 10240.
No wait, I figured out an ordering. I'm pretty sure there's 3104 solvable 4x4 mazes from top left to bottom right. ideone.com/0mrNH8
 
@MooingDuck what do ! and ? indicate?
 
@OlaviMustanoja: Both indicate squares that could be either # or .. I ordered the mazes by the "leftmost lowest" path of 6 moves that could solve them, and beneath are the number of mazes in each category. The ! mirror the #, because I thought that would be needed, but it turns out to be irrelevant.
 
@MooingDuck How did you decide where to place the #s and ?s ?
 
9:18 PM
While reviewing it right now I found an error in one path category, correct result is 3200.
Basically I first plotted each of the . paths. Then I determined where the # must be to force that path to be the "leftmost lowest" path. The ! and ? were then put everywhere else
 
what do you mean by "leftmost lowest" path?
oh.. uh, heh, yeah I can see the pattern now
 
It seems obvious to my mind I'm having trouble putting it into words. Each solvable 4x4 maze has at least one solution, of which one/some are shortest. Of the shortest paths for each 4x4 maze, there is no possible maze where a shortest solution ever goes up or left.
So it's the shortest solution for each mazeset that stays closest to the bottom
5x5 would be significantly more challenging because shortest solutions can go up/left :/
 
yeah I just understood it after looking at it
 
(Shortest solutions for the maze, not for your puzzle)
 
Sorry I haven't slept in almost two days :D
 
9:26 PM
Well go do that then
 
nah, not sleepy yet
 
I wrote a program to test/confirm answers but it's crazy buggy still
it says that RDRDRDRDRDRDRDRD solves all 16384/3200 :(
 
couldn't we generate every possible maze, and out of those simply exclude all mazes that have even one block that cannot be reached or thouched
 
That would require you to iterate over all 3200 mazes, but yes. My code uses j_random_hacker's idea of space/wall/unspecified to calculate many at a time. I assumed it's faster but may not be
Your idea sounds simpler though
 
to me the execution time doesn't really matter if it's /waitable/
30s is perfectly fine, though generating all those mazes won't take two seconds
 
9:34 PM
step 1 is to write code that determines if an answer is right or wrong quickly. step 2 is to put it in a loop and brute force an answer :D
 
Yeah, no problem. there are 3828 mazes with simply a path in existance
 
hmm, that doesn't match my math. I wonder which of us is wrong?
 
I'll link you the generating methods (Java), just a sec. you can review it, but practise shows me it's correct
generateMazes() recursively generates all possible mazes, discarding mazes with no solution
 
ideone.com/i42KG9 well that's half of some code
 
lol it was split in half. just a sec I'll do it again
ugh, ok here it is: pastebin.com/F1qZsZnK
the canMove() is a horrible method, sorry about that. I'm storing all maze layouts in 1D int arrays, 16 in length
 
9:50 PM
You didn't post the maze class. I made one with an empty constructor and no other members and got the same result. Sounds buggy. ideone.com/i42KG9
oh no, nevermind, the Maze class is the output
 
Oh haha, forgot to change it
 
rewrote my code, now also coming up with 3828, so apparently that's the right number
 
I'm starting to think this might actually be a dynamic programming problem
as in every situation can be reduced to a choice between RIGHT and DOWN
 
10:06 PM
only for the shortest path. A generic answer has to work its way out of dead ends, which takes ups/lefts.
 
yeah that's what I meant. the shortest path, that when mirrored will solve the same amount of mazes
after finding one such path, we just have to get every maze back to (0, 0) and do the mirrored sequence
I think getting all permutations of RIGHT and DOWN commands will be enough. There won't be a significant amount of those
 
heh, can't brute force. 4^29 possible strings each of length 29 -> 14155776TB
 
2^6 + 2^7 + 2^8 + . . . + 2 ^ k was my idea
 
even just iterating over 2^30 possible strings would take forever
 
very doable. After generating each permutation, I check if the permutation will end up with at least 1914 solved mazes. if yes, then try if the mirrored sequence will solve the rest. if yes, we have our first solution
given that we know 29 total moves is enough, I can conclude that 2^15 is the absolute maximum needed
 
10:19 PM
why mirrored if it's a full 29-length solution
for X, undo X, mirror X, you'd want X to have a length of 10 or 11
 
I'll explain again. I want to achieve such a solution which will end up with at least 1914 solved mazes, and after getting all mazes back to the start, do the same sequence, only mirrored.
I'll go with the RRDDRRDDRR possibility
it solved about 2300 mazes, which is over a half
if the same sequence, mirrored, would solve the remaining ~1500 mazes if they started from (0, 0), we would have a sequence that solves all mazes
 
no, you have a sequence that solves half, and the mirror solves the other half
or a triple-length sequence that solves all
 
so
1. RRDDRRDDRR solves ~2300 mazes (10 moves)
2. get all mazes back to (0, 0) (optimally 9 moves)
3. DDRRDDRRDD solves the rest of the mazes (10 moves)
 
really? neat
 
to generalize (SEQ is a sequence that solves half of the mazes, !SEQ is mirrored)
1. SEQ solves >= 1914 mazes
2. move all mazes back to (0, 0)
1. !SEQ solves rest of the mazes
 
10:28 PM
well yes, but the result is triple the length. I was just surprised you found a ten length that solves half who's inverse solve the other half
 
now we know that RRDDRRDDRR is not such a sequence. the problem is, we have to find such a sequence
 
oh, you had me going
yeah, your logic is sound, I would just be surprised if such a sequence exists
 
but what I'm going at is, that to find such a sequence that is anywhere from 6 to 12 in length, and contains only R and D moves
there aren't much
2^6 + 2^7 + 2^8 + 2^9 + 2^10 + 2^11 + 2^12 = 8128
easily doable, very fast
 
11:03 PM
If you're still there, I found such a sequence
there's actually exactly one such sequence :'D
it is...
du dum
RRRRDDDDDRDDD
 
oh?
 
actually no. what the hell. something went wrong
 
that can't be right, there's 5 D in a row
 
yeah I got a bit hasty there
what's the bug...
 
alright, I give up.
 
11:08 PM
lol that was a leftover print from somewhere
I removed it and... no solutions
shit
 
11:24 PM
Here's an actual result!
RRDRRRDRLDRDR
I got this shit
thanks to this I got a 41 long solution:
DDSDDDSDASDSDASAWWAWDWWWAWAASSDSSSDSWDSDD
 
Based on there being 27 commands. Seems like the solution should have 5 downs, 5 lefts, 5 rights, and 4 ups.
 
oops, wrong codes
 
no wait.. miscounted.
 
RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRR
 
Should be 6 of each then down, left and right.
 
11:31 PM
Missing one char
RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRRD works
 
11:49 PM
RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD
R: 14 L: 7 U: 8 D: 13
 

  last day (15 days later) »