33
\$\begingroup\$

You are on an advanced intergalactic space station. A friend of yours who is minoring in the Study of Gravity just created a game that involves using microgravity as a way to move a ball around.

She hands you a small controller with four directional arrows on it and a maze like structure with a ball sitting to the left. She begins to explain how the game works.

  • You have 2 directional buttons, left < and right >.
  • You also have 2 gravity buttons, up ^ and down v (at least from your frame of reference)
  • You will use these arrow buttons to move the ball around on your screen.

"Now there are some rules that need to be followed." she says

  1. All platforms must be traversed before getting to the cup \ /
  2. Arrows < > ^ v will be used to specify movement of the ball
  3. Gravity is ^ v (up & down). This moves the ball all the way to the next platform in that direction. (Distance is not calculated for up and down)
  4. Losing the ball is bad! Don't fall over the edge, and don't switch gravity too soon such that your ball never reaches a platform
  5. Movement is counted in steps of < >
  6. The ball can enter the cup from any direction as long as Rule 1 is followed
  7. You must specify direction of gravity so your ball doesn't float away
  8. Movement may be random as long as Rule 1 and Rule 4 is followed
  9. For cases that cannot be solved output False or Invalid

Simple Example of a ball, platform, and cup:

v
o
---\ /

v>

 o
---\ /

v>>

  o
---\ /

v>>>

   o
---\ /

v>>>>


---\o/

Example of traversing over the same platform again.

v    

 o
 ----

\ /-------

v>   

  o
 ----

\ /-------

v>>

   o
 ----

\ /-------

v>>>

    o
 ----

\ /-------

v>>>>


 ----
     o
\ /-------

v>>>>>


 ----
      o
\ /-------

v>>>>>>


 ----
       o
\ /-------

v>>>>>>>


 ----
        o
\ /-------

v>>>>>>>>


 ----
         o
\ /-------

v>>>>>>>><<<<<<<< # move all the way to the left to get to the cup


 ----

\o/-------

Example of switching gravity

v
   --/ \

o
----

v>
   --/ \

 o
----

v>>
   --/ \

  o
----

v>>>
   --/ \

   o
----

v>>>^
   --/ \
   o

----

v>>>^>
   --/ \
    o

----

v>>>^>>
   --/ \
     o

----

v>>>^>>>
   --/o\


----

Task

Your task is to create a program that will take an ASCII representation of a course as input. And output a string of arrows <>^v representing the direction and gravitational pull to move a ball o across all platforms into a cup.

Standard code golf rules apply

Test Cases

Input (A situation where gravity is being switched)

         ----   --/ \
---    --
o

  ------    -----

Output

^>>v>>>>>^>>>>>v>>>>^>>>

enter image description here


Input (A situation where direction is being switched)

       ---
o   
----
    ---

     -----  

    --\ /

Output

v>>>>>>^>>>v<<<<<v>>>

enter image description here


Input (A situation where you need to traverse over the same platform twice)

 o
 ------

  ------

 ------ 

\ /------

Output

v>>>>>><<<<<<>>>>>>><<<<<<

enter image description here


Bad Cases, Program should output Falsy for these

No way for the ball to get to the next platform

o
--- ---

Ball would float off into space

---
o
   ---

A situation where the ball gets to the cup, but all platforms don't get traversed.

o
----
    ----
        \ /----
\$\endgroup\$
  • 3
    \$\begingroup\$ Rule 1 makes this quite challenging... hmmm... \$\endgroup\$ – JungHwan Min Aug 30 '17 at 3:47
  • \$\begingroup\$ Will the puzzle always be solvable? Also, I think you should include a test case that requires backtracking. \$\endgroup\$ – FryAmTheEggman Aug 30 '17 at 4:08
  • \$\begingroup\$ Yes, puzzles should always be solvable. Gaps or jumps that lose the ball or situations that make the maze unsolvable won't be done. \$\endgroup\$ – tisaconundrum Aug 30 '17 at 4:12
  • 3
    \$\begingroup\$ @JungHwanMin Rule 1 is exactly why this is a challenge and not trivial. \$\endgroup\$ – Erik the Outgolfer Aug 30 '17 at 9:37
  • 2
    \$\begingroup\$ I've never felt so far down a rabbit hole on a codegolf question \$\endgroup\$ – dj0wns Aug 31 '17 at 16:35
