2

最近出现的代码挑战之一要求我解决最少量的输入材料，我可以使用这些材料来应用一组给定的反应并获得 1 个单位的输出材料。

例如，给定

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 的大部分挑战。这个似乎——<em>似乎——很适合 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)).

老实说，我什至不确定 list 参数是否是一个好的结构，或者函子表示法 ( 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，但我不确定它是否足够，因为我们可能会关心剩菜（毕竟这是一个最小化问题）？

我被困在接下来的两件事情上：

  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)]（即，如果我一直;按提示，它会继续）。有没有办法来解决这个问题？
4

3 回答 3

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约束，是正确的结果。

于 2019-12-15T15:22:50.487 回答
0

在制作咖啡时，这显然是 CLP(FD) 引擎的东西。

如果我们有有向无环反应图

  • 图表右侧的 FUEL 节点和
  • 中间产品 IP[i] (i in 0..n) 的节点，可能
  • 几个 FUEL 节点，即产生 FUEL 的几种方式： FUEL[0] ... FUEL[v] 并且可能
  • 中间产品 IP[i] 的多个节点，即创建中间产品 IP[i>0] 的几种方法：IP[i,1] ... IP[i,ways(i)] 和
  • IP[0] 用图表左侧的 ORE 标识

最后两点为我们提供了一种选择产品组合策略的方法，那么：

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

上面的所有内容都是一个变量

以及问题陈述给出的以下内容，带有 FUEL[0] ... FUEL[v] 变量和其余常量：

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

对于每个IP[i>0]，使用 IP[i] 变量和其余常量：

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

如果有几种生成 IP[i] 的方法，我们混合（这就像从其可能的方式 IP[i,j] 中为 IP[i] 的混合引入一个图形节点）：

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

和IP[0]（即ORE）要最小化的自由变量。

您会看到这里出现了一个未指定的线性规划问题，一个矩阵在对角线下方有零，因为它是一个 DAG，但它包含要在矩阵本身中优化的变量。怎么攻击那个？

于 2019-12-16T10:16:57.600 回答
0

在示例中，没有“替代”路径，也没有多个“矿石来源”，因此可以使用 Prolog 以非常不灵活的方式对示例进行编码，如下所示：

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

然后

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

但这只是一种愚蠢和不雅的尝试。

其中潜伏着一个重大的普遍问题，包括解析任意复杂的反应有向无环图并构建适当的结构。好的想法是它是一个有向无环图，所以不能从“后来的成分”中生成“早期的成分”。

示例矿石加工的 DAG

于 2019-12-15T22:43:11.347 回答