Rozwiązanie w Prologu. Niestety nie udało mi się znaleźć przenośnego modułu do arytmetyki na liczbach wymiernych, więc jest dłuższe niż mogłoby być:
:- op(500, 'xfx', '--').
expr([A|T]--X, A) :- T == X.
expr([A|B]--T, E) :- B \== T, expr([A|X]--X, B--T, E).
expr(LHead--LTail, RHead--RTail, E) :-
LHead \== LTail, RHead \== RTail,
expr(LHead--LTail, E1),
expr(RHead--RTail, E2),
myop(X), E =.. [X, E1, E2].
expr(LHead--LTail, RHead--RTail, E) :-
LHead \== LTail, RHead \== RTail,
RHead = [A|B],
LTail = [A|X],
expr(LHead--X, B--RTail, E).
myop('+').
myop('-').
myop('*').
myop('/').
eval(X, r(X, 1) ) :- integer(X).
eval(A + B, r(L, M)) :-
eval(A, r(AL, AM)), eval(B, r(BL, BM)),
L is AL * BM + BL * AM,
M is AM * BM.
eval(A - B, r(L, M)) :-
eval(A, r(AL, AM)), eval(B, r(BL, BM)),
L is AL * BM - BL * AM,
M is AM * BM.
eval(A * B, r(L, M)) :-
eval(A, r(AL, AM)), eval(B, r(BL, BM)),
L is AL * BL,
M is AM * BM.
eval(A / B, r(L, M)) :-
eval(A, r(AL, AM)), eval(B, r(BL, BM)), BL \= 0,
L is AL * BM,
M is AM * BL.
year(E, V) :-
expr([1,2,3,4,5,6,7,8,9|X]--X, E),
eval(E, r(L,M)),
0 is L mod M, % ulamek skracalny do liczby calkowitej
V is L // M, V >= 2011, V =< 2100.
:- findall(E, (year(E, V), format('~p = ~d~n', [E, V])), _), halt.
Poprawka
Poprzednia wersja miała trochę zbyt zachłanną metodę nawiasowania. Teraz powinno być już dobrze. Wyszło mi 32386 wyników (trochę sporo). Oczywiście nie uwzględniam takich rzeczy jak łączność dodawania, więc (1+2)+3 jest różnym nawiasowaniem od 1+(2+3).
Rozwiązanie nie jest zbyt eleganckie, bo wykonanie zajęło przerażające 4.5min :P Jak można przyśpieszyć ? Zamiast liczyć kolejne podproblemy od nowa, należałoby je spamiętywać jako szablony, tzn. nawiasowań 3-ch elementów za pomocą 4-rech operatorów jest 32, nie zależnie od tego jakie to elementy. Żeby wygenerować szablon dla czterech elementów wystarczy odpowiednio połączyć szablony dla 3-ch,2-ch i jednego elemenu. Itd... Oczywiście zużycię pamięci wzrośnie, ale obliczenia będą dużo krótsze.
