tribonacci.jl

"""
https://fivethirtyeight.com/features/can-you-make-it-to-2023/

From Dean Ballard comes a puzzle to help us ring in the new year, 2023:

The Fibonacci sequence begins with the numbers 1 and 1,2 with each new term in the
sequence equal to the sum of the preceding two. The first few numbers of the Fibonacci
sequence are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 and so on.

One can also make variations of the Fibonacci sequence by starting with a different pair
of numbers. For example, the sequence that starts with 1 and 3 is 1, 3, 4, 7, 11, 18,
29, 47, 76 and so on. Generalizing further, a “tribonacci” sequence starts with three
whole numbers, with each new term equal to the sum of the preceding three.

Many tribonacci sequences include the number 2023. For example, if you start with 23,
1000 and 1000, then the very next term will be 2023. Your challenge is to find starting
whole numbers a, b and c so that 2023 is somewhere in their tribonacci sequence,
a ≤ b ≤ c, and the sum a + b + c is as small as possible.
"""

struct Trib{T}
    a       :: T
    b       :: T
    c       :: T
    max_val :: Int64
end

function Trib(a::T, b::T, c::T, max_val) where {T}
    Trib(a, b, c, Int64(max_val))
end

struct TIter{T}
    a::T
    b::T
    c::T
end

Base.IteratorSize(::Trib) = Base.SizeUnknown()
Base.IteratorEltype(::Trib) = Base.HasEltype()

eltype(t::Trib) = eltype(t.a)

next(t::Trib) = t.a + t.b + t.c
next(t::TIter) = t.a + t.b + t.c

function Base.iterate(t::Trib)
    # This is the first iteration
    # If we've hit the limit, return nothing
    if next(t) > t.max_val
        return nothing
    end

    return (next(t), TIter(t.b, t.c, next(t)))
end

function Base.iterate(t::Trib, s::TIter)
    # If we've hit the limit, return nothing
    if next(s) > t.max_val
        return nothing
    end

    # Calculate the next result and the next TIter
    return (next(s), TIter(s.b, s.c, next(s)))
end

has_val(t::Trib, val) = val in t

"""
Finds the smallest a, b, c that produce a tribonacci sequence containing `final_val`,
where a ≤ b ≤ c
"""
function brute_force(final_val)
    # Define the best values so far. This is the maximum case
    ba = 1
    bb = 1
    bc = final_val - 2

    # Go in reverse, so that the values are always getting smaller
    for c in reverse(1:final_val)
        for b in reverse(1:c)
            for a in reverse(1:b)
                if has_val(Trib(a, b, c, final_val), final_val) &&
                   ((a + b + c) < (ba + bb + bc))
                    ba = a
                    bb = b
                    bc = c
                end
            end
        end
    end

    return ba, bb, bc
end