Solution to a riddler

middle_square_method.jl

"""
# [Middle Square Method](https://fivethirtyeight.com/features/can-you-solve-middle-square-madness/)

Thanks to Twitter, I recently became aware of the “middle-square method” for generating
pseudorandom numbers (numbers that appear random, but are derived in a deterministic
sequence).

This week, let's look at the middle-square method for generating pseudorandom four-digit
numbers. First, we start with a four-digit number, such as 9,876. If we square it, we
get the eight-digit number 97,535,376. Our next pseudorandom number is taken from the
middle four digits of that square: 5,353. And to get the next pseudorandom number, we
can square 5,353, which gives us 28,654,609, the middle four digits of which are 6,546.

Of course, many four-digit numbers have a square that's seven digits rather than eight.
And in a sequence of middle-square numbers, you also might encounter smaller numbers
whose squares have six or fewer digits. In these cases, you can append zeros to the
beginning of the square until you have eight total digits, and once again take the
middle four digits.

No matter what initial four-digit number you pick, your sequence of pseudorandom numbers
will eventually repeat itself in a loop. If you want the longest sequence of such
numbers before any repetition occurs, what starting number should you pick? And how many
unique numbers are in the sequence?
"""

"""
    next_middle_square(x::Int)::Int

Calculates the next middle square pseudo-random number
"""
function next_middle_square(x::Int)::Int
    parse(Int, string(x^2, pad = 8)[3:6])
end

"""
    how_many_till_repeat(starting_number::Int, n_reps::Int = 100_000)::Int

From this starting number, how many pseudo-rnadom numbers can you get until a repeat
occurs?
"""
function how_many_till_repeat(starting_number::Int, n_reps::Int = 100_000)::Int
    curr = starting_number
    seen = Set{Int}()
    for cnt = 1:n_reps
        new = next_middle_square(curr)
        if new ∈ seen
            return cnt
        else
            curr = new
            push!(seen, new)
        end
    end
    error("Reached max runs. Bailing out")
end

function get_best()
    sort([n => how_many_till_repeat(n) for n = 1000:9999], by = x -> x.second, rev = true)
end