HHC 2019 programming contest entries
10-10-2019, 10:24 PM (This post was last modified: 10-10-2019 11:50 PM by dramsey.)
Post: #1
 dramsey Member Posts: 59 Joined: Dec 2013
HHC 2019 programming contest entries
Sorry for the delay, but here are the (scanned) HHC 2019 programming contest entries, along with the rules page.

The basic problem was "write a program that finds all three digits numbers equal to the sums of the cubes of their digits." It's a deliberately simple problem to explain, because there have been some problems in previous conferences where I couldn't even start to formulate an approach. I was looking for clever optimizations to a straightforward problem. Oh, my, did I get those!

If I ever do this again, I'll change a few things: in particular I won't give hints like "there are four numbers that satisfy the conditions", as it allowed for optimizations based on the fact that you knew the number of answers going in, which wasn't what I was looking for. But it was in the rules, so...

I originally came up with this problem in college, when I got my TI SR-52 calculator. It's been modified over the years, especially as indirect addressing was added to HP's RPN implementation. Tne fun part of the contest was seeing all the optimizations and tricks I hadn't thought of in the last 40 years or so. I'm not bitter.

I received entries in "modern" RPN (42/DM42), "classic" RPN (15C/41C), RPL, and Prime languages. Namir Shammas submitted multiple entries and won the overall award; Roger Hill, as usual, took the best RPL award. (I should mention here that Joe Horn was dragooned into judging the RPL entries.)

An anonymous note left at my place when I was away reads "Anonymous note to judge: A smart programmer can cut search space in half by requiring first two digits to have the same even-odd parity." I have no idea if this is true but wish the submitter had included a program...

If I ever do this again, I'll use a slightly more difficult problem. In the meantime, the zip attachment has the programming contest rules and the entries received. Enjoy!
10-11-2019, 12:09 AM
Post: #2
 Thomas Okken Senior Member Posts: 988 Joined: Feb 2014
RE: HHC 2019 programming contest entries
(10-10-2019 10:24 PM)dramsey Wrote:  Sorry for the delay, but here are the (scanned) HHC 2019 programming contest entries, along with the rules page.

I don't see any attachments...
10-11-2019, 12:26 AM
Post: #3
 3298 Member Posts: 111 Joined: Oct 2014
RE: HHC 2019 programming contest entries
(10-10-2019 10:24 PM)dramsey Wrote:  If I ever do this again, I'll change a few things: in particular I won't give hints like "there are four numbers that satisfy the conditions", as it allowed for optimizations based on the fact that you knew the number of answers going in, which wasn't what I was looking for. But it was in the rules, so...
I don't think leaving the hint out will do much there, in this class of problems people will quickly find such shortcuts anyway. My entry was intended to be a joke (as the grinning face at the end shows; since it was only submitted online it wasn't competing anyway), but it highlights the actual issue better than the others: for calculations with absolutely no input you can just optimize the calculation away. Any kind of input is fine: stack input is the norm, but system state such as date/time (as in the HHC 2018 contest) would do too. In 2018 pre-calculating stuff was not an issue for the challenge, and pretty much everyone did it. (I wrote quite a big block of text about the pre-calculation used for my solution back then, which was pretty much identical to those of others.)

