Home > Stepping Stones > Description

Stepping Stones

Ends: 5 Nov 2022 15:00
Now: 4 Oct 2022 15:38

AZsPCs | AP Math | Description

The Stepping Stones Puzzle

Start with a positive integer n and an infinite square grid. Then proceed as follows:

  1. Place n 1's in any n cells of the grid.
  2. Place the numbers 2, 3, ..., m in order, subject to the constraint that when you place k, the sum of its eight neighbors must equal k.
Try to maximize m.

For example, given n = 2, you could achieve m = 16 by proceeding as follows:


First place two 1's
1
1

Then place the 2
1
2
1

Then place the 3
1
3 2
1

Then place the 4
4 1
3 2
1

Then place 5, 6, ..., 16
9 5 10 11
4 1
12 8 3 2 16
6 1 15
13 7 14

The Stepping Stones Puzzle is the invention of Thomas Ladouceur and Jeremy Rebenstock. It has been publicized by N.J.A.Sloane on youtube and has spawned several sequences in the OEIS, notably A337663. My thanks to Roy van Rijn for calling it to my attention.


The Contest

Submit your best solution for each of the 25 values of n in { 7, 8, ..., 31 }.

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

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

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


How to Enter

Solutions must be formatted as follows, and then entered on the Submit page.

Format each row of your solution as a comma-delimited list of integers. Use a nonpositive integer for a sequence of empty cells. Use a positive integer for a single non-empty cell. Format the entire solution as a comma-delimited list of parenthesized rows.

For example, the above solution would be formatted as follows:

(9,5,10,11), (-1,4,1), (12,8,3,2,-1,16), (-3,6,1,15), (-2,13,7,14)

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

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


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 solution (that is, the one having the most integers placed). Your "raw score" for that n is the value of the last integer placed.

  • 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 solutions for only three values of n: 4, 5 and 6. Further suppose that we have 3 entrants: Ivana, Marla and Melania.

We begin by noting the raw score of each submitted solution:

n = 4 n = 5 n = 6
Ivana 30 49 55
Marla 34 39 60
Melania 38 44 50

Next, we note the highest raw score for each value of n:

n = 4 n = 5 n = 6
Highest Raw Score 38 49 60

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

n = 4 n = 5 n = 6 Contest Score
Ivana 30 / 38 = .789 49 / 49 = 1.000 55 / 60 = .917 2.706
Marla 34 / 38 = .895 39 / 49 = .796 60 / 60 = 1.000 2.691
Melania 38 / 38 = 1.000 44 / 49 = .898 50 / 60 = .833 2.731

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


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.

    • 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 "last-name-1 / last-name-2 / ... / last-name-n". 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.

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

    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 would be disadvantaging those who either don't hear about your tool or 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 solutions
    • detailed algorithms

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