prolog - 解决序言中的链式 react

Question

One of the recent Advent of code challenges要求我解决可用于应用给定 react 集并获得 1 单位输出 Material 的最小输入 Material 量。

例如给定

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

我们总共需要 31 个矿石来制造 1 个燃料(1 个矿石用来生产单位 B，然后 30 个矿石来制造所需的 28 A)。

今年，我一直在努力拓展我的编程语言视野，所以我已经完成了 SML/NJ 中的大部分挑战。这看起来——似乎——很适合 Prolog，因为我对它知之甚少:逻辑编程、约束求解等。

但是，我还没有能够成功地对约束进行建模。

我首先将这个简单的例子变成了一些事实:

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)).

老实说，我什至不确定列表参数是否是一个好的结构，或者仿函数符号 (ore(10)) 是否是一个好的模型。

然后我想建立允许你说的规则，例如，10 矿石足够 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).

这可行¹，但我不确定它是否足够，因为我们可能关心剩菜(毕竟这是一个最小化问题)？

不过我还停留在接下来的两个部分:

1. 我可以问是什么让 7 A 得到 10 矿石，但我不能问什么对 20 A 足够:我如何编写编码乘法/整数因子的规则？
2. 我可以说 7 A 和 1 E 产生 1 种燃料，但我不能递归地说明:也就是说，我不能说 14 A 和 1 D 也产生 1 种燃料。我该如何编写对此进行编码的规则？

我愿意为我呈现的事实使用替代数据编码——最终，我将编写从 Advent 的输入到 Prolog 的事实的转换脚本，所以这是我最不担心的。我觉得如果我能让这个小例子起作用，我就能解决更大的问题。

---

1. ?- makes(X, a(7)). 无限返回 X=[ore(10)](即，如果我继续点击 ; 在提示符下，它继续运行)。有办法解决这个问题吗？

Answer 1

不是对您的具体问题的直接回答，但我对这个问题的第一个想法是在 Prolog 中使用 chr。

然后我想我会将链从 fuel 转发到我需要的 ore 数量。

基本约束:

:- 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).

查询:

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

然后您需要添加一个搜索过程来消除两个 b/1 和两个 c/1。

我还没有实现这个但是:

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

这只有 ore_add/1 约束并且是正确的结果。