Balto's Puzzle
Ends: | 4 Jan 2025 15:00 |
Now: | 4 Dec 2024 14:48 |
Description | Submit An Entry | Standings |
The Elevator Pitch
Solve 25 versions of a sliding tile puzzle similar to the well-known 15 puzzle.
The Puzzles
Each of the 25 puzzles is played on a regular hexagonal grid. The puzzles differ from each other only in the sizes of their grids, which vary from order 3 to order 27. For this contest we'll generally refer to a grid of order n as being of size n.
Each grid has k - 1 moveable tiles, numbered from 1 to k - 1, where k is the number of cells in the grid.
Initially, each puzzle's tiles are distributed randomly
among its grid's cells, leaving one cell empty.
Example starting grid for n = 3
The starting grids for the 25 puzzles are here.
Your goal for each puzzle is to find a sequence of moves which relocates each tile to (or close to) its home cell, and does so with as few moves as possible.
The following diagram shows a grid with each tile in its home cell – the center cell is empty and the tiles are otherwise arranged in row major order.
Each tile in its home cell
A move consists of choosing one of the vertices of the empty cell as a "center of rotation", and then rotating the tiles in the 3 adjacent cells by 120 degrees. Your first move can rotate either clockwise or anticlockwise. Thereafter, the direction of rotation must change with each move.
Before rotation
After rotation
If the center of rotation is on the perimeter of the grid, the rotation will necessarily include one or two cells from other sides of the grid. These diagrams indicate which cells are considered adjacent to the vertices on the grid's perimeter.
Perimeter vertices
(in blue)
Cells that are considered
adjacent to perimeter vertices
How to Enter
Represent a solution (that is, a sequence of moves) as a string, each character of which represents a move. This character indicates both the center and direction of the rotation, as shown here. Numeric characters are used for clockwise rotation, and alphabetic characters for anticlockwise.
Clockwise rotation
Anticlockwise rotation
For example, the string "1D5" indicates three moves to be executed in sequence:
• clockwise around vertex 1 of the empty cell,
• anticlockwise around vertex D of the empty cell, and
• clockwise around vertex 5 of the empty cell.
Execution of move 1 | → | ||||
Execution of move D | → | ||||
Execution of move 5 | → |
To submit this sequence of 3 moves as a solution, preface the string with the size of the grid to which it applies, and insert a colon to separate the size from the moves. Then paste this concatenation into the large box on the Submit page and click Submit Entry. For this solution you would paste:
3:1D5
To submit more than one solution at a time, separate them with semicolons. Do not place a semicolon after the last solution.
Include spaces and other white space (tabs, line breaks, etc.) anywhere you like – but not, of course, within the grid-size prefix.
Over the course of the contest, you can submit more than one solution for the same grid size, but only the best of them will count.
The Scoring System
-
Frist, two values are calculated from each solution:
-
•
sum-of-distances
• number-of-moves
Sum-of-distances is the sum, over all tiles, of the taxicab distance between the tile's ending cell and its home cell. The taxicab distance between two cells is best explained with a few examples:
Distance = 2
Distance = 4
Distance = 4
Distance = 3Here is an example of computing sum-of-distances for a grid of size 2:
Final positions of tiles
Home positions of tilesTile Distance 1 0 2 1 3 1 4 2 5 2 6 0 Sum-of-distances 6
DistancesNumber-of-moves for a solution is, unsurprisingly, the number of moves in the solution.
-
Then, a raw-score for each submission is calculated as follows:
-
Raw-score =
sum-of-distances + (
number-of-moves / 1000000) + 1
-
Finally, we use the raw-scores from your submissions to compute your contest-score. The contestant with the highest contest-score wins. Here's how we calculate your contest-score:
-
• For each of the 25 grid sizes, your
grid-size-score is the
best (that is, lowest) grid-score for your submissions of that size.
• For each of the 25 grid sizes, we compute your subscore. We do this by dividing your grid-size-score into the lowest grid-size-score for that grid size across all contestants. Each of your subscores therefore has a value from 0 to 1.
• Your contest-score is the sum of your 25 subscores. -
If two contestants have the same contest-score, we break the tie by giving preference to the contestant whose last improvement was submitted least recently.
Let's walk through an example. Suppose we modify the contest by asking you to submit solutions for only 3 grid sizes: 3, 4 and 5. Further suppose that we have only 3 contestants (Harry, Ron and Hermione) and that each has submitted exactly one solution for each grid size.
We begin by noting the sum-of-distances and number-of-moves for each submitted grid:
Grid size = 3 | Grid size = 4 | Grid size = 5 | ||||
---|---|---|---|---|---|---|
Sum of Distances |
Number of Moves |
Sum of Distances |
Number of Moves |
Sum of Distances |
Number of Moves |
|
Harry | 49 | 5 | 119 | 120 | 269 | 75 |
Ron | 39 | 60 | 138 | 10 | 259 | 130 |
Hermione | 29 | 115 | 129 | 65 | 281 | 20 |
Then, we calculate the raw-score for each submission:
Grid size = 3 | Grid size = 4 | Grid size = 5 | |
---|---|---|---|
Harry | 50.000005 | 120.000120 | 270.000075 |
Ron | 40.000060 | 139.000010 | 260.000130 |
Hermione | 30.000115 | 130.000065 | 282.000020 |
Next, we note the lowest raw-score for each grid size:
Grid size = 3 | Grid size = 4 | Grid size = 5 | |
---|---|---|---|
Lowest Raw-Score |
30.000115 | 120.000120 | 260.000130 |
Finally, we calculate the subscores and contest-score for each contestant:
Grid size = 3 | Grid size = 4 | Grid size = 5 | Contest Score | |
---|---|---|---|---|
Harry | 30.000115 / 50.000005 = .600 | 120.000120 / 120.000120 = 1.000 | 260.000130 / 270.000075 = .962 | 2.562 |
Ron | 30.000115 / 40.000060 = .750 | 120.000120 / 139.000010 = .863 | 260.000130 / 260.000130 = 1.000 | 2.613 |
Hermione | 30.000115 / 30.000115 = 1.000 | 120.000120 / 130.000065 = .923 | 260.000130 / 282.000020 = .922 | 2.885 |
Hermione has the highest contest-score and therefore is the winner.
Getting Your Questions Answered
First, check the FAQ section below. If you can't find the information you need there, send your question to the discussion group. If your question is of a personal nature, and not of general interest, send an email directly to Al Zimmermann.
The Discussion Group
If you think you might enter the contest, you should join the contest discussion group. You can join either by sending a blank email here or by visiting the group on groups.io . The discussion group serves two purposes. First, it allows contestants to ask for clarifications to the rules. Be aware that sometimes these requests result in changes to the rules, and the first place those changes are announced is in the discussion group. Second, the discussion group allows contestants to interact with each other regarding programming techniques, results and anything else relevant to the contest.
Frequently Asked Questions
-
Can teams enter the contest?
Yes. But a team can only be formed by those who have not already entered the contest as individuals. Once you enter as an individual, team membership is no longer open to you. Likewise, once you've joined a team you can't resign from it and start submitting grids on your own behalf.
If you would like to form a team, please follow these instructions:
-
If they do not already exist, create individual accounts for each team member.
Do not create a second account for any team member who already has one.
-
Let me know
each team member's name and registered email address. It is important that
no team member submit any entries to this contest until I notify you
that the team has been created.
-
After I've created the team, team members can submit entries to
the contest from their individual accounts. The contest engine
automatically intercepts these entries and diverts them to the
team account. The team is listed on the standings page.
- Unless you are satisfied with the defaults, also let me know what team name and team location you would like to use on the standings page. Note that if all team members are from the same organization, the organization name can be included in the location, e.g., "Olaf Academy, Oslo, Norway". – For name, the default is a combination of your last names. For example, "Newton / Leibniz". – For location, the default is the smallest geographic entity containing all team member locations. For example, "Western Europe".
Note: Teams are contest-specific. Joining a team for this contest does not affect your participation in other contests.
-
If they do not already exist, create individual accounts for each team member.
Do not create a second account for any team member who already has one.
-
May I write a program that submits entries by bypassing my browser?
Yes.
-
May I programmatically download the standings page at regular intervals? How frequently would be reasonable?
Yes, you may programmatically download the standings page at regular intervals. Please feel free to download it as often as once per second. If you want to download the standings page more frequently than that, please contact me first.
-
I've written a little program that helps a person generate solutions manually. May I distribute the executable to other contestants?
However, if you are part of a team, you may share such tools with your teammates.
-
What topics are appropriate for the discussion group?
With only one exception, if it's related to AZsPCs then it's fine to talk about it in the discussion group. The exception is spoilers. Spoilers include:
-
• specific solutions
• detailed algorithms (yes, detailedness is subjective)If you are not sure if something would be considered a spoiler, ask me.
-
Who is Balto?
Balto was an Alaskan husky and an American hero. He achieved fame leading a team of sled dogs on the final leg of the 1925 antitoxin run to Nome (Alaska) to combat an outbreak of diphtheria. A bronze statue of Balto is installed in New York City's Central Park.