I wanted to use Prolog today, and this is a good task for it. Prolog is a really cool language. It's one of the few logic programming languages, which are built around declaratively stating facts and relationships. It then uses a backtracking unification engine to find solutions to queries. It's vaguely like pattern-matching in functional languages, but is used to drive the entire program through backtracking.
A predicate like length(List, N) might normally be called like
length([1,2,3], N)., which will bind N to the length of the list,
but if it's written the right way (which this particular example is),
you can also call it as length(List, 3)., which will generate a list
of 3 unbound elements, each of which can be unified with anything, or
even as length(List, N), which will generate lists of 0, 1, 2, etc
unbound elements. You can combine predicates with , (read "and"),
and you can define your own predicates with :- (read
"if"). Variables start with uppercase letters. A period ends a
statement of fact.
So you can define:
president(reagan).
president(hw_bush).
president(clinton).
president(w_bush).
alive(clinton).
alive(w_bush).
living_president(Person) :- president(Person), alive(Person).
Where living_president(Person) :- president(Person), alive(Person).
can be read as "Person is a living_president if they are a
president and they are alive." It will initially use president
to find the first president in the data, reagan. Then
alive(reagan) is false, so it will backtrack and try hw_bush, but
alive(hw_bush) is also false. Finally, it will try clinton, and
alive(clinton) is a fact we have, so it will offer it as a solution.
Backtracking can still be triggered, however, in a situation like
living_president(P), P \= clinton., where the not-equals operator
(\=) will trigger backtracking when it fails. When a solution is
offered in the REPL, you can trigger backtracking manually by typing
;.
Prolog is such a fascinating language. More people should learn it!
The first step of the task is to find the lists of integers in a list of lists which are in an order that satisfies a list of constraints. The constraints are of the form 'X|Y', which means that X must appear before Y in the sequence. We want to sum the middle number of each of these lists.
We can start with the IO, because it's straightforward. Our main/0
predicate will look like:
main :-
open('input.txt', read, Stream),
read_constraints(Stream, Constraints),
read_updates(Stream, Updates),
close(Stream),
middle_sum(Updates, Constraints, MiddleSum),
print(MiddleSum),
nl.
Which is to say, it will open input.txt for reading, read the
constraints (up to the first blank line), then read the updates (up to
the end of the file), close the file, find the sum of middle numbers
matching the read constraints, print them, and then print a newline.
Reading constraints and updates are both very similar. We use
read_line_to_string/2 to read Line from Stream, and then check
whether Line is at our end condition. If it is, we bind the result
to an empty list, otherwise we parse the line into a Prolog data
structure, recrusively read another element from the stream, and
finally bind the output to our result consed onto the recursive
result. An if/else structure can be represented in Prolog as ( <pred> -> <then> ; <else> ), where the branch is selected based on whether
or not <pred> unifies.
read_constraints(Stream, Constraints) :-
read_line_to_string(Stream, Line),
( Line = ""
-> Constraints = []
; parse_constraint(Line, Constraint),
read_constraints(Stream, RestConstraints),
Constraints = [Constraint|RestConstraints]
).
read_updates(Stream, Updates) :-
read_line_to_string(Stream, Line),
( Line = end_of_file
-> Updates = []
; parse_update(Line, Update),
read_updates(Stream, RestUpdates),
Updates = [Update|RestUpdates]
).
For parse_constraint/2 and parse_update/2, we can make use of the
built-in split_string/4 for splitting a string by a delimiter, as
well as the atom_number/2 predicate for reading an integer from a
string. We'll represent constraints as pairs with -/2; X-Y in
Prolog is like (cons x y) in Lisp.
parse_constraint(Line, X-Y) :-
split_string(Line, "|", "", [XString, YString]),
atom_number(XString, X),
atom_number(YString, Y).
parse_update(Line, Update) :-
split_string(Line, ",", "", UpdateStrings),
maplist(atom_number, UpdateStrings, Update).
Next up is to implement middle_sum/3, which takes an update, a list
of constraints, and an unbound variable for the sum of the middle
elements of updates which do not violate any constraints. Its
definition isn't too hard: if there is at least one update, and it has
no violations, then we add the middle element to our running
sum. Otherwise, if there's an element in the update, we don't sum it,
and continue on with the rest of the update. If the update is empty,
the middle sum is 0:
middle_sum([Update|Updates], Constraints, Sum) :-
violations(Update, Constraints, []),
middle_sum(Updates, Constraints, RestSum),
middle(Update, Middle),
Sum is RestSum + Middle.
middle_sum([_|Updates], Constraints, Sum) :-
middle_sum(Updates, Constraints, Sum).
middle_sum([], _, 0).
middle/2 just binds its second argument to the middle element of its first. It can be read, "middle(List, Middle) is true if the length of List is Length, HalfIndex is the integer division result of Length and 2, and the 0-indexed HalfIndexth element of List is Middle:
middle(List, Middle) :-
length(List, Length),
HalfIndex is div(Length, 2),
nth0(HalfIndex, List, Middle).
Then to calculation violations, we need to loop over constraints and
for each of them, check that the starting bound never appears after
the ending bound. This will depend on an after/3 predicate that
we'll right in a second. Aside from that, \+ is a "not" operator
that negates the result of a predicate. We use it to ensure that the
only time we don't add a violation is when there was not one.
violations(Updates, [X-Y|Constraints], [X-Y|Violations]) :-
after(X, Y, Updates),
violations(Updates, Constraints, Violations).
violations(Updates, [X-Y|Constraints], Violations) :-
\+ after(X, Y, Updates),
violations(Updates, Constraints, Violations).
violations([], _, _).
violations(_, [], []).
after/3 is pretty simple, and is a good demonstration of the
declarative, Prolog way of thinking. X is after Y in List if
List could be created by prepending some list (_) to a list that
begins with Y and follows with Tail, and X is a member of that
Tail:
after(X, Y, List) :-
append(_, [Y|Tail], List),
member(X, Tail).
That's all we need to compute our solution. Here it is all together:
violations(Updates, [X-Y|Constraints], [X-Y|Violations]) :-
after(X, Y, Updates),
violations(L, Constraints, Violations).
violations(Updates, [X-Y|Constraints], Violations) :-
\+ after(X, Y, Updates),
violations(Updates, Constraints, Violations).
violations([], _, _).
violations(_, [], []).
after(X, Y, List) :-
append(_, [Y|Tail], List),
member(X, Tail).
middle(List, Middle) :-
length(List, Length),
HalfIndex is div(Length, 2),
nth0(HalfIndex, List, Middle).
middle_sum([Update|Updates], Constraints, Sum) :-
violations(Update, Constraints, []),
middle_sum(Updates, Constraints, RestSum),
middle(Update, Middle),
Sum is RestSum + Middle.
middle_sum([_|Updates], Constraints, Sum) :-
middle_sum(Updates, Constraints, Sum).
middle_sum([], _, 0).
parse_constraint(Line, X-Y) :-
split_string(Line, "|", "", [XString, YString]),
atom_number(XString, X),
atom_number(YString, Y).
parse_update(Line, Update) :-
split_string(Line, ",", "", UpdateStrings),
maplist(atom_number, UpdateStrings, Update).
read_constraints(Stream, Constraints) :-
read_line_to_string(Stream, Line),
( Line = ""
-> Constraints = []
; parse_constraint(Line, Constraint),
read_constraints(Stream, RestConstraints),
Constraints = [Constraint|RestConstraints]
).
read_updates(Stream, Updates) :-
read_line_to_string(Stream, Line),
( Line = end_of_file
-> Updates = []
; parse_update(Line, Update),
read_updates(Stream, RestUpdates),
Updates = [Update|RestUpdates]
).
main :-
open('input.txt', read, Stream),
read_constraints(Stream, Constraints),
read_updates(Stream, Updates),
close(Stream),
middle_sum(Updates, Constraints, MiddleSum),
print(MiddleSum),
nl.
For task 2, we need to modify the script so that we only look at the updates that do have violations, we sort them so that they don't have violations, and then sum the middle numbers.
This is a pretty simple change. We start by updating middle_sum/3 so
that we fix violations before grabbing the middle element:
middle_sum([Update|Updates], Constraints, Sum) :-
violations(Update, Constraints, [_|_]),
middle_sum(Updates, Constraints, RestSum),
fix_violations(Update, Constraints, ReorderedUpdate),
middle(ReorderedUpdate, Middle),
Sum is RestSum + Middle.
To implement fix_violations/3, we'll use an auxiliary function
fix_violations_aux/4 which takes an additional accumulator parameter in
which we'll build up the fixed version of the update. The base case,
when there are no elements in the update left to insert, is a simple
rule that the accumulator is the reordered update at that point. If
the list has at least one element, then we insert it so that it
doesn't violate any constraints, and then continue inserting the
remainder of the update:
fix_violations(Update, Constraints, ReorderedUpdate) :-
fix_violations_aux(Update, Constraints, [], ReorderedUpdate).
fix_violations_aux([], _, ReorderedUpdate, ReorderedUpdate).
fix_violations_aux([X|Rest], Constraints, Acc, ReorderedUpdate) :-
insert_with_constraints(X, Acc, Constraints, AccWithX),
fix_violations_aux(Rest, Constraints, AccWithX, ReorderedUpdate).
We could have implemented fix_violations even more simply, as just:
%% Don't use this; just for demonstration purposes.
fix_violations(Update, Constraints, ReorderedUpdate) :-
permutation(Update, ReorderedUpdate),
violations(ReorderedUpdate, Constraints, []).
This is correct, but it would step through all n! permutations of the list, including trying to build off of prefixes that are already invalid, so the search space is too large and it would take too long to run.
insert_with_constraints/3 is pretty simple: it just calls out to
another predicate we'll define, insert/3, to insert X at some
position in the update list, then it verifies that that update has no
constraint violations. If it does have violations, it will fail to unify, and Prolog will backtrack and try again with X inserted at the next position in Update.
insert/3 is also pretty simple, but a bit trickier. It says that X
inserted into an empty list is [X], and then the next two clauses
say that it can be inserted at the head of the list (when the Rest
is the same) or that it can be inserted after the head (Ys and
Rest are different, because there's an X somewhere in Rest).
insert_with_constraints(X, Update, Constraints, UpdateWithX) :-
insert(X, Update, UpdateWithX),
violations(UpdateWithX, Constraints, []).
insert(X, [], [X]).
insert(X, [Y|Rest], [X,Y|Rest]).
insert(X, [Y|Ys], [Y|Rest]) :-
insert(X, Ys, Rest).