HHC 2019 programming contest entries

10102019, 10:24 PM
(This post was last modified: 10102019 11:50 PM by dramsey.)
Post: #1




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 SR52 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 evenodd 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! 

10112019, 12:09 AM
Post: #2




RE: HHC 2019 programming contest entries  
10112019, 12:26 AM
Post: #3




RE: HHC 2019 programming contest entries
(10102019 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 precalculating stuff was not an issue for the challenge, and pretty much everyone did it. (I wrote quite a big block of text about the precalculation used for my solution back then, which was pretty much identical to those of others.) (10102019 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 evenodd 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 threedigit 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 twodigit number, not a threedigit 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: \<< 

10112019, 12:51 AM
Post: #4




RE: HHC 2019 programming contest entries
(10102019 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 evenodd 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) 

10112019, 02:20 AM
(This post was last modified: 10112019 02:21 AM by Gene.)
Post: #5




RE: HHC 2019 programming contest entries
Here are the PDFs Dave mentioned. He had problems getting them posted.
Gene HHC 2019 Programming Contest.pdf (Size: 207.04 KB / Downloads: 19) Chuck McCord HP15.pdf (Size: 397.17 KB / Downloads: 20) Namir Shammas Prime41cHP67 .pdf (Size: 1.03 MB / Downloads: 23) Craig Bladow DM42.pdf (Size: 181.28 KB / Downloads: 18) Bill Butler RPL.pdf (Size: 163.03 KB / Downloads: 20) 

10112019, 02:22 AM
Post: #6




RE: HHC 2019 programming contest entries
Last couple of PDFs
Gene Roger Hill RPL.pdf (Size: 2.42 MB / Downloads: 26) Joey Shaprd RPL.pdf (Size: 596.63 KB / Downloads: 17) 

10132019, 09:09 PM
Post: #7




RE: HHC 2019 programming contest entries
Here are machinereadable 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:
Roger Hill: Code:
Joey Shepard: Code:


« Next Oldest  Next Newest »

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