McNuggets problem: Difference between revisions
(→{{header|Python}}: add single-expression version) |
(Added Kotlin) |
||
Line 84: | Line 84: | ||
{{out}} |
{{out}} |
||
<pre> |
|||
Maximum non-McNuggets number is 43 |
|||
</pre> |
|||
=={{header|Kotlin}}== |
|||
{{trans|Go}} |
|||
<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}} |
|||
<pre> |
<pre> |
||
Maximum non-McNuggets number is 43 |
Maximum non-McNuggets number is 43 |
Revision as of 10:50, 26 October 2018
You are encouraged to solve this task according to the task description, using any language you may know.
From Wikipedia:
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).
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
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
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
Python
<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>
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
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
zkl
<lang zkl>nuggets:=[0..100].pump(List()); // (0,1,2,3..100), mutable foreach s,n,t in ([0..100/6],[0..100/9],[0..100/20])
{ nuggets[(6*s + 9*n + 20*t).min(100)]=0 }
println((0).max(nuggets));</lang>
- Output:
43