#215383. [Google Hashcode 2022 Finals] Santa Tracker

Introduction

Every year since 2004, the Google Santa Tracker project has helped visualize the route taken by the legendary character Santa Claus each December to distribute gifts to kids around the world.

Though December is months away, preparations are in full swing at Santa's home in Lapland. The Google Santa Tracker is also getting ready, and rumors are that this year is going to be especially interesting. A secret team of Engineers in Light-speed Flights (ELF), in collaboration with the Gnome Institute of Generous Gift Logistics Engineering (GIGGLE) in Lapland, is working to develop new experimental optimization algorithms that help Santa deliver gifts more effectively.

The early results are promising, but Santa thinks they can be improved. When Santa learned about the famous optimization skills of Hash Code participants, he asked if Hash Code World Finalists would be able to help out. Are you up for the challenge?

Task

Santa is delivering gifts on a frictionless 2D plane, using a reindeer-powered sleigh that accelerates using... carrots 🥕.

Your task is to plan actions for the sleigh to make gift deliveries and maximize the total score.

The world

The world is a 2D grid with integer coordinates. We refer to a cell at column and row as ().

The distance between two cells and is calculated as (Euclidean distance).

Santa starts at Lapland where all the gifts are stored.

:::align{center} :::

Santa only has seconds to deliver the gifts, so hurry up!

Gifts and carrots

There are two types of things Santa can load onto his sleigh: gifts and carrots.

Gifts need to be delivered to children around the world. You are given the list of gifts, for each of which you know:

• the name of the child that should receive it,
• the score awarded for delivering this gift,
• the weight of the gift in kilograms (kg),
• the coordinates where it needs to be delivered.

Carrots are food for Santa's magic reindeer who need to eat them to accelerate. Each carrot weighs kg (yes, we know they are heavy... but they really are magic!).

Thanks to a very effective team of helper gnomes, gift delivery happens instantaneously at the beginning of the second. Similarly, gift/carrots pick up happens instantaneously at the beginning of the second.

Range

Santa can deliver gifts to all children within a maximum distance of (inclusive) from his sleigh. Similarly, Santa can pick up gifts and carrots whenever the sleigh is within a maximum distance of (inclusive) from his base at . We call this maximum distance of "range".

::::info[For example:]

For example, for the range and the sleigh at :

• The cell is within the range from , because the Euclidean distance is and .
• The cell (marked in black in the figure below) is not within the range from , because the Euclidean distance is and .

:::align{center} :::

::::

Navigation

Santa moves around the world on his magic sleigh.

Thanks to the magic coating on his sleigh, Santa encounters no friction and conserves speed indefinitely. At any point the movement of the sleigh can be described as its velocity , denoting how fast the sleigh moves in each direction within one second.

Santa starts with the velocity of (not moving).

::::info[For example:]

For example, in the figure below the sleigh is initially at position and its velocity is .

As long as the velocity remains constant, after each second the sleigh will move 1 position to the right and 2 positions upwards.

:::align{center} :::

::::

Maneuvering

Each second, Santa can choose to feed one carrot (previously loaded to the sleigh) to the reindeer to accelerate by a chosen value in one of four directions: up, down, left, right. "Acceleration" means changing the velocity. If the velocity is initially and Santa accelerates, then:

• "accelerating up" by means changing the velocity to
• "accelerating down" by means changing the velocity to
• "accelerating right" by means changing the velocity to
• "accelerating left" by means changing the velocity to

Note that the concept of "acceleration" (defined above) allows Santa to "decelerate" (slow down) as well. For example, if accelerating up by 2 makes Santa's sleigh go faster, then a subsequent "acceleration" down by 2 will make them go slower.

Santa can choose to accelerate, but even magic sleighs have their limitations! The maximum acceleration that Santa's reindeers can provide at a given moment depends on the current weight of the sleigh. The heavier the sleigh, the slower the maximum acceleration!

The weight of the sleigh is a sum of:

• the weight of the gifts loaded on the sleigh
• the weight of the carrots loaded on the sleigh

Each input data set specifies the maximum acceleration in given ranges of sleigh weights. Maximum acceleration of for sleigh weight range means that the maximum acceleration is equal to (inclusive) for all sleigh weights of that meet the constraints of .

