%
% Solve the problems from
% https://www.theguardian.com/science/2025/oct/13/can-you-solve-it-the-london-cab-that-rode-into-history
%
% Author: Joachim Schimpf, 2025
% Creative Commons Attribution 4.0 International License.
%

:- lib(ic).
:- lib(branch_and_bound).


% Ramanujan's interesting taxicab number 1729

solve0 :-
        [A,B,C,D,N] #:: 1..999999,
        N #= A^3 + B^3,
        N #= C^3 + D^3,
        A #=< B,
        C #=< D,
        A #< C,
        
        bb_min(labeling([A,B,C,D,N]), N, _),
        writeln(N = A^3+B^3 and N = C^3+D^3).


% Square pair
%
% What is the smallest number that can be expressed as the sum of a
% pair of squares in two different ways?  Hint:  it is less than 100

solve1 :-
        model1(N, A, B, C, D),
        bb_min(labeling([A,B,C,D,N]), N, _),
        writeln(N=A^2+B^2 and N=C^2+D^2).

    model1(N, A, B, C, D) :-
        [A,B,C,D,N] #:: 1..99,
        N #= sqr(A) + sqr(B),
        N #= sqr(C) + sqr(D),
        A #=< B,
        C #=< D,
        A #< C.


% Strip tease
% 
% I have five strips of wood with lengths 1, 2, 7, 17 and 29
% centimetres.  It is impossible to arrange any three of these strips
% into a triangle.  I would like to add another strip of wood so that I
% still cannot take three strips and make a triangle.
% 
% How many different lengths are possible for the seventh strip, and
% what are they?  Lengths must be a whole number of centimetres.

solve2 :-
        findall(L, (model2(L), labeling([L])), Ls),
        writeln(Ls).

    model2(L) :-
        L #:: 1..29,
        Ss = [1,2,7,17,29,L],
        ( fromto(Ss,[A|Ss1],Ss1,[]) do
            ( fromto(Ss1,[B|Ss2],Ss2,[]),param(A) do
                ( fromto(Ss2,[C|Ss3],Ss3,[]),param(A,B) do
                    no_triangle(A, B, C)
                )
            )
        ).

    no_triangle(A, B, C) :-
        % exclude degenerate triangles too:
        neg (A + B #>= C and A + C #>= B and B + C #>= A).
        % only exclude proper triangles:
        %neg (A + B #> C and A + C #> B and B + C #> A).
        

% Sick sixth
% 
% I have four numbers, a, b, c, and d.
% There are six ways to multiply two of these numbers together:  ab, cd,
% ac, bd, ad, bc.
% The values of five of these products, but not necessarily in this
% order, are 2, 3, 4, 5 and 6.
% What is the value of the sixth product?
% 
% ?- solve3(Xs, Ps).
% Xs = [_440{1.0954185886776011 .. 1.0954716419854169},
%       _454{1.8256976477960021 .. 1.8257860699756954},
%       _468{2.1908371773552018 .. 2.1909432839708343},
%       _482{2.7385464716940038 .. 2.7386791049635426}]
% Ps = [2, _1441{2.3998837688408541 .. 2.4001162367884517}, 3, 4, 5, 6]
% There are 18 delayed goals.
% Yes (0.05s cpu, solution 1, maybe more)
%
% Xs = [_440{1.2649108104473876 .. 1.2649113176873663},
%       _454{1.581138513059235 .. 1.5811391471092082},
%       _468{1.8973662156710813 .. 1.8973669765310492},
%       _482{3.1622770261184696 .. 3.1622782942184169}]
% Ps = [2, _1441{2.39999903758 .. 2.4000009624203837}, 4, 3, 5, 6]
% There are 18 delayed goals.
% Yes (0.06s cpu, solution 2)

solve3(Xs, Ps) :-
        Xs = [A,B,C,D],
        Xs $:: 1..9,
        A $=< B, B $=< C, C $=< D, 
        AB $= A*B,
        AC $= A*C,
        AD $= A*D,
        BC $= B*C,
        BD $= B*D,
        CD $= C*D,
        Ps = [AB,AC,AD,BC,BD,CD],
        element(_, Ps, 2),
        element(_, Ps, 3),
        element(_, Ps, 4),
        element(_, Ps, 5),
        element(_, Ps, 6),
        
        locate(Xs, Xs, 0.0001, lin).