解决水桶之谜！
上下文
水桶谜语或水壶谜语是一个简单的谜语，可以用相当一般的形式表述为：
给定n > 0正整数a_1, a_2, \cdots, a_n代表n桶的容量(以体积单位表示)和一个正整数t \leq \max(a_1, a_2, \cdots, a_n)，找到一个“移动”序列，将t单位的水量放置在桶i中。
要定义有效的“移动”，让c_1, c_2, \cdots, c_n用0 \leq c_i \leq a_i\ \forall i表示每个水桶i包含的水量单位。然后，在每一步中，您都可以执行以下任何操作：
- 完全填充一个桶i，设置c_i = a_i
- 完全清空一个桶i，设置c_i = 0
- 将水桶i倒在桶j上，设置
也就是说，你把桶i倒在桶j上，直到桶i变空或桶j满了为止，不管先发生什么(如果这两件事同时发生的话)。
任务
给定桶容量和目标测量，您的任务是输出一个最小的运动序列，将t单位的水量放置在其中一个桶中。
输入
桶的容量是正整数。您可以假设这些能力是独特的和有序的。您可以采用多种合理的格式，包括但不限于：
- 整数列表
- 函数的参数
此外，您将接受一个不大于输入容量列表中的最大值的正整数t。
您可以假设输入参数指定水桶问题的可解实例。
输出
您的程序/功能/etc应该输出最短的移动顺序，将t单位的水量放置在一个水桶中。如果存在多个这样的序列，则可以输出任意一个序列。请注意，一些移动通勤，这也引入了一些问题的多重解决方案。
您的程序可以打印该序列，或者将其作为移动列表或任何其他合理的内容返回。
要确定移动和桶，您可以选择任何适合您的需要的编码，只要它在测试用例之间是一致的，并且完全明确。一个建议是，使用三个字母来识别这三个动作，比如"E"用于倒桶，"F"用于倒桶，"P"用于倒入并使用数字来识别桶(例如，0索引或1索引或使用其总容量)。
使用此编码，要识别移动，始终需要一个字母和一个数字。在“倾注”移动的情况下，还需要第二个整数。您应该始终如一地使用"P" n m，就像n被倒在m上或者m被倒在n上一样。
测试用例
我们使用上面的编码，"P" n m的意思是“倒入桶n而不是桶m”。
[1, 2, 3, 4], 1 -> ['F 1']
[1, 2, 3, 4], 2 -> ['F 2']
[1, 2, 3, 4], 3 -> ['F 3']
[1, 2, 3, 4], 4 -> ['F 4']
[13, 17], 1 -> ['F 13', 'P 13 17', 'F 13', 'P 13 17', 'E 17', 'P 13 17', 'F 13', 'P 13 17', 'E 17', 'P 13 17', 'F 13', 'P 13 17']
[4, 6], 2 -> ['F 6', 'P 6 4']
[1, 4, 6], 2 -> ['F 6', 'P 6 4']
[3, 4, 6], 2 -> ['F 6', 'P 6 4']
[4, 5, 6], 2 -> ['F 6', 'P 6 4']
[4, 6, 7], 2 -> ['F 6', 'P 6 4']
[1, 3, 5], 2 -> ['F 3', 'P 3 1']
[7, 9], 4 -> ['F 9', 'P 9 7', 'E 7', 'P 9 7', 'F 9', 'P 9 7']
[8, 9, 13], 6 -> ['F 9', 'P 9 8', 'P 8 13', 'P 9 8', 'F 13', 'P 13 8']
[8, 9, 13], 7 -> ['F 8', 'P 8 9', 'F 8', 'P 8 9']
[8, 9, 11], 10 -> ['F 8', 'P 8 9', 'F 11', 'P 11 9']
[8, 9, 12], 6 -> ['F 9', 'P 9 12', 'F 9', 'P 9 12']
[8, 9, 12], 5 -> ['F 8', 'P 8 12', 'F 9', 'P 9 12']
[23, 37, 41], 7 -> ['F 41', 'P 41 23', 'P 41 37', 'P 23 41', 'F 41', 'P 41 23', 'P 41 37', 'F 41', 'P 41 37', 'E 37', 'P 41 37', 'E 37', 'P 41 37', 'F 41', 'P 41 37']
[23, 31, 37, 41], 7 -> ['F 23', 'P 23 37', 'F 31', 'P 31 37', 'P 31 41', 'P 37 31', 'P 31 41']您可以检查这里的香草Python参考实现
回答 1
Code Golf用户
发布于 2020-03-22 04:31:21
Javascript，364个字节
我相信这很容易就能打得更好。
S=t=>G=>{L=t.length;r=(f,n,a,i,e=0)=>{if(0==n)return f.indexOf(G)>=0&&[];a=(A,B,C,D)=>(X=f.slice(),X[A]=B,X[C]=D,X);for(;e<L;++e){for(K of[0,t[e]])if(F=r(a(e,K),n-1))return[[+!K,e]].concat(F);for(i=0;i<L;++i)if(i!=e&&(O=r(a(e,Math.max(0,f[e]-t[i]+f[i]),i,Math.min(t[i],f[e]+f[i])),n-1)))return[[2,e,i]].concat(O)}};for(T=1;!(E=r(Array(L).fill(0),T));++T);return E}返回数组的数组。每个数组的格式都是[n, i] if n=0 (填充)或n=1 (空)，或者[2, i, j]表示“倒桶i到桶j”。桶总是以索引形式给出，从0开始。
使用与其他答案相同的基本搜索方法。非缩小版本：
var S = (capacities, target) => {
let n = capacities.length;
var waterBuckets = (levels, maxSteps) => {
if (maxSteps == 0) return levels.indexOf(target) >= 0 ? [] : false;
let getCopy = () => levels.slice();
for (let i = 0; i < n; ++i) {
for (let level of [0, capacities[i]]) {
let levelsCopy = getCopy();
levelsCopy[i] = level;
let res = waterBuckets(levelsCopy, maxSteps - 1);
if (res) return [[+!level, i]].concat(res);
}
for (let j = 0; j < n; ++j) {
if (i === j) continue;
let levelsCopy = getCopy();
levelsCopy[i] = Math.max(0, levels[i] - capacities[j] + levels[j]);
levelsCopy[j] = Math.min(capacities[j], levels[i] + levels[j]);
let res = waterBuckets(levelsCopy, maxSteps - 1);
if (res) return [[2, i, j]].concat(res);
}
}
};
for (let s = 1;; ++s) {
let r = waterBuckets(Array(n).fill(0), s);
if (r) return r;
}
};https://codegolf.stackexchange.com/questions/201489
复制相似问题
腾讯云开发者