This sleigh weight above includes the carrot just about to be eaten by the reindeer. However, right after the acceleration, the carrot is eaten and converted into reindeer energy, instantaneously reducing the weight of the sleigh by kg.

If reindeer can't handle the weight of the sleigh ( is above maximum ) they can't accelerate at all (max acceleration = 0). The sleigh keeps its speed and continues floating until acceleration becomes possible again (e.g. gifts are delivered) or the time runs out. Also, if there are no carrots on the sleigh, acceleration is not possible!

The acceleration is instantaneous and happens in the beginning of the second. Santa's sleigh can only accelerate once per second (it must float for at least one second before another acceleration is possible).

Consider the example represented in the description and the figure below.

The acceleration ranges are as follows, for the sleigh weight denoted as :

• if kg, the sleigh can accelerate by up to 4
• if kg kg, the sleigh can accelerate by up to 2
• if the weight is higher than 500 kg the sleigh can't accelerate at all

::::info[For example:]

The initial weight of the sleigh consists of 20 kg of presents and 11 kg of carrots. So the total weight is 31 kg which means the maximum acceleration is 2. The initial velocity at seconds is .

• At seconds: the sleigh is at . The sleigh accelerates up by 2 (which is the maximum allowed acceleration for the sleigh weight of 31 kg). Since acceleration occurs instantaneously at the beginning of the second, the new velocity at the beginning of seconds is . The weight of the sleigh becomes 30 kg because one carrot is used. Then the sleigh floats for 1 second.
• At seconds: the sleigh is at . The sleigh accelerates down by 3 (which is now allowed since in the previous second the weight decreased to 30 kg, increasing the maximum acceleration to 4). The new velocity at the beginning of seconds is . Then the sleigh floats for 1 second.
• At seconds: the sleigh is at . The sleigh doesn't accelerate (the velocity remains at ) and just floats for another second.
• At seconds: the sleigh is at

:::align{center} :::

::::

Note that the weight of the sleigh is also updated when gifts are delivered to children.

::::info[For example:]

Consider the example below. The sleigh movement is the same as in the figure above, but we add gift deliveries. The range is .

• At seconds: the sleigh is at . We deliver a gift to cell , reducing the weight of the sleigh by 5 kg.
• At seconds: the sleigh is at . We deliver a gift to cell (the same cell in which the sleigh is located), reducing the weight of the sleigh by another 5 kg.

Observe that, even though between and the sleigh passes close to the gift delivery location at , it is not possible to deliver it. This is because gift deliveries must happen at the beginning of a second, not while the sleigh is floating.

:::align{center} :::

::::

Actions

The sleigh can perform the following actions. All actions apart from "Float" are instantaneous (take 0 seconds). All actions can be performed regardless of whether the sleigh is moving (no need to stop to make deliveries or load the sleigh).

• Accelerate in one of four directions (up, down, left or right) by a given acceleration (not more than the maximum acceleration for the current weight of the sleigh). The sleigh has to take the float action at least once between two consecutive accelerations.
• Float for a number of seconds. The velocity of the sleigh remains constant during the float action.
• Load a number of carrots. The sleigh needs to be within a distance from the initial position .
• Load a given gift. The sleigh needs to be within a distance from the initial position .
• Deliver a given gift. The delivery location of the given gift has to be within a distance from the sleigh's position.

:::info[For example:]

For instance, the following 3 sequences of actions are valid:

1. Accelerate up → Float → Accelerate down → Float
2. Accelerate up → Give Gift → Float → Load Carrots → Float → Accelerate left → Float
3. Float → Accelerate up

Observe that in (3) the last "Accelerate up" action is not affecting the final position of the sleigh: the velocity is updated, but the sleigh doesn't move at the updated velocity until a "Float" command is issued.

The following 2 sequences of actions are invalid because there are two acceleration actions without any float action between them:

• ❌ Accelerate left → Accelerate down → Float
• ❌ Float → Accelerate up → Load Carrots → Accelerate down :::

Input Data Full input (zipped)

Each input data set is provided in a plain text file. The file contains only ASCII characters with lines ending with a single '\n' character (also called "UNIX-style" line endings). When multiple strings and numbers are given in one line, they are separated by a single space between each two elements.

