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\$
  • 1
    \$\begingroup\$ Related: One, Two. \$\endgroup\$ – AdmBorkBork Mar 29 '18 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\$ – Arnauld Mar 29 '18 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\$ – Manfred Radlwimmer Mar 31 '18 at 6:22
  • \$\begingroup\$ If input the destination directly, can we require the place of destination be 'sand' symbol? \$\endgroup\$ – l4m2 Mar 31 '18 at 13:10
  • \$\begingroup\$ @l4m2 Sure, that way it would stay consistent with all the other rules. \$\endgroup\$ – Manfred Radlwimmer Mar 31 '18 at 21:06
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\$
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\$
  • \$\begingroup\$ Could if k+1 not be if-~k? \$\endgroup\$ – Jonathan Frech Apr 19 '18 at 10:52
  • \$\begingroup\$ @JonathanFrech yes, thanks \$\endgroup\$ – HyperNeutrino Apr 20 '18 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\$
  • 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\$ – Kevin Cruijssen Apr 19 '18 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\$ – Kevin Cruijssen Apr 19 '18 at 13:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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