Solving chain reactions in prolog

Question

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 works¹, 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?

Answer 1

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.

Answer 2

In the example there are no "alternative" path and no multiple "ore sources", so coding the example up in a very non-flexible way using Prolog can be done like this:

need(FUEL,OREOUT) :- need(FUEL,0,0,0,0,0,0,OREOUT).

need(FUEL,E,D,C,A,B,ORE,OREOUT) :- FUEL > 0, A2 is 7*FUEL+A, E2 is FUEL+E, need(0, E2, D, C, A2, B, ORE,OREOUT).
need(0,E,D,C,A,B,ORE,OREOUT)    :- E > 0, A2 is 7*E+A, D2 is E+D, need(0, 0, D2, C, A2, B, ORE,OREOUT).
need(0,0,D,C,A,B,ORE,OREOUT)    :- D > 0, A2 is 7*D+A, C2 is D+C, need(0, 0, 0, C2, A2, B, ORE,OREOUT).
need(0,0,0,C,A,B,ORE,OREOUT)    :- C > 0, A2 is 7*C+A, B2 is C+B, need(0, 0, 0, 0, A2, B2, ORE,OREOUT).
need(0,0,0,0,A,B,ORE,OREOUT)    :- X is A + B, X > 0, ORE2 is ORE + (A + 9)//10 + B, need(0, 0, 0, 0, 0, 0, ORE2,OREOUT).
need(0, 0, 0, 0, 0, 0, ORE, ORE).

Then

?- need(1011,ORE).
ORE = 3842

But this is just a silly and inelegant attempt.

There is a major general problem lurking thereunder, which includes parsing the arbitrarily complex reaction directed acyclic graph and building an appropriate structure. The good think is that it is a DAG, so one cannot generate an "earlier ingredient" from a "later one".

Answer 3

While making coffee, this is clearly something for the CLP(FD) engine.

If we have directed acyclic graph of reactions with

• FUEL node on the right of the graph and
• nodes for intermediate products IP[i] (i in 0..n) in between, with possibly
• several FUEL nodes, i.e. several ways generating FUEL: FUEL[0] ... FUEL[v] and possibly
• several nodes for intermediate products IP[i], i.e. several ways of creating intermediate product IP[i>0]: IP[i,1] ... IP[i,ways(i)] and
• IP[0] identified with ORE on the left side of the graph

with the last two points giving us a way of choosing a strategy for the product mix, then:

FUEL_NEEDED   = mix[0] * FUEL[0] + ... + mix[v] * FUEL[v]

with everything in the above a variable

and the following given by the problem statement, with FUEL[0] ... FUEL[v] variables and the rest constants:

out_fuel[0] * FUEL[0] = ∑_j ( IP[j] * flow(IPj->FUEL0) )
⋮
out_fuel[v] * FUEL[v] = ∑_j ( IP[j] * flow(IPj->FUELv) )

and for each IP[i>0], with the IP[i] variables and the rest constants:

out_ip[i] * IP[i] = ∑_j≠i ( IP[j] * flow(IPj->IPi) )

in case of a several ways to generate IP[i], we mix (this is like introducing a graph node for the mix of IP[i] from its possible ways IP[i,j]):

out_ip[i]   * IP[i]   = ∑_j(0..ways(i)) ( IP[i,j] * mix[i,j] )

out_ip[i,1] * IP[i,1] = ∑_j≠i ( IP[j] * flow(IP[j]->IP[i,1]) )
⋮
out_ip[i,ways(i)] * IP[i,ways(i)] = ∑_j≠i ( IP[j] * flow(IP[j]->IP[i,ways(i)]) )

and IP[0] (i.e. ORE) a free variable to be minimized.

You see an underspecified linear programming problem appearing here, with a matrix having zeroes below the diagonal because it's a DAG, but it contains variables to be optimized in the matrix itself. How to attack that?