The first line of the input file contains:

• - the time limit in seconds, ()
• - the reach range (), that is maximum distance from sleigh for gift delivery and gift/carrot pick up
• - the number of acceleration ranges sleigh has ()
• - the number of gifts in the dataset, ()

The subsequent lines contain the acceleration ranges description - two integer numbers separated by a single space:

• - an integer number, the maximum weight of the sleigh to use the following acceleration ()
• - an integer number, the max acceleration for this acceleration range ()

Note that the weight range of the sleigh for max acceleration is where . It is guaranteed that and

The subsequent lines contain gift descriptions - strings and integer numbers separated by single spaces:

• - the name of the child (a unique string of a-z, A-Z, 0-9 characters up to 30 characters long)
• - an integer number, the score for delivering the gift ()
• - an integer number, the weight of the gift in kilograms ()
• - the column of the location of the child ()
• - the row of the location of the child ()

Every position in the datasets is guaranteed to have at most 1 gift recipient and Lapland at is guaranteed to have none.

You need to specify the actions for Santa.

File Format

The submission file must be a plain text file containing exclusively ASCII character lines terminated with a single '\n' character ("UNIX-style" line endings).

The first line must contain a single integer (): the number of actions for Santa.

Each of the following lines must contain a valid action for the sleigh. Each action description must contain the action name and the action argument, separated by a space. The possible actions are:

• AccUp (a) - Accelerates in the "up" direction by integer (, where is the applicable maximum acceleration for the current weight of the sleigh)
• AccDown (a) - Accelerates in the "down" direction by integer (, where is the applicable maximum acceleration for the current weight of the sleigh)
• AccLeft (a) - Accelerates in the "left" direction by integer (, where is the applicable maximum acceleration for the current weight of the sleigh)
• AccRight (a) - Accelerates in the "right" direction by integer (, where is the applicable maximum acceleration for the current weight of the sleigh)
• Float (t) - Advances the time by integer seconds (). In each second the position of the sleigh advances by the current velocity.
• LoadCarrots (N) - Loads integer carrots onto the sleigh (), only valid within a distance inclusive from .
• LoadGift (ChildName) - Loads a gift for the given child, only valid within a distance inclusive from .
• DeliverGift (ChildName) - Delivers the gift for the given child, only valid within a distance inclusive from the child.

样例输入 1

15 3 4 4
15 8
30 6
45 4
60 2
Olivia 1 10 5 1
Emma 2 10 -10 1
Liam 5 10 8 4
Bob 10 15 0 -100

样例输出 1

23
LoadCarrots 10
LoadGift Olivia
LoadGift Liam
AccRight 4
Float 1
DeliverGift Olivia
AccUp 2
Float 1
DeliverGift Liam
AccLeft 8
Float 1
AccDown 4
Float 1
LoadGift Bob
AccRight 4
Float 1
AccDown 6
Float 1
AccDown 6
Float 1
AccDown 6
Float 4
DeliverGift Bob

Example

Note that the input file does not contain any blank lines. Blank lines and line wrapping in the example above are added for clarity.

Note that the submission file should not contain any blank lines. Blank lines and line wrapping in the example above are added for clarity.

Validation

In order for the submission to be accepted, it must fulfill the following conditions:

• ⚠️ The submission file must have exactly lines in the format described above.
• ⚠️ Santa must not attempt loading gifts or carrots onto the sleigh when he's further than from .
• ⚠️ Santa must not attempt delivering a gift when he's further than from the destination.
• ⚠️ Santa can only deliver each gift once, and only if it was loaded to the sleigh previously.
• ⚠️ Santa can only load each gift once. (After a gift is loaded, it is either delivered, or it stays on the sleigh until the end of the simulation.)
• ⚠️ Santa must not attempt to accelerate more than what is permitted given the current weight of the sleigh.
• ⚠️ Santa must not attempt to accelerate more than once in a second (without a Float action in between).
• ⚠️ Santa must not attempt the Float action after the time of simulation ran out.

Scoring

The score of your solution is the sum of the scores awarded for each gift that have been delivered.

Note that there are multiple data sets representing separate instances of the problem. The final score for your team will be the sum of your best scores on the individual data sets.