Description

Submit An Entry

Standings

Final Report

The Setup

You have an n × n grid filled with tokens, one token per cell. Each token is labeled with the coordinates of its cell. Each of the four edges of the grid wraps around to the opposite edge . For example, this is the grid for n = 4:

	AD ⇑	BD ⇑	CD ⇑	DD ⇑
DA⇐	AA	BA	CA	DA	⇒AA
DB⇐	AB	BB	CB	DB	⇒AB
DC⇐	AC	BC	CC	DC	⇒AC
DD⇐	AD	BD	CD	DD	⇒AD
	⇓ AA	⇓ BA	⇓ CA	⇓ DA

It is interesting to note that having the edges wrap around makes the grid topologically equivalent to the surface of a torus, as demonstrated here for n = 8.

The Task

Your task is to rearrange the tokens so that pairs of tokens that are near each other become far from each other and those that are far from each other become near. The evaluation function that we use to quantify success is given below, where we will demonstrate its use in deciding which of the following two example rearrangements for n = 5 is more successful.

The Evaluation Function

The following computation measures the extent to which a rearrangement fails to satisfy the task's objective – as with golf, you want a low score.

1. For each pair of tokens
   
   
   1. calculate the square of the distance between them in the original grid,
   2. calculate the square of the distance between them in your rearrangement grid, and
   3. multiply the two squared distances together.
   
   (Remember that, when calculating the distance between two tokens, the shortest path might require wrapping around the edges of the grid.)
   
   
2. Take the sum of these products.
   
   
3. Subtract the appropriate lower bound given in this table:
   

   n	Lower Bound
   1	0
   2	10
   3	72
   4	816
   5	3,800
   6	16,902
   7	52,528
   8	155,840
   9	381,672
   10	902,550

   n	Lower Bound
   11	1,883,244
   12	3,813,912
   13	7,103,408
   14	12,958,148
   15	22,225,500
   16	37,474,816
   17	60,291,180
   18	95,730,984
   19	146,469,252
   20	221,736,200

   n	Lower Bound
   21	325,763,172
   22	474,261,920
   23	673,706,892
   24	949,783,680
   25	1,311,600,000
   26	1,799,572,164
   27	2,425,939,956
   28	3,252,444,776
   29	4,294,801,980
   30	5,643,997,650

In an n × n grid there are n²(n² - 1) / 2 pairs of distinct tokens. For example, when n = 5 there are 300 such pairs. The following abridged tables illustrate the application of the evaluation function to Examples 1 and 2 above.

Evaluating Example 1

Table Row	Point Pair	Distance2		Product
		Original Grid	Example 1
1	AA,BA	1	5	5
2	AA,CA	4	5	20
3	AA,DA	4	2	8
• • •
24	AA,EE	2	8	16
25	BA,CA	1	5	5
26	BA,DA	4	5	20
27	BA,EA	4	4	16
• • •
47	BA,EE	5	4	20
48	CA,DA	1	8	8
49	CA,EA	4	8	32
50	CA,AB	5	5	25
• • •
69	CA,EE	5	5	25
• • •
300	DE,EE	1	5	5
Sum of products				5200
Lower bound				3800
Evaluation				1400

Evaluating Example 2

Table Row	Point Pair	Distance2		Product
		Original Grid	Example 2
1	AA,BA	1	4	4
2	AA,CA	4	5	20
3	AA,DA	4	4	16
• • •
24	AA,EE	2	5	10
25	BA,CA	1	5	5
26	BA,DA	4	1	4
27	BA,EA	4	4	16
• • •
47	BA,EE	5	5	25
48	CA,DA	1	8	8
49	CA,EA	4	1	4
50	CA,AB	5	2	10
• • •
69	CA,EE	5	1	5
• • •
300	DE,EE	1	5	5
Sum of products				4850
Lower bound				3800
Evaluation				1050

So Example 2 is the better rearrangement.

The Contest

For each value of n from 6 through 30 submit an n × n rearrangement with as low an evaluation as you can find.

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

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

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

The Prizes

The participants who finish in first or second place will each receive their choice of either

• a crystal award plaque engraved with the details of their accomplishment, or
  
  
• their choice of any item from Bathsheba Sculpture worth
  • $500 or less (for the first place participant), or
  • $100 or less (for the second place participant).

How to Enter

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

• Represent the rearrangement as a comma-delimited list of rows.
  
  
• Represent each row as a comma-delimited list of tokens, enclosed in parentheses.
  
  
• To submit more than one rearrangement at a time, separate them with semicolons. Do not put a semicolon after your last rearrangement.
  
  
• Include spaces and line breaks anywhere you like (except within a token) to improve readability.

For example, if you wanted to submit the rearrangement shown above as Example 1 you could enter:

(AE, DB, AC, ED, CA),
(CD, BD, BA, CC, BB),
(AA, EC, DD, AD, BE),
(DE, DA, EA, DC, CB),
(EB, AB, EE, CE, BC)

The more astute will have noticed that the letters from A to Z are not sufficient to uniquely label the rows or columns of a 30 × 30 grid. Please use the following characters to represent the 4 rows or columns following Z. Note that for each row or column there are two different characters you can use – the choice is yours.

Column or Row	Characters to Use
Z + 1	[	1
Z + 2	\	2
Z + 3	]	3
Z + 4	^	4

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 rearrangement – that is, the rearrangement with the lowest evaluation. Your "raw score" for that n is the evaluation for that best rearrangement.
  
  
• For each of the 25 values of n, we compute a "subscore" from 0 to 1. We do this by dividing that n's raw score into the lowest raw score for that n across all entrants.
  
  
• 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 rearrangements for only three values of n: 4, 5 and 6. And further suppose that we have 3 entrants (Siri, Daeng and Civilai) and that their best rearrangements have raw scores as follows:

	4 × 4	5 × 5	6 × 6
Siri	80	1422	20934
Daeng	912	700	10924
Civilai	418	2950	5526

We note the smallest raw score for each value of n, as follows:

	4 × 4	5 × 5	6 × 6
Smallest Raw Score	80	700	5526

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

	4 × 4	5 × 5	6 × 6	Contest Score
Siri	80 / 80 = 1.000	700 / 1422 = 0.492	5526 / 20934 = 0.264	1.756
Daeng	80 / 912 = 0.088	700 / 700 = 1.000	5526 / 10294 = 0.537	1.625
Civilai	80 / 418 = 0.191	700 / 2950 = 0.237	5526 / 5526 = 1.000	1.428

Siri has the highest contest score and therefore wins.

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 to AZsPCs+subscribe@groups.io or by visiting the AZsPCs group on groups.io/g/AZsPCs. 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.

Once you've joined, you can post messages by emailing your messages to AZsPCs@groups.io.

You can leave the group at any time by sending a blank email to AZsPCs+unsubscribe@groups.io.

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 you tell us more about the evaluation function?

  The formula is effectively equivalent to the Pearson correlation coefficient. There is an observation for each pair of tokens and a variable for each of the two grids.

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

  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 token pairs that contribute the most and the least to the output of the evaluation function. 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.

• In most AZsPCs contests, after I submit a solution the scorer shows me the solution's canonical representation. Why isn't the scorer doing that in this contest?

  In this contest, each solution belongs to an equivalence class with 128n⁴ members. For large n the AZsPCs server cannot pick one of those members to serve as the canonical representation in a reasonable amount of time. Instead, the canonical representations are determined offline in order to display them in the Final Report.
  This contest's original algorithm for determining canonical representations considered only 8n² equivalent variations on each solution. My thanks to Herbert Kociemba for showing me that each of those variations is the seed for generating 16n² additional equivalent variations.