prologclpfdconstraint-handling-rules

Solving chain reactions in prolog

One of the recent Advent of code challenges tasks me with solving for the smallest amount of input material that I can use to apply a given set of reactions and get 1 unit of output material.

For example, given

10 ORE => 10 A
1 ORE => 1 B
7 A, 1 B => 1 C
7 A, 1 C => 1 D
7 A, 1 D => 1 E
7 A, 1 E => 1 FUEL

We need 31 total ore to make 1 fuel (1 to produce a unit of B, then 30 to make the requisite 28 A).

This year, I've been trying to push my programming-language horizons, so I've done most of the challenges in SML/NJ. This one seems—seemed—like a good fit for Prolog, given the little I know about it: logic programming, constraint solving, etc.

I haven't, however, been able to successfully model the constraints.

I started by turning this simple example into some facts:

makes([ore(10)], a(10)).
makes([ore(1)], b(1)).
makes([a(7), b(7)], c(1)).
makes([a(7), c(1)], d(1)).
makes([a(7), d(1)], e(1)).
makes([a(7), e(1)], fuel(1)).

To be honest, I'm not even sure if the list argument is a good structure, or if the functor notation (ore(10)) is a good model either.

Then I wanted to build the rules that allow you to say, e.g., 10 ore makes enough for 7 a:

% handles the case where we have leftovers?
% is this even the right way to model all this... when we have leftovers, we may
% have to use them in the "reaction"...
makes(In, Out) :-
    Out =.. [F,N],
    Val #>= N,
    OutN =.. [F,Val],
    makes(In, OutN).

This works1, but I'm not sure it's going to be adequate, since we may care about leftovers (this is a minimization problem, after all)?

I'm stuck on the next two pieces though:

  1. I can ask what makes 7 A and get back 10 ore, but I can't ask what is enough for 20 A: how do I write a rule which encodes multiplication/integer factors?
  2. I can say that 7 A and 1 E makes 1 fuel, but I can't state that recursively: that is, I cannot state that 14 A and 1 D also make 1 fuel. How do I write the rule that encodes this?

I'm open to alternate data encodings for the facts I presented—ultimately, I'll be scripting the transformation from Advent's input to Prolog's facts, so that's the least of my worries. I feel that if I can get this small example working, I can solve the larger problem.

  1. ?- makes(X, a(7)). gives back X=[ore(10)] infinitely (i.e., if I keep hitting ; at the prompt, it keeps going). Is there a way to fix this?
Solution

  • Not a direct answer to your specific question but my first thought on this problem was to use chr in Prolog.

    I then thought I would forward chain from fuel to the amount of ore I need.

    The basic constraints:

    :- chr_constraint ore/1, a/1, b/1,c/1, ab/1, bc/1, ca/1, fuel/0.

a(1),a(1) <=> ore(9).
b(1),b(1),b(1) <=> ore(8).
c(1),c(1),c(1),c(1),c(1) <=> ore(7).

ab(1) <=> a(3),b(4).
bc(1) <=> b(5),c(7).
ca(1) <=> c(4),a(1).
fuel <=> ab(2),bc(3),ca(4).

%Decompose foo/N into foo/1s

a(X) <=> X>1,Y#=X-1|a(Y),a(1).
b(X) <=> X>1,Y#=X-1|b(Y),b(1).
c(X) <=> X>1, Y#=X-1 | c(Y),c(1).

ab(X) <=> X>1, Y#=X-1|ab(Y),ab(1).
bc(X) <=> X>1,Y#=X-1| bc(Y),bc(1).
ca(X) <=> X>1, Y#= X-1| ca(Y),ca(1).

ore(X)<=>X >1, Y #= X -1 |ore(Y),ore(1).

%aggregation (for convenience) 
:- chr_constraint ore_add/1, total_ore/1.

total_ore(A), total_ore(Total) <=> NewTotal #= A + Total, total_ore(NewTotal).
ore_add(A) ==> total_ore(A).

ore(1) <=> ore_add(1).

    Query:

    ?-fuel.
b(1),
b(1),
c(1),
c(1),
ore_add(1),
ore_add(1),
...
total_ore(150).

    Then you would need to add a search procedure to eliminate the two b/1s and two c/1s.

    I have not implemented this but:

    ?-fuel,b(1),c(3).
ore_add(1),
...
total_ore(165)

    This has only ore_add/1 constraints and is the correct result.