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

Home > General
Star Trek (Posted on 2005-09-23) Difficulty: 3 of 5
                                    
                  * * * * * 
            * * * * 4 7 7 * * * * 
        * * * 5 4 4 8 3 3 4 6 3 * * * 
      * * 1 4 5 1 1 1 4 5 1 7 1 3 5 * *
    * * 4 9 4 9 6 7 5 5 5 8 7 6 6 8 5 * *
    * 3 7 2 9 8 3 5 6 7 3 9 1 8 7 5 8 5 *
  * * 1 4 7 8 4 2 9 2 7 1 1 8 2 2 7 6 3 * *
  * 7 2 1 8 5 5 3 1 1 3 1 3 3 4 2 8 6 1 3 *
  * 4 2 6 7 2 5 2 4 2 2 5 4 3 2 8 1 7 7 3 *
* * 4 1 6 5 1 1 1 9 1 4 3 4 4 3 1 9 8 2 7 * *
* 4 3 5 2 3 2 2 3 2 4 2 5 3 5 1 1 3 5 5 3 7 *
* 2 7 1 5 1 1 3 1 5 3(3)2 4 2 3 7 7 5 4 2 7 *
* 2 5 2 2 6 1 2 4 4 6 3 4 1 2 1 2 6 5 1 8 8 *
* * 4 3 7 5 1 9 3 4 4 5 2 9 4 1 9 5 7 4 8 * *
  * 4 1 6 7 8 3 4 3 4 1 3 1 2 3 2 3 6 2 4 *
  * 7 3 2 6 1 5 3 9 2 3 2 1 5 7 5 8 9 5 4 *
  * * 1 6 7 3 4 8 1 2 1 2 1 2 2 8 9 4 1 * *
    * 2 5 4 7 8 7 5 6 1 3 5 7 8 7 2 9 3 *
    * * 6 5 6 4 6 7 2 5 2 2 6 3 4 7 4 * *
      * * 2 3 1 2 3 3 3 2 1 3 2 1 1 * *
        * * * 7 4 4 5 7 3 4 4 7 * * *
            * * * * 3 3 4 * * * *
                  * * * * *

