11 Erlang
Part I Assignment
I’ve been planning to try out Erlang for some time.
It’s straightforward to install on Ubuntu,
just use apt install.
In the script,
we need to compile the module aoc11 stored in file aoc11.erl
and then run its main function:
$ erl
erl>c(aoc11).
aoc11:main().
Part I Assignment
-module(aoc11).
-export([main/0]).
-import(lists,[reverse/1,sort/1,sublist/3,sublist/2,nth/2,nthtail/2,map/2]).
-import(maps,[get/2]).
-import(string,[slice/3,slice/2]).
% reads lines from Fn and returns a list of strings
readlines(Fn) ->
% we should check if this fails, but ...
{ok, Data} = file:read_file(Fn),
% last expressions is returned
% here the binary strings are mapped to strings
map(fun(X) -> binary:bin_to_list(X) end, string:lexemes(Data, "\n")).
% converting a list of string tokens (lexemes) into integers
% this pattern matches the end of the recursion and reverses the result
lexemes_to_integers([], L) -> reverse(L);
lexemes_to_integers([H|T], []) ->
case H of
% just ignore the first token
"Starting" -> lexemes_to_integers(T, []);
% just ignore the second token
"items:" -> lexemes_to_integers(T, []);
_ ->
% to_integer might return an error, ignore it
{F, _} = string:to_integer(H),
% return the integer and concatenate with the recursive result
[F] ++ map(fun(X) -> {Int, _} = string:to_integer(X), Int end, T)
end.
% parse lines into maps
% this pattern matches the end of the recursion, returns reversed lists
parse_lines(_, [], A, B) -> {reverse(A), reverse(B)};
parse_lines(N, [H|T], [M|MT], [X|XT]) ->
% check the first letter of the line
H1 = slice(H, 0, 1),
case H1 of
% Monkey header
"M" ->
if
% we are at the first line, do nothing
N == 0 ->
parse_lines(N+1, T, [M] ++ MT, [X] ++ XT);
% we are at a header further in the file =>
% prepend the initialized monkey map and 0 to the two lists
true ->
parse_lines(N+1, T, [#{n=>length(MT)+1}] ++ [M] ++ MT, [0] ++ [X] ++ XT)
end;
" " ->
% non header line
H3 = slice(H, 2, 1),
case H3 of
% parse the list of items at this line
"S" ->
% tokenize the line
Toks = string:lexemes(H, ", "),
% convert the tokens into a list of integers
Ints = lexemes_to_integers(Toks, []),
% update the monkey
M2 = M#{s => Ints},
% recursively call the parsing on the rest of the lines
parse_lines(N+1, T, [M2] ++ MT, [X] ++ XT);
% parse the operation
"O" ->
% set the monkey's operator
M2 = M#{o => slice(H, 23, 1)},
H26 = slice(H, 25, 1),
% check the second operand
case H26 of
% the second operand is the original number => store "old"
"o" ->
M3 = M2#{a => "old"};
% _ branch to catch the rest
% parse the second operand
_ ->
{Y, _} = string:to_integer(slice(H, 25)),
M3 = M2#{a => Y}
end,
% update the monkey and continue parsing
parse_lines(N+1, T, [M3] ++ MT, [X] ++ XT);
% parse division argument
"T" ->
{Y, _} = string:to_integer(slice(H, 21)),
M2 = M#{d => Y},
% update the monkey and continue parsing
parse_lines(N+1, T, [M2] ++ MT, [X] ++ XT);
% parse the decision for the receiving monkey
" " ->
H5 = slice(H, 4, 1),
case H5 of
% this line contains the decision rule
"I" ->
H7 = slice(H, 7, 1),
case H7 of
% in the case the number is divisible, select monkey
"t" ->
{Y, _} = string:to_integer(slice(H, 29, 1)),
M2 = M#{t => Y + 1};
% in the non-divisible case
_ ->
{Y, _} = string:to_integer(slice(H, 30, 1)),
M2 = M#{f => Y + 1}
end,
% update monkey and continue
parse_lines(N+1, T, [M2] ++ MT, [X] ++ XT);
% this should not happen!
_ -> nil
end
end
end.
% find out what value is thrown at what monkey
monkey_turn(M) ->
% current items of monkey M
Mitems = get(s, M),
if
% nothing to throw => end the recursion
length(Mitems) == 0 -> {0, nil};
% select what to throw
true ->
% first item to throw
X = nth(1, Mitems),
% do the operation as prescribed for monkey M
Opres = operation(X, get(o, M), get(a, M)),
% divide by 3 without the reminder
New = Opres div 3,
% check the divisibility
R = New rem get(d, M),
% choose the monkey to which to throw the value
case R of
0 -> {get(t, M), New};
_ -> {get(f, M), New}
end
end.
% process items of one monkey
monkey_loop(N, L1, L2) ->
% the current monkey to process
M = nth(N, L1),
% get the thing to throw at <Next> monkey
{Next, Thing} = monkey_turn(M),
if
% nothing to throw, finish processing this monkey
Next == 0 -> {L1, L2};
true ->
% remove the item from the current monkey
Mless = M#{s => nthtail(1, get(s, M))},
% get the monkey which will receive the thing
NextM = nth(Next, L1),
% append the thing to the list of its things
NextM2 = NextM#{s => get(s, NextM) ++ [Thing]},
% immutable lists need to be updated...
Newl0 = sublist(L1, N-1) ++ [Mless] ++ nthtail(N, L1),
Newl1 = sublist(Newl0, Next-1) ++ [NextM2] ++ nthtail(Next, Newl0),
Newl2 = sublist(L2, N-1) ++ [nth(N, L2)+1] ++ nthtail(N, L2),
% continue processing things of monkey at position N
monkey_loop(N, Newl1, Newl2)
end.
% go through the monkeys
% at the end of the list => finish recursion
monkeys_loop(0, L1, L2) -> {L1, L2};
monkeys_loop(I, L1, L2) ->
% update the lists and process the Nth monkey
{L1b, L2b} = monkey_loop(length(L1) - I + 1, L1, L2),
% continue recursively
monkeys_loop(I-1, L1b, L2b).
% do this 20 times
main_loop(0, M, T) -> {M, T};
main_loop(N, M, T) ->
{M2, T2} = monkeys_loop(length(M), M, T),
main_loop(N-1, M2, T2).
% based on the operands and operator, compute the value
operation(A, "*", "old") -> A * A;
operation(A, "+", "old") -> A + A;
operation(A, "*", N) -> A * N;
operation(A, "+", N) -> A + N.
main() ->
% get the lines from the file
Lines = readlines("11.input"),
% parse the lines and create Monkey = list of monkeys (maps) and
% TX = the counts of their activity
{Monkeys, TX} = parse_lines(0, Lines, [#{n=>1}], [1]),
% main loop, update the activity
{_, Times} = main_loop(20, Monkeys, TX),
% sort and reverse to find out the two most active monkey at the beginning
T2 = reverse(sort(Times)),
% multiply the activities to get the final result
Result = nth(1, T2) * nth(2, T2),
% print out the result
io:format("Result: ~p\n", [Result]).
Part II
Since the main is now parametrized, we need to call:
$ erl
> c(aoc11).
> aoc11:main(10000, "11.input").
The code is almost the same. The principle is to limit the size of the huge numbers, it is done by modulo by the least common multiply. I shamelessly took the numbers from the input file and got the LCM from Python3:
from math import lcm
from functools import reduce
print(reduce(lcm, [<numbers>]))
The code itself is here:
-module(aoc11).
-export([main/2]).
-import(lists,[reverse/1,sort/1,sublist/3,sublist/2,nth/2,nthtail/2,map/2]).
-import(maps,[get/2]).
-import(string,[slice/3,slice/2]).
readlines(Fn) ->
{ok, Data} = file:read_file(Fn),
map(fun(X) -> binary:bin_to_list(X) end, string:lexemes(Data, "\n")).
lexemes_to_integers([], L) -> reverse(L);
lexemes_to_integers([H|T], []) ->
case H of
"Starting" -> lexemes_to_integers(T, []);
"items:" -> lexemes_to_integers(T, []);
_ ->
{F, _} = string:to_integer(H),
[F] ++ map(fun(X) -> {Int, _} = string:to_integer(X), Int end, T)
end.
parse_lines(_, [], A, B) -> {reverse(A), reverse(B)};
parse_lines(N, [H|T], [M|MT], [X|XT]) ->
H1 = slice(H, 0, 1),
case H1 of
"M" ->
if
N == 0 ->
parse_lines(N+1, T, [M] ++ MT, [X] ++ XT);
true ->
parse_lines(
N+1,
T,
[#{n=>length(MT)+1}] ++ [M] ++ MT,
[0] ++ [X] ++ XT
)
end;
" " ->
H3 = slice(H, 2, 1),
case H3 of
"S" ->
Toks = string:lexemes(H, ", "),
Ints = lexemes_to_integers(Toks, []),
M2 = M#{s => Ints},
parse_lines(N+1, T, [M2] ++ MT, [X] ++ XT);
"O" ->
XX = slice(H, 23, 1),
if
XX == "*" -> M2 = M#{o => 1};
true -> M2 = M#{o => 0}
end,
H26 = slice(H, 25, 1),
case H26 of
"o" ->
M3 = M2#{a => 0};
_ ->
{Y, _} = string:to_integer(slice(H, 25)),
M3 = M2#{a => Y}
end,
parse_lines(N+1, T, [M3] ++ MT, [X] ++ XT);
"T" ->
{Y, _} = string:to_integer(slice(H, 21)),
M2 = M#{d => Y},
parse_lines(N+1, T, [M2] ++ MT, [X] ++ XT);
" " ->
H5 = slice(H, 4, 1),
case H5 of
"I" ->
H7 = slice(H, 7, 1),
case H7 of
"t" ->
{Y, _} = string:to_integer(slice(H, 29, 1)),
M2 = M#{t => Y + 1};
_ ->
{Y, _} = string:to_integer(slice(H, 30, 1)),
M2 = M#{f => Y + 1}
end,
parse_lines(N+1, T, [M2] ++ MT, [X] ++ XT);
_ -> nil
end
end
end.
monkey_turn(M) ->
Mitems = get(s, M),
if
length(Mitems) == 0 -> {0, nil};
true ->
New = operation(nth(1, Mitems), get(o, M), get(a, M)),
R = New rem get(d, M),
case R of
% normalize with the least common multiple of all items
0 -> {get(t, M), New rem 1582340793412478299200};
_ -> {get(f, M), New rem 1582340793412478299200}
end
end.
monkey_loop(N, L1, L2) ->
M = nth(N, L1),
{Next, Thing} = monkey_turn(M),
if
Next == 0 -> {L1, L2};
true ->
Mless = M#{s => nthtail(1, get(s, M))},
NextM = nth(Next, L1),
NextM2 = NextM#{s => reverse([Thing] ++ reverse(get(s, NextM)))},
Newl0 = sublist(L1, N-1) ++ [Mless] ++ nthtail(N, L1),
Newl1 = sublist(Newl0, Next-1) ++ [NextM2] ++ nthtail(Next, Newl0),
Newl2 = sublist(L2, N-1) ++ [nth(N, L2)+1] ++ nthtail(N, L2),
monkey_loop(N, Newl1, Newl2)
end.
monkeys_loop(0, L1, L2) -> {L1, L2};
monkeys_loop(I, L1, L2) ->
{L1b, L2b} = monkey_loop(length(L1) - I + 1, L1, L2),
monkeys_loop(I-1, L1b, L2b).
main_loop(0, M, T) -> {M, T};
main_loop(N, M, T) ->
{M2, T2} = monkeys_loop(length(M), M, T),
main_loop(N-1, M2, T2).
% slightly improved operation matching
operation(A, 1, 0) -> A * A;
operation(A, 0, 0) -> A + A;
operation(A, 1, N) -> A * N;
operation(A, 0, N) -> A + N.
% main is now parametrized: number of loops, filename
main(Loops, Fn) ->
Lines = readlines(Fn),
{Monkeys, TX} = parse_lines(0, Lines, [#{n=>1}], [1]),
{_, Times} = main_loop(Loops, Monkeys, TX),
T2 = reverse(sort(Times)),
Result = nth(1, T2) * nth(2, T2),
io:format("Result: ~p\n", [Result]).
Some good resources I used
What I learned
- Tuples
{atom1, atom2}. - Maps
MAP#{attr}. erlang:display(Term)will print anything, good for debugging.- Erlang code can be updated online.
- The documentation is fine, but since Erlang has a small community, it’s hard to find examples online.
- For lists of small integers, Erlang guesses it might be a string and prints it as such.
- Erlang errors during compilation are not very useful…
- Profiling with
fprof:apply(module,function,[param1,param2, ...]). fprof:profile(). fprof:analyse(). - Erlang, similar to Python, has unlimited integer arithmetics.
published: 2022-12-11
last modified: 2023-01-21
https://vit.baisa.cz/notes/code/advent-of-code-2022/11/
last modified: 2023-01-21
https://vit.baisa.cz/notes/code/advent-of-code-2022/11/