11
+25
\$\begingroup\$

Pyth, 431 bytes

This is my first Pyth program (actually this is my first program in any code-golf language), which means it can be probably still improved.

Jmmck\:cd\%c.Z"xÚU±Ã@DÅ W,J áDPáÒ­V`ýüw{g$ÍÀÞÇr§o.÷å8èÝÇr{øºy{~1åõ:noßÃú/.yçíäÂ'ëL¢êF¸èÆ\ka´QÒnÒ@tãÒÁµÆ¾õö»bÍH¥¦$¨%5Eyîÿ}ó§ûrh³oÄåËÄqõ XÔHû"\_KYDrGHFN@JGIn=bm:d.*NHHRb)RHDiNTR.turNG.tT;M:jH)hh@JG0DXGHN=Ti+3qG\^HI!},GTK aK,GT aY+eKNI&!g5T}\EjT)N.q;D(GHNT)INIqHhT=ZrGhtTInZhtTXHZ+eTN))).?I&nHhTgGhtTXHhtT+eTH; aK,di2i1r0.z aY+eKk#=N.(Y0(6\vkN)(7\^kN)(8\v\<N)(9\v\>N)(10\^\<N)(11\^\>N

Try it here (the last testcase needs too long, it must be tested with a local Pyth installation).

Hex dump of the code (use xxd -r <filename> to decode):

