Home > Hexagonal Neighbors > Description

Hexagonal Neighbors

Ends: 2 Feb 2019 16:00
Now: 14 Nov 2018 22:43

AZsPCs | Hexagonal Neighbors | Description

The Problem

In this contest we will fill regular hexagonal grids1 with positive integers so that when a cell contains some integer k, the integers 1, 2, …, k-1 will be among that cell's neighbors2. Figure 1 is an example.

Figure 1 Figure 2

Figure 2 is the same as Figure 1, except that we've used blue to single out one cell and red for its neighbors. Notice that, because the blue cell is 4, its neighbors include 1, 2 and 3.


1A hexagonal grid is a grid whose cells are regular hexagons. A regular hexagonal grid is one that has six sides and has the same number of cells along each side. A regular hexagonal grid has n3 - (n - 1)3 cells, where n is the number of hexagons on each side, and is said to be "order n".

2We consider two cells to be neighbors if they share a side. Interior cells, for example, have 6 neighbors and corner cells have 3.


The Contest

For each value of n from 3 through 27 submit an order n hexagonal grid as described above. Your objective, for each n, is to maximize the sum of the grid's cells. For example, in Figure 1 the sum of the cells is 47.

For each value of n you can submit more than one grid, but only your best grid will count.

See How to Enter, below, for instructions on how to submit grids.

See The Scoring System, below, to learn how we determine the winner.

My thanks to Dan Dima for suggesting this contest.


The Prizes

The participants who finish in first or second place will each receive a crystal award plaque, engraved with the details of their accomplishment.


How to Enter

Paste your grids into the appropriate box on the Submit page and click Submit Entry. Format your grids as follows:

  • Represent each row of your grid as a comma-delimited list of integers and enclose the list in parentheses. An order n grid has 2n - 1 rows.

  • Enter the rows as a comma-delimited list.

  • To submit more than one grid at a time, separate them with semicolons. Do not put a semicolon after your last grid.

  • Include spaces and line breaks anywhere you like (except within a number) to improve readability.

For example, if you wanted to submit the grid shown above you could enter:

(4,3,2), (2,1,3,1), (3,1,5,2,4), (2,1,4,3), (2,3,1)


The Scoring System

The entrant with the highest "contest score" wins. Here's how we calculate your contest score:

  • For each of the 25 values of n, we find your best grid (that is, the one whose cells have the largest sum). Your "raw score" for that n is the total of the values in the grid, minus (3n2 - 3n + 1). For example, for the grid shown above, the raw score is 47 - 19 = 28.

  • For each of the 25 values of n, we compute your "subscore". We do this by dividing each n's raw score by the highest raw score for that n across all entrants. Every subscore therefore has a value from 0 to 1.

  • Your contest score is the sum of your 25 subscores.

If two entrants have the same contest score, we break the tie by giving preference to the entrant whose last improvement was submitted least recently.

Let's walk through a simplified example. Suppose we modify the contest by asking you to submit grids for only three values of n: 3, 4 and 5. Further suppose that we have 3 entrants: Amy, Bernadette and Penny.

We begin by summing the cell values in each submitted grid:

n = 3 n = 4 n = 5
Amy 47 112 181
Bernadette 49 107 185
Penny 51 97 180

Next, we subtract (3n2 - 3n + 1) from these sums to obtain raw scores:

n = 3 n = 4 n = 5
3n2 - 3n + 1 19 37 61
n = 3 n = 4 n = 5
Amy 28 75 120
Bernadette 30 70 124
Penny 32 60 119

We note the highest raw score for each value of n:

n = 3 n = 4 n = 5
Highest Raw Score 32 75 124

Finally, we compute the subscores and contest score for each entrant:

n = 3 n = 4 n = 5 Contest Score
Amy 28 / 32 = .875 75 / 75 = 1.000 120 / 124 = .968 2.843
Bernadette 30 / 32 = .938 70 / 75 = .933 124 / 124 = 1.000 2.871
Penny 32 / 32 = 1.000 60 / 75 = .800 119 / 124 = .960 2.760

Bernadette 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 Yahoo!. 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. You do not need to have a Yahoo! account to join the group.


My Lawyer Would Want Me To Say This

I reserve the right to discontinue the contest at any time. I reserve the right to disqualify any entry or entrant for any reason that suits me. I reserve the right to interpret the rules as I see fit. I reserve the right to change the contest rules in mid-contest. In all matters contest-related, my word is final.


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 and that it is okay to begin submitting.

    • 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.

    • Note: Teams are contest-specific. Joining a team for this contest does not affect your participation in other contests.
  • May I write a program that submits entries by bypassing my browser?

    Yes and no. If your program keeps track of your submissions and only submits improved grids, yes. Otherwise, no. For the Son of Darts contest a few years ago, there was one participant who wrote a program to exhaustively generate all possible entries and submit every one of them. Within two weeks he'd submitted over a million entries. The AZsPCs database had grown to 10 times its normal size and this individual was single-handedly responsible for 90% of the entries in the database. Please compute responsibly.

  • I've written a little program that draws grids and highlights the portions of the grid that contribute the least to the sum of the cell values. May I distribute the executable to other contestants?

    No. This is a programming contest and writing useful tools is something a programmer should be able to do for himself. That alone would be sufficient reason to disallow the distribution of such tools, but consider also that you'd be disadvantaging those who don't hear about your tool and those who can't run your executable in their environment.

  • 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 grids
    • detailed algorithms

    If you are not sure if something would be considered a spoiler, ask me.

  • After I submit a grid, the scorer shows me the grid's "canonical representation". What is that?

    To create the canonical representation of a grid, the scorer considers the 12 versions of the grid resulting from rotations and reflection and then selects the version that is lexicographically first. Representing grids canonically makes it easier to notice when two seemingly different grids are fundamentally the same.