Programming Contest
Triangles

Introduction

Given any sequence of positive integers we can generate a triangular array of numbers by using the given sequence as the triangle’s base and then letting each remaining value in the triangle be the absolute difference of the two values immediately below it. For example, starting with the sequence (89, 78, 12, 13) we can construct this triangle:

10
55   65
11   66   1
89   78   12   13

We say that a sequence of positive integers is acceptable if no integer appears more than once in the triangle it generates. The sequence (89, 78, 12, 13), whose triangle is shown above, is acceptable. The sequence (19, 80, 51, 77) is not acceptable because its triangle contains two instances of the integer 29:

29
32   3
61   29   26
19   80   51   77

Given an acceptable sequence of positive integers, its span is the difference between the largest and smallest values in the corresponding triangle. For example, the span of (89, 78, 12, 13) is 88.

Given two acceptable sequences of the same length, the one with the smaller span is considered better. For example, (83, 73, 14, 47) is better than (89, 78, 12, 13) because their spans are 73 and 88, respectively.

The Contest

The goal is to find acceptable sequences with small spans.

Send me your best (that is, least span) acceptable sequence for each sequence length from 2 to 25. I’ll calculate a subscore for each sequence (details of the scoring system are below) and the total of your 24 subscores will be your contest score. The person with the highest contest score wins the contest. In case of a tie, I’ll choose a winner at random from among those tied.

The Prizes

First prize is $300. Second prize is $50.

How to Enter

Send an email containing your entry to bitzenbeitz@aol.com before Noon GMT on October 15, 2002. Put just the word TRIANGLES in the subject line. The body of the email should be formatted as follows.

The first line should contain your sequence of length 2. The second line should contain your sequence of length 3. And so forth through your sequence of length 25. Each sequence should be written as a list of comma-delimited integers. After your last sequence leave a blank line. After that blank line provide your name. On the line after your name provide your city (and state or province, if applicable) and country.

Do not include any extraneous information before your first sequence. Do not include any extraneous information between your last sequence and your name/location. Do not include any sequences whose lengths are less than 2 or greater than 25.

Do not use any integers greater than 99,999.

Your location information (that is, your city and country) will be published on the Triangles Contest Interim Standings page. Be certain that you do not include anything (such as your street address) that you do not want made public.

Scoring will be done by computer, so be careful in composing your email.

You may enter as often as you like, but you are only eligible to win one prize. If you enter more than once, you should send from the same email address each time.

The Scoring System

Each time you submit an entry I will merge it with your prior entries, if any. The result will be a virtual entry containing your best sequence for each of the 24 sequence lengths. I will give each of these 24 sequences a subscore from 0 to 1 and their sum will be your contest score.

I score the individual sequences as follows. If your sequence is the best sequence that was submitted for that length, I give it 1 point; otherwise I give it only a fraction of a point. The fraction is the smallest submitted span for that length, divided by your span. For example, suppose your sequence of length 6 has a span of 12 and further suppose that the smallest span that was submitted to the contest (for a sequence of length 6) was 9. Then your subscore for that sequence is 9 / 12 = 0.75.

There’s a more detailed example of the scoring in the FAQ section, below.

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 list. If your question is of a personal nature, you can send email directly to alzimmerma@aol.com.

The Discussion List

If you think you might enter the contest, it is important that you join the contest discussion list by clicking here. The discussion list serves two purposes. First, it allows people to ask for clarifications to the rules. Be aware that sometimes these requests result in changes to the rules, and the only place those changes are announced is on the list. Second, the list allows contestants to interact with each other to discuss programming techniques, results and anything else relevant to the contest.

Acknowledgment

A hearty thanks to Jean-Charles Meyrignac for inspiring this 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. I reserve the right to have French Fries with my pizza and I don’t care who laughs. In all matters contest-related, my word is law.

Frequently Asked Questions

Can you give an example of a valid contest entry?

I asked the guy who changes my oil to beta test the contest rules. Here’s what he emailed me. I’m not sure if his sequences are any good, but they are all acceptable and he got the syntax correct.