00000000: 4a6d 6d63 6b5c 3a63 645c 2563 2e5a 2278  Jmmck\:cd\%c.Z"x
00000010: da55 8eb1 8ac3 400c 447f c58d 2057 2c99  .U....@.D... W,.
00000020: 4aa0 e144 50e1 d2ad 5660 87fd 84fc 7f77  J..DP...V`.....w
00000030: 7b67 1f24 cdc0 8319 de1c c772 a76f 2ef7  {g.$.......r.o..
00000040: e538 e8dd c772 7bf8 9eba 797b 7e31 e5f5  .8...r{...y{~1..
00000050: 8e3a 6e8f 6fdf c3fa 2f2e 0c79 e717 ede4  .:n.o.../..y....
00000060: c21f 27eb 8395 189a 4c15 140b a28d ea82  ..'.....L.......
00000070: 46b8 e8c6 5c05 1b6b 1d61 b490 0251 d28c  F...\..k.a...Q..
00000080: 6ed2 4087 74e3 1ad2 c1b5 c6be f5f6 1cbb  n.@.t...........
00000090: 6286 cd48 a5a6 24a8 2535 4579 eeff 7df3  b..H..$.%5Ey..}.
000000a0: 8a8a 1613 a7fb 7204 68b3 6fc4 e51b 160c  ......r.h.o.....
000000b0: 1304 cbc4 8a71 f57f 2058 d448 fb22 5c5f  .....q.. X.H."\_
000000c0: 4b59 4472 4748 464e 404a 4749 6e3d 626d  KYDrGHFN@JGIn=bm
000000d0: 3a64 2e2a 4e48 4852 6229 5248 4469 4e54  :d.*NHHRb)RHDiNT
000000e0: 522e 7475 724e 472e 7454 3b4d 3a6a 4829  R.turNG.tT;M:jH)
000000f0: 6868 404a 4730 4458 4748 4e3d 5469 2b33  hh@JG0DXGHN=Ti+3
00000100: 7147 5c5e 4849 217d 2c47 544b 2061 4b2c  qG\^HI!},GTK aK,
00000110: 4754 2061 592b 654b 4e49 2621 6735 547d  GT aY+eKNI&!g5T}
00000120: 5c45 6a54 294e 2e71 3b44 2847 484e 5429  \EjT)N.q;D(GHNT)
00000130: 494e 4971 4868 543d 5a72 4768 7454 496e  INIqHhT=ZrGhtTIn
00000140: 5a68 7454 5848 5a2b 6554 4e29 2929 2e3f  ZhtTXHZ+eTN))).?
00000150: 4926 6e48 6854 6747 6874 5458 4868 7454  I&nHhTgGhtTXHhtT
00000160: 2b65 5448 3b20 614b 2c64 6932 6931 7230  +eTH; aK,di2i1r0
00000170: 2e7a 2061 592b 654b 6b23 3d4e 2e28 5930  .z aY+eKk#=N.(Y0
00000180: 2836 5c76 6b4e 2928 375c 5e6b 4e29 2838  (6\vkN)(7\^kN)(8
00000190: 5c76 5c3c 4e29 2839 5c76 5c3e 4e29 2831  \v\<N)(9\v\>N)(1
000001a0: 305c 5e5c 3c4e 2928 3131 5c5e 5c3e 4e    0\^\<N)(11\^\>N

Explanation

The main idea for this program was to use regular expressions to modify the input. To save space all these regular expressions are contained in a compressed string. The first step in the program is to decompress the string and to split it int single regular expression and the corresponding replacement strings.

            .Z"..."     Decompress the string
           c       \_   Split the result into pieces (separator is "_")
  m    cd\%             Split all pieces (separator is "%")
 m ck\:                 Split all sub-pieces (separator is ":")
J                       Assign the result to variable J

The contents of variable J are then:

[[['\\\\ /', '=M='], ['/ \\\\', '=W=']],
 [[' (?=[V6M=-])', 'V'], ['o(?=[V6M=-])', '6']],
 [['(?<=[A9W=-]) ', 'A'], ['(?<=[A9W=-])o', '9'], ['(?<=[X0W=-])V', 'X'], ['(?<=[X0W=-])6', '0']],
 [['6V', 'V6'], ['0X', 'X0'], ['6-', '6='], ['0-', '0='], ['6M', 'VE'], ['0M', 'XE']],
 [['A9', '9A'], ['X0', '0X'], ['-9', '=9'], ['-0', '=0'], ['W9', 'EA'], ['W0', 'EX']],
 [['[MW-]']],
 [['[60]']],
 [['[90]']],
 [['V6', '6V'], ['V0', '6X'], ['X6', '0V'], ['X0', '0X']],
 [['6V', 'V6'], ['0V', 'X6'], ['6X', 'V0'], ['0X', 'X0']],
 [['A9', '9A'], ['A0', '9X'], ['X9', '0A'], ['X0', '0X']],
 [['9A', 'A9'], ['0A', 'X9'], ['9X', 'A0'], ['0X', 'X0']]]

KY   Set the variable K to an empty list

The function r applies regex substitutions from the list stored in J at the index G to all strings in the list H. It returns as soon as any of the strings was changed.

DrGH                         Define the function r(G,H)
    FN@JG              )     Loop for all entries in J[G]
             m:d.*NH         Regex substitution, replace N[0] with N[1] in all strings in list H
           =b                Store the result in variable b
         In         HRb      If b != H return b
                        RH   Return H

The function i is similar to function r with 2 differences. It applies the substitutions on a transposed list (vertical instead on horizontal). It also performs the substitutions repeatedly as long as anything is changed.

DiNT          ;   Define the function i(N,T)
           .tT    Transpose the list T
       urNG       Apply r(N,...) repeatedly as long as something changes
    R.t           Transpose the result back and return it

The function g checks if the regex from the list stored in J at the index G can by found in any string in the list H.

M             Define the function g(G,H)
     hh@JG    Get the single regex stored in J[G]
  jH)         Join all strings in H
 :        0   Check if the regex is found anywhere in the joined string

The rest of the code contains the actual program logic. It performs a breadth-first search for the possible movements until a solution is found. The position in the search tree is uniquely defined by the direction of the gravity and a modified copy of the program input. To avoid the processing of the same position again and again, processed positions are stored in the global list K. Positions which still have to be processed are stored together with the corresponding part of the solution in the list Y.

The modification of the input and initialization of K and Y is performed by the following code:

           .z          Get all input as a line list
     i2i1r0            Apply the regular expressions stored in J[0] horizontally, and the the ones from J[1] and J[2] vertically
   ,d                  Create a list with " " (represents "no gravity set") and the modifed input
 aK                    Append the result to the list K
                 eK    Retrieve the appended list again
                +  k   Append "" to the list (represents the empty starting solution)
              aY       Append the result to the list Y

The input modification does something like the following. The input:

         ----   --/ \
---    --
o

  ------    -----

is transformed to:

VVVVVVVVV----VVV--=W=
---VVVV--AAAXVVVXAAAA
9AXVVVVXAAAAXVVVXAAAA
AAXVVVVXAAAAXVVVXAAAA
AA------AAAA-----AAAA

The values have the following meaning:

  • - Platform which must be still visited
  • = Platform which doesn't need to be visited anymore
  • M Cup which can be entered with gravity set to "down"
  • W Cup which can be entered with gravity set to "up"
  • V Safe to move to this place with gravity set to "down"
  • A Safe to move to this place with gravity set to "up"
  • X Safe to move to this place regardless of the gravity setting
  • 6 Ball on a place which would be marked as V
  • 9 Ball on a place which would be marked as A
  • 0 Ball on a place which would be marked as X

The logic is using regular expressions to perform the movements. In the example above, if the gravity would be set to "up", we can replace "9A" with "A9" with an regex to move the ball to the right. This means by trying to apply the regex we can find all possible movements.


The function X performs vertical ball movements based on the current gravity setting, stores the result in global lists K and Y, and checks if a solution was found.

DXGHN                                             ;   Define the function X(G,H,N)
        +3qG\^                                        Select the correct set of regular expressions based on the current gravity setting G (3 for "v" and 4 for "^")
     =Ti      H                                       Apply i(...,H) and store the result in T 
               I!},GTK                                If [G,T] not in K
                       aK,GT                          Store [G,T] in K 
                             aY+eKN                   Store [G,T,N] in Y 
                                   I&!g5T}\EjT)       If J[5] not found in T and T contains "E" (all platforms visited and ball in cup)
                                               N.q    Print N and exit

The function ( implements checks for the 4 directional/gravity buttons. The gravity buttons can be pressed only if the current gravity would change and if the ball is in a safe place to change the gravity. The directional buttons can be pressed only if it is safe to move to the corresponding place.

D(GHNT)                                                    ;   Define the function ( (G,H,N,T)
       IN                           )                          If N is not empty (contains either "<" or ">" representing directional buttons)
         IqHhT                     )                           If H (gravity setting for which this test is performed) is equal T[0] (the current gravity)
              =ZrGhtT                                          Apply r(G,T[1]) and store the result in Z (G is the appropriate regex index for the combination of gravity and directional button, T[1] is the current modified input) 
                     InZhtT       )                            If Z != T[1] (the regex operation changed something, meaning we found a valid move)
                           XHZ+eTN                             Call X(H,Z,[T[2],N]) 
                                     .?                        Else (gravity button pressed)
                                       I                       If ...
                                         nHhT                  H (new gravity setting) is not equal T[0] (current gravity setting) 
                                        &                      ... and ...
                                             gGhtT             J[G] found in T[1] (ball is in an appropriate place to switch gravity) 
                                                  XHhtT+eTH    Call X(H,T[1],[T[2],H])

Finally the main loop. The first element of Y is removed repeatedly, and checks for all possible moves are performed.

#                                                        Loop until error (Y empty)
 =N.(Y0                                                  Pop first element of Y and store it in the variable N
       (6\vkN)                                           Call ( (6,"v","",N)
              (7\^kN)                                    Call ( (7,"^","",N)
                     (8\v\<N)                            Call ( (8,"v","<",N)
                             (9\v\>N)                    Call ( (9,"v",">",N)
                                     (10\^\<N)           Call ( (10,"^","<",N)
                                              (11\^\>N   Call ( (11,"^",">",N)
\$\endgroup\$
  • \$\begingroup\$ Am I right in thinking that you assume that every input is solvable? Because the question still says unsolvable inputs should be detected, the comments, however, suggests that every input will be solvable. I am uncertain which is the case, though I think your code does not detect unsolvability. \$\endgroup\$ – Jonathan Frech Sep 8 '17 at 17:48
  • \$\begingroup\$ @JonathanFrech If the input is unsolvable there will be no output. When all possibilities were checked, the Y list will be empty, the pop will throw an error and the # loop will end. \$\endgroup\$ – Sleafar Sep 8 '17 at 18:22
  • 1
    \$\begingroup\$ When you remove the cup from the input (`/ \`), the puzzle becomes unsolvable (as you cannot reach the cup) yet your program still generates an output. \$\endgroup\$ – Jonathan Frech Sep 8 '17 at 18:31
  • \$\begingroup\$ I did not mean what your program does, I ment that this unsolvable puzzle input generates an output. \$\endgroup\$ – Jonathan Frech Sep 8 '17 at 19:07
  • \$\begingroup\$ @JonathanFrech You are right. I'm just trying to fix it, but I have encoding problems with the compressed string. \$\endgroup\$ – Sleafar Sep 8 '17 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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