Starting from the central cell of this maze (there's a (3) in it), the challenge is to find a path that leads you off the maze, and to a "star" (*).

The number at each cell shows how many steps, in a straight line, you must take. You can travel horizontally, vertically, or diagonally, up or down, left or right.

But! You must reach the first star in the direction you are travelling in an exact number of steps, and not go any further. If you reach a star, and still have some steps "left over", you cannot exit that way.

See The Solution Submitted by pcbouhid    
Rating: 3.6000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution | Comment 11 of 27 |

The computer algorithm is recursive, backing up when all directions lead to a dead end, where a dead end means that either a node is revisited (overall in all solutions) with more steps than it took before, or there is no node in that direction and it is more than one unit away from the digits. So long as viable paths lead from a point all such viable paths are explored.  It proceeds rather rapidly, to arrive at a 9-move solution (It was told initially to go no more than 100 levels deep--no more than 100 moves--and its first found solution had 92 steps.)

The 9-step solution, can be described in words.  First of all, except for the last step it is all on a diagonal running from upper right to lower left, and exiting by making a right-angled turn at the 4 that's near the lower left end of this diagonal (the 6 that is next to it is on the edge).  All the solutions seem to go through that 4.

From the initial 3 go down and to the left to a 4; then down and to the left to the 6; then up and to the right to another 6 and further to the upper right to a 2. Again go up and to the right to a 5 on the edge.  From there, down and to the left to a 4, and again down and to the left to another 4. Down and to the left again leads to the magic 4, where a right angled turn in either direction (upper left or lower right) takes you out.

The program, listed below, initially reads in the digits from a file and places them in an array, centering each row on the middle element of the array.  When presenting the result it sends an expanded form of the original array to a file, with each single digit preceded by the time at which that node is visited and with a directional indicator next to the original digit showing the direction to the next node in sequence. (That's to make the longer paths more easy to follow.)

DECLARE SUB move (row!, col!)
CLEAR , , 20000

OPEN "startrek.txt" FOR INPUT AS #1
DO
  LINE INPUT #1, l$
  ct = 0
  FOR i = 1 TO LEN(l$)
    IF INSTR("0123456789", MID$(l$, i, 1)) THEN ct = ct + 1
  NEXT
  IF ct > maxCt THEN maxCt = ct
  IF ct > 0 THEN lCt = lCt + 1
LOOP UNTIL EOF(1)
CLOSE
PRINT maxCt; lCt


DIM SHARED cell(lCt + 1, maxCt + 1), had(lCt, maxCt), gridSize, lvl
DIM SHARED drH(lCt, maxCt), dcH(lCt, maxCt)
DIM SHARED when(lCt + 1, maxCt + 1), when2(lCt + 1, maxCt + 1), solCt, bestSol

gridSize = maxCt

midPos = INT((maxCt + 1) / 2)

OPEN "startrek.txt" FOR INPUT AS #1
lCt = 0
DO
  LINE INPUT #1, l$
  ct = 0
  FOR i = 1 TO LEN(l$)
    IF INSTR("0123456789", MID$(l$, i, 1)) THEN ct = ct + 1
  NEXT
  IF ct > 0 THEN
   lCt = lCt + 1
   midCt = INT((ct + 1) / 2)
   offSet = midPos - midCt
   FOR i = 1 TO LEN(l$)
     IF INSTR("0123456789", MID$(l$, i, 1)) THEN
       offSet = offSet + 1
       cell(lCt, offSet) = VAL(MID$(l$, i, 1))
     END IF
   NEXT
  END IF
LOOP UNTIL EOF(1)
CLOSE

FOR row = 1 TO lCt
  FOR col = 1 TO maxCt
    PRINT cell(row, col);
  NEXT
  PRINT
NEXT

had(midPos, midPos) = 1
when(midPos, midPos) = 1
lvl = 1
bestSol = 9999
OPEN "startrk3.txt" FOR OUTPUT AS #2

move midPos, midPos

PRINT solCt, bestSol

CLOSE

END

SUB move (row, col)
 stpSize = cell(row, col)
 FOR dr = -1 TO 1
   FOR dc = -1 TO 1
     IF dr OR dc THEN
      good = 1
      r1 = row + dr * (stpSize - 1): c1 = col + dc * (stpSize - 1)
      IF r1 > 0 AND r1 <= gridSize AND c1 > 0 AND c1 <= gridSize THEN
        IF cell(r1, c1) THEN
         r = row + dr * stpSize: c = col + dc * stpSize
         IF cell(r, c) = 0 THEN
           when(r, c) = lvl + 1
           drH(row, col) = dr
           dcH(row, col) = dc
           FOR rw = 1 TO gridSize
            FOR cl = 1 TO gridSize
              IF drH(rw, cl) < 0 AND when(rw, cl) > 0 THEN
               SELECT CASE dcH(rw, cl)
                CASE -1
                 PRINT #2, "  \  ";
                CASE 0
                 PRINT #2, "   ^ ";
                CASE 1
                 PRINT #2, "    /";
               END SELECT
              ELSE
               PRINT #2, "     ";
              END IF
            NEXT cl
            PRINT #2,
            FOR cl = 1 TO gridSize
             IF when(rw, cl) > 0 THEN
              PRINT USING "##"; when(rw, cl);
              COLOR 14: IF cell(rw, cl) = 0 THEN COLOR 9
              PRINT USING "#"; cell(rw, cl);
              IF drH(rw, cl) = 0 AND dcH(rw, cl) < 0 THEN
                PRINT #2, "<";
               ELSE
                PRINT #2, " ";
              END IF
              PRINT #2, USING "##"; when(rw, cl);
              PRINT #2, USING "#"; cell(rw, cl);
              IF drH(rw, cl) = 0 AND dcH(rw, cl) > 0 THEN
                PRINT #2, ">";
               ELSE
                PRINT #2, " ";
              END IF
              COLOR 7
             ELSE
              IF cell(rw, cl) THEN
               COLOR 14: IF cell(rw, cl) = 0 THEN COLOR 9
               PRINT USING "  #"; cell(rw, cl);
               PRINT #2, USING "   # "; cell(rw, cl);
               COLOR 7
              ELSE
               PRINT "   ";
               PRINT #2, "     ";
              END IF
             END IF
            NEXT cl
            PRINT #2,
            FOR cl = 1 TO gridSize
              IF drH(rw, cl) > 0 AND when(rw, cl) > 0 THEN
               SELECT CASE dcH(rw, cl)
                CASE -1
                 PRINT #2, "  /  ";
                CASE 0
                 PRINT #2, "   v ";
                CASE 1
                 PRINT #2, "    \";
               END SELECT
              ELSE
               PRINT #2, "     ";
              END IF
            NEXT cl
            PRINT #2,
            PRINT : PRINT
           NEXT
           solCt = solCt + 1
           IF lvl < bestSol THEN bestSol = lvl
           when(r, c) = 0
         ELSE
            IF lvl < 100 AND (had(r, c) = 0 OR when2(r, c) > lvl) THEN
             drH(row, col) = dr
             dcH(row, col) = dc
             lvl = lvl + 1
             had(r, c) = 1
             when(r, c) = lvl
             when2(r, c) = lvl
            
             move r, c

             when(r, c) = 0
             lvl = lvl - 1
            END IF
         END IF
        END IF
      END IF
     END IF
   NEXT
 NEXT
END SUB

 


  Posted by Charlie on 2005-09-24 02:29:46
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 (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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