HHC 2019 programming contest entries

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