1, 3
13, 12, 3
2, 15, 11, 1
5, 40, 27, 15, 7
57, 28, 9, 63, 52, 46
96, 118, 29, 129, 127, 115, 69
228, 288, 248, 231, 143, 46, 107, 295
274, 310, 130, 242, 5, 241, 231, 22, 178
432, 468, 423, 221, 341, 63, 376, 363, 32, 276
425, 504, 339, 435, 118, 73, 480, 46, 138, 32, 102
91, 206, 384, 766, 633, 989, 241, 952, 36, 95, 16, 401
278, 668, 636, 1073, 1339, 338, 1161, 1282, 367, 42, 1276, 560, 970
203, 1736, 1026, 1455, 1656, 418, 1545, 124, 153, 833, 762, 1530, 957, 1311
3389, 1086, 2868, 1486, 414, 2692, 180, 570, 3388, 847, 2581, 179, 2215, 1922, 653
3121, 3294, 1810, 3251, 2996, 2662, 111, 1173, 1447, 1353, 160, 2255, 3018, 2045, 1725, 2707
1450, 2550, 1638, 2740, 1719, 1127, 4267, 936, 4009, 129, 112, 3430, 4333, 176, 2732, 2416, 1962
2092, 439, 4958, 6345, 862, 3258, 869, 228, 5794, 2342, 5925, 988, 6716, 5792, 6811, 1538, 4231, 3448
3539, 1558, 8819, 6845, 8788, 4540, 4618, 7656, 5178, 1846, 6970, 724, 8533, 7539, 3546, 1717, 6585, 2978, 2131
300, 676, 8752, 1901, 7248, 1238, 9995, 2811, 4027, 4312, 1728, 5940, 8627, 4951, 2153, 323, 8957, 2497, 5858, 2870
3029, 8394, 4622, 8018, 835, 9219, 9450, 1502, 13086, 10962, 11579, 2925, 1984, 1681, 11140, 12727, 3565, 263, 8743, 3346, 5060
9451, 11910, 8047, 387, 14356, 13998, 1698, 8084, 13704, 14429, 8843, 11645, 9315, 12587, 1343, 15174, 13062, 8652, 10581, 14509, 15183, 5785
512, 15214, 20606, 2440, 17727, 5975, 14204, 19938, 19642, 17737, 19510, 19174, 3861, 15237, 6754, 14146, 958, 17663, 1899, 5011, 17309, 7253, 10307
6683, 20328, 15340, 21133, 2081, 18398, 7194, 3995, 5905, 21849, 2101, 9052, 4721, 11227, 15343, 8524, 5441, 17214, 731, 3400, 17605, 18141, 2427, 12671
3825, 11493, 22750, 12170, 17578, 10782, 1003, 6146, 16297, 20037, 24688, 28934, 4847, 11503, 5965, 15014, 23727, 937, 27300, 19702, 21688, 8589, 7260, 18430, 6620

Speedy Goodwrench
Mechanicsburg, Pennsylvania, USA

Can you give an example of how the scoring system works?

Suppose that the contest required only sequences of lengths 2 through 4 and that Able, Baker and Charlie submitted the following sequences:

Able

5, 3

11, 14, 5

17, 12, 20, 19

Baker

2, 6

13, 17, 6

17, 1, 11, 19

Charlie

7, 2

9, 6, 13

15, 13, 16, 4

The triangles that are generated from these sequences are:

Able

2
5   3

6
3   9
11   14   5

4
3   7
5   8   1
17   12   20   19

Baker

4
2   6

7
4   11
13   17   6

4
6   2
16   10   8
17   1   11   19

Charlie

5
7   2

4
3   7
9   6   13

8
1   9
2   3   12
15   13   16   4

The spans of these sequences are:

Able

3

11

19

Baker

4

13

18

Charlie

5

10

15

The smallest submitted spans are:

 

3

10

15

The sequence subscores are:

Able

1.00

0.91

0.79

Baker

0.75

0.77

0.83

Charlie

0.60

1.00

1.00

The scores for each person are:

Able

2.70

Baker

2.35

Charlie

2.60

So Able is the winner.

Do I have to submit a sequence for every length from 2 to 25?

Yes. You will not be given a score unless you’ve submitted an acceptable sequence for each of the 24 sequence lengths.

How will I know that you’ve received my entry?

When I receive an entry I process it with the automated Parser/Scorer and then send a confirmation back to the submitter. Although the Parser/Scorer is automated, the process of getting entries into the Parser/Scorer is not, so it may take as long as 24 hours for you to receive your confirmation.

My email software automatically inserts line breaks into long lines. Will this cause my entry to be rejected?

If the Parser/Scorer rejects an entry but the submitter's intent is clear, I'll probably (depending on the effort involved) repair the entry. In particular, I will always fix spurious line breaks inserted by your email software.

What do you mean by the "length" of a sequence?

The length of a sequence is the number of terms it contains. For example, the length of (1, 2, 4) is 3.


Triangles Contest Results Al Zimmermann's Programming Contests

You are visitor to this site.