Home > Reversing Nearness > Description

Reversing Nearness

Ends: 26 Oct 2019 16:00
Now: 22 Aug 2019 19:41

AZsPCs | Preserving Nearness | Description

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.


"Torus from rectangle" by Kieff, from Wikimedia Commons

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.

Example 1

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
Example 2

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

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
    8155,840
    9381,672
    10902,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
    19146,469,252
    20221,736,200
    n Lower Bound
    21 325,763,172
    22 474,261,920
    23 673,706,892
    24 949,783,680
    251,311,600,000
    261,799,572,164
    272,425,939,956
    283,252,444,776
    294,294,801,980
    305,643,997,650

In an n × n grid there are n2(n2 - 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
1AA,BA15 5
2AA,CA4520
3AA,DA42 8
• • •
24AA,EE2816
25BA,CA15 5
26BA,DA4520
27BA,EA4416
• • •
47BA,EE5420
48CA,DA18 8
49CA,EA4832
50CA,AB5525
• • •
69CA,EE5525
• • •
300DE,EE15 5
Sum of products5200
Lower bound3800
Evaluation1400
Evaluating Example 2

Table
Row
Point
Pair
Distance2 Product
Original Grid Example 2
1AA,BA14 4
2AA,CA4520
3AA,DA4416
• • •
24AA,EE2510
25BA,CA15 5
26BA,DA41 4
27BA,EA4416
• • •
47BA,EE5525
48CA,DA18 8
49CA,EA41 4
50CA,AB5210
• • •
69CA,EE51 5
• • •
300DE,EE15 5
Sum of products4850
Lower bound3800
Evaluation1050

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

  • 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 the scorer considers the 8n2 versions of the grid resulting from rotating and/or reflecting and/or shifting the grid and then selects the version that is lexicographically first. Also, the four characters [\]^ are replaced by 1234. Representing grids canonically makes it easier to notice when two seemingly different grids are fundamentally the same.