4
\$\begingroup\$

Let's play code golf... by playing golf.

Input

Your input will be a string consisting of #'s, an o, an @, and .'s. For example:

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

. - playable golf course (all shots must end on one of these)
# - a barrier (shots cannot go through this)
o - the starting position of your golf ball
@ - the hole

How to Play ASCII Golf

You start at the o. Here is a valid shot from point A to point B:

1) This shot is straight line that can be drawn between A and B (no curved shots).

A....
....B

2) The line AB may not intersect with a # (barrier), e.g.:

A.#.B

It may, however, be tangent to a barrier:

A#
.B

3) (For clarity) You may not bounce shots off barriers or the edge of the golf course.

Output

Print to stdout (or an acceptable equivalent) the minimum number of shots to get the ball into the hole @. If it is not possible, print -1.

Examples

o....@

=> 1

o.#.@

=> -1

o..#
..#@

=> 2 (you can pass through the vertices of a #, but not the edges)

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

=> 4

\$\endgroup\$
13
  • 6
    \$\begingroup\$ Can’t your “6” example be done in 4 shots (south 1, southeast 1, northeast 2, southeast 2)? \$\endgroup\$ Commented May 20, 2016 at 3:51
  • \$\begingroup\$ In the worst case you would need to write/golf a pathfinder algorithm like A* or something similar. Which may be quite difficult/challenging for some languages. \$\endgroup\$
    – Rolf ツ
    Commented May 20, 2016 at 8:25
  • \$\begingroup\$ @AndersKaseorg Good point, fixed. \$\endgroup\$
    – AMACB
    Commented May 20, 2016 at 12:56
  • \$\begingroup\$ What would ..@ \no#. mean? \$\endgroup\$
    – Leaky Nun
    Commented May 20, 2016 at 13:07
  • \$\begingroup\$ Can you do this in 1 shot? o### / #..# / ###@ (3 rows) \$\endgroup\$ Commented May 20, 2016 at 17:52

1 Answer 1

3
\$\begingroup\$

Python 2, 469

Pretty long, but it's a start:

R=range
def l(c,x,y,z,t):
 f=abs(z-x);g=1-2*(z<x);p=abs(t-y);q=1-2*(t<y);v=r=0
 for i in R(f):
  w=f+(2*i+1)*p
  for j in R(v,(w-1)/2/f+1):r|='.'>c[x+g*i][y+q*j]
  v=w/2/f
 for j in R(v,p+1):r|='.'>c[z][y+q*j]
 return r
def f(c):
 a="".join(c);n=len(c[0]);b=len(a);d=[[9**9*l(c,i/n,i%n,j/n,j%n)+1for i in R(b)]for j in R(b)]
 for k in R(b):
  for i in R(b):
   for j in R(b):
    t=d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    if"o@"==a[i]+a[j]:r=t
 return-1if r>9**9else r

Function f takes a list of strings and returns the number of shots.

Test suite:

def test(s,r):
 print"ok"if f(s.split())==r else"fail"

test("o # @", -1)
test("......@.. .....##.. ......... ......o..", 2)
test("o....@", 1)
test("o.#.@", -1)
test("o..# ..#@", 2)
test("o#...# .#.#.# ...#.@", 4)
test("o### #..# ###@", 3)
test("o.## ##.@", 1)
test("...o .@#.", 2)
\$\endgroup\$
0

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