12
\$\begingroup\$

You know those wooden toys with little ball bearings where the object is to move around the maze? This is kinda like that. Given a maze and a series of moves, determine where the ball ends up.

The board is held vertically, and the ball moves only by gravity when the board is rotated. Each "move" is a rotation (in radians).

The maze is simply concentric circular walls, with each wall having exactly one opening into the outer corridor, similar to this (assume those walls are circles and not pointed):

labyrinth

As you can see, the ball starts in the middle and is trying to get out. The ball will instantly fall through as soon as the correct orientation is achieved, even if it's midway through a rotation. A single rotation may cause the ball to fall through multiple openings. For instance, a rotation >= n * 2 * pi is enough to escape any maze.

For the purposes of the game, a ball located within 0.001 radians of the opening is considered a "fit", and will drop through to the next corridor.

Input:

Input is in two parts:

  • The maze is given by an integer n representing how many walls/openings are in the maze. This is followed by n lines, with one number on each, representing where the passage to the next corridor is.

  • The moves are given as an integer m representing how many moves were taken, followed (again on separate lines) by m clockwise rotations of the board in radians (negative is anticlockwise).

All passage positions are given as 0 rad = up, with positive radians going clockwise.

For the sample image above, the input may look like this:

7                        // 7 openings
0
0.785398163
3.14159265
1.74532925
4.71238898
4.01425728
0
3                        // 3 moves
-3.92699082
3.14159265
0.81245687

Output: Output the corridor number that the ball ends in. Corridors are zero-indexed, starting from the center, so you start in 0. If you pass through one opening, you're in corridor 1. If you escape the entire maze, output any integer >= n

For the sample input, there are three moves. The first will cause the ball to fall through two openings. The second doesn't find an opening, and the third finds one. The ball is now in corridor 3, so expected output is:

3

Behavior is undefined for invalid input. Valid input is well-formed, with n >= 1 and m >= 0.

Scoring is standard code golf, lowest number of bytes wins. Standard loopholes are forbidden. Input must not be hard-coded, but can be taken from standard input, arguments, console, etc. Output can be to console, file, whatever, just make it output somewhere visible.

\$\endgroup\$
  • \$\begingroup\$ "Behavior is undefined for invalid input." <<-- This needs to be put in all puzzles! \$\endgroup\$ – TheDoctor Apr 29 '14 at 22:44
  • \$\begingroup\$ In that hypothetical case, you could also calculate π whenever needed with variable accuracy, raising the accuracy until it is sufficient to tell whether a ball has fallen or not. A problem I have with the tolerance for a fit (or at least its current wording) is if A) consecutive fits are closer than 0.001 to each other such that the ball only falls two levels if the tolerance is taken into account B) when the ball is within 0.001 of a hole, it jumps to the hole (if you really want to read something into the wording). \$\endgroup\$ – Wrzlprmft May 1 '14 at 1:07
  • \$\begingroup\$ @Wrzlprmft The ball doesn't jump to the hole. Think of the threshold as meaning that the holes are slightly wider than the ball. It still drops through to the same location, just one level further. If you imagine the threshold was 1, you'd just be working with large holes, not jumping balls to the center of the hole when they fall. \$\endgroup\$ – Geobits May 2 '14 at 19:54
  • \$\begingroup\$ Why is the input in such an inconvenient format? I'm pretty sure I've golfed entire programs shorter than what I need to read it :/ \$\endgroup\$ – Tal May 4 '14 at 16:32
2
\$\begingroup\$

Perl, 211 191

With newlines and indentation for readability:

$p=atan2 0,-1;
@n=map~~<>,1..<>;
<>;
while(<>){
    $_=atan2(sin,cos)for@n;
    $y=abs($n[$-]+$_)<$p-.001
        ?$_
        :($_<=>0)*$p-$n[$-];
    $_+=$y for@n;
    $p-.001<abs$n[$-]&&++$-==@n&&last;
    $_-=$y;
    .001<abs&&redo
}
print$-

Number of moves in the input is discarded, stdin's eof indicates end of moves.

\$\endgroup\$
5
\$\begingroup\$

JavaScript 200

function f(i){with(Math)for(m=i.split('\n'),o=m.slice(1,t=+m[0]+1),m=m.slice(t+1),c=PI,p=2*c,r=0,s=1e-3;m.length;c%=p)abs(c-o[r])<s?r++:abs(t=m[0])<s?m.shift(c+=t):(b=t<0?-s:s,c+=p-b,m[0]-=b);return r}

EDIT : Here is an animated example proving that this solver works : http://jsfiddle.net/F74AP/4/

animated

The function must be called passing the input string.
Here is the call of the example given by the OP :

f("7\n0\n0.785398163\n3.14159265\n1.74532925\n4.71238898\n4.01425728\n0\n3\n-3.92699082\n3.14159265\n0.81245687");

It returns 3 as intended.

\$\endgroup\$
  • 2
    \$\begingroup\$ From the challenge, "...input must not be hard-coded...". Unless I am mistaken, that means you have to read it in, and you also have to have a complete program. This looks like just a function. \$\endgroup\$ – Rainbolt Apr 30 '14 at 13:01
  • 2
    \$\begingroup\$ I don't understand, the values are not hard-coded ! "...Input must not be hard-coded, but can be taken from standard input, arguments, console, etc.". Concerning the complete program, I don't see where it is specified and anyway, IMO this is a complete JS solution. \$\endgroup\$ – Michael M. Apr 30 '14 at 13:30
  • \$\begingroup\$ I didn't specify a full program, so I see no problem with a function only. However, input is specified as being separated by newlines, not already arranged into native arrays. That should be simple to satisfy. \$\endgroup\$ – Geobits Apr 30 '14 at 15:10
  • 1
    \$\begingroup\$ @Geobits, I will modify it later, have a look at this fiddle : jsfiddle.net/F74AP/1 \$\endgroup\$ – Michael M. Apr 30 '14 at 15:32
  • 1
    \$\begingroup\$ @Geobits, right ! Simple sign error... Fixed ;-) \$\endgroup\$ – Michael M. Apr 30 '14 at 18:03

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.