The Riddler, 2017-07-28 edition

Here’s a link to the problems and a link to the code on Github.

Riddler Express

Not much to explain here. I figured from previous “you-versus-other-Riddlers” questions, there’d around 2000 to 2500 submissions, with a fair percentage of them being trolls who will submit 1 just for the lolz. Given this, I threw game theory out of the window and prayed for luck-of-the-draw. I figured a mid-to-high two-digit prime number might be a winner; a bit more number crunching and coin flipping resulted in my final guess of 67.

Riddler Classic

I could not think of an “elegant” solution off the top of my head, so I resorted to a brute-force approach. Our good old friend recursion becomes helpful here:

from __future__ import print_function

import math
import sys


def divs_and_mults(num, maxval):

    valid = set()

    # compute divisors
    mid = math.ceil(math.sqrt(num))
    for n in range(1, int(mid) + 1):
        if num % n == 0:
            valid.add(n)
            div = num / n
            if div != n:
                valid.add(div)
            
    # compute multiples
    mult = 2 * num
    while mult <= maxval:
        valid.add(mult)
        mult += num

    return valid


def valid_next(chain, valid, maxval):

    if len(chain) == 0:
        return set(range(1, maxval + 1))
    else:
        return valid[chain[-1]] - set(chain)


def build_recursive(chain, valid, maxval):

    longest = list(chain)

    # loop through all valid next links
    for n in valid_next(chain, valid, maxval):
        chain.append(n)
        result = build_recursive(chain, valid, maxval)
        if len(result) > len(longest):
            longest = result
        chain.pop()

    return longest


def longest_chain(maxval):

    # compute valid "next" links for all values
    valid = {}
    for n in range(1, maxval + 1):
        valid[n] = divs_and_mults(n, maxval)

    return build_recursive([], valid, maxval)


if __name__ == "__main__":

    if len(sys.argv) >= 2:
        maxval = int(sys.argv[1])
    else:
        maxval = 100

    assert maxval > 2, "invalid maximum value"

    chain = longest_chain(maxval)
    print("Found chain of length {0}.".format(len(chain)))
    print(chain)

Allow me to explain my reasoning. As with any recursive program, I looked to minimize the amount of computation required within the actual recursive call. Thus, I precomputed all divisors and multiples for each number from 1 to 100 and used these precomputed values to create a set of “valid” next links during each recursive call. The rest was easy: maintain the longest known chain and remove links from the “current” chain once all possible links are exhausted. This brute-force method works, but is unfortunately incredibly inefficient: running this with maxval = 30 takes a whopping 2.5 minutes on a single 3.4GHz i7 core, with exponentially increasing runtime as maxval grows bigger.

Following this debacle, I tried replacing the recursion with a single loop in an attempt to improve efficiency. This allowed me to collapse functions valid_next, build_recursive, and longest_chain into a single function:

def longest_chain(maxval):

    # compute valid "next" links for all values
    valid = {}
    for n in range(1, maxval + 1):
        valid[n] = divs_and_mults(n, maxval)

    # maintain a stack to store "recursive" data
    longest = []
    chain = []
    stack = []

    links = range(maxval, 0, -1)
    while True:

        # last set of links was exhausted, back up and try again
        if not links:
            if len(chain) > len(longest):
                longest = list(chain)
            if len(chain) == 0:
                break
            chain.pop()
            links = stack.pop()

        # add new link to chain
        else:
            chain.append(links.pop())
            stack.append(links)
            links = valid[chain[-1]] - set(chain)

    return longest

Easy enough, but this still took way too long – around 1.5 minutes for maxval = 30 – to run, making the problem intractable for maxval = 100 (where’s a Hadoop cluster when you need one). Undeterred, I decided to run the program that I had written for a select set of lower maxvals, hoping to see a pattern:

#    result              example chain
5    4  possibilities    [2, 4, 1, 3]
10   9  possibilities    [4, 8, 1, 5, 10, 2, 6, 3, 9]
15   13 possibilities    [6, 12, 4, 8, 1, 7, 14, 2, 10, 5, 15, 3, 9]
20   17 possibilities    [7, 14, 2, 8, 16, 4, 12, 6, 18, 9, 3, 15, 5, 10, 20, 1, 19]
25   21 possibilities    [9, 18, 6, 12, 24, 8, 16, 4, 20, 10, 1, 11, 22, 2, 14, 7, 21, 3, 15, 5, 25]
30   26 possibilities    [11, 22, 1, 13, 26, 2, 14, 28, 7, 21, 3, 27, 9, 18, 6, 12, 24, 8, 16, 4, 20, 10, 30, 15, 5, 25]
31   26 possibilities    [11, 22, 1, 13, 26, 2, 14, 28, 7, 21, 3, 27, 9, 18, 6, 12, 24, 8, 16, 4, 20, 10, 30, 15, 5, 25]
32   27 possibilities    [11, 22, 1, 13, 26, 2, 32, 16, 8, 24, 12, 6, 18, 9, 27, 3, 21, 7, 14, 28, 4, 20, 10, 30, 15, 5, 25]
33   28 possibilities    [13, 26, 1, 21, 7, 28, 14, 2, 22, 11, 33, 3, 27, 9, 18, 6, 12, 24, 8, 32, 16, 4, 20, 10, 30, 15, 5, 25]
34   28 possibilities    [13, 26, 1, 21, 7, 28, 14, 2, 22, 11, 33, 3, 27, 9, 18, 6, 12, 24, 8, 32, 16, 4, 20, 10, 30, 15, 5, 25]

One pattern jumps out very quickly: prime numbers greater than half of maxval are nowhere to be found unless they are at the beginning or end of the chain. The reason for this becomes obvious once we treat each number as a node in a graph: its only possible link to the rest of the chain is the number 1. Once we reach maxval = 34, our chain starts to miss 17 and 34 as well. These are missing for a similar reason: their only link to the rest of the chain is 1 and 2, and 2 has already been used to link other values. For maxval = 100, a similar argument can be made for 31, 62, and 93 as well. Thus, our longest possible chain for maxval = 100 will exclude 31, 37, 41, 43, 47, 53, 59, 61, 62, 67, 71, 73, 74, 79, 82, 83, 86, 89, 93, 94, and 97, which gives us a longest possible length of 79.

DISCLAIMER: This is very much an educated guess. Wish I had a bit more time to figure this one out – it’s an interesting Riddler and deserves a bit more attention.