All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Unbounded Maze (Posted on 2008-01-18) Difficulty: 3 of 5
A programmable robotic mouse is placed at an intersection on a square grid, the borders of which are extendable as needed.

From its initial location the mouse moves one cell forward. It turns right with its next move incrementing by 1.

This incremental process continues up to a certain constraint whereby the mouse resumes the process with a move of one space until that constraint is met again; continue this process until you either return to your starting position or you evidently will never return.

What generalisations can be made about how variations of the value of the constraint affect the path forced upon the mouse?


Note:It will be necessary to test a range of constraining values.

See The Solution Submitted by brianjn    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts findings | Comment 1 of 19

The only type of rule governing resetting the step size to 1 that I have investigated is to reset to 1 after having reached a given limit.

The path below starts with the zero, considered the origin. The numbers initially refer to how many steps to get there. When digits run out, lower case, and then upper case, letters are used. When the step size reached 12, the next step was size 1.  Since 12 is a multiple of 4, it's in the same direction as the previous step of 1, starting an iteration of the same pattern, which leaves off and restarts 6 columns to the right and 6 rows up. Thus the mouse gets ever farther up and to the right (when the original direction is down).

                               X           Y
                                 T       U
                                   P   Q
                         L           M
                                   O N
                           H       I
                                 S     R
                             D   E
                               W         V
                   z           A
                             C B
                     v       w
                           G     F
                       r   s
                         K         J
             n           o
                       q p
               j       k
                     u     t
                 f   g
                   y         x
       b           c
                 e d
         7       8
               i     h
           3   4
             m         l
           2 1
         6     5
       a         9

When the sequence of step sizes goes up to a number that's not a multiple of 4, the pattern repeats in place. Again below, where the steps go from 1 to 11, the sequence of positions is 0 (the start point), 123456789abcdefghijklmnopqrstuvwxyzABCDEFGH.  After H the path retraces 0123....

       j        k
         f    g
 v         w
         e  d7       8
   r     s
       i      h3   4
     n o
     mH         l0
               2 1
   q   pD      E
             6     5
 u       tz  A
           a         9
        C    B
      G        F

For a maximum step size of 10 (even, but not a multiple of 4), there's only a twofold symmetry:     

         7       8
           3   4
   j         0
           2 1
     f     g
         6     5
       b c
       a         9
     e   d
   i       h

(The positions starting at 0 follow after position j.)
There will always be this fourfold symmetry for odd maxima and twofold symmetry for even maxima that are not multiples of four. Multiples of four will always exceed any bounds you might set. 

Odd maxima: If first time through changes x coordinate by a, and y coordinate by b, then the next time through changes the x coordinate by b and the y by a; the next two negate the coordinate changes of the first two, so you wind up where you started.

Even maxima, not multiple of four: Second time through, the net column and row change of the sequence is reversed, again winding up where you started.

Multiple of four: The net change in x and y from the sequence is repeated over and over, getting farther and farther from the origin.

x = 20: y = 36
dirx = 0: diry = 1
amt = 1
lim = 10

s$ = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
mNo = 1
 LOCATE y, x : PRINT MID$(s$, mNo, 1);
 DO: a$ = INKEY$: LOOP UNTIL a$ > "": IF a$ = CHR$(27) THEN EXIT DO
 x = x + dirx * amt: y = y + diry * amt
 amt = amt + 1: IF amt > lim THEN amt = 1
 diryNew = dirx: dirxNew = -diry
 diry = diryNew: dirx = dirxNew
 mNo = mNo + 1
 IF mNo > LEN(s$) THEN mNo = 1

  Posted by Charlie on 2008-01-18 18:39:07
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information