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?

M

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

  Submitted by brianjn    
Rating: 4.0000 (1 votes)
Solution: (Hide)
The program below runs a multiplicity of paths.

Depending upon the initial choice of x and y, the constraint is set by the value of 4*x + mod(y,4); mod(y,4) is to be interpreted as 0, 1, 2 or 3.

This formula generates four sequences which have their own unique pattern.
"4 * x + 1" generates a closed spiral of four lobes which never pass through the centre of the spiral array.
"4 * x + 2" generates a closed two lobed spiral that never passes through the centre.
"4 * x + 3" generates a four lobed spiral which does pass through the centre of the array, AND does trace over paths "already trod."
Lastly "4 * x" creates a never ending diagonal chain.

I wrote the program some 12/15 years ago in response to a "hands-on" maths lesson when it became apparent that the children could never get enough space in playground, where we first walked our paths. Inside we replayed on graph paper (suitably sized). The computer program offered them their verification. {This was done with 9-10 yo's - I can probably find the source - literary documentation - of this if required but do not have it personally}.

Charlie's code in his comment at that location runs in a text environment; the characters locate the ends of lineal segments of the path. That which follows calls up a graphics environment. As such, without having a visual of the pathway I don't think Charlie would arrive as fully as that tabulated above.

Nikki's first comment and her next in relation to 'condition' are also worth attention.

' This program will draw 4 different families of "spirals"
 
DEFINT A-Z

DECLARE SUB intro ()
DECLARE SUB order ()
DECLARE SUB plot ()
DECLARE SUB centre (Row, Text$)
DECLARE SUB keyproc ()
DECLARE SUB keyin ()
DECLARE SUB startpos ()

DIM SHARED fast
DIM SHARED x
DIM SHARED y
DIM SHARED tm
DIM SHARED z
DIM SHARED l
DIM SHARED s
DIM SHARED v
DIM SHARED gr
DIM SHARED k$
DIM SHARED Rw
DIM SHARED Cl
DIM SHARED or$
DIM SHARED MaxCol
DIM SHARED ScrHeight
DIM SHARED mode
DIM SHARED ScrWidth

SCREEN 9
WIDTH 80, 25
MaxCol = 80
COLOR 15, 8

intro
 
END

'To create text that is centred
SUB centre (Row, Text$)
  Col = MaxCol \ 2
  LOCATE Row, Col - (LEN(Text$) / 2 + .5)
  PRINT Text$;
 
END SUB

SUB intro
morespir:
CLS
  SCREEN 9, 0, 1, 1
    LINE (0, 0)-(639, 349), 5, B
    COLOR 7
    centre 4, "S P I R A L S"
    COLOR 14
    centre 7, "This program draws spiral paths."
    centre 8, "Each family has its own starting point."
    centre 10, "At any time the program may be interrupted"
    centre 11, "by pressing the space bar."
   
    COLOR 4
    centre 13, "A Reminder message is printed "
    centre 14, "in the top right corner of the screen"
   
    COLOR 6
    centre 16, "Press any key to go on"
      keyin

  ' Page 2 of intro
        CLS
        COLOR 9
        centre 6, "Enter your spiral order, 1 to 20"
        LOCATE 7, 45: PRINT "_ "
        Rw = 7: Cl = 45
        keyproc
        startpos
        plot
         
        GOTO morespir
END SUB

' Get a character from the keyboard
SUB keyin
        k$ = ""
        DO
           k$ = INKEY$
        LOOP WHILE k$ = ""
       
END SUB

SUB keyproc
or$ = ""
nextkey:
  keyin
    IF k$ = "*" THEN SYSTEM
    IF or$ = "" AND k$ = CHR$(13) THEN k$ = "": GOTO nextkey
    IF k$ = CHR$(13) GOTO leave
    IF or$ = "" AND k$ = CHR$(8) THEN k$ = "": GOTO nextkey
    IF k$ = CHR$(8) THEN or$ = LEFT$(or$, LEN(or$) - 1): GOTO over
      or$ = or$ + k$
over:
        LOCATE Rw, Cl: PRINT or$; "_  "
        GOTO nextkey
leave:
  
END SUB

'plots the spiral of the chosen family group
SUB plot
        CLS
        PRINT gr
        tm = 1
        FOR f = 1 TO l
          FOR s = 1 TO v
           COLOR 14: LOCATE 1, 40: PRINT "Press ENTER for next step"
           COLOR 8: LOCATE 2, 40: PRINT "Press C to finish spiral"
              ON tm GOSUB up, left, down, right
                 tm = tm + 1
                 IF tm = 5 THEN tm = 1
          NEXT s
        NEXT f
       
        GOTO donespir

 END
up:
        FOR a = 1 TO s
          LINE (x, y)-(x, y - z), 7
          y = y - z
          GOSUB star
        NEXT
        RETURN
END

left:
        FOR a = 1 TO s
          LINE (x, y)-(x - z, y), 7
          x = x - z
          GOSUB star
        NEXT
        RETURN
END

down:
        FOR a = 1 TO s
          LINE (x, y)-(x, y + z), 7
          y = y + z
          GOSUB star
        NEXT
        RETURN

END

right:
        FOR a = 1 TO s
          LINE (x, y)-(x + z, y), 7
          x = x + z
          GOSUB star
        NEXT
        RETURN

END

star:
        LINE (x - 1, y + 1)-(x + 1, y - 1), 14
        LINE (x - 1, y - 1)-(x + 1, y + 1), 14
reloc:
       
        IF fast = 1 THEN GOTO quick
        keyin
        IF k$ = "c" THEN fast = 1
        IF k$ = CHR$(32) THEN END
        IF k$ <> CHR$(13) THEN GOTO reloc
        
quick:  RETURN
END

donespir:
     COLOR 14
     LOCATE 23, 48: PRINT "Press any key to go on (or  x  to end)"
     keyin

END SUB

SUB startpos
        fast = 0
        v = VAL(or$)
        z = 24
        z = INT(6 * z / v)
        x = 320
        y = 200
          
           IF v = 1 THEN gr = 1: GOTO jump
           
          gr = (v / 4 - INT(v / 4)) * 4
jump:
       l = 4
          IF gr = 1 THEN y = 240: x = 350
          IF gr = 2 THEN l = 2
          IF gr = 3 THEN x = 300: y = 150
          IF gr = 0 THEN y = 60: x = 100

END SUB

Comments: ( You must be logged in to post comments.)
  Subject Author Date
re(4): Revisionbrianjn2008-01-27 18:36:46
re(3): RevisionCharlie2008-01-27 11:00:04
re(2): Revisionbrianjn2008-01-26 21:34:57
re: RevisionCharlie2008-01-26 11:47:26
Revisionbrianjn2008-01-26 03:25:26
re(6): No Subject - ConstraintCharlie2008-01-23 11:47:41
re(5): No Subject - ConstraintCharlie2008-01-23 11:28:25
re(5): No Subject - ConstraintCharlie2008-01-23 10:52:46
re(5): No Subject - Constraintbrianjn2008-01-23 08:39:35
re(4): No Subject - Constraintnikki2008-01-22 17:14:04
re(3): No Subject - Constraint and shebrianjn2008-01-21 21:05:28
re(3): No SubjectCharlie2008-01-21 01:49:47
re(2): No Subjectnikki2008-01-20 23:39:26
re(3): findings - like DNAbrianjn2008-01-20 17:40:46
re(2): findings - like DNACharlie2008-01-20 11:57:27
re: No Subjectbrianjn2008-01-20 09:35:19
re: findings - like DNAbrianjn2008-01-20 09:16:13
Some ThoughtsNo Subjectnikki2008-01-18 18:51:22
Some ThoughtsfindingsCharlie2008-01-18 18:39:07
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


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

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information