HHC 2019 programming contest entries

[dramsey]

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!

[Thomas Okken]

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

[3298]

(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
\>>

[Albert Chan]

(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)

[Gene]

Here are the PDFs Dave mentioned. He had problems getting them posted.

Gene

  HHC 2019 Programming Contest.pdf (Size: 207.04 KB / Downloads: 28)

  Chuck McCord HP-15.pdf (Size: 397.17 KB / Downloads: 22)

  Namir Shammas Prime-41c-HP67 .pdf (Size: 1.03 MB / Downloads: 28)

  Craig Bladow DM42.pdf (Size: 181.28 KB / Downloads: 21)

  Bill Butler RPL.pdf (Size: 163.03 KB / Downloads: 24)

[Gene]

Last couple of PDFs

Gene

  Roger Hill RPL.pdf (Size: 2.42 MB / Downloads: 35)

  Joey Shaprd RPL.pdf (Size: 596.63 KB / Downloads: 23)

[John Keith]

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

[DavidM]

(10-13-2019 09:09 PM)John Keith Wrote:  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.

I realize this is an old thread, but I took a look at the hand-written notes for Roger's entry and I believe I may have translated them into a working version of his program:

Code:

\<< 1. 9. FOR m                       @ m goes from 1 to 9
  m DUPDUP * *                        @ calc m^3
  m 2. MOD                            @ lower limit of n
  m 1. + 2. ALOG * PICK3 - 3. XROOT   @ upper limit of n
  FOR n                               @ start m-loop
    n DUPDUP * *                      @ calc n^3
    DUP2 +                            @ calc m^3+n^3
    m 10. * n + 1. + 10. * n + 1. +   @ calc thing in refinement #4
      10. * SWAP - 3. XROOT
    0. SWAP                           @ limits for p
    FOR p                             @ start p-loop
      DUP2 + p DUPDUP * * +           @ calc m^3+n^3+p^3
      m 10. * n + 10. * p +           @ calc number mnp
      OVER == IF                      @ are they equal
      THEN R\->I                      @ real->integer form for better appearance
      UNROT                           @ put above other stuff
      ELSE DROP END
    NEXT DROP                         @ done with this m, n
  2. STEP DROP                        @ go to next n in steps of 2
  NEXT \>>                            @ go to next m; end of program when
                                      @   m is exhausted

The above appears to give the correct output on a 50g, but the checksum and size are still not the same as indicated in Roger's notes. Given that his stated filesize is 25 bytes smaller than the above code (265.5 vs. 290.5 for this one), I'm wondering if he used an earlier version of the program for those figures in his notes.