McNuggets problem
From Wikipedia:
You are encouraged to solve this task according to the task description, using any language you may know.
The McNuggets version of the coin problem was introduced by Henri Picciotto, who included it in his algebra textbook co-authored with Anita Wah. Picciotto thought of the application in the 1980s while dining with his son at McDonald's, working the problem out on a napkin. A McNugget number is the total number of McDonald's Chicken McNuggets in any number of boxes. In the United Kingdom, the original boxes (prior to the introduction of the Happy Meal-sized nugget boxes) were of 6, 9, and 20 nuggets.
- Task
Calculate (from 0 up to a limit of 100) the largest non-McNuggets
number (a number n which cannot be expressed with 6x + 9y + 20z = n
where x, y and z are natural numbers).
11l
<lang 11l>V nuggets = Set(0..100) L(s, n, t) cart_product(0 .. 100 I/ 6,
0 .. 100 I/ 9, 0 .. 100 I/ 20) nuggets.discard(6*s + 9*n + 20*t)
print(max(nuggets))</lang>
- Output:
43
Ada
<lang Ada>with Ada.Text_IO; use Ada.Text_IO;
procedure McNugget is
Limit : constant := 100; List : array (0 .. Limit) of Boolean := (others => False); N : Integer;
begin
for A in 0 .. Limit / 6 loop for B in 0 .. Limit / 9 loop for C in 0 .. Limit / 20 loop N := A * 6 + B * 9 + C * 20; if N <= 100 then List (N) := True; end if; end loop; end loop; end loop; for N in reverse 1 .. Limit loop if not List (N) then Put_Line ("The largest non McNugget number is:" & Integer'Image (N)); exit; end if; end loop;
end McNugget;</lang>
- Output:
The largest non McNugget number is: 43
ALGOL 68
<lang algol68>BEGIN
# Solve the McNuggets problem: find the largest n <= 100 for which there # # are no non-negative integers x, y, z such that 6x + 9y + 20z = n # INT max nuggets = 100; [ 0 : max nuggets ]BOOL sum; FOR i FROM LWB sum TO UPB sum DO sum[ i ] := FALSE OD; FOR x FROM 0 BY 6 TO max nuggets DO FOR y FROM 0 BY 9 TO max nuggets DO FOR z FROM 0 BY 20 TO max nuggets DO INT nuggets = x + y + z; IF nuggets <= max nuggets THEN sum[ nuggets ] := TRUE FI OD # z # OD # y # OD # x # ; # show the highest number that cannot be formed # INT largest := -1; FOR i FROM UPB sum BY -1 TO LWB sum WHILE largest := i; sum[ i ] DO SKIP OD; print( ( "The largest non McNugget number is: " , whole( largest, 0 ) , newline ) )
END</lang>
- Output:
The largest non McNugget number is: 43
APL
<lang APL>100 (⌈/(⍳⊣)~(⊂⊢)(+/×)¨(,⎕IO-⍨(⍳∘⌊÷))) 6 9 20</lang>
- Output:
43
AppleScript
Generalised for other set sizes, and for other triples of natural numbers. Uses NSMutableSet, through the AppleScript ObjC interface: <lang applescript>use AppleScript version "2.4" use framework "Foundation" use scripting additions
on run
set setNuggets to mcNuggetSet(100, 6, 9, 20) script isMcNugget on |λ|(x) setMember(x, setNuggets) end |λ| end script set xs to dropWhile(isMcNugget, enumFromThenTo(100, 99, 1)) set setNuggets to missing value -- Clear ObjC pointer value if 0 < length of xs then item 1 of xs else "No unreachable quantities in this range" end if
end run
-- mcNuggetSet :: Int -> Int -> Int -> Int -> ObjC Set on mcNuggetSet(n, mcx, mcy, mcz)
set upTo to enumFromTo(0) script fx on |λ|(x) script fy on |λ|(y) script fz on |λ|(z) set v to sum({mcx * x, mcy * y, mcz * z}) if 101 > v then {v} else {} end if end |λ| end script concatMap(fz, upTo's |λ|(n div mcz)) end |λ| end script concatMap(fy, upTo's |λ|(n div mcy)) end |λ| end script setFromList(concatMap(fx, upTo's |λ|(n div mcx)))
end mcNuggetSet
-- GENERIC FUNCTIONS ----------------------------------------------------
-- concatMap :: (a -> [b]) -> [a] -> [b] on concatMap(f, xs)
set lng to length of xs set acc to {} tell mReturn(f) repeat with i from 1 to lng set acc to acc & |λ|(item i of xs, i, xs) end repeat end tell return acc
end concatMap
-- drop :: Int -> [a] -> [a]
-- drop :: Int -> String -> String
on drop(n, xs)
set c to class of xs if c is not script then if c is not string then if n < length of xs then items (1 + n) thru -1 of xs else {} end if else if n < length of xs then text (1 + n) thru -1 of xs else "" end if end if else take(n, xs) -- consumed return xs end if
end drop
-- dropWhile :: (a -> Bool) -> [a] -> [a] -- dropWhile :: (Char -> Bool) -> String -> String on dropWhile(p, xs)
set lng to length of xs set i to 1 tell mReturn(p) repeat while i ≤ lng and |λ|(item i of xs) set i to i + 1 end repeat end tell drop(i - 1, xs)
end dropWhile
-- enumFromThenTo :: Int -> Int -> Int -> [Int] on enumFromThenTo(x1, x2, y)
set xs to {} repeat with i from x1 to y by (x2 - x1) set end of xs to i end repeat return xs
end enumFromThenTo
-- enumFromTo :: Int -> Int -> [Int] on enumFromTo(m)
script on |λ|(n) if m ≤ n then set lst to {} repeat with i from m to n set end of lst to i end repeat return lst else return {} end if end |λ| end script
end enumFromTo
-- foldl :: (a -> b -> a) -> a -> [b] -> a on foldl(f, startValue, xs)
tell mReturn(f) set v to startValue set lng to length of xs repeat with i from 1 to lng set v to |λ|(v, item i of xs, i, xs) end repeat return v end tell
end foldl
-- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: First-class m => (a -> b) -> m (a -> b) on mReturn(f)
if class of f is script then f else script property |λ| : f end script end if
end mReturn
-- sum :: [Num] -> Num on sum(xs)
script add on |λ|(a, b) a + b end |λ| end script foldl(add, 0, xs)
end sum
-- NB All names of NSMutableSets should be set to *missing value* -- before the script exits. -- ( scpt files can not be saved if they contain ObjC pointer values ) -- setFromList :: Ord a => [a] -> Set a on setFromList(xs)
set ca to current application ca's NSMutableSet's ¬ setWithArray:(ca's NSArray's arrayWithArray:(xs))
end setFromList
-- setMember :: Ord a => a -> Set a -> Bool on setMember(x, objcSet)
missing value is not (objcSet's member:(x))
end setMember</lang>
- Output:
43
AWK
<lang AWK>
- syntax: GAWK -f MCNUGGETS_PROBLEM.AWK
- converted from Go
BEGIN {
limit = 100 for (a=0; a<=limit; a+=6) { for (b=a; b<=limit; b+=9) { for (c=b; c<=limit; c+=20) { arr[c] = 1 } } } for (i=limit; i>=0; i--) { if (!arr[i]+0) { printf("%d\n",i) break } } exit(0)
} </lang>
- Output:
43
BASIC
<lang basic>10 DEFINT A-Z: DIM F(100) 20 FOR A=0 TO 100 STEP 6 30 FOR B=A TO 100 STEP 9 40 FOR C=B TO 100 STEP 20 50 F(C)=-1 60 NEXT C,B,A 70 FOR A=100 TO 0 STEP -1 80 IF NOT F(A) THEN PRINT A: END 90 NEXT A</lang>
- Output:
43
BCPL
<lang bcpl>get "libhdr" manifest $( limit = 100 $)
let start() be $( let flags = vec limit
for i = 0 to limit do flags!i := false for a = 0 to limit by 6 for b = a to limit by 9 for c = b to limit by 20 do flags!c := true for i = limit to 0 by -1 unless flags!i $( writef("Maximum non-McNuggets number: %N.*N", i) finish $)
$)</lang>
- Output:
Maximum non-McNuggets number: 43.
C
<lang c>#include <stdio.h>
int main() {
int max = 0, i = 0, sixes, nines, twenties;
loopstart: while (i < 100) {
for (sixes = 0; sixes*6 < i; sixes++) { if (sixes*6 == i) { i++; goto loopstart; }
for (nines = 0; nines*9 < i; nines++) { if (sixes*6 + nines*9 == i) { i++; goto loopstart; }
for (twenties = 0; twenties*20 < i; twenties++) { if (sixes*6 + nines*9 + twenties*20 == i) { i++; goto loopstart; } } } } max = i; i++; }
printf("Maximum non-McNuggets number is %d\n", max);
return 0;
}</lang>
- Output:
Maximum non-McNuggets number is 43
C#
<lang c#> using System;
public class McNuggets {
public static void Main() { bool[] isMcNuggetNumber = new bool[101]; for (int x = 0; x <= 100/6; x++) { for (int y = 0; y <= 100/9; y++) { for (int z = 0; z <= 100/20; z++) { int mcNuggetNumber = x*6 + y*9 + z*20; if (mcNuggetNumber <= 100) { isMcNuggetNumber[mcNuggetNumber] = true; } } } }
for (int mnnCheck = isMcNuggetNumber.Length-1; mnnCheck >= 0; mnnCheck--) { if (!isMcNuggetNumber[mnnCheck]) { Console.WriteLine("Largest non-McNuggett Number less than 100: " + mnnCheck.ToString()); break; } } }
} </lang>
- Output:
Largest non-McNuggett Number less than 100: 43
Clojure
<lang clojure>(defn cart [colls]
(if (empty? colls) '(()) (for [more (cart (rest colls)) x (first colls)] (cons x more))))
(defn nuggets n6 n9 n20 (+ (* 6 n6) (* 9 n9) (* 20 n20)))
(let [possible (distinct (map nuggets (cart (map range [18 13 6]))))
mcmax (apply max (filter (fn [x] (not-any? #{x} possible)) (range 101)))] (printf "Maximum non-McNuggets number is %d\n" mcmax))</lang>
- Output:
Maximum non-McNuggets number is 43
Cowgol
<lang cowgol>include "cowgol.coh"; const LIMIT := 100;
var flags: uint8[LIMIT+1]; MemZero(&flags[0], @bytesof flags);
var a: @indexof flags; var b: @indexof flags; var c: @indexof flags;
a := 0; while a <= LIMIT loop
b := a; while b <= LIMIT loop c := b; while c <= LIMIT loop flags[c] := 1; c := c + 20; end loop; b := b + 9; end loop; a := a + 6;
end loop;
a := LIMIT; loop
if flags[a] == 0 then print("Maximum non-McNuggets number: "); print_i32(a as uint32); print_nl(); break; end if; a := a - 1;
end loop;</lang>
- Output:
Maximum non-McNuggets number: 43
Dart
<lang dart>import 'dart:math'; main() {
var nuggets = List<int>.generate(101, (int index) => index); for (int small in List<int>.generate((100 ~/ (6 + 1)), (int index) => index)) { for (int medium in List<int>.generate((100 ~/ (9 + 1)), (int index) => index)) { for (int large in List<int>.generate((100 ~/ (20 + 1)), (int index) => index)) { nuggets.removeWhere((element) => element == 6 * small + 9 * medium + 20 * large); } } } print('Largest non-McNuggets number: ${nuggets.reduce(max).toString() ?? 'none'}.');
}</lang>
- Output:
Largest non-McNuggets number: 43.
Dyalect
<lang dyalect>func mcnugget(limit) {
var sv = Array.empty(limit + 1, false) for s in 0^6..limit { for n in s^9..limit { for t in n^20..limit { sv[t] = true } } } for i in limit^-1..0 { if !sv[i] { print("Maximum non-McNuggets number is \(i)") return } }
}
mcnugget(100)</lang>
- Output:
Maximum non-McNuggets number is 43
Elixir
Uses MapSet and Comprehension
<lang Elixir>defmodule Mcnugget do
def solve(limit) do 0..limit |> MapSet.new() |> MapSet.difference( for( x <- 0..limit, y <- 0..limit, z <- 0..limit, Integer.mod(x, 6) == 0, Integer.mod(y, 9) == 0, Integer.mod(z, 20) == 0, x + y + z <= limit, into: MapSet.new(), do: x + y + z ) ) |> Enum.max() end
end
Mcnugget.solve(100) |> IO.puts </lang>
- Output:
43
F#
<lang fsharp> // McNuggets. Nigel Galloway: October 28th., 2018 let fN n g = Seq.initInfinite(fun ng->ng*n+g)|>Seq.takeWhile(fun n->n<=100) printfn "%d" (Set.maxElement(Set.difference (set[1..100]) (fN 20 0|>Seq.collect(fun n->fN 9 n)|>Seq.collect(fun n->fN 6 n)|>Set.ofSeq))) </lang>
- Output:
43
Factor
<lang factor>USING: backtrack kernel math.ranges prettyprint sequences sets ; 101 <iota> [ 0 6 9 20 [ 100 swap <range> amb-lazy ] tri@ ] bag-of diff last .</lang>
- Output:
43
FOCAL
<lang focal>01.10 F N=0,100;S T(N)=0 01.20 F A=0,6,100;F B=A,9,100;F C=B,20,100;S T(C)=-1 01.30 S N=101 01.40 S N=N-1 01.50 I (T(N))1.4 01.60 T %3,N,! 01.70 Q</lang>
- Output:
= 43
FreeBASIC
<lang freebasic> Dim As Integer l(100), a, b, c, n For a = 0 To 100/6
For b = 0 To 100/9 For c = 0 To 100/20 n = a*6 + b*9 + c*20 If n <= 100 Then l(n) = true Next c Next b
Next a For n = 100 To 1 Step -1
If l(n) = false Then Print "El mayor número que no sea McNugget es:"; n: Exit For
Next n End </lang>
- Output:
El mayor número que no sea McNugget es: 43
Go
<lang go>package main
import "fmt"
func mcnugget(limit int) {
sv := make([]bool, limit+1) // all false by default for s := 0; s <= limit; s += 6 { for n := s; n <= limit; n += 9 { for t := n; t <= limit; t += 20 { sv[t] = true } } } for i := limit; i >= 0; i-- { if !sv[i] { fmt.Println("Maximum non-McNuggets number is", i) return } }
}
func main() {
mcnugget(100)
}</lang>
- Output:
Maximum non-McNuggets number is 43
Haskell
<lang haskell>import Data.Set (Set, fromList, member)
gaps :: [Int] gaps = dropWhile (`member` mcNuggets) [100,99 .. 1]
mcNuggets :: Set Int mcNuggets =
let size = enumFromTo 0 . quot 100 in fromList $ size 6 >>= \x -> size 9 >>= \y -> size 20 >>= \z -> let v = sum [6 * x, 9 * y, 20 * z] in [ v | 101 > v ]
main :: IO () main =
print $ case gaps of x:_ -> show x [] -> "No unreachable quantities found ..."</lang>
Or equivalently, making use of the list comprehension notation: <lang haskell>import Data.Set (Set, fromList, member)
gaps :: [Int] gaps = dropWhile (`member` mcNuggets) [100,99 .. 1]
mcNuggets :: Set Int mcNuggets =
let size n = [0 .. quot 100 n] in fromList [ v | x <- size 6 , y <- size 9 , z <- size 20 , let v = sum [6 * x, 9 * y, 20 * z] , 101 > v ]
main :: IO () main =
print $ case gaps of x:_ -> show x [] -> "No unreachable quantities found ..."</lang>
43
J
Brute force solution: calculate all pure (just one kind of box) McNugget numbers which do not exceed 100, then compute all possible sums, and then remove those from the list of numbers up to 100 (which is obviously a McNugget number), then find the largest number remaining:
<lang J> >./(i.100)-.,+/&>{(* i.@>.@%~&101)&.>6 9 20 43</lang>
Technically, we could have used 100 in place of 101 when we were finding how many pure McNugget numbers were in each series (because 100 is obviously a McNugget number), but it's not like that's a problem, either.
Java
<lang Java>public class McNuggets {
public static void main(String... args) { int[] SIZES = new int[] { 6, 9, 20 }; int MAX_TOTAL = 100; // Works like Sieve of Eratosthenes int numSizes = SIZES.length; int[] counts = new int[numSizes]; int maxFound = MAX_TOTAL + 1; boolean[] found = new boolean[maxFound]; int numFound = 0; int total = 0; boolean advancedState = false; do { if (!found[total]) { found[total] = true; numFound++; } // Advance state advancedState = false; for (int i = 0; i < numSizes; i++) { int curSize = SIZES[i]; if ((total + curSize) > MAX_TOTAL) { // Reset to zero and go to the next box size total -= counts[i] * curSize; counts[i] = 0; } else { // Adding a box of this size still keeps the total at or below the maximum counts[i]++; total += curSize; advancedState = true; break; } } } while ((numFound < maxFound) && advancedState); if (numFound < maxFound) { // Did not find all counts within the search space for (int i = MAX_TOTAL; i >= 0; i--) { if (!found[i]) { System.out.println("Largest non-McNugget number in the search space is " + i); break; } } } else { System.out.println("All numbers in the search space are McNugget numbers"); } return; }
}</lang>
- Output:
Largest non-McNugget number in the search space is 43
JavaScript
<lang javascript>(() => {
'use strict';
// main :: IO () const main = () => { const size = n => enumFromTo(0)( quot(100, n) ), nuggets = new Set( size(6).flatMap( x => size(9).flatMap( y => size(20).flatMap( z => { const v = sum([6 * x, 9 * y, 20 * z]); return 101 > v ? ( [v] ) : []; } ), ) ) ), xs = dropWhile( x => nuggets.has(x), enumFromThenTo(100, 99, 1) );
return 0 < xs.length ? ( xs[0] ) : 'No unreachable quantities found in this range'; };
// GENERIC FUNCTIONS ----------------------------------
// dropWhile :: (a -> Bool) -> [a] -> [a] const dropWhile = (p, xs) => { const lng = xs.length; return 0 < lng ? xs.slice( until( i => i === lng || !p(xs[i]), i => 1 + i, 0 ) ) : []; };
// enumFromThenTo :: Int -> Int -> Int -> [Int] const enumFromThenTo = (x1, x2, y) => { const d = x2 - x1; return Array.from({ length: Math.floor(y - x2) / d + 2 }, (_, i) => x1 + (d * i)); };
// ft :: Int -> Int -> [Int] const enumFromTo = m => n => Array.from({ length: 1 + n - m }, (_, i) => m + i);
// quot :: Int -> Int -> Int const quot = (n, m) => Math.floor(n / m);
// sum :: [Num] -> Num const sum = xs => xs.reduce((a, x) => a + x, 0);
// until :: (a -> Bool) -> (a -> a) -> a -> a const until = (p, f, x) => { let v = x; while (!p(v)) v = f(v); return v; };
// MAIN --- return console.log( main() );
})();</lang>
- Output:
43
jq
<lang jq>[
[range(18) as $n6 | range(13) as $n9 | range(6) as $n20 | ($n6 * 6 + $n9 * 9 + $n20 * 20)] | unique | . as $possible | range(101) | . as $n | select($possible|contains([$n])|not)
] | max</lang>
- Output:
43
Julia
Simple brute force solution, though the BitSet would save memory considerably with larger max numbers. <lang julia>function mcnuggets(max)
b = BitSet(1:max) for i in 0:6:max, j in 0:9:max, k in 0:20:max delete!(b, i + j + k) end maximum(b)
end
println(mcnuggets(100))
</lang>
- Output:
43
Kotlin
<lang scala>// Version 1.2.71
fun mcnugget(limit: Int) {
val sv = BooleanArray(limit + 1) // all false by default for (s in 0..limit step 6) for (n in s..limit step 9) for (t in n..limit step 20) sv[t] = true
for (i in limit downTo 0) { if (!sv[i]) { println("Maximum non-McNuggets number is $i") return } }
}
fun main(args: Array<String>) {
mcnugget(100)
}</lang>
- Output:
Maximum non-McNuggets number is 43
Locomotive Basic
<lang locobasic>100 CLEAR 110 DIM a(100) 120 FOR a=0 TO 100/6 130 FOR b=0 TO 100/9 140 FOR c=0 TO 100/20 150 n=a*6+b*9+c*20 160 IF n<=100 THEN a(n)=1 170 NEXT c 180 NEXT b 190 NEXT a 200 FOR n=0 TO 100 210 IF a(n)=0 THEN l=n 220 NEXT n 230 PRINT"The Largest non McNugget number is:";l 240 END</lang>
- Output:
The largest non McNugget number is: 43
Lua
<lang lua> function range(A,B)
return function() return coroutine.wrap(function() for i = A, B do coroutine.yield(i) end end) end
end
function filter(stream, f)
return function() return coroutine.wrap(function() for i in stream() do if f(i) then coroutine.yield(i) end end end) end
end
function triple(s1, s2, s3)
return function() return coroutine.wrap(function() for x in s1() do for y in s2() do for z in s3() do coroutine.yield{x,y,z} end end end end) end
end
function apply(f, stream)
return function() return coroutine.wrap(function() for T in stream() do coroutine.yield(f(table.unpack(T))) end end) end
end
function exclude(s1, s2)
local exlusions = {} for x in s1() do exlusions[x] = true end return function() return coroutine.wrap(function() for x in s2() do if not exlusions[x] then coroutine.yield(x) end end end) end
end
function maximum(stream)
local M = math.mininteger for x in stream() do M = math.max(M, x) end return M
end
local N = 100 local A, B, C = 6, 9, 20
local Xs = filter(range(0, N), function(x) return x % A == 0 end) local Ys = filter(range(0, N), function(x) return x % B == 0 end) local Zs = filter(range(0, N), function(x) return x % C == 0 end) local sum = filter(apply(function(x, y, z) return x + y + z end, triple(Xs, Ys, Zs)), function(x) return x <= N end)
print(maximum(exclude(sum, range(1, N)))) </lang>
- Output:
43
Mathematica/Wolfram Language
<lang mathematica>FrobeniusNumber[{6, 9, 20}]</lang>
- Output:
43
MiniZinc
<lang MiniZinc> %McNuggets. Nigel Galloway, August 27th., 2019 var 0..99: n; constraint forall(x in 0..16,y in 0..11,z in 0..5)(6*x + 9*y + 20*z!=n); solve maximize n; output [show(n)] </lang>
- Output:
43 ---------- ==========
Nim
<lang Nim>const Limit = 100
var mcnuggets: array[0..Limit, bool]
for a in countup(0, Limit, 6):
for b in countup(a, Limit, 9): for c in countup(b, Limit, 20): mcnuggets[c] = true
for n in countdown(Limit, 0):
if not mcnuggets[n]: echo "The largest non-McNuggets number is: ", n break</lang>
- Output:
The largest non-McNuggets number is: 43
Perl
<lang perl>use ntheory qw/forperm gcd vecmin/;
sub Mcnugget_number {
my $counts = shift;
return 'No maximum' if 1 < gcd @$counts;
my $min = vecmin @$counts; my @meals; my @min;
my $a = -1; while (1) { $a++; for my $b (0..$a) { for my $c (0..$b) { my @s = ($a, $b, $c); forperm { $meals[ $s[$_[0]] * $counts->[0] + $s[$_[1]] * $counts->[1] + $s[$_[2]] * $counts->[2] ] = 1; } @s; } } for my $i (0..$#meals) { next unless $meals[$i]; if ($min[-1] and $i == ($min[-1] + 1)) { push @min, $i; last if $min == @min } else { @min = $i; } } last if $min == @min } $min[0] ? $min[0] - 1 : 0
}
for my $counts ([6,9,20], [6,7,20], [1,3,20], [10,5,18], [5,17,44], [2,4,6], [3,6,15]) {
print 'Maximum non-Mcnugget number using ' . join(', ', @$counts) . ' is: ' . Mcnugget_number($counts) . "\n"
}</lang>
- Output:
Maximum non-Mcnugget number using 6, 9, 20 is: 43 Maximum non-Mcnugget number using 6, 7, 20 is: 29 Maximum non-Mcnugget number using 1, 3, 20 is: 0 Maximum non-Mcnugget number using 10, 5, 18 is: 67 Maximum non-Mcnugget number using 5, 17, 44 is: 131 Maximum non-Mcnugget number using 2, 4, 6 is: No maximum Maximum non-Mcnugget number using 3, 6, 15 is: No maximum
Perl using Regex
<lang Perl>use strict; use warnings;
$_ = 1 . 0 x 100; 1 while s/ (?=1) (?:.{6}|.{9}|.{20}) \K 0 /1/x; /01*$/ and print "Maximum non-Mcnugget number is: $-[0]\n";</lang>
- Output:
Maximum non-Mcnugget number is: 43
Phix
<lang Phix>constant limit=100 sequence nuggets = repeat(false,limit+1) for sixes=0 to limit by 6 do
for nines=sixes to limit by 9 do for twenties=nines to limit by 20 do nuggets[twenties+1] = true end for end for
end for printf(1,"Maximum non-McNuggets number is %d\n", rfind(false,nuggets)-1)</lang>
- Output:
Maximum non-McNuggets number is 43
Also, since it is a bit more interesting, a
<lang Phix>function Mcnugget_number(sequence counts)
if gcd(counts)>1 then return "No maximum" end if
atom cmin = min(counts) sequence meals = {} sequence smin = {} integer a = -1 while true do a += 1 for b=0 to a do for c=0 to b do sequence s = {a, b, c} for i=1 to factorial(3) do sequence p = permute(i,s) integer k = sum(sq_mul(p,counts))+1 if k>length(meals) then meals &= repeat(0,k-length(meals)) end if meals[k] = 1 end for end for end for for i=1 to length(meals) do if meals[i] then if length(smin) and smin[$]+1=i-1 then smin = append(smin,i-1) if length(smin)=cmin then exit end if else smin = {i-1} end if end if end for if length(smin)=cmin then exit end if end while return sprintf("%d",iff(smin[1]?smin[1]-1:0))
end function
constant tests = {{6,9,20}, {6,7,20}, {1,3,20}, {10,5,18}, {5,17,44}, {2,4,6}, {3,6,15}} for i=1 to length(tests) do
sequence ti = tests[i] printf(1,"Maximum non-Mcnugget number using %s is: %s\n",{sprint(ti),Mcnugget_number(ti)})
end for</lang>
- Output:
Maximum non-Mcnugget number using {6,9,20} is: 43 Maximum non-Mcnugget number using {6,7,20} is: 29 Maximum non-Mcnugget number using {1,3,20} is: 0 Maximum non-Mcnugget number using {10,5,18} is: 67 Maximum non-Mcnugget number using {5,17,44} is: 131 Maximum non-Mcnugget number using {2,4,6} is: No maximum Maximum non-Mcnugget number using {3,6,15} is: No maximum
PicoLisp
<lang PicoLisp>(de nuggets1 (M)
(let Lst (range 0 M) (for A (range 0 M 6) (for B (range A M 9) (for C (range B M 20) (set (nth Lst (inc C))) ) ) ) (apply max Lst) ) )</lang>
Generator from fiber: <lang PicoLisp>(de nugg (M)
(co 'nugget (for A (range 0 M 6) (for B (range A M 9) (for C (range B M 20) (yield (inc C)) ) ) ) ) )
(de nuggets2 (M)
(let Lst (range 0 M) (while (nugg 100) (set (nth Lst @)) ) (apply max Lst) ) )</lang>
Test versions against each other: <lang PicoLis>(test
T (= 43 (nuggets1 100) (nuggets2 100) ) )</lang>
PL/I
<lang pli>mcnugget: procedure options(main);
declare nugget(0:100) bit, (a, b, c) fixed; do a=0 to 100; nugget(a) = '0'b; end; do a=0 to 100 by 6; do b=a to 100 by 9; do c=b to 100 by 20; nugget(c) = '1'b; end; end; end; do a=100 to 0 by -1; if ^nugget(a) then do; put skip list('Maximum non-McNuggets number:', a); stop; end; end;
end mcnugget;</lang>
- Output:
Maximum non-McNuggets number: 43
PL/M
<lang plm>100H: BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS; EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT; PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9, S); END PRINT;
PRINT$NUMBER: PROCEDURE (N);
DECLARE S (6) BYTE INITIAL ('...',13,10,'$'); DECLARE P ADDRESS, (N, C BASED P) BYTE; P = .S(3);
DIGIT:
P = P-1; C = N MOD 10 + '0'; N = N/10; IF N>0 THEN GO TO DIGIT; CALL PRINT(P);
END PRINT$NUMBER;
DECLARE (A, B, C) BYTE; DECLARE NUGGET (101) BYTE;
DO A=0 TO 100; NUGGET(A) = 0; END; DO A=0 TO 100 BY 6;
DO B=A TO 100 BY 9; DO C=B TO 100 BY 20; NUGGET(C) = -1; END; END;
END;
A = 100; DO WHILE NUGGET(A); A = A-1; END; CALL PRINT$NUMBER(A); CALL EXIT; EOF</lang>
- Output:
43
PowerShell
<lang powershell>$possible = @{} For ($i=0; $i -lt 18; $i++) {
For ($j=0; $j -lt 13; $j++) { For ( $k=0; $k -lt 6; $k++ ) { $possible[ $i*6 + $j*9 + $k*20 ] = $true } }
}
For ( $n=100; $n -gt 0; $n-- ) {
If ($possible[$n]) { Continue } Else { Break }
} Write-Host "Maximum non-McNuggets number is $n"</lang>
- Output:
Maximum non-McNuggets number is 43
Python
Python: REPL
It's a simple solution done on the command line: <lang python>>>> from itertools import product >>> nuggets = set(range(101)) >>> for s, n, t in product(range(100//6+1), range(100//9+1), range(100//20+1)): nuggets.discard(6*s + 9*n + 20*t)
>>> max(nuggets)
43
>>> </lang>
Single expression version (expect to be slower, however no noticeable difference on a Celeron B820 and haven't benchmarked): <lang python>>>> from itertools import product >>> max(x for x in range(100+1) if x not in ... (6*s + 9*n + 20*t for s, n, t in ... product(range(100//6+1), range(100//9+1), range(100//20+1)))) 43 >>> </lang>
Using Set Comprehension
<lang python>
- Wherein I observe that Set Comprehension is not intrinsically dysfunctional. Nigel Galloway: October 28th., 2018
n = {n for x in range(0,101,20) for y in range(x,101,9) for n in range(y,101,6)} g = {n for n in range(101)} print(max(g.difference(n))) </lang>
- Output:
43
List monad
A composition of pure functions, including dropwhile, which shows a more verbose and unwieldy (de-sugared) route to list comprehension, and reveals the underlying mechanics of what the (compact and elegant) built-in syntax expresses. May help to build intuition for confident use of the latter.
Note that the innermost function wraps its results in a (potentially empty) list. The resulting list of lists, some empty, is then flattened by the concatenation component of bind.
<lang python>mcNuggets list monad
from itertools import (chain, dropwhile)
- mcNuggetsByListMonad :: Int -> Set Int
def mcNuggetsByListMonad(limit):
McNugget numbers up to limit.
box = size(limit) return set( bind( box(6) )(lambda x: bind( box(9) )(lambda y: bind( box(20) )(lambda z: ( lambda v=sum([x, y, z]): ( [] if v > limit else [v] ) )()))) )
- Which, for comparison, is equivalent to:
- mcNuggetsByComprehension :: Int -> Set Int
def mcNuggetsByComprehension(limit):
McNuggets numbers up to limit box = size(limit) return { v for v in ( sum([x, y, z]) for x in box(6) for y in box(9) for z in box(20) ) if v <= limit }
- size :: Int -> Int -> [Int]
def size(limit):
Multiples of n up to limit. return lambda n: enumFromThenTo(0)(n)(limit)
- -------------------------- TEST --------------------------
def main():
List monad and set comprehension - parallel routes
def test(limit): def go(nuggets): ys = list(dropwhile( lambda x: x in nuggets, enumFromThenTo(limit)(limit - 1)(1) )) return str(ys[0]) if ys else ( 'No unreachable targets in this range.' ) return lambda nuggets: go(nuggets)
def fName(f): return f.__name__
limit = 100 print( fTable(main.__doc__ + ':\n')(fName)(test(limit))( lambda f: f(limit) )([mcNuggetsByListMonad, mcNuggetsByComprehension]) )
- ------------------------ GENERIC -------------------------
- bind (>>=) :: [a] -> (a -> [b]) -> [b]
def bind(xs):
List monad injection operator. Two computations sequentially composed, with any value produced by the first passed as an argument to the second. return lambda f: chain.from_iterable( map(f, xs) )
- enumFromThenTo :: Int -> Int -> Int -> [Int]
def enumFromThenTo(m):
Integer values enumerated from m to n with a step defined by nxt-m. def go(nxt, n): d = nxt - m return range(m, n - 1 if d < 0 else 1 + n, d) return lambda nxt: lambda n: go(nxt, n)
- ------------------------ DISPLAY -------------------------
- fTable :: String -> (a -> String) ->
- (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
Heading -> x display function -> fx display function -> f -> xs -> tabular string. def gox(xShow): def gofx(fxShow): def gof(f): def goxs(xs): ys = [xShow(x) for x in xs] w = max(map(len, ys))
def arrowed(x, y): return y.rjust(w, ' ') + ' -> ' + fxShow(f(x)) return s + '\n' + '\n'.join( map(arrowed, xs, ys) ) return goxs return gof return gofx return gox
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
List monad and set comprehension - parallel routes: mcNuggetsByListMonad -> 43 mcNuggetsByComprehension -> 43
Quackery
<lang Quackery>0 temp put 100 6 / times
[ i 6 * 100 9 / times [ dup i 9 * + 100 20 / times [ dup i 20 * + dup 101 < if [ dup bit temp take | temp put ] drop ] drop ] drop ]
-1 temp take 101 times
[ dup i bit & 0 = if [ nip i swap conclude ] ]
drop dup 0 < iff
[ drop say "There are no non-McNugget numbers below 101" ]
else
[ say "The largest non-McNugget number below 101 is " echo ]
char . emit</lang>
Output:
The largest non-McNugget number below 101 is 43.
R
Assuming that the natural numbers start at 0.
There are two natural approaches. The first is to generate all valid x, y, and z and then apply the function: <lang r>allInputs<-expand.grid(x=0:(100%/%6),y=0:(100%/%9),z=0:(100%/%20)) mcNuggets<-do.call(function(x,y,z) 6*x + 9*y + 20*z, allInputs)</lang> The second is to find all of the valid 6x, 9y, and 20z, and then sum them: <lang r>mcNuggets2<-rowSums(expand.grid(seq(0,100,6),seq(0,100,9),seq(0,100,20)))</lang> Either way, we get identical results, as checked by: <lang r>all(mcNuggets==mcNuggets2)</lang> For our final answer, note that our choice to remove values from the vector 0:100 means our outputs will already be sorted, unique, and no greater than 100. <lang r>results<-setdiff(0:100,mcNuggets) cat("The non-McNuggets numbers that are no greater than 100 are:",results,"\nThe largest is",max(results),"\n")</lang> Ultimately, this can be done in one line: <lang r>max(setdiff(0:100,rowSums(expand.grid(seq(0,100,6),seq(0,100,9),seq(0,100,20)))))</lang>
- Output:
> all(mcNuggets==mcNuggets2) [1] TRUE
The non-McNuggets numbers that are no greater than 100 are: 1 2 3 4 5 7 8 10 11 13 14 16 17 19 22 23 25 28 31 34 37 43 The largest is 43
> max(setdiff(0:100,rowSums(expand.grid(seq(0,100,6),seq(0,100,9),seq(0,100,20))))) [1] 43
Racket
(one of them)
<lang racket>#lang racket (apply max (set->list (for*/fold ((s (list->set (range 1 101))))
((x (in-range 0 101 20)) (y (in-range x 101 9)) (n (in-range y 101 6))) (set-remove s n))))</lang>
Raku
(formerly Perl 6)
No hard coded limits, no hard coded values. General purpose 3 value solver. Count values may be any 3 different positive integers, in any order, that are relatively prime.
Finds the smallest count value, then looks for the first run of consecutive count totals able to be generated, that is at least the length of the smallest count size. From then on, every number can be generated by simply adding multiples of the minimum count to each of the totals in that run.
<lang perl6>sub Mcnugget-number (*@counts) {
return '∞' if 1 < [gcd] @counts;
my $min = min @counts; my @meals; my @min;
for ^Inf -> $a { for 0..$a -> $b { for 0..$b -> $c { ($a, $b, $c).permutations.map: { @meals[ sum $_ Z* @counts ] = True } } } for @meals.grep: so *, :k { if @min.tail and @min.tail + 1 == $_ { @min.push: $_; last if $min == +@min } else { @min = $_; } } last if $min == +@min } @min[0] ?? @min[0] - 1 !! 0
}
for (6,9,20), (6,7,20), (1,3,20), (10,5,18), (5,17,44), (2,4,6), (3,6,15) -> $counts {
put "Maximum non-Mcnugget number using {$counts.join: ', '} is: ", Mcnugget-number(|$counts)
}</lang>
- Output:
Maximum non-Mcnugget number using 6, 9, 20 is: 43 Maximum non-Mcnugget number using 6, 7, 20 is: 29 Maximum non-Mcnugget number using 1, 3, 20 is: 0 Maximum non-Mcnugget number using 10, 5, 18 is: 67 Maximum non-Mcnugget number using 5, 17, 44 is: 131 Maximum non-Mcnugget number using 2, 4, 6 is: ∞ Maximum non-Mcnugget number using 3, 6, 15 is: ∞
REXX
This REXX version generalizes the problem (does not depend on fixed meal sizes), and also checks for:
- a meal that doesn't include McNuggets (in other words, zero nuggets)
- a meal size that includes a double order of nuggets
- a meal size that includes a single nugget (which means, no largest McNugget number)
- excludes meals that have a multiple order of nuggets
- automatically computes the high value algebraically instead of using 100.
<lang rexx>/*REXX pgm solves the McNuggets problem: the largest McNugget number for given meals. */ parse arg y /*obtain optional arguments from the CL*/ if y= | y="," then y= 6 9 20 /*Not specified? Then use the defaults*/ say 'The number of McNuggets in the serving sizes of: ' space(y) $=
- = 0 /*the Y list must be in ascending order*/
z=.
do j=1 for words(y); _= word(y, j) /*examine Y list for dups, neg, zeros*/ if _==1 then signal done /*Value ≡ 1? Then all values possible.*/ if _<1 then iterate /*ignore zero and negative # of nuggets*/ if wordpos(_, $)\==0 then iterate /*search for duplicate values. */ do k=1 for # /* " " multiple " */ if _//word($,k)==0 then iterate j /*a multiple of a previous value, skip.*/ end /*k*/ $= $ _; #= # + 1; $.#= _ /*add─►list; bump counter; assign value*/ end /*j*/
if #<2 then signal done /*not possible, go and tell bad news. */ _= gcd($) if _\==1 then signal done /* " " " " " " " */ if #==2 then z= $.1 * $.2 - $.1 - $.2 /*special case, construct the result. */ if z\==. then signal done h= 0 /*construct a theoretical high limit H.*/
do j=2 for #-1; _= j-1; _= $._; h= max(h, _ * $.j - _ - $.j) end /*j*/
@.=0
do j=1 for #; _= $.j /*populate the Jth + Kth summand. */ do a=_ by _ to h; @.a= 1 /*populate every multiple as possible. */ end /*s*/
do k=1 for h; if \@.k then iterate s= k + _; @.s= 1 /*add two #s; mark as being possible.*/ end /*k*/ end /*j*/
do z=h by -1 for h until \@.z /*find largest integer not summed. */ end /*z*/
say done: if z==. then say 'The largest McNuggets number not possible.'
else say 'The largest McNuggets number is: ' z
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ gcd: procedure; $=; do j=1 for arg(); $=$ arg(j); end; $= space($)
parse var $ x $; x= abs(x); do while $\==; parse var $ y $; y= abs(y); if y==0 then iterate do until y==0; parse value x//y y with y x; end end; return x</lang>
- output when using the default inputs:
The number of McNuggets in the serving sizes of: 6 9 20 The largest McNuggets number is: 43
Ring
<lang ring> Nuggets = list(100)
for six = 0 To 100/6
for nine = 0 To 100/9 for twenty = 0 To 100/20 n = six*6 + nine*9 + twenty*20 If n <= 100 and not (six = 0 and nine = 0 and twenty = 0) Nuggets[n] = true ok next next
next
for n = 100 to 1 step -1
if Nuggets[n] = false ? "Maximum non-McNuggets number is: " + n exit ok
next </lang>
- Output:
Maximum non-McNuggets number is: 43
Ruby
<lang ruby>def mcnugget(limit)
sv = (0..limit).to_a
(0..limit).step(6) do |s| (0..limit).step(9) do |n| (0..limit).step(20) do |t| sv.delete(s + n + t) end end end
sv.max
end
puts(mcnugget 100)</lang>
- Output:
43
Generic solution, allowing for more or less then 3 portion-sizes: <lang ruby>limit = 100 nugget_portions = [6, 9, 20]
arrs = nugget_portions.map{|n| 0.step(limit, n).to_a } hits = arrs.pop.product(*arrs).map(&:sum) p ((0..limit).to_a - hits).max # => 43</lang>
Rust
No hard limits. Generalization of Rødseth’s Algorithm explained in post. Working code: 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], [7_074_047, 8_214_596, 9_098_139], [582_795_988, 1_753_241_221, 6_814_151_015], [4, 30, 16], [12, 12, 13], [6, 15, 1], ]; for case in &test_cases { print!("g({}, {}, {}) = ", case[0], case[1], case[2]); println!( "{}", match frobenius(case.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 rod = if a_prime[0] == 1 { -1 } else { // 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; -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 { cc } else { let y = congruence(m, -cc, aa); (m * y + cc) / aa }
}</lang>
- Output:
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
Swift
<lang swift>func maxNugget(limit: Int) -> Int {
var (max, sixes, nines, twenties, i) = (0, 0, 0, 0, 0)
mainLoop: while i < limit { sixes = 0
while sixes * 6 < i { if sixes * 6 == i { i += 1 continue mainLoop }
nines = 0
while nines * 9 < i { if sixes * 6 + nines * 9 == i { i += 1 continue mainLoop }
twenties = 0
while twenties * 20 < i { if sixes * 6 + nines * 9 + twenties * 20 == i { i += 1 continue mainLoop }
twenties += 1 }
nines += 1 }
sixes += 1 }
max = i i += 1 }
return max
}
print(maxNugget(limit: 100))</lang>
- Output:
43
Tailspin
<lang tailspin> templates largestNonMcNuggetNumber
@: { largest: 0, mcNuggetNumbers: [1..$+20 -> 0] }; @.mcNuggetNumbers([6,9,20]): 1..3 -> 1; 1..$ -> # $@.largest ! when <?($@.mcNuggetNumbers($) <=0>)> do @.largest: $; otherwise @.mcNuggetNumbers([$ + 6, $ + 9, $ + 20]): 1..3 -> 1;
end largestNonMcNuggetNumber
100 -> largestNonMcNuggetNumber -> !OUT::write </lang>
- Output:
43
UNIX Shell
<lang bash>possible=() for (( i=0; i<18; ++i )); do
for (( j=0; j<13; ++j )); do for (( k=0; k<6; ++k )); do (( n = i*6 + j*9 + k*20 )) if (( n )); then possible[n]=1 fi done done
done
for (( n=100; n; n-- )); do
if [[ -n ${possible[n]} ]; then continue fi break
done
printf 'Maximum non-McNuggets number is %d\n' $n</lang>
- Output:
Maximum non-McNuggets number is 43
<lang bash>possible= i=0 while [ $i -lt 18 ]; do
j=0 while [ $j -lt 13 ]; do k=0 while [ $k -lt 6 ]; do possible="${possible+$possible }"`expr $i \* 6 + $j \* 9 + $k \* 20` k=`expr $k + 1` done j=`expr $j + 1` done i=`expr $i + 1`
done
n=100 while [ $n -gt 0 ]; do
if echo "$possible" | tr ' ' '\n' | fgrep -qx $n; then n=`expr $n - 1` continue fi break
done echo "Maximum non-McNuggets number is $n"</lang>
- Output:
Maximum non-McNuggets number is 43
Wren
<lang ecmascript>var mcnugget = Fn.new { |limit|
var sv = List.filled(limit+1, false) var s = 0 while (s <= limit) { var n = s while (n <= limit) { var t = n while (t <= limit) { sv[t] = true t = t + 20 } n = n + 9 } s = s + 6 } for (i in limit..0) { if (!sv[i]) { System.print("Maximum non-McNuggets number is %(i)") return } }
}
mcnugget.call(100)</lang>
- Output:
Maximum non-McNuggets number is 43
zkl
<lang zkl>nuggets:=[0..101].pump(List()); // (0,1,2,3..101), mutable foreach s,n,t in ([0..100/6],[0..100/9],[0..100/20])
{ nuggets[(6*s + 9*n + 20*t).min(101)]=0 }
println((0).max(nuggets));</lang>
- Output:
43