24
\$\begingroup\$

The goal of this challenge is to write a program or function that returns the least amount of strikes needed to complete a given course.

Input

  • The layout of the course can be passed in any suitable way and format you prefer. (read from the console, passed as an input parameter, read from a file or any other, multiline-string, string array, two-dimensional character/byte array).
  • The start position of the ball and the hole can be passed as input too, it doesn't have to be parsed from the input. In the test-cases they are included in the course to make sure there is no confusion about the actual position.
  • You can remap the input characters to something else, as long as they are still recognisable as distinct characters (e.g. printable ASCII characters).

Output

  • The program must return the lowest possible score (least amount of strikes needed to reach the hole) for any course passed as input in a sensible format (string, integer, float or a haiku describing the result)
  • If the course is impossible to beat, return -1 (or any other falsy value of your choice that wouldn't be returned for a beatable course).

Example:

In this example positions are notated 0-based, X/Y, left-to-right, top-down - but you can use any format you like since the result is completely format-independent anyways.

Input:

########### # ....# # ...# # ~ . # # ~~~ . # # ~~~~ # # ~~~~ # # ~~~~ o # # ~~~~ # #@~~~~ # ########### Ball (Start-Position): 1/9 Hole (End-Position): 8/7 

Output:

8 

Example course

Rules and fields

The course can consist of the following fields:

  • '@' Ball - The start of the course
  • 'o' Hole - The goal of the course
  • '#' Wall - Ball will stop when it hits a wall
  • '~' Water - Must be avoided
  • '.' Sand - Ball will stop on sand immediately
  • ' ' Ice - Ball will continue to slide until it hits something

The basic rules and restrictions of the game:

  • The ball can't move diagonally, only left, right, up and down.
  • The ball will not stop in front of water, only in front of walls, on sand and in the hole.
    • Shots into the water are invalid/impossible
    • The ball will stay in the hole, not skip over it like it would on ice
  • The course is always rectangular.
  • The course is always bordered by water or walls (no boundary checks required).
  • There is always exactly one ball and one hole.
  • Not all courses are possible to beat.
  • There might be multiple paths that result in the same (lowest) score.

Loopholes and Winning Condition

  • Standard loopholes are forbidden
  • Programs must terminate
  • You can't make up additional rules (hitting the ball so hard it skips over water, rebounds off a wall, jumps over sand fields, curves around corners, etc.)
  • This is , so the solution with the least amount of characters wins.
  • Solutions must be able to handle all provided test-cases, if this is impossible due to restrictions of the used language please specify that in your answer.

Test cases

Course #1 (2 strikes)

#### # @# #o~# #### 

Course #2 (not possible)

##### #@ # # o # # # ##### 

Course #3 (3 strikes)

~~~ ~@~ ~.~ ~ ~ ~ ~ ~ ~ ~ ~ ~.~ ~o~ ~~~ 

Course #4 (2 strikes)

######### #~~~~~~~# #~~~@~~~# ## . ## #~ ~ ~ ~# #~. o .~# #~~~ ~~~# #~~~~~~~# ######### 

Course #5 (not possible)

~~~~~~~ ~... ~ ~.@.~.~ ~... ~ ~ ~ ~.~ ~ . .o~ ~~~~~~~ 

More Test cases:

https://pastebin.com/Azdyym00

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Related: One, Two. \$\endgroup\$ Commented Mar 29, 2018 at 12:51
  • \$\begingroup\$ If we use a two-dimensional byte array as input, are we allowed to use a custom mapping for the symbols? \$\endgroup\$ Commented Mar 29, 2018 at 14:52
  • \$\begingroup\$ @Arnauld Not sure what the usual consensus regarding that is here, but I'd say it's ok as long as the input is still be recognisable. I've updated the Input section. \$\endgroup\$ Commented Mar 31, 2018 at 6:22
  • \$\begingroup\$ If input the destination directly, can we require the place of destination be 'sand' symbol? \$\endgroup\$ Commented Mar 31, 2018 at 13:10
  • \$\begingroup\$ @l4m2 Sure, that way it would stay consistent with all the other rules. \$\endgroup\$ Commented Mar 31, 2018 at 21:06

3 Answers 3

6
\$\begingroup\$

JavaScript (ES6), 174 bytes

Takes input in curling currying syntax ([x, y])(a), where x and y are the 0-indexed coordinates of the starting position and a[ ] is a matrix of integers, with 0 = ice, 1 = wall, 2 = sand, 3 = hole and 4 = water

Returns 0 if there's no solution.

p=>a=>(r=F=([x,y],n,R=a[y],c=R[x])=>R[c&(R[x]=4)|n>=r||[-1,0,1,2].map(d=>(g=_=>(k=a[v=Y,Y+=d%2][h=X,X+=~-d%2])||g())(X=x,Y=y)>3?0:k>2?r=-~n:F(k>1?[X,Y]:[h,v],-~n)),x]=c)(p)|r 

Try it online!

Commented

p => a => ( // given the starting position p[] and the matrix a[] r = // r = best result, initialized to a non-numeric value F = ( // F = recursive function taking: [x, y], // (x, y) = current position n, // n = number of shots, initially undefined R = a[y], // R = current row in the matrix c = R[x] // c = value of the current cell ) => // R[ // this will update R[x] once the inner code is executed c & (R[x] = 4) | // set the current cell to 4 (water); abort if it was n >= r || // already set to 4 or n is greater than or equal to r [-1, 0, 1, 2].map(d => // otherwise, for each direction d: (g = _ => ( // g = recursive function performing the shot by k = a[ // saving a backup (h, v) of (X, Y) v = Y, Y += d % 2][ // and updating (X, Y) until we reach a cell h = X, X += ~-d % 2]) // whose value k is not 0 (ice) || g() // )(X = x, Y = y) // initial call to g() with (X, Y) = (x, y) > 3 ? // if k = 4 (water -> fail): 0 // abort immediately : // else: k > 2 ? // if k = 3 (hole -> success): r = -~n // set r to n + 1 : // else: F( // do a recursive call to F(): k > 1 ? // if k = 2 (sand): [X, Y] // start the next shots from the last cell : // else (wall): [h, v], // start from the last ice cell -~n // increment the number of shots ) // end of recursive call ), x // end of map(); x = actual index used to access R[] ] = c // restore the value of the current cell to c )(p) | r // initial call to F() at the starting position; return r 
\$\endgroup\$
0
5
\$\begingroup\$

Python 3, 273 bytes

def p(g,c,d,k=0): 	while 1>k:c+=d;k=g.get(c,9) 	return-(k==2)or c-d*(k==3) def f(g): 	c={q for q in g if g.get(q,9)>4};I=0;s=[c] 	while all(g.get(q,9)-4for q in c): 		c={k for k in{p(g,k,1j**q)for k in c for q in range(4)}if-~k} 		if c in s:return-1 		s+=[c];I+=1 	return I 

Try it online!

-41 bytes thanks to ovs
-1 byte thanks to Jonathan Frech

\$\endgroup\$
2
  • \$\begingroup\$ Could if k+1 not be if-~k? \$\endgroup\$ Commented Apr 19, 2018 at 10:52
  • \$\begingroup\$ @JonathanFrech yes, thanks \$\endgroup\$ Commented Apr 20, 2018 at 2:11
2
\$\begingroup\$

C#, 461 418 bytes

This is just a non-competitive reference implementation to (hopefully) revive this challenge:

Golfed by Kevin Cruijssen

int P(string[]C){int w=C[0].Length,i=0,l=c.Length;var c=string.Join("",C);var h=new int[l];for(var n=new List<int>();i<l;n.Add(i++))h[i]=c[i]!='@'?int.MaxValue:0;for(i=1;;i++){var t=n;n=new List<int>();foreach(int x in t){foreach(int d in new[]{-1,1,-w,w}){for(int j=x+d;c[j]==' ';j+=d);if(c[j]=='#'&h[j-d]>s){h[j-d]=s;n.Add(j-d);}if(c[j]=='.'&h[j]>s){h[j]=s;n.Add(j);}if(c[j]=='o')return s;}}if(n.Count<1)return -1;}} 

Ungolfed

int IceGolf(string[] course) { // Width of the course int w = course[0].Length; // Course as single string var c = string.Join("", course); // Array of hits per field var hits = new int[c.Length]; // Fields to continue from var nextRound = new List<int>(); // Initialize hits for (int i = 0; i < hits.Length; i++) { if (c[i] != '@') // All fields start with a high value hits[i] = Int32.MaxValue; else { // Puck field starts with 0 hits[i] = 0; nextRound.Add(i); } } for (int s = 1; ; s++) { // clear the fields that will be used in the next iteration var thisRound = nextRound; nextRound = new List<int>(); foreach (int i in thisRound) { // test all 4 directions foreach (int d in new[] { -1, 1, -w, w }) { int j = i+d; // ICE - slide along while (c[j] == ' ') j += d; // WALL - stop on previous field if (c[j] == '#' && hits[j-d] > s) { hits[j-d] = s; nextRound.Add(j-d); } // SAND - stop if (c[j] == '.' && hits[j] > s) { hits[j] = s; nextRound.Add(j); } // HOLE return strikes if (c[j] == 'o') return s; } } // No possible path found if (nextRound.Count == 0) return -1; } } 

Try it online

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Golfed a bit more: int P(string[]C){int w=C[0].Length,i=0,l=c.Length;var c=string.Join("",C);var h=new int[l];for(var n=new List<int>();i<l;n.Add(i++))h[i]=c[i]!='@'?int.MaxValue:0;for(i=1;;i++){var t=n;n=new List<int>();foreach(int x in t){foreach(int d in new[]{-1,1,-w,w}){for(int j=x+d;c[j]==' ';j+=d);if(c[j]=='#'&h[j-d]>s){h[j-d]=s;n.Add(j-d);}if(c[j]=='.'&h[j]>s){h[j]=s;n.Add(j);}if(c[j]=='o')return s;}}if(n.Count<1)return -1;}} (418 bytes). Also, could you perhaps add a TIO-link with test code? \$\endgroup\$ Commented Apr 19, 2018 at 9:17
  • \$\begingroup\$ Thanks for the TIO link. The code I provided above didn't work, so I fixed it, and golfed three more bytes. Try it online 415 bytes. (You'll have to re-add your huge test case again from your current TIO. I couldn't paste the link in this comment because the link was too big with that test case.. ;p) \$\endgroup\$ Commented Apr 19, 2018 at 13:57

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.