18
\$\begingroup\$

Getting hit in the knee with arrows seems to be the injury of choice right now. As such, I propose the following golf challenge.

You have an adventurer that looks like this:

  O
 /|\
/ | \
  |
  |
 / \
/   \

Given a text file that contains one bow (drawn as a } symbol), a set of walls (drawn as # symbols) and one adventurer, write the smallest code that calculates the angle and initial velocity at which you should fire an arrow in order to hit him in the knee.

Assume the following:

  • Each character in the file is 0.5 x 0.5 meters.
  • The arrow is fired from the center of the }, i.e. an offset of 0.25m, 0.25m
  • Gravity is 10ms^-2
  • Arrow weighs 0.1kg
  • Arrow is a point, i.e. collisions only occur when the arrow's coordinate enters one of the blocks.
  • Maximum initial velocity is 50m/s
  • Angle may be between 0 (straight up) and 180 (straight down)
  • Hitting any part of the adventurer's leg is considered a hit to the knee.
  • A wall (# character) takes up one entire 0.5m x 0.5m block.
  • The arrow can travel over the "top" of the file, but there's nothing to stop the input from starting with a ceiling of # characters.
  • You can't penetrate walls with arrows.
  • Hitting any other part of the adventurer is not allowed!
  • You should display an error if hitting him in the knee is impossible.

Example input:

                                 #                        
}                                                     O   
                        #                            /|\  
                                                    / | \ 
            #                                         |   
                            #                         |   
                                                     / \  
                                                    /   \  

Feel free to ask questions if you need to :)

\$\endgroup\$
  • 1
    \$\begingroup\$ Can the arrow travel "over" the area depicted by the text file? \$\endgroup\$ – J B Dec 12 '11 at 10:33
  • 2
    \$\begingroup\$ How many people do you know who are over 3m tall? :P \$\endgroup\$ – Peter Taylor Dec 12 '11 at 10:39
  • \$\begingroup\$ @JB - Yes, but there's nothing to stop the input starting with a big line of #############... \$\endgroup\$ – Polynomial Dec 12 '11 at 10:45
  • 2
    \$\begingroup\$ @PeterTaylor - Everyone knows that people in RPG games are disproportionately huge ;) \$\endgroup\$ – Polynomial Dec 12 '11 at 10:46
  • 2
    \$\begingroup\$ The weight of the arrow is redundant, surely ? \$\endgroup\$ – Paul R Dec 12 '11 at 17:17
11
\$\begingroup\$

Python, 599 chars

import os,sys
from math import*
I=os.read(0,999)
O=[]
h=v=0
for i in I:
 if'#'==i:O+=[(h,v,h+1,v+1),(h+1,v,h,v+1)]
 if'O'==i:O+=[(h,v+1,h-2,v+3)];T=(h,v+5,h-2,v+7)
 if'}'==i:e=h+.5;c=v+.5
 h+=1
 if'\n'==i:v+=1;h=0

def X(K,L):
 A,B,C=K;p=L[0];q=L[2]-p;r=L[1];s=L[3]-r;A,B,C=A*q*q,2*A*p*q+B*q-s,A*p*p+B*p+C-r;d=B*B-4*A*C
 return 0 if d<0 else any(0<x<1 for x in[(sqrt(d)-B)/2/A,(-sqrt(d)-B)/2/A])

R=range(1,999)
for v in R:
 for z in R:
  z*=pi/999;d=v*sin(z)/10;b=-v*cos(z)/10
  K=20/d/d,b/d-40*e/d/d,c+20*e*e/d/d-b*e/d
  if X(K,T)and not any(X(K,x)for x in O):print v/2,z;sys.exit(0)
print'ERROR'

The X(K,L) routine takes a parabola K=(a,b,c) representing y=ax^2+bx+c and a line segment L=(a,b,c,d) representing the segment between (a,b) and (c,d). Both obstacles (O) and the target (T) are repesented as line segments. All distances are scaled by a factor of 2.

The example input gives the following trajectory (by default, the minimum velocity one):

  --                             #          --            
--                                            -       O   
                        #                      -     /|\  
                                                -   / | \ 
            #                                    -    |   
                            #                     -   |   
                                                   - / \  
                                                    -   \  

you can reverse R to get the maximum velocity path:

                                 #                        
-------------                                         O   
             -----------#                            /|\  
                        --------                    / | \ 
            #                   -------               |   
                            #          -----          |   
                                            -----    / \  
                                                 -----  \  
\$\endgroup\$
  • \$\begingroup\$ Good work. Only complaint is that the input size limit is 999 bytes. It could quite easily be more, considering the potential size of these ASCII drawings. 9999 would be more sensible, at the cost of only 1 character. (though at that point you might as well do 8**5 to get 64kB) \$\endgroup\$ – Polynomial Dec 13 '11 at 6:48
  • \$\begingroup\$ Pretty sure you could then save that one character by assigning w=v+1 and replacing the 3 instances of v+1 with w. I don't code much Python though, so I may be wrong. \$\endgroup\$ – Polynomial Dec 13 '11 at 6:56

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.