McNuggets problem: Difference between revisions
m (→{{header|REXX}}: simplified a couple of DO loops.) |
(Added Go) |
||
Line 51: | Line 51: | ||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
||
=={{header|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> |
|||
{{out}} |
|||
<pre> |
|||
Maximum non-McNuggets number is 43 |
|||
</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 21:38, 25 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>
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
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>
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