Reducing constraints 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 was able to put together a working version of this, with some help, and I found the time to read a few tutorials on CHR programming. I think I mostly understand that, below, we say that if we know 10 a(1) items (what are these called? proofs?), then we can replace that with ore(10)—which will be expanded into 10 separate ore(1) calls.

%prolog

:- module(ore, [ fuel/1 ]).
:- use_module(library(chr)).
:- use_module(library(clpfd)).

% constraint names
% ore and fuel are guaranteed
:- chr_constraint
    ore/1,
    a/1,
    b/1,
    c/1,
    d/1,
    e/1,
    fuel/1.

% problem constraints
a(1),a(1),a(1),a(1),a(1),a(1),a(1),a(1),a(1),a(1) <=> ore(10).
b(1) <=> ore(1).
c(1) <=> a(7), b(1).
d(1) <=> a(7), c(1).
e(1) <=> a(7), d(1).
fuel(1) <=> a(7), e(1).

% decompositions (one per element???)
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 | a(Y), a(1).
d(X) <=> X #> 1, Y #= X-1 | d(Y), d(1).
e(X) <=> X #> 1, Y #= X-1 | e(Y), e(1).
ore(X) <=> X#> 1, Y #= X-1 | ore(Y), ore(1).

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

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

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

It would be really nice to be able to write the following, though:

a(10) <=> ore(10)

and somehow tell prolog that if I "know," e.g., a(8), that I can still replace that ore(10) (since I need 10 ore to make those 8 a, and some are just wasted).

I think that if I can accomplish this, I can turn this output

?- fuel(1).
ore:a(1),
ore:a(1),
ore:a(1),
ore:a(1),
ore:a(1),
ore:a(1),
ore:a(1),
ore:a(1),
ore:total_ore(21).

into

?- fuel(1).
ore:total_ore(31).

If I manually add ,ore:a(2) to the fuel query, I get the correct total ore.

To sum up,

1. How can I express the constraint that I cannot partially run a reaction, but I can run the reaction to get more than I need? In other words, if I need a(8), that's enough to know I need a(10)? This, I think, will also allow me to write the original problem statement in language like a(10) <=> ore(10), instead of the absurd a(1),a(1).... Or will it?
2. Will this solve my "searching" problem, such that fuel(1) will give me ore:total_ore(31)?

---

Update: I spent some time playing with (1) to get

%prolog

:- module(ore, [ fuel/1 ]).
:- use_module(library(chr)).
:- use_module(library(clpfd)).

% constraint names
% ore and fuel are guaranteed
:- chr_constraint
    ore/1,
    a/1,
    b/1,
    c/1,
    d/1,
    e/1,
    fuel/1.

% problem constraints
a(X) <=> X #>= 1, X #=< 10 | ore(10).
b(1) <=> ore(1).
c(1) <=> a(7), b(1).
d(1) <=> a(7), c(1).
e(1) <=> a(7), d(1).
fuel(1) <=> a(7), e(1).

% decompositions (one per element???)
b(X) <=> X #> 1, Y #= X-1 | b(Y), b(1).
c(X) <=> X #> 1, Y #= X-1 | a(Y), a(1).
d(X) <=> X #> 1, Y #= X-1 | d(Y), d(1).
e(X) <=> X #> 1, Y #= X-1 | e(Y), e(1).
ore(X) <=> X#> 1, Y #= X-1 | ore(Y), ore(1).

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

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

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

Which produced total_ore(41) for my query. I believe the "leftovers" are getting converted to ore, which in this case is not what I want (though it is of course specified). The as are now being removed too early—i.e., this is correct but not minimal. How to prefer whole reactions? Hm...

Answer 1

I was able to get the exact answer using

%prolog

:- module(ore, [ fuel/1 ]).
:- use_module(library(chr)).
:- use_module(library(clpfd)).

% constraint names
% ore and fuel are guaranteed
:- chr_constraint
    ore/1,
    fuel/1.

% aggregation
% always present
:- chr_constraint ore_add/1, total_ore/1.
total_ore(A), total_ore(Total) <=> NewTotal #= A + Total, total_ore(NewTotal).
ore(X) <=> total_ore(X).

% BEGIN TO GENERATE

:- chr_constraint
    a/1,
    b/1,
    c/1,
    d/1,
    e/1.