(10-10-2019 10:24 PM)dramsey Wrote:  An anonymous note left at my place when I was away reads "Anonymous note to judge: A smart programmer can cut search space in half by requiring first two digits to have the same even-odd parity." I have no idea if this is true but wish the submitter had included a program...
I spotted that trick too, but after the joke submission wasn't received so well, I just thought, ehh, I have other things to work on, and dropped out of this challenge.
Anyway, the reasoning is approximately like this (just a rough sketch, I'm skipping some parts that would be required for a formal proof but simply tag them as "observation", they should be easy enough to prove):
(1) Observation: Cubes preserve the parity of their input. (It even holds for any positive integer power, but we only need the cubes here.)
(2) Observation: In even bases (such as base 10, which this challenge is issued for), the parity of a number is the same as the parity of its last digit.
(3) Therefore, each of our three-digit numbers causes the cube of its last digit to have the same parity as the original number.
(4) Observation: The sum of or difference between two numbers with the same parity is always even. The sum of or difference between two numbers with different parity is always odd.
(5) As a result, the difference between the original number and the cube of its last digit (which must be the sum of the cubes of the first two digits due to the challenge requirement) must be even.
(6) Using (4) once more, the cubes of the first two digits must have the same parity.
(7) Applying (1) in reverse, we can deduct that the first two digits themselves must have the same parity.

So for any valid first digit (1...9 because 0 would produce at most a two-digit number, not a three-digit one) you can only pick one of five digits (instead of all ten) as the second one: {1 3 5 7 9} if the first digit was one of {1 3 5 7 9}, or {0 2 4 6 8} if the first digit was one of {2 4 6 8}. There it is, the search space is cut in half.

In a UserRPL implementation that uses three nested loops to iterate over the digit choices, you could even use this result fairly efficiently:
Code:
\<<   1. 9. FOR firstdigit     firstdigit 2. MOD 9. FOR seconddigit       0. 9. FOR thirddigit         (the check if a number fits the requirements would go here...)       NEXT     2. STEP   NEXT \>>
10-11-2019, 12:51 AM
Post: #4
 Albert Chan Senior Member Posts: 944 Joined: Jul 2018
RE: HHC 2019 programming contest entries
(10-10-2019 10:24 PM)dramsey Wrote:  An anonymous note left at my place when I was away reads "Anonymous note to judge: A smart programmer can cut search space in half by requiring first two digits to have the same even-odd parity." I have no idea if this is true but wish the submitter had included a program...

Proof:

Let N = 100 a + 10 b + c

Rephrase the problem to search (a^3 - 100 a) + (b^3 - 10 b) + (c^3 - c) = 0

Mod 2: (a^3 - 100 a) + (b^3 - 10 b) + (c^3 - c) ≡ a + b + 0 ≡ 0

→ a ≡ b (mod 2)
10-11-2019, 02:20 AM (This post was last modified: 10-11-2019 02:21 AM by Gene.)
Post: #5
 Gene Moderator Posts: 992 Joined: Dec 2013
RE: HHC 2019 programming contest entries
Here are the PDFs Dave mentioned. He had problems getting them posted.

Gene

10-11-2019, 02:22 AM
Post: #6
 Gene Moderator Posts: 992 Joined: Dec 2013
RE: HHC 2019 programming contest entries
Last couple of PDFs

Gene

10-13-2019, 09:09 PM
Post: #7
 John Keith Senior Member Posts: 541 Joined: Dec 2013
RE: HHC 2019 programming contest entries
Here are machine-readable program listings for the three RPL entries.

Roger Hill's program does not run correctly and does not have the indicated size and checksum. If anyone has access to the actual program data or can figure out what the problem is, please post it here.

Joey Shepard's program returns the correct numbers but crashes at the end due to an index error for GET. The problem seems to be that the list in the program has only 8 elements. I added an extra 9 to the list in the version posted here which makes the program run correctly.

Bill Butler's program runs without errors and returns the correct numbers. I'll be damned if I can figure out how it works but it does.

Bill Butler:

Code:
 \<< 0. 9.   FOR j j DUP 3. ^ NEG DUP2 + { 0. 1. 8. 7. 4. 5. 6. 3. 2. 9. } SWAP OVER - 10. MOD DUP 3. ^ SWAP 10. * PICK3 ADD 10. * 5. ROLL ADD 4. ROLL OVER ADD ROT 4. ROLL 3. ^ ADD OVER - XOR SWAP IFT   NEXT + + + EVAL \>>

Roger Hill:

Code:
 \<< 1. 9.   FOR m m DUPDUP * * m 2. MOD m 1. + 2. ALOG * PICK3 - 3. XROOT     FOR n n DUPDUP * * DUP 2. + m 10. * n + 1. + 10. * n + 1. + 10. * SWAP - 3. XROOT 0. SWAP       FOR p DUP 2. + p DUPDUP * * + m 10. * n + p + OVER ==         IF         THEN R\->I UNROT         ELSE DROP         END       NEXT DROP 2.     STEP DROP   NEXT \>>

Joey Shepard:

Code:
 \<< 1. 9.   FOR I I I I * * 'A' STO I 100. * 'C' STO 0. { 6. 7. 8. 8. 9. 9. 9. 9. 9. } I GET     FOR J J J J * * 'B' STO J 10. * 'D' STO 0. 9.       FOR K A B K K K * * + + C D K + + DUP ROT         IF \=/         THEN DROP         END       NEXT     NEXT   NEXT { A B C D } PURGE \>>
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)