TopCoder problem "HexGolf" used in SRM 89 (Division I Level Two)

Problem Statement


Regular hexagons can be placed adjacent to each other, filling the plane.  Each
hexagon is adjacent to 6 other hexagons. The six primary directions in the
field of hexagons correspond to the directions between the centers of adjacent
hexagons. We will call them (in clockwise order) northeast, east, southeast,
southwest, west, and northwest. Of course a negative movement to the northeast
is the same as a positive movement to the southwest, etc. 

Here is a picture showing the locations of 60 hexagons in a field of hexagons.
Each letter is the center of a hexagon. One hexagon and its six neighbors are
shown with T. (This would correspond to a tee area of size 1, and the hexagon
marked H might be the hole  -- see below).

x x x x x x x x x x x x
 x x x x T T x x x x x x
x x x x T T T x x x x x
 x x x x T T x x x H x x
x x x x x x x x x x x x


Look! A vast field of hexagons! Its a perfect day to play HexGolf.

The rules are simple.  Choose a hexagonal cell in the tee area to start from.
Then for each shot, choose a club, and one of the 6 primary directions in the
field of hexagons.  Your shot will travel the number of hexagons specified for
the club. Repeat this until a shot ends in the hexagon where the hole is. The
only exception is that on your first shot (since you get to tee the ball up)
the ball will go 3 hexagons farther than the club specifies.  Create a class
HexGolf that contains the method playHole that takes the tee size, a collection
of golf clubs, and the hole location, and returns the minimum number of shots
required.  If it is not possible to score 5 or less on the hole, return -1.

Class:  HexGolf
Method: playHole
Parameters:  int, int[], int, int
Returns: int
Method Signature: (be sure your method is public) int playHole(int teeSize,
int[] club, int eastToHole, int southeastToHole);

The tee area is specified by a non-negative teeSize. The tee area consists of a
central hexagon and the teeSize concentric rings of hexagons around it. For
example, if teeSize = 2, the tee area contains 19 hexagons (the central one,
the ring of six around it, and the ring of 12 around that).

The location of the hole is given by telling the distances east, then southeast
from the center of the tee to the hole.

- If the hole cannot be played in 5 or less, return -1
- Shots after the first one never get the 3 hexagon bonus, even if they are
from a hexagon in the tee area.

TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:
- teeSize >= 0, and the tee area does not include the hole
- club has between 1 and 5 elements inclusive
- each element of club is between 1 and 500 inclusive
- eastToHole is between -5000 and 5000 inclusive
- southeastToHole is between -5000 and 5000 inclusive


0)   teeSize=1, club={1,6,4}, eastToHole=4, southeastToHole=1: return 1

This is shown in the picture above. A hole-in-one can be achieved in only one
way: tee it up in the southeast-most hexagon in the tee area, choose the club
with length 1, and shoot east (remember the 3 bonus).

1)  teeSize=0, club={2,2,2,2,2}, eastToHole=-5, southeastToHole=0: return 1

A shot west using one of the clubs will go 2+3 hexagons west, ending up in the

2)  teeSize=0, club={2,2,2,2,2}, eastToHole=4, southeastToHole=0: return -1

There are lots of ways to get next to the hole, but no way to get into the hole.

3)  teeSize=1, club={2,2,2,2,2}, eastToHole=4, southeastToHole=0: return 1

This is the same as example 2, except teeSize=1. Tee it up one hexagon west of
the center of the tee area, shoot east, and get a hole-in-one.

4)  teeSize=0, club={1,3,139}, eastToHole=137, southeastToHole=3: return 4

Shoot 139+3 to the east, 3 to the southwest, 1 to the west, 1 to the west.
(There are many other ways to do it in 4 shots.)

5) teeSize=10, club={1,3,7,15,310}, eastToHole=4000, southeastToHole=4003:
return -1        


Parameters:int, int[], int, int
Method signature:int playHole(int param0, int[] param1, int param2, int param3)
(be sure your method is public)

Problem url:

Problem stats url:




Problem categories: