-module(ninetynine).
-compile(export_all).

%%%%%%%%%
%% P01 %%
%%%%%%%%%
mylast(A) -> mylast(A,[]).

mylast([],B) -> B;
mylast([H|T],A) ->
  mylast(T,H).

%%%%%%%%%
%% P02 %%
%%%%%%%%%
mybutlast(A) -> mybutlast(A, [], []).

mybutlast([], A, B) -> A;
mybutlast([H|T], A, B) ->
  mybutlast(T, B, H).

%%%%%%%%%
%% P03 %%
%%%%%%%%%
kthelem(A, N) -> kthelem(A, 1, N).

kthelem([], _, _) -> {error, out_of_range};
kthelem([H|T], Current, Current) -> H;
kthelem([H|T], Current, N) ->
  kthelem(T, Current+1, N).

%%%%%%%%%
%% P04 %%
%%%%%%%%%
len(A) -> len(A, 0).

len([], Len) -> Len;
len([H|T], Len) -> len(T, Len+1).

%%%%%%%%%
%% P05 %%
%%%%%%%%%
reverse([]) -> [];
reverse([H|T]) -> reverse(T,[H]).

reverse([], L) -> L;
reverse([H|T], L) ->
  reverse(T, [H|L]).

%%%%%%%%%
%% P06 %%
%%%%%%%%%
palindrome(A) ->
  B=reverse(A),
  case A of
   B -> true;
   _ -> false
  end.

%%%%%%%%%
%% P07 %%
%%%%%%%%%
%% I had difficulties with this one, and ended up
%% getting a hint or three from lists:flatten/1’s source code :-(
%% and it's quite clever
flatten(List) ->
%% Note the guard here supposed to protect us
%% against calling it with something else as a list
%% would be better to return a custom error
flatten(List, []).

flatten([H|T], Tail) when is_list(H) ->
 flatten(H, flatten(T, Tail));
flatten([H|T], Tail) ->
 [H|flatten(T, Tail)];
flatten([], Tail) ->
 Tail.

%%%%%%%%%
%% P08 %%
%%%%%%%%%
compress(A) -> compress(A, [], []).
compress([], L, _) -> flatten(L);
compress([H|T], L, H) -> compress(T, L, H);
compress([H|T], L, X) -> compress(T, [L,H], H).

%%%%%%%%%
%% P09 %%
%%%%%%%%%
pack(A) -> pack(A,[],[],[]).
pack([], X, Liste, Acc) -> reverse([flatten([Acc,X])|Liste]);
pack([H|T], H, Liste,Acc) ->
  pack(T, H, Liste, [H,Acc]);
pack([H|T], [], Liste, Acc) ->
  pack(T, H, Liste, [H]);
pack([H|T], X, Liste, []) ->
  pack(T, H, [[X]|Liste], []);
pack([H|T], X, Liste, Acc) ->
  pack(T, H, [flatten([Acc,X])|Liste], []).

%%%%%%%%%
%% P10 %%
%%%%%%%%%
runlen(A) -> runlen(A,[],[],[]).
runlen([], X, Liste, Acc) -> 
%% we are done compacting, let's do the sums
  runlengths([flatten([Acc,X])|Liste],[]);

runlen([H|T], H, Liste,Acc) ->
  runlen(T, H, Liste, [H,Acc]);
runlen([H|T], [], Liste, Acc) ->
  runlen(T, H, Liste, [H]);
runlen([H|T], X, Liste, []) ->
  runlen(T, H, [[X]|Liste], []);
runlen([H|T], X, Liste, Acc) ->
  runlen(T, H, [flatten([Acc,X])|Liste], []).

%% Compute sums
runlengths([],Acc) -> Acc;
runlengths([H|T],Acc) ->
%% Extract one element
  [Elem|_]=H,
%% Loop by replacing the list of identical elements
%% by a list of [Length, Element]
%% There's no need to reverse the list expressly,
%% as we do in many other examples
%% since we are doing it here:
  runlengths(T,[[len(H), Elem]|Acc]).

%%%%%%%%%
%% P11 %%
%%%%%%%%%
runlen2(A) -> runlen2(A,[],[],[]).

runlen2([], X, Liste, Acc) -> 
  runlengths2([flatten([Acc,X])|Liste],[]);

runlen2([H|T], H, Liste,Acc) ->
  runlen2(T, H, Liste, [H,Acc]);
runlen2([H|T], [], Liste, Acc) ->
  runlen2(T, H, Liste, [H]);
runlen2([H|T], X, Liste, []) ->
  runlen2(T, H, [[X]|Liste], []);
runlen2([H|T], X, Liste, Acc) ->
  runlen2(T, H, [flatten([Acc,X])|Liste], []).

%% Compute sums
runlengths2([],Acc) -> Acc;
runlengths2([H|T],Acc) ->
  [Elem|_]=H,
  Len=len(H),
  case Len of
    1 -> runlengths2(T,[[Elem]|Acc]);
    _ -> runlengths2(T,[[len(H), Elem]|Acc])
  end.

%%%%%%%%%
%% P12 %%
%%%%%%%%%
decoderunlength(A) -> decoderunlength(A, []).

decoderunlength([], Acc) -> reverse(Acc);
decoderunlength([H|T], Acc) ->
  Len=len(H),
  case Len of
    1 -> decoderunlength(T, [H|Acc]);
    _ -> decoderunlength(T, [deflate(H)|Acc])
  end.

%% Auxilliary routine, will also be used later.
%% Takes a length and an element
%% and returns a list with Len elements
%% deflate(4, a) ==> [a, a, a, a]
deflate([Len, Elem]) -> deflate(Elem, 1, Len, [Elem]).

deflate(Elem, Current, Current, Liste) -> Liste;
deflate(Elem, Current, Len, Liste) ->
  deflate(Elem, Current+1, Len, [Elem|Liste]).

%%%%%%%%%
%% P14 %%
%%%%%%%%%
dupli(A) -> dupli(A, []).
dupli([], Acc) -> reverse(Acc);
dupli([H|T], Acc) ->
  dupli(T, [H,H|Acc]).

%%%%%%%%%
%% P15 %%
%%%%%%%%%
repli(A, Times) -> repli(A, Times, []).

repli([], Times, Acc) -> reverse(flatten(Acc));
repli([H|T], Times, Acc) ->
  repli(T, Times, [deflate([Times, H])|Acc]).

%%%%%%%%%
%% P16 %%
%%%%%%%%%
dropnth(A, N) -> dropnth(A, 1, N, []).

dropnth([], _, _, Acc) -> reverse(Acc);
dropnth([H|T], Current, Current, Acc) ->
  dropnth(T, 1, Current, Acc);
dropnth([H|T], Current, N, Acc) ->
  dropnth(T, Current+1, N, [H|Acc]).

%%%%%%%%%
%% P17 %%
%%%%%%%%%
split(A, Len) -> split(A, 1, Len, []).

split([], _, _, Acc) -> reverse(Acc);
split([H|T], Current, Current, Acc) -> [reverse([H|Acc])|[T]];
split([H|T], Current, Len, Acc) ->
  split(T, Current+1, Len, [H|Acc]).

%%%%%%%%%
%% P18 %%
%%%%%%%%%
slice(A, Start, End) when Start > End ->
  {error, start_point_greater_than_endpoint};
slice(A, 0, End) ->
  {error, start_point_is_null};
slice(A, Start, End) -> slice(A, 1, Start, End, []).

slice([], End, Start, End, Acc) -> reverse(Acc);
slice([H|T], End, Start, End, Acc) -> reverse([H|Acc]);
slice([H|T], Start, Start, End, Acc) ->
  slice(T, Start+1, Start, End, [H|Acc]);
slice([H|T], Current, Start, End, _) when Current < Start ->
  slice(T, Current+1, Start, End, []);
slice([H|T], Current, Start, End, Acc) ->
  slice(T, Current+1, Start, End, [H|Acc]).

%%%%%%%%%
%% P19 %%
%%%%%%%%%
lrot(A, N) -> lrot(A, 1, N, []).
lrot([], _, _, Acc) -> {error};
lrot([H|T], Current, Current, Acc) ->
  flatten([T|reverse([H|Acc])]);
lrot([H|T], Current, N, Acc) ->
  lrot(T, Current+1, N, [H|Acc]).

%%%%%%%%%
%% P20 %%
%%%%%%%%%
drop(List, N) -> drop(List, 1, N, []).
drop([], _, _, Acc) -> reverse(Acc);
drop([H|T], Current, Current, Acc) -> flatten(reverse([T|Acc]));
drop([H|T], Current, N, Acc) ->
  drop(T, Current+1, N, [H|Acc]).

%%%%%%%%%
%% P21 %%
%%%%%%%%%
insertAt(Elem, Liste, Position) -> insertAt(Liste, 1, Position, Elem, []).
insertAt([], _, _, Elem, Acc) -> reverse(Acc);
insertAt([H|T], Current, Current, Elem, Acc) -> flatten(reverse([T, H, Elem|Acc]));
insertAt([H|T], Current, N, Elem, Acc) ->
  insertAt(T, Current+1, N, Elem, [H|Acc]).

%%%%%%%%%
%% P22 %%
%%%%%%%%%
range(Start, End) ->
  if
   Start == End -> [Start];
   Start > End -> {error, "Start > End"};
   Start < End -> range(Start, End, [])
  end.

range(End, End, Acc) -> reverse([End|Acc]);
range(Start, End, Acc) ->
  range(Start+1, End, [Start|Acc]).

%%%%%%%%%
%% P23 %%
%%%%%%%%%
rndSelect(Liste, Len) -> rndSelect(Liste, Len, []).
rndSelect([], _, Acc) -> reverse(Acc);
rndSelect(Liste, 0, Acc) -> reverse(Acc);
rndSelect(Liste, N, Acc) ->
  L=len(Liste),
  Rnd=random:uniform(L),
  [NewList, Number]=extract(Liste, 1, Rnd, []),
  rndSelect(NewList, N-1, [Number|Acc]).

%% Extracts element X of List
%% and returns [NewList, Element]
extract([H|T], Current, Current, Acc) -> [flatten(reverse([T|Acc])), H];
extract([H|T], Current, N, Acc) ->
  extract(T, Current+1, N, [H|Acc]).

%%%%%%%%%
%% P24 %%
%%%%%%%%%
lottoSelect(N, Max) ->
  rndSelect(range(1,Max),N).

%%%%%%%%%
%% P25 %%
%%%%%%%%%
rndPermu(Liste) -> rndSelect(Liste, len(Liste)).

%%%%%%%%%
%% P26 %%
%%%%%%%%%
%% main entry point for this exercice is combi/2
combi(Liste, Number) -> reverse(cb(Liste, Number, [])).

%% This routine extracts the N leftmos elements f the list
%% Used in cb2
left(Liste, N) -> left(Liste, 1, N, []).
left([], _, _, _) -> {error};
left([H|T], Current, Current, Acc) -> reverse([H|Acc]);
left([H|T], Current, N, Acc) ->
  left(T, Current+1, N, [H|Acc]).

cb(List, Num, Acc) ->
  A=cb2(List, Num, Acc),
  [H|T]=List,
  Len=len(T)+1,
  case Len of
    Num -> A;
    _   -> cb(T, Num, A)
  end.

cb2(List, Num, Acc) -> reverse(cb2(List, Num, 2, Acc, List)).

cb2(List, Num, X, Acc, Backup) ->
  Len=len(List),
  case Len of
    Num ->
      % Pop Element X and loop
      X1=X+1,
      Len2=len(Backup),
      case Num of
        Len2 -> reverse([List|Acc]); % Done
        _ ->
         NewList=drop(Backup, 2),
         cb2(NewList, Num, X1, [List|Acc], NewList)
      end;
    _   ->
      A1=left(List, Num),
      NewList=drop(List,Num),
      cb2(NewList, Num, X, [A1|Acc], Backup)
  end.