Anonymous user
McNuggets problem: Difference between revisions
→{{header|rust}}: Rust version.
(Realize in miniZinc) |
(→{{header|rust}}: Rust version.) |
||
Line 1,208:
hits = arrs.pop.product(*arrs).map(&:sum)
p ((0..limit).to_a - hits).max # => 43</lang>
=={{header|Rust}}==
No hard limits.
Generalization of Rødseth’s Algorithm explained in [https://parramining.blogspot.com/2019/09/generalization-of-rdseths-algorithm-for.html post].
Working code: [https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e7ab8beb3e00da8d6ac35157ea531d24 Rust playground].
<lang rust>fn main() {
let test_cases = vec![
[6, 9, 20],
[12, 14, 17],
[12, 13, 34],
[5, 9, 21],
[10, 18, 21],
[71, 98, 99],
[7074047, 8214596, 9098139],
[582795988, 1753241221, 6814151015],
[4, 30, 16],
[12, 12, 13],
[6, 15, 1],
];
for i in 0..test_cases.len() {
print!(
"g({}, {}, {}) = ",
test_cases[i][0], test_cases[i][1], test_cases[i][2]
);
println!(
"{}",
match frobenius(test_cases[i].to_vec()) {
Ok(g) => format!("{}", g),
Err(e) => e,
}
);
}
}
fn frobenius(unsorted_a: Vec<i64>) -> Result<i64, String> {
let mut a = unsorted_a;
a.sort();
assert!(a[0] >= 1);
if gcd(gcd(a[0], a[1]), a[2]) > 1 {
return Err("Undefined".to_string());
}
let d12 = gcd(a[0], a[1]);
let d13 = gcd(a[0] / d12, a[2]);
let d23 = gcd(a[1] / d12, a[2] / d13);
let mut a_prime = vec![a[0] / d12 / d13, a[1] / d12 / d23, a[2] / d13 / d23];
a_prime.sort();
let mut rod = -1;
if a_prime[0] > 1 {
// Rødseth’s Algorithm
let mut a1 = a_prime[0];
let mut s0 = congruence(a_prime[1], a_prime[2], a_prime[0]);
let mut s = vec![a1];
let mut q: Vec<i64> = vec![];
while s0 != 0 {
s.push(s0);
let s1 = if s0 == 1 { 0 } else { s0 - (a1 % s0) };
let q1 = (a1 + s1) / s0;
q.push(q1);
a1 = s0;
s0 = s1;
}
let mut p = vec![0, 1];
let mut r = (s[1] * a_prime[1] - p[1] * a_prime[2]) / a_prime[0];
let mut i = 1;
while r > 0 {
let p_next = q[i - 1] * p[i] - p[i - 1];
p.push(p_next);
r = (s[i + 1] * a_prime[1] - p_next * a_prime[2]) / a_prime[0];
i += 1;
}
let v = i - 1;
rod = -a_prime[0] + a_prime[1] * (s[v] - 1) + a_prime[2] * (p[v + 1] - 1)
- (a_prime[1] * s[v + 1]).min(a_prime[2] * p[v]);
}
Ok(rod * d12 * d13 * d23 + a[0] * (d23 - 1) + a[1] * (d13 - 1) + a[2] * (d12 - 1))
}
fn gcd(a: i64, b: i64) -> i64 {
if b == 0 {
a
} else {
gcd(b, a % b)
}
}
fn congruence(a: i64, c: i64, m: i64) -> i64 {
// Solves ax ≡ c mod m
let aa = a % m;
let cc = (c + a * m) % m;
if aa == 1 {
return cc;
} else {
let y = congruence(m, -cc, aa);
(m * y + cc) / aa
}
}</lang>
{{out}}
<pre>
g(6, 9, 20) = 43
g(12, 14, 17) = 61
g(12, 13, 34) = 79
g(5, 9, 21) = 22
g(10, 18, 21) = 65
g(71, 98, 99) = 1307
g(7074047, 8214596, 9098139) = 48494282357
g(582795988, 1753241221, 6814151015) = 173685179295403
g(4, 30, 16) = Undefined
g(12, 12, 13) = 131
g(6, 15, 1) = -1
</pre>
=={{header|Tailspin}}==
| |||