5
\$\begingroup\$

There is a mouse in a room, in the top-left corner. It can move up, down, left, or right, and the mouse cannot go through any cell in the room twice. Given this, return all the possible paths in which the mouse will visit every square.

Input: Two integers m and n, which represent the m x n room. m<9, n<9.

Output: The m x n room, with ^<>v noting the direction the path goes. Each line of the room will be seperated by a newline, and each room will be seperated by one newline. The last room the mouse enters will be noted by a dot.

v > v .
v ^ v ^
> ^ > ^

next room goes here...

Test Cases:

Input: 2 3, output:

v > v
> ^ .

> > v
. < <

v . <
> > ^

Shortest code wins.

Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ Is there any restriction about the very last step? Since the mouse already entered each cell, any of the four directions would be ok. \$\endgroup\$
    – Howard
    Jul 1, 2012 at 15:20
  • \$\begingroup\$ @Howard: Whoops! The mouse can only go through cells once. \$\endgroup\$
    – beary605
    Jul 1, 2012 at 16:01
  • 1
    \$\begingroup\$ So that means that the last step must go "outside" of the grid? Because the very last example in your test cases does not fulfill this rule. (should be v^<, >>^ then) \$\endgroup\$
    – Howard
    Jul 1, 2012 at 16:13
  • \$\begingroup\$ @Howard: Ok, I see what you are getting at now. The last step is unrestricted. \$\endgroup\$
    – beary605
    Jul 1, 2012 at 16:22
  • 1
    \$\begingroup\$ I edited your question to improve the example output formatting. While doing so, I also moved the dot in the last example output room, since it appeared to be misplaced. (The mouse cannot end its path in the upper left corner, since that's where it started.) Please correct me if I made any mistakes. \$\endgroup\$
    – Ilmari Karonen
    Jul 2, 2012 at 15:42

3 Answers 3

Reset to default
5
\$\begingroup\$

GolfScript, 146 137 characters

~:h\:w*:s(4\?,{[[0.]{\.4/\4%@[0$"<^v>"3$=]@2*)@[~2$3/+(\@3%+(\]@\}s(*[\;46]].{.0=.~0(>\0(>@~h<\w<&&&\0=~w*+*}%$s,={${1=}%h/n*n+n+}{;}if}%

The code shows a very direct implementation in GolfScript. Therefore, I suspect that there is plenty room for improvement. Be aware that the algorithm is really slow if you try it on anything larger than 3x3 or 2x4. I decided to put a . for the last position since any direction would be allowed there (the mouse already entered each cell and the last step is irrelevant).

Example:

> 2 4
>>>v
.<<<

v.<<
>>>^

v>>v
>^.<

v>v.
>^>^

Edit: Minor changes.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I like your dot idea. I will add that into the rules \$\endgroup\$
    – beary605
    Jul 2, 2012 at 4:08
4
\$\begingroup\$

Python, 296 269

With so many suggestions from others, I decided to make this a community solution. Tabs have been replaced with 4 spaces.

a=[-1,0,1,0];d='<^>v.'
def r(x,y):
 if G.values().count(4)<2:
    for i in n:print''.join(d[G[j,i]]for j in m)
    print
 for i in range(4):
    X=x+a[i];Y=y+a[i-1]
    if 4==G.get((X,Y)):G[x,y]=i;r(X,Y);G[X,Y]=4
m,n=map(range,input())
G=dict(((i,j),4)for i in m for j in n)
r(0,0)

Example

$ python paths.py
5,2
>>>>v
.<<<<

v>>>v
>^.<<

v>v>v
>^>^.

v>v.<
>^>>^

v.<<<
>>>>^
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ By three newlines, I meant \n for the end of the first room, \n to seperate them, and... I'm not sure why there's a third. You only need one newline now. \$\endgroup\$
    – beary605
    Jul 2, 2012 at 4:11
  • \$\begingroup\$ @beary605 w00, saved 6 characters! \$\endgroup\$
    – boothby
    Jul 2, 2012 at 4:17
  • 1
    \$\begingroup\$ You could save a few characters with m,n=map(range,input()). It would mean you could use for i in m rather than for i in range(m). \$\endgroup\$
    – grc
    Jul 2, 2012 at 5:14
  • 1
    \$\begingroup\$ Also an additional two chars by swapping up and down ('<^>v') and then X=x+a[i];Y=y+a[i-1]. \$\endgroup\$
    – Howard
    Jul 2, 2012 at 5:39
  • 1
    \$\begingroup\$ Small changes: if(X,Y)in G and'.'==G[X,Y] -> if'.'==G.get((X,Y)), print''.join(...); print -> print''.join(...)+'\n' and substitute '.' with a variable. \$\endgroup\$
    – Ante
    Jul 2, 2012 at 13:40
1
\$\begingroup\$

Mathematica 347 315 chars

Very slow for all but the smallest arrays. This is because the solution is overly general, treating the paths as Hamiltonian Graphs rather than something more specific like a grid. Anyway, here's the code:

Needs["Combinatorica`"]
p=ReplacePart;
q[l_,{},s_]:=p[s,l->"."]//Grid
q[l_, d_,s_]:=q[l+d[[1,1]], Rest@d,p[s,l:>d[[1,2]]]]
f[r_,c_]:=Column[q[{1,1},Differences[#]/.{-1-> {{0,-1},"<"},1-> {{0,1},">"},c-> {{1,0},"v"},-c-> {{-1,0},"^"}},ConstantArray[0,{r,c}]]&/@Cases[HamiltonianPath[GridGraph[c,r],All],{1,__}],Spacings->{0,3}]

Example (I reformatted the output into a table):

"4 4"
f@@ImportString[%,"Table"][[1]]

result44

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.