17
\$\begingroup\$

Background

I feel that for a site named code-golf we have a shockingly little amount of golf being played. Let's fix that.

Challenge

Determine whether the hole of a minigolf course can be reached after exactly a certain number of movements and whether it can be reached at all.

How to play

Inputs are an integer "power level" and an ASCII art minigolf course. The ball starts on the X (capital) and the hole is an O (capital). The walls of the course are made of the characters + | - \ and /. The characters + | and - rotate the direction of the ball 180 degrees and the characters \ and / rotate the direction 90 degrees as you would expect. When a ball hits the wall it enters the wall for that turn and then leaves the next turn.

Launch the ball in each of the four cardinal directions from the starting X.

  • If the ball enters the hole after exactly the power level moves, then output truthy.
  • If the ball could make it to the hole given a different power level, then output mediumy.
  • If the ball cannot enter the hole regardless of the power level, output falsy.

Rules

  • This is so shortest answer in bytes wins.
  • Assume only valid input will be given.
  • All input strings will be rectangular. (All rows will be the same length)
  • Assume that there is no way to escape the course and leave the edge of the string.
  • No solution will require the ball to be in the same place facing the same direction twice.
  • Standard loopholes disallowed.
  • Only a string or a list of strings is acceptable for the course input.
  • Output can be any three distinct values.
  • The ball will never hit the characters | or - "end-on."

Example

11
   -----+ 
  /   X | 
 | +----+ 
 | |      
 |O|      
 +-+      

This is true. If the ball starts heading east it will be on the wall after two movements.

   -----+ 
  /   X o<- ball right here. movements:2
 | +----+ 
 | |      
 |O|      
 +-+      

It will then change directions until it hits the corner

   -----+ 
  o   X | movements:8
 | +----+ 
 | |      
 |O|      
 +-+      

Now it is heading south and will end in the hole after 11 moves. Note that 13 would also be true as the ball could bounce off of the bottom wall and into the hole. Other valid power levels for this course are 7 and 9.

Test Cases

All answers validated using this java code: https://github.com/Dragon-Hatcher/CodeGolfMiniGolf/tree/master/MinigolfCodeGolf/src

power
course
output

11
   -----+ 
  /   X | 
 | +----+ 
 | |      
 |O|      
 +-+      
          
truthy

10
    +---+ 
    | X | 
    +---+ 
 +-+      
 |O|      
 +-+        
          
falsy

25
                   
      ---------    
     /     X   \   
    +++-------+ |  
    | |       | |  
    |O|       | |  
    | \-------/ |  
     \         /   
      ---------    
                   
truthy

2
     
 +-+ 
 |X| 
 | | 
 | | 
 |O| 
 +-+      
                
mediumy

34
                
      +------+  
      |/    \|  
      | +--+ |  
      |X|  | |  
  +---+ +--+ |  
  |    O    /|  
  +---+ +----+  
      +-+       
                
true
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Hi and welcome to Code golf! One point: Only a string is acceptable for the course input limiting the input this way, assuming you mean a string with carriage returns as opposed to a list/array of strings, is discouraged. \$\endgroup\$
    – Noodle9
    Jul 28, 2020 at 21:00
  • \$\begingroup\$ Okay good to know I've changed the rules \$\endgroup\$
    – user197974
    Jul 28, 2020 at 21:07
  • 1
    \$\begingroup\$ Great! One other point: Get your input from the standard input usually answers can be either full programs or functions (which may get their input from parameters). \$\endgroup\$
    – Noodle9
    Jul 28, 2020 at 22:18
  • \$\begingroup\$ Thanks, I fixed it. \$\endgroup\$
    – user197974
    Jul 28, 2020 at 22:21
  • 6
    \$\begingroup\$ It would be better to just not mention any rules about how to get input, and let the default input rules apply. \$\endgroup\$ Jul 28, 2020 at 22:24

6 Answers 6

5
\$\begingroup\$

APL (Dyalog Unicode), 146 115 bytes

{(∨/+⍺⊃⊢)∨⌿↑{'O'=1↓⊃¨⊢∘(((⊢,⍉∘⊖∘⌽¨)1⌽¨⊂,⊂∘⍉)⊃⍨1⌈¯2+'X O\/'⍳⊃)\(4×≢,⍵)⍴⊂⍵}¨({¯1+⊃⊃⍸'X'=⍵}⌽⍉)⍣2¨(⊢,⌽∘⊖¨)(⊂,⊂∘⍉)⍵,⍳≢⍵}

-31 bytes (!) thanks to @Bubbler (combining transformations; simplifying iteration end condition; smaller details)

Try it online!

Outputs 2 for truthy, 1 for mediumy, and 0 for falsy.

Similarly to my solution to Solve the Halting Problem for Modilar SNISP, this moves the grid around the ball location, so the ball is always in the top-left, moving right. This might not be the best strategy (as opposed to storing a pointer position and direction) in this case because the ball doesn't always start from the top-left moving right, so I spend many bytes rotating and aligning the grid.

Details

Append 1,2,3,4,...,n to the input grid. This prevents symmetric grids from comparing equal after some sequence of moves

⍵,⍳≢⍵

We must be careful here and elsewhere in the code that we do not affect the angle of / and \. Using a simple reflection to reverse direction should change / to \, but the reflection of the character '/' is '/'.

Conveniently, APL matrix reflection operators are visually sensible:

  • reflects across a vertical line: swaps / and \
  • reflects across a horizontal line: swaps / and \
  • (transpose) reflects across the main diagonal: no change

Thus we must use an even total number of and in all transforms.

Obtain all 4 starting directions/rotations:

(⊢,⌽∘⊖¨)(⊂,⊂∘⍉)

Shift each grid so that 'X' is in the top left (Shifts 'X' to the left edge twice, transposing the matrix in between)

{(¯1+⊃⊃⍸'X'=⍵)⌽⍉⍵}⍣2¨

For each starting grid, beginning with the starting grid, repeat 4×#coordinates (= max # of states) times...

\(4×≢,⍵)⍴⊂⍵

...move by one step:

(((⊢,⍉∘⊖∘⌽¨)1⌽¨⊂,⊂∘⍉)⊃⍨1⌈¯2+'X O\/'⍳⊃)
  ⍝ Get the ID of the entry: `X`, ` `, or `O`:1, `\`:2, `/`:3, `|`,`+`, or `-`:4
  ⍝ We can consider |, +, and - as the same because we are always travelling
  ⍝ horizontally (albeit on a rotated grid), and these all do the same action 
  1⌈¯2+'X O\/'⍳⊃
  ⍝ Get the corresponding grid position after the move
  ((⊢,⍉∘⊖∘⌽¨)1⌽¨⊂,⊂∘⍉)⊃⍨

1 if there exists a move history whose final move's top-left element is O, and add another 1 if there exists a move history where the -th move has top-left element equal to O.

(∨/+⍺⊃⊢)∨⌿↑{'O'=1↓⊃¨
\$\endgroup\$
5
  • \$\begingroup\$ Actually I think this works. This is why I included the phrase "No solution will require the ball to be in the same place facing the same direction twice." This means that you don't have to consider looping around the whole course. \$\endgroup\$
    – user197974
    Jul 29, 2020 at 17:33
  • 1
    \$\begingroup\$ @JonathanAllan Fixed both problems. "until 4 Os" suffices since the ball cannot pass over the hole more than 4 times. Also, I was padding with repeats of the original path if it was shorted, which caused excess 1s, so padding with 0s via works properly \$\endgroup\$ Jul 29, 2020 at 17:34
  • \$\begingroup\$ @user197974 I edited a few seconds before you posted your comment. Since there are 4 directions, the ball can loop around the whole course (see my suggested test case on the original post). \$\endgroup\$ Jul 29, 2020 at 17:36
  • \$\begingroup\$ @fireflame241 good catch let me whip up a test case. \$\endgroup\$
    – user197974
    Jul 29, 2020 at 17:38
  • \$\begingroup\$ Whenever I think of the grid-altering approach, I get lost with handling obstacles properly. Nice job. Meanwhile, I could bring it down to 115 bytes. \$\endgroup\$
    – Bubbler
    Jul 31, 2020 at 0:51
4
\$\begingroup\$

JavaScript (Node.js),  170 ... 147  145 bytes

Expects (n)(a), where n is an integer and a is an array of strings. Returns 3 for truthy, 0 for falsy or 1 for mediumy.

n=>a=>(g=(d,y=a.findIndex(r=>~(x=r.search`X`),j=n))=>+(a+a+1)[~j]?D&&g(--D):!(k=Buffer(a[y+=(d-2)%2])[x+=~-d%2]*5%26%5)*-~!--j|g(d^4-k&3,y))(D=3)

Try it online!

How?

We use the following compass for the directions:

  1
0 + 2
  3

Which means that we have \$dx=(d-1)\bmod 2\$ and \$dy=(d-2)\bmod 2\$, assuming that the sign of the modulo is the sign of the dividend.

With this setup, we want to update \$d\$ to:

  • \$(d\operatorname{XOR}2)\$ for a 180° turn (bouncing on either -, + or |)
  • \$(d\operatorname{XOR}1)\$ for a 90° turn when bouncing on a \
  • \$(d\operatorname{XOR}3)\$ for a 90° turn when bouncing on a /

We use the following formula to convert any board character of ASCII code \$n\$ to \$k\in[0..4]\$:

$$k=((n\times5)\bmod 26)\bmod 5$$

The great thing about this formula is that the value that \$d\$ must be XOR'ed with when going through a character is immediately given by \$4-k\$ (except O which is turned into \$4\$).

 char. | code | *5  | %26 | %5 | 4-k
-------+------+-----+-----+----+-----
  ' '  |   32 | 160 |   4 |  4 |  0
  'X'  |   88 | 440 |  24 |  4 |  0
  'O'  |   79 | 395 |   5 |  0 |  4
  '/'  |   47 | 235 |   1 |  1 |  3
  '\'  |   92 | 460 |  18 |  3 |  1
  '|'  |  124 | 620 |  22 |  2 |  2
  '-'  |   45 | 225 |  17 |  2 |  2
  '+'  |   43 | 215 |   7 |  2 |  2

Commented

n => a => (                   // n = number of moves; a[] = array of strings
  g = (                       // g is a recursive function using:
    d,                        //   d = current direction
    y = a.findIndex(r =>      //   y = index of the row r[] in a[]
      ~(x = r.search`X`),     //       which contains an 'X' at position x
      j = n                   //   j = move counter, initialized to n
    )                         //
  ) =>                        //
    +(a + a + 1)[~j] ?        //   if j is negative and we have visited at
                              //   least more than twice the total number of
                              //   cells in a[]:
      D &&                    //     if D is not equal to 0:
        g(--D)                //       do a recursive call with D - 1
    :                         //   else:
      !(k =                   //     compute k:
        Buffer(               //       get the ASCII code at (x + dx, y + dy)
          a[y += (d - 2) % 2] //       add dy to y
        )[x += ~-d % 2]       //       add dx to x
        * 5 % 26 % 5          //       apply the formula described above
      ) *                     //     k = 0 means that we've reached the hole,
      -~!--j                  //     in which case we yield 1 if j != 0
      |                       //     or 2 if j = 0 (j is first decremented)
      g(d ^ 4 - k & 3, y)     //     update d and do a recursive call
)(D = 3)                      // initial call to g with d = D = 3
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Great explanation as always \$\endgroup\$
    – ElPedro
    Jul 30, 2020 at 13:36
  • \$\begingroup\$ Nice! How did you construct/find the equation k = ((n * 5) mod 26) mod 5? \$\endgroup\$
    – Quelklef
    Aug 14, 2020 at 23:58
  • 2
    \$\begingroup\$ @Quelklef I wrote a small script to find (p,m0,m1) tuples such that n*p%m0%m1 is a surjective function from the set of ASCII codes to the set of bouncing behaviors. One of the tuples caught my eye because it was not only giving correct unique IDs but could also almost directly provide the correct XOR values. It was a fortunate, unexpected result. \$\endgroup\$
    – Arnauld
    Aug 15, 2020 at 6:56
2
\$\begingroup\$

Python 3, 384 378 bytes

def l(d,r,m,i,c,p):
 m+=[[d]+p];p[1]+=(d-1)*(~d%2);p[0]-=(d-2)*(d&1);s=r"/\-|+OX ".index(c[p[1]][p[0]])
 if s<2:d+=(s^d&1)*2+1;d%=4
 if 1<s<5:d+=2;d%=4
 if s==5:r+=[i]
 if [d]+p in m:return r
 return l(d,r,m,i+1,c,p)
def f(c,v):
 i=c.index("X");i2=c.index("\n");p=[i%(i2+1),i//i2];c=c.split("\n");r=[];
 for d in range(4):r+=l(d,[],[],1,c,p)
 print([[1,0],[2,2]][v in r][r==[]])

Try it online!

Edit: Saved 6 Bytes thanks to Ad Hoc Garf Hunter's suggestion.

Takes input c = string, v = power level Outputs 0 for falsy, 1 for mediumly and 2 for truthy

This is my first codegolf submission, so there's most likely a better way but I tried best:

Explanation:

Note: Directions are encoded as an integer, where 0 = North, 1 = East, 2 = South, 3 = West

def l(d,r,m,i,c,p):                       # d:=direction, r:=result, m:=moves
                                          # i:=steps, c:=course, p:=position
    m += [[d]+p]                          # add direction and position as a move
    p[1] += (d-1)*(~d%2)                  # if direction is even move up or down
    p[0] -= (d-2)*(d&1)                   # if direction is odd move to the left or to the right
    s = r"/\-|+OX ".index(c[p[1]][p[0]])  # get next token as an int
    if s<2:                               # case "/" or "\"
        d += (s^d&1)*2+1                  # rotate either 270 or 90 degrees, depending on 
                                          # whether the direction is odd or even
                                          # flip the condition depending if "/" or "\"
        d%=4                              # correct direction in case of overflow
    if 1 < s < 5:                         # edge hit
        d += 2                            # rotate 180 degrees
        d %= 4                            # if direction overflows
    if s == 4:                            # case "O"
        r+=[i]                            # add number of steps to result list
    if [d]+p in m:                        # if move was already made
        return r                          # return result
    return l(d,r,m,i+1,c,p)               # call next step

def f(c,v):                                             # c is the string, v the power level
    i = c.index("X")                                    # getting the index of the "X"
    i2 = c.index("\n")                                  # getting the width of the course
    p = [i % (i2+1), i // i2]  # transforming it to a [x,y] position
    c = c.split("\n")                                   # splitting the string into a list
                                                        # so it can be accessed via [y][x]
    r = []
    for d in range(4):                                  # the 4 starting directions
        r += l(d,[],[],1,c,p)                           # starting the loop with the init values
    print(2 if v in r else 0 if r == [] else 1)         # if the power level is in the list
                                                        # output 2 
                                                        # if the list is empty (hole could not be reached)
                                                        # output 0
                                                        # else output 1

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to the site. I think you can save bytes by using boolean indexing instead of if else. e.g. a if b else c is shorter as [c,a][b]. \$\endgroup\$
    – Wheat Wizard
    Jul 30, 2020 at 16:28
2
\$\begingroup\$

Charcoal, 94 bytes

WS⊞υι≔⪫υ¶ηPη…η⌕ηX≔⟦⟧υF⁴«≔⟦⟧ζW¬№ζ⟦ⅈⅉι⟧«⊞ζ⟦ⅈⅉι⟧M✳⊗ι≡KKO⊞υLζ\≦⁻³ι/≔﹪⁻⁵ι⁴ι¿№+|-KK≔﹪⁺²ι⁴ι»»⎚FυP=№υN

Try it online! Link is to verbose version of code. Takes input as the course and power level separated by a blank line, and outputs - for correct power level, = for incorrect power level, and nothing for an impossible course. Explanation:

WS⊞υι

Input the course until the blank line is reached.

≔⪫υ¶ηPη

Join the lines back together and print the course without moving the cursor.

…η⌕ηX

Print the course up to the X, which leaves the cursor at the start.

≔⟦⟧υ

Start keeping track of the working power levels.

F⁴«

Loop over all orthogonal directions.

≔⟦⟧ζ

Start keeping track of visited positions. (Because I really need a repeat...until loop here, this is slightly golfier than just comparing the current position with the initial position. I also need the number of steps anyway.)

W¬№ζ⟦ⅈⅉι⟧«

Repeat until we're at a previous position and direction. (This can only happen when we get back to our starting point and direction, since the other saved positions can only be reached from there.)

⊞ζ⟦ⅈⅉι⟧

Save the current position and direction.

M✳⊗ι

Move in the current direction. (In Charcoal, direction 0 is to the right, increasing by 45 degrees anticlockwise each time, so that e.g. 6 is down. Since we're not interested in diagonals, I work in multiples of right angles and double them for the Move command.)

≡KK

Switch on the character under the cursor.

O⊞υLζ

If it's an O then save the power level (i.e. number of steps) needed to get here.

\≦⁻³ι

If it's a \ then XOR the direction with 3, which here is simply equivalent to subtracting it from 3, as Charcoal has no XOR operator.

/≔﹪⁻⁵ι⁴ι

If it's a / then XOR the direction with 1, which is equivalent to subtracting from 5 modulo 4.

¿№+|-KK≔﹪⁺²ι⁴ι

Otherwise if it's any other wall then XOR the direction with 2, which is equivalent to adding 2 modulo 4.

»»⎚

Clear the canvas once all directions have been considered.

FυP=

If it was possible to get the ball in the hole then output a =.

№υN

But if the input power level was correct then change that to a -.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 240 bytes

(g,P,w=g.indexOf('\n')+1,f=(d,i=g.indexOf('X'),p=P,a=[],c=g.replace(/-|\|/g,'+')[i],s=Math.sign(d),q=w+1-d/s)=>a.includes(k=''+[i,d])?0:!p&&c=='O'?3:c=='O'|f((d=c=='/'?-s*q:c=='\\'?s*q:c=='+'?-d:d),i+d,p-1,[...a,k]))=>f(1)|f(-1)|f(w)|f(-w);

Returns 3 for truthy, 1 for mediumy, and 0 for falsey.

Try it online!

Nice question!

I'm not super happy with my result, but I did learn a cool trick in the meantime: you can save some bytes by replacing

(a1,a2)=>{x=f(a1,a2);return g(x)}

with

(a1,a2,x=f(a1,a2))=>g(x)
\$\endgroup\$
2
\$\begingroup\$

Scala, 298 bytes

l=>s=>{def h(d:Int,c:(Int,Int),p:Int,r:Set[Any]):Int={val x=(c._1+(d-2)%2,c._2+(d-1)%2)
val a=s(x._2)(x._1)
if(a==79)if(p==1)1 else math.max(0,h(d,x,p-1,r+(c->d)))else if(!r(x->d))h(d^(4-5*a%26%5),x,p-1,r+(c->d))else-1}
0 to 3 map(h(_,s.map(_ indexOf'X').zipWithIndex.find(_._1>=0)get,l,Set()))max}

Try it online!

I used the brilliant formula Arnauld used in their answer, but it's still a pretty large amount of code.

Outputs -1 for false, 0 for mediumy, and 1 for truthy.

Prettier version:

//l is the power level, s is the golf course, split on \n
l => s => {
  //h is a recursive helper function
  //dir is the direction, c is the (x,y) coordinates of the ball,
  //p is the power level, and seen is a set holding a tuple of all the coordinates and directions
  //(In reality, seen is a Set[((Int,Int),Int)], but I was lazy)
  def h(dir: Int, c: (Int, Int), p: Int, seen: Set[Any]): Int = {
    //The new position
    val x = (c._1 + (dir - 2) % 2, c._2 + (dir - 1) % 2)
    //The character at the new position
    val a = s(x._2)(x._1)
    if (a == 79) {  //Found the hole!
      if (p == 1) 1 //Power level is right
      else math.max(0, h(dir, x, p - 1, seen + (c->d))) //Power level is right
    } else if (seen(x, d)) -1 //We're just looping around, it's never going to work
    else h(dir ^ (4 - 5 * a % 26 % 5), x, p - 1, seen + (c -> d)) //Go on to the next move
  }
  //Try out every direction
  (0 to 3).map(h(d =>
    d,
    s.map(_.indexOf('X')).zipWithIndex.find(_._1 >= 0).get, //The start coordinate
    l,
    Set()
  )).max
}
\$\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.