Описание

Числа Chicken McNugget - это числа, которые можно выразить в виде суммы 6, 9 или 20 - начальных размеров известных коробок Chicken McNuggets, продаваемых McDonald's. В этой сумме число может встречаться более одного раза, так же 6 + 6 = 12как и такое число, и число должно «содержать» хотя бы один из упомянутых размеров. Первые цифры Куриные МакНуггет:

6
9
6 + 6 = 12
6 + 9 = 15
9 + 9 = 6 + 6 + 6 = 18
20
6 + 6 + 9 = 21
...

Вызов

Ваша задача состоит в том, чтобы написать программу или функцию, которая, учитывая положительное целое число, определяет, может ли это число быть выражено описанным способом, и поэтому является таким числом Цыпленка МакНуггета. Затем он должен вывести истинное или ложное значение на основе своего решения.

Контрольные примеры

6 -> true
7 -> false
12 -> true
15 -> true
21 -> true
40 -> true
42 -> true

Это код-гольф , поэтому выигрывает самый короткий ответ в байтах и ​​применяются стандартные лазейки!

Python, 27 байт

lambda n:0x82492cb6dbf>>n&1

Попробуйте онлайн!

Python 3 , 24 байта

lambda n:0<=n--n%3*20!=3

Попробуйте онлайн!

объяснение

С 6и9 без него можно сделать все целые числа делимыми, на 3которые они больше, чем 3указано в комментарии ovs к вызову . Предполагается, что можно также сделать 0. В заключение можно сделать 0,6,9,12,15,....

С одним экземпляром 20, можно сделать: 20,26,29,32,35,....

С двумя экземплярами 20, можно сделать: 40,46,49,52,55,....

Три экземпляра никогда не нужны, для 3 x 20 = 10 x 6.

Обратите внимание, что случаи, когда нет 20необходимости, также делятся на 3; случаи, когда 20это необходимо, оставляют остаток2 ; случаи, когда 20необходимо два, оставляет остаток 1.

Следовательно, количество 20необходимых может быть рассчитано как (-n)%3. Затем мы делаем, n-(((-n)%3)*20)чтобы удалить количество 20нужных из числа. Затем мы проверяем, что это число неотрицательно, но не является 3.

Python 2 , 28 байт

lambda n:-n%3-n/20<(n%20!=3)

Попробуйте онлайн!

Желе , 11 байт

ṗ3’æ.“©µÞ‘ċ

Попробуйте онлайн!

Как это работает

ṗ3’æ.“©µÞ‘ċ  Main link. Argument: n

ṗ3           Cartesian power; yield all 3-tuples over [1, ..., n].
  ’          Decrement all coordinates.
     “©µÞ‘   Yield [6, 9, 20].
   æ.        Take the dot product of each 3-tuple and [6, 9, 20].
          ċ  Count the occurrences of n (Positive for Chicken McNuggets numbers).

Haskell , 36 байт

f n|n<1=n==0
f n=any(f.(n-))[6,9,20]

Попробуйте онлайн!

объяснение

Это решение настолько простое, насколько это возможно. Первая строка объявляет, что для любого числа меньше 1 это число МакНуггет, если n==0. То есть это0 это число МакНуггет, а все отрицательные числа - нет.

Вторая строка объявляет, что для всех других чисел, n это число МакНуггет, если оно минус любой из размеров Наггетта, это число МакНуггет.

Это довольно простой рекурсивный поиск.

Python 3 , 48 46 42 байта

lambda n:n+50in b'2345679:<=?@BCEHIKNQTW]'

Попробуйте онлайн!

Переключатели Trueа False.

Желе , 11 байт

_20$%3$¿o>3

Попробуйте онлайн!

Порт моего ответа на Python , но немного измененный: вычитайте 20до деления на 3, затем проверяйте, принадлежит ли он 0,6,9,..., сопоставляя 0с входом (используя or), и затем проверяйте, больше ли он, чем3 .

Единственные три числа, которые появляются 0после завершения первого шага 0, это 20, или 40, если первый находится вне домена, а остальные больше чем 3.

Mathematica, 53 байта

!Flatten@Table[Tr/@Tuples[{6,9,20},i],{i,#}]~FreeQ~#&

Mathematica, 30 байт

{6,9,20}~FrobeniusSolve~#!={}&

Попробуйте это на Wolfram Sandbox.

Mathematica, 20 байтов

0<=#-20Mod[-#,3]!=3&

Анонимная функция. Принимает число как ввод и возвращает Trueили Falseкак вывод. Логика скопирована из ответа Лики Нун , с некоторыми дополнительными злоупотреблениями Inequality.

Машинный код x86-64, 22 байта

48 B8 41 92 34 6D DB F7 FF FF 83 F9 40 7D 03 48 D3 E8 83 E0 01 C3

Вышеуказанные байты определяют функцию в 64-битном машинном коде x86, которая определяет, является ли входное значение числом Чикен МакНуггет. Один положительный целочисленный параметр передается в ECXрегистр в соответствии с 64-битным соглашением о вызовах Microsoft, используемым в Windows. Результатом является логическое значение, возвращаемое в EAXрегистре.

Неуправляемая сборка мнемоники:

; bool IsMcNuggetNumber(int n)
; n is passed in ECX
    movabs  rax, 0xFFFFF7DB6D349241   ; load a 64-bit constant (the bit field)
    cmp     ecx, 64
    jge     TheEnd                    ; if input value >= 64, branch to end
    shr     rax, cl
TheEnd:
    and     eax, 1                    ; mask off all but LSB
    ret

Очевидно, что это сильно противоречит решению Андерса Касерга в Python , так как оно основано на битовом поле, представляющем значения, представляющие собой числа Чикен МакНуггет. В частности, каждый бит в этом поле, который соответствует действительному номеру Chicken McNugget, устанавливается в 1; все остальные биты установлены в 0. (Это считает, что 0 является действительным числом Chicken McNugget, но если вам это не нравится, ваши предпочтения - это однобитная модификация.)

Мы начинаем с простой загрузки этого значения в регистр. Это 64-битное значение, для кодирования которого уже требуется 8 байтов, плюс нам нужен однобайтовый префикс REX.W, так что мы действительно потратили немного времени на байты, но это суть решения, поэтому Я думаю, это того стоит.

Затем мы сдвигаем поле вправо на входное значение. ^* Наконец, мы маскировать все , кроме бита низшего порядка, и становится нашим Логическое результат.

Однако, поскольку вы не можете сдвинуться больше, чем на количество битов, фактически находящихся в значении, это работает только для входов от 0 до 63 Чтобы поддерживать более высокие входные значения, мы вставляем тест в верхней части функции, которая ветвится в нижней части входного значения:> = 64. Единственное, что интересно в этом, это то, что мы предварительно загружаем константу битового поля в RAX, а затем выполняем переход вплоть до инструкции, которая маскирует бит самого младшего порядка, гарантируя, что мы всегда возвращаем 1.

Попробуйте онлайн!
_{(Вызов функции C там помечен атрибутом, который заставляет GCC вызывать его, используя соглашение о вызовах Microsoft, которое использует мой ассемблерный код. Если бы TIO предоставил MSVC, в этом не было бы необходимости.)}

__
_{* В качестве альтернативы сдвигу мы могли бы использовать BTинструкцию x86 , но для кодирования это на 1 байт больше, так что никаких преимуществ. Если только мы не были вынуждены использовать другое соглашение о вызовах, в котором не было удобно передавать входное значение в ECXрегистр. Это было бы проблемой, потому что SHR требует, чтобы его исходный операнд был CLдля счетчика динамического сдвига. Поэтому другое соглашение о вызовах потребовало бы, чтобы мы MOVредактировали входное значение из любого регистра, в который оно было передано ECX, что стоило бы нам 2 байта. BTКоманда может использовать любой регистр в качестве операнда - источника, при стоимости только 1 байт. Так что в такой ситуации это было бы предпочтительнее.BT заносит значение соответствующего бита в флаг переноса (CF), так что вы бы использоватьSETCинструкция для получения этого значения в целочисленном регистре, например, ALчтобы оно могло быть возвращено вызывающей стороне.}

Альтернативная реализация, 23 байта

Вот альтернативная реализация, которая использует операции по модулю и умножению, чтобы определить, является ли входное значение числом Чикен МакНуггет.

Он использует соглашение о вызовах System V AMD64 , которое передает входное значение в EDIрегистр. Результат все еще логический, возвращенный в EAX.

Обратите внимание, что, в отличие от приведенного выше кода, это обратный логический тип (для удобства реализации). Он возвращает, falseесли входное значение является числом Чикен МакНуггет, или trueесли входное значение не является числом Чикен МакНуггет.

                    ; bool IsNotMcNuggetNumber(int n)
                    ; n is passed in EDI
8D 04 3F            lea    eax, [rdi+rdi*1]   ; multiply input by 2, and put result in EAX
83 FF 2B            cmp    edi, 43
7D 0E               jge    TheEnd             ; everything >= 43 is a McNugget number
99                  cdq                       ; zero EDX in only 1 byte
6A 03               push   3
59                  pop    rcx                ; short way to put 3 in ECX for DIV
F7 F1               div    ecx                ; divide input value by 3
6B D2 14            imul   edx, edx, 20       ; multiply remainder of division by 20
39 D7               cmp    edi, edx
0F 9C C0            setl   al                 ; AL = (original input) < (input % 3 * 20)
                 TheEnd:
C3                  ret

Уродливым в этом является необходимость явной обработки входных значений> = 43 с помощью функции сравнения и ветвления вверху. Очевидно, есть другие способы сделать это, которые не требуют ветвления, например алгоритм caird coinheringaahing , но для кодирования потребуется намного больше байтов, так что это не является разумным решением. Я полагаю, что мне, вероятно, не хватает некоторого хитрого трюка, который сделал бы эту работу более элегантной и занимал бы меньше байтов, чем решение на основе битового поля выше (поскольку кодирование самого битового поля занимает так много байтов), но я изучил это для некоторое время и до сих пор не вижу этого.

Ну ладно, попробуйте в любом случае онлайн !

05AB1E, 17 16 байт

ŽGç₂в©IED®âO«]I¢

Попробуйте онлайн!

объяснение

  ŽGç₂в                 The list [6, 9, 20]
       ©                Store this list in register_c
        IE              Loop <input> number of times
           ®â           Cartesian product stack contents with list in register_c
             O          Sum up the contents of each sub array
          D   «         List duplicated before taking Cartesian product, concat
               ]        End for loop
                I¢      Count occurences of input

JavaScript (ES6), 69 64 байта

n=>'ABCDEFHIKLNOQRTWXZ]`cfl'.includes(String.fromCharCode(n+65))

f=
n=>'ABCDEFHIKLNOQRTWXZ]`cfl'.includes(String.fromCharCode(n+65))

<input onkeydown=a.innerHTML=f(this.value)>
<pre id=a>

Выходные данные falseдля чисел Chicken McNugget, в trueпротивном случае.

Java, 21 57 24 bytes

Try it online!

Golfed:

n->(n-=n*2%3*20)>=0&n!=3

Ungolfed:

import java.util.*;

public class ChickenMcNuggetNumbers {

  private static final Set<Integer> FALSE_VALUES = new HashSet<>(Arrays.asList(
    new Integer[] { 0, 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23,
    25, 28, 31, 34, 37, 43 }));

  public static void main(String[] args) {
    for (int i = 0; i < 45; ++i) {
      System.out.println(i + " -> expected=" + !FALSE_VALUES.contains(i)
        + ", actual=" + f(n->(n-=n*2%3*20)>=0&n!=3, i));
    }
  }

  public static boolean f(java.util.function.Function<Integer, Boolean> f, int n) {
    return f.apply(n);
  }
}

Python 2, 51 bytes

-1 byte thanks to @LeakyNun

lambda n:max(n>43,25<n>n%3>1,5<n>n%3<1,n in[20,40])

Try it online! Footer prints all non McNugget numbers

Pyth, 15 bytes

fg.{CM"     "{T./

Try it online!

The string contains the characters corresponding to codepoints 6, 9, and 20.

Haskell, 64 56 bytes

I didn't do any bit trickery, but looking at the other answers it might actually be shorter to import the Bits module and use those methods. This approach checks much more directly.

f x=(\l->elem x[i*6+j*9+k*20|i<-l,j<-l,k<-l,x/=0])[0..x]

Javascript, 92 78 72 bytes

*saved 14 bytes thanks to @Jonasw

a=>!(a in[0,1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37,43])

Uses the fact that "All integers are McNugget numbers except 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43." from @LeakyNun's comment

APL (Dyalog), 19 bytes

⊢∊6 9 20+.×⍨∘↑∘⍳3⍴⊢

with ⎕IO←0

Same algorithm with Dennis's answer

Try it online!

Retina, 26 bytes

.+
$*
^(1{6}|1{9}|1{20})+$

Try it online!

Add++, 35 bytes

D,f,@,A6$%0=@20$%0=A3$%0=A8<A43<s1<

Try it online!

Look ma, no while loops. Or strings. Or lists. Or really anything that helps save bytes. But mainly because Add++ doesn't know what any of those are.

3 months later, I realised that this was invalid, and fixed it. Somehow, that golfed it by 13 bytes. This is a function that takes one argument and tests whether that argument is a Chicken McNugget number or not.

How it works

D,f,@,                        - Create a monadic (one argument) function called f (example argument: 3)
A                             - Push the argument again; STACK = [3 3]
 6                            - Push 6;                  STACK = [3 3 6]
  $                           - Swap the top two values; STACK = [3 6 3]
   %                          - Modulo;                  STACK = [3 3]
    0                         - Push 0;                  STACK = [3 3 0]
     =                        - Are they equal?          STACK = [3 0]
      @                       - Reverse the stack;       STACK = [0 3]
       20                     - Push 20;                 STACK = [0 3 20]
         $                    - Swap the top two values; STACK = [0 20 3]
          %                   - Modulo;                  STACK = [0 3]
           0                  - Push 0;                  STACK = [0 3 0]
            =                 - Are they equal?          STACK = [0 0]
             A                - Push the argument;       STACK = [0 0 3]
              3               - Push 3;                  STACK = [0 0 3 3]
               $              - Swap the top two values; STACK = [0 0 3 3]
                %             - Modulo;                  STACK = [0 0 0]
                 0            - Push 0;                  STACK = [0 0 0 0]
                  =           - Are they equal?          STACK = [0 0 1]
                   A          - Push the argument;       STACK = [0 0 1 3]
                    8         - Push 8;                  STACK = [0 0 1 3 8]
                     <        - Less than;               STACK = [0 0 1 0]
                      A       - Push the argument;       STACK = [0 0 1 0 3]
                       43     - Push 43;                 STACK = [0 0 1 0 3 43]
                         <    - Less than;               STACK = [0 0 1 0 0]
                          s   - Sum;                     STACK = [1]
                           1  - Push 1;                  STACK = [1 1]
                            < - Less than;               STACK = [0]

Excel, 87 bytes

=AND(OR(MOD(A1,3)*MOD(A1,20)*IF(A1>43,MOD(A1-40,3),1)*IF(A1>23,MOD(A1-20,3),1)=0),A1>5)

Alternatively, 92 bytes:

=CHOOSE(MOD(A1,3)+1,A1>3,IF(A1>43,MOD(A1-40,3)=0,A1=40),IF(A1>23,MOD(ABS(A1-20),3)=0,A1=20))

PHP, 69+1 bytes

for($n=$argn;$n>0;$n-=20)if($n%3<1)for($k=$n;$k>0;$k-=9)$k%6||die(1);

exits with 1 for a Chicken McNugget Number, 0 else.

Run as pipe with -n or try it online.

Python 2, 61 bytes

lambda n:n in[int(c,36)for c in'1234578ABDEGHJMNPSV']+[37,43]

Try it online!

Mathematica, 59 bytes

!Select[IntegerPartitions@#,{6,9,20}~SubsetQ~#&]=={}&&#!=0&

Javascript 37 bytes

Takes a positive integer n and outputs true for Chicken McNugget numbers and false for others.

F=n=>!(n<0||(n%6&&!F(n-9)&&!F(n-20)))

Explanation

F=n=>!(            // negate the internal test for non-Chicken McNugget numbers
    n<0 || (       // if n < 0, or
        n%6 &&     // if n % 6 is truthy,
        !F(n-9) && // and n-9 is not a Chicken McNugget number
        !F(n-20)   // and n-20 is not a Chicken McNugget number
                   // then n is not a Chicken McNugget number
    )
)

The recursion on this function is heinous, and for any sufficiently large n, you will exceed call stack limits. Here's a version that avoids those limits by checking if n is larger than the largest non-Chicken McNugget number (43 bytes [bonus points for being the largest non-Chicken McNugget number?]):

F=n=>n>43||!(n<0||(n%6&&!F(n-9)&&!F(n-20)))

F=n=>n>43||!(n<0||(n%6&&!F(n-9)&&!F(n-20)))

$('#input').on('keyup', () => $('#output').text(F(parseInt($('#input').val(), 10))))

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<input type="text" id="input" />
<span id="output"></span>

JavaScript ES5, 46 bytes

n=>n>5&&(!(n%20)||(n<24?!(n%3):n<44?n%3-1:1));

Explicit boolean answer, 50 bytes:

n=>!!(n>5&&(!(n%20)||(n<24?!(n%3):n<44?n%3-1:1)));

Clumsy, but it gets the job done. Returns false or 0 for every value that isn't 0, 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, or 43, and true, -1, or 1 for everything else.

Explicit solution returns true or false only.

n=>!!(                                          ); forces Boolean type (optional)
      n>5                                          false for 0, 1, 2, 3, 4, 5 (and negative inputs)
            !(n%20)                                explicit true for 20, 40
                      n<24?!(n%3)                  false for 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23
                                  n<44?n%3-1       false for 25, 28, 31, 34, 37, 43

Clojure 33 bytes

An on ok quick attempt: #(-> %(rem 20)(rem 9)(rem 6)(= 0))

Pari/GP, 48 bytes

0 is falsy. everything else is truthy.

n->n*Vec(1/(1-x^6)/(1-x^9)/(1-x^20)+O(x^n++))[n]

Try it online!