% file: "smith.erl"
-ifdef(ETOS).
-define(IS_INTEGER(X),is_integer(X)).
-else.
-define(IS_INTEGER(X),integer(X)).
-endif.
-module(smith).
-export([?MODULE/0]).
?MODULE() ->
Tops = generate_sequences(100,32,1),
Side = generate_sequence(32,0),
statistics(runtime),
R = loop(2,Tops,Side,0),
{R,R =:= 16}.
max(A,B) when ?IS_INTEGER(A), ?IS_INTEGER(B) ->
if
A > B -> A;
true -> B
end.
alpha_beta_penalty(A,B) when ?IS_INTEGER(A), ?IS_INTEGER(B) -> max(A-4,B-1).
generate_sequence(Length,R) when ?IS_INTEGER(Length) ->
if
Length == 0 -> [];
true -> [R rem 10 | generate_sequence(Length-1,
(R * 11 + 1237501)
rem 10067)]
end.
generate_sequences(0,_,_) -> [];
generate_sequences(N,Length,R) when ?IS_INTEGER(N), ?IS_INTEGER(Length) ->
[generate_sequence(Length, R) | generate_sequences(N-1,Length,R+1)].
match_entry(Top,Side,UpperLeft,Upper,Left) when ?IS_INTEGER(Top), ?IS_INTEGER(Side) ->
MeLeft = alpha_beta_penalty(element(3, Left), element(1, Left)),
MeUpper = alpha_beta_penalty(element(3, Upper), element(2, Upper)),
MeUpperLeft =
if
Top == Side ->
max(MeLeft,
max(MeUpper,
max(element(3,UpperLeft)+1,0)));
true ->
max(MeLeft,
max(MeUpper,
max(element(3,UpperLeft),0)))
end,
{MeLeft, MeUpper, MeUpperLeft,
max(MeUpperLeft,
max(element(4,Left),
max(element(4,Upper),element(4,UpperLeft))))}.
match_zero_entry(Top,Side,{Left,_,UpperLeft,Max}) when ?IS_INTEGER(Top), ?IS_INTEGER(Side) ->
ELeft = alpha_beta_penalty(UpperLeft, Left),
Weight = max(1-abs(Side-Top),0),
EUpperLeft = max(max(ELeft,max(1-abs(Side-Top),0)),0),
EMax = max(max(Max,EUpperLeft),0),
{ELeft, -1, EUpperLeft, EMax}.
match(Tops,Side,Prev,UpperLeft,Left) ->
match0(Tops, Side, Prev, UpperLeft, Left, [], none).
match0([],_,_,_,_,Acc,Last) -> {Acc,Last};
match0([Top|Tops],Side,[Upper|Prev],UpperLeft,Left,Acc,Last) when
?IS_INTEGER(Top), ?IS_INTEGER(Side) ->
E = match_entry(Top, Side, UpperLeft, Upper, Left),
match0(Tops, Side, Prev, Upper, E, [E|Acc], E);
match0([Top|Tops],Side,none,UpperLeft,Left,Acc,Last) when
?IS_INTEGER(Top), ?IS_INTEGER(Side) ->
E = match_zero_entry(Top, Side, Left),
match0(Tops, Side, none, UpperLeft, E, [E|Acc], E).
match_two_seq(Side,Top,Prev) ->
match_two_seq0(Side, Top, Prev, none).
match_two_seq0([],_,_,Result) -> Result;
match_two_seq0([S|Side],Top,Prev,Acc) when ?IS_INTEGER(S) ->
{Row,Result} = match(Top,S,Prev,{0,0,0,0},{0,0,0,0}),
match_two_seq0(Side, Top, Row, Result).
match_sequences(Tops,Side) ->
match_sequences0(Tops, Side, -9999999).
match_sequences0([],_,MaxResult) -> MaxResult;
match_sequences0([Top|Tops],Side,CrntResult) ->
Result = element(4, match_two_seq(Top, Side, none)),
match_sequences0(Tops, Side, max(CrntResult, Result)).
loop(0,Tops,Side,R) -> R;
loop(N,Tops,Side,R) -> loop(N-1,Tops,Side,match_sequences(Tops,Side)).
