McNuggets problem: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|Python}}: Sub-headers.)
Line 482: Line 482:


=={{header|Python}}==
=={{header|Python}}==
===Python: REPL===
⚫
{{trans|FSharp}}
It's a simple solution done on the command line:
⚫
<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>
⚫
{{out}}
⚫
<pre>
⚫
43
⚫
</pre>
<lang python>>>> from itertools import product
<lang python>>>> from itertools import product
>>> nuggets = set(range(101))
>>> nuggets = set(range(101))
Line 511: Line 502:
>>> </lang>
>>> </lang>


===Python: Just functions===

Or, composing pure functions, including dropwhile:
Or, composing pure functions, including dropwhile:
<lang python>from itertools import (chain, dropwhile)
<lang python>from itertools import (chain, dropwhile)
Line 565: Line 556:
{{Out}}
{{Out}}
<pre>43</pre>
<pre>43</pre>

===Python: From F#===
⚫
{{trans|FSharp}}
⚫
<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>
⚫
{{out}}
⚫
<pre>
⚫
43
⚫
</pre>


=={{header|REXX}}==
=={{header|REXX}}==

Revision as of 16:20, 28 October 2018

Task
McNuggets problem
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).

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

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

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

==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) import Data.List (uncons)

gaps :: [Int] gaps = dropWhile (`member` mcNuggets) [100,99 .. 1]

mcNuggets :: Set Int mcNuggets = 

 fromList $
 [0 .. quot 100 6] >>=
 \x ->
    [0 .. quot 100 9] >>=
    \y ->
       [0 .. quot 100 20] >>=
       \z ->
          let v = sum [6 * x, 9 * y, 20 * z]
          in [ v
             | 101 > v ]

main :: IO () main = 

 print $
 case uncons gaps of
   Just (x, _) -> show x
   Nothing -> "No unreachable quantities found ..."</lang>

43

JavaScript

<lang javascript>(() => { 

   'use strict';

   // main :: IO ()
   const main = () => {

       const
           upTo = enumFromTo(0),
           nuggets = new Set(
               bindList(
                   upTo(quot(100, 6)),
                   x => bindList(
                       upTo(quot(100, 9)),
                       y => bindList(
                           upTo(quot(100, 20)),
                           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 ----------------------------------

   // bindList (>>=) :: [a] -> (a -> [b]) -> [b]
   const bindList = (xs, mf) => [].concat.apply([], xs.map(mf));

   // 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

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.

Kotlin

Translation of: 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:
Maximum non-McNuggets number is 43

Perl 6

Works with: Rakudo version 2018.09

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, though if they are all even, no maximum non-McNugget number is possible (can't form odd numbers).

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 'No maximum' if so all @counts »%%» 2;

   my $min = [min] @counts;
   my @meals;
   my @min;

   for ^Inf -> $a {
       for 0..$a -> $b {
           for 0..$b -> $c {
               ($a, $b, $c).permutations.map: {
                   for flat $_ Z* @counts {
                       @meals[sum $^first, $^second, $^third] = 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) -> $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: No maximum

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>

Python: Just functions

Or, composing pure functions, including dropwhile: <lang python>from itertools import (chain, dropwhile)


def main(): 

   upTo = enumFromTo(0)
   mcNuggets = set(
       concatMap(
           lambda x:
           concatMap(
               lambda y:
               concatMap(
                   lambda z: (
                       lambda v=sum([6 * x, 9 * y, 20 * z]): (
                           [v] if 101 > v else []
                       )
                   )()
               )(upTo(100 // 20))
           )(upTo(100 // 9))
       )(upTo(100 // 6))
   )
   xs = list(dropwhile(
       lambda x: x in mcNuggets,
       enumFromThenTo(100)(99)(1))
   )
   print(
       xs[0] if xs else 'No unreachable quantities found in this range.'
   )


  1. GENERIC ABSTRACTIONS ------------------------------------
  1. concatMap :: (a -> [b]) -> [a] -> [b]

def concatMap(f): 

   return lambda xs: list(chain.from_iterable(map(f, xs)))


  1. enumFromThenTo :: Int -> Int -> Int -> [Int]

def enumFromThenTo(m): 

   return lambda next: lambda n: (
       list(range(m, 1 + n, next - m))
   )


  1. enumFromTo :: Int -> Int -> [Int]

def enumFromTo(m): 

   return lambda n: list(range(m, 1 + n))


if __name__ == '__main__': 

   main()</lang>
Output:
43

Python: From F#

Translation of: FSharp

<lang python>

  1. 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

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) $=

  1. = 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

Translation of: Go

<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

Translation of: Python

<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
Retrieved from "https://rosettacode.org/wiki/McNuggets_problem?oldid=286129"