% problem constraints (script to generate these?)
a(X), a(Y) <=> S #= X+Y, S #> 10, L #= S - 10 | ore(10), a(L).
a(X), a(Y) <=> S #= X+Y, S #=< 10 | ore(10).
b(1) <=> ore(1).
c(1) <=> a(7), b(1).
d(1) <=> a(7), c(1).
e(1) <=> a(7), d(1).
fuel(1) <=> a(7), e(1).

The constraints on a say

1. If we need X+Y a, where X+Y > 10, then we can do so with 10 ore, but we have 10-(X+Y) a leftover; and
2. If we need X+Y a, where X+Y < 10, then we can also do so with 10 ore and no leftovers (unfortunately, we never see the wasted as).

I believe the ordering asks prolog to prefer the first rule, which helps with our minimization problem. I have yet to test this strategy on other versions of the problem, however—I suspect that the invisible waste of the production might bite me.

This gives

?- fuel(1).
ore:total_ore(31)

---

For more complex problems, the key is this: whenever a reaction produces 1 of x, using, say n of a you can encode that as

x(X) <=> A #= X*n | a(A).

When a reaction produces A of x, you can encode that as

x(A) <=> ... .
x(X) <=> X #> A, L #= X - A | ..., x(L).
x(X), x(Y) <=> S #= X+Y, S #> A, L #= S - A | ..., x(L).
x(X), x(Y) <=> S #= X+Y, S #=< A | ... .

For some problems, but not all, you also need the following—sometimes you need it to deal with leftovers, but other times, because of minimization, you want to avoid this rule... especially when there are other reactions yet left to perform.

x(X) <=> X #=< A | ... .

A good test-case for this last bit is

9 ORE => 2 A
8 ORE => 3 B
7 ORE => 5 C
3 A, 4 B => 1 AB
5 B, 7 C => 1 BC
4 C, 1 A => 1 CA
2 AB, 3 BC, 4 CA => 1 FUEL

which can be solved with

%prolog

:- module(ore, [
    fuel/1,
    total_ore/1
    ]).
:- use_module(library(chr)).
:- use_module(library(clpfd)).

% constraint names
% ore and fuel are guaranteed
:- chr_constraint
    ore/1,
    fuel/1.

% aggregation
% always present
:- chr_constraint total_ore/1.
total_ore(A), total_ore(Total) <=> NewTotal #= A + Total, total_ore(NewTotal).
ore(X) <=> total_ore(X).

% BEGIN TO GENERATE

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

% 9 ORE => 2 A
% 8 ORE => 3 B
% 7 ORE => 5 C
% 3 A, 4 B => 1 AB
% 5 B, 7 C => 1 BC
% 4 C, 1 A => 1 CA
% 2 AB, 3 BC, 4 CA => 1 FUEL

% problem constraints (script to generate these?)
a(2) <=> ore(9).
a(X) <=> X #> 2, L #= X - 2 | ore(9), a(L).
a(X), a(Y) <=> S #= X+Y, S #> 2, L #= S - 2 | ore(9), a(L).
a(X), a(Y) <=> S #= X+Y, S #=< 2 | ore(9).
a(X) <=> X #< 2 | ore(9).
b(3) <=> ore(8).
b(X) <=> X #> 3, L #= X - 3 | ore(8), b(L).
b(X), b(Y) <=> S #= X+Y, S #> 3, L #= S - 3 | ore(8), b(L).
b(X), b(Y) <=> S #= X+Y, S #=< 3 | ore(8).
b(X) <=> X #<3 | ore(8).
c(5) <=> ore(7).
c(X) <=> X #> 5, L #= X - 5 | ore(7), c(L).
c(X), c(Y) <=> S #= X+Y, S #> 5, L #= S - 5 | ore(7), c(L).
c(X), c(Y) <=> S #= X+Y, S #=< 5 | ore(7).
a(X) <=> X #< 5 | ore(7).
ab(X) <=> A #= 3*X, B #= 4*X | a(A), b(B).
bc(X) <=> B #= 5*X, C #= 7*X | b(B), c(C).
ca(X) <=> A #= X, C #= 4*X | a(A), c(C).
fuel(1) <=> ab(2), bc(3), ca(4).