Descrição

Os números do Chicken McNugget são números que podem ser expressos como uma soma de 6, 9 ou 20 - os tamanhos iniciais das famosas caixas Chicken McNuggets vendidas pelo McDonald's. Nessa soma, um número pode ocorrer mais de uma vez, o mesmo 6 + 6 = 12ocorre também, e o número deve "conter" pelo menos um dos tamanhos mencionados. Os primeiros números do Chicken McNugget são:

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

Desafio

Sua tarefa é escrever um programa ou função que, dado um número inteiro positivo, determine se esse número pode ser expresso da maneira descrita, portanto, é um número do Chicken McNugget. Em seguida, deve gerar um valor verdadeiro ou falso com base em sua decisão.

Casos de teste

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

Isso é código-golfe , então a resposta mais curta em bytes vence e as brechas padrão se aplicam!

Python, 27 bytes

lambda n:0x82492cb6dbf>>n&1

Experimente online!

Python 3 , 24 bytes

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

Experimente online!

Explicação

Com 6e 9sozinho, é possível tornar todos os números inteiros divisíveis pelos 3quais são maiores que 3, como é afirmado no comentário de ovs ao desafio . Supõe-se que também se pode fazer 0. Em conclusão, pode-se fazer0,6,9,12,15,... .

Com uma instância de 20, pode-se fazer:20,26,29,32,35,... .

Com duas instâncias de 20, pode-se fazer:40,46,49,52,55,... .

Três instâncias nunca são necessárias, para 3 x 20 = 10 x 6.

Observe que os casos em que não 20é necessário também são divisíveis por 3; os casos em que um 20é necessário deixa um restante 2; Nos casos em que 20são necessários dois, resta um1 .

O número de 20itens necessários pode, portanto, ser calculado por (-n)%3. Então, fazemos n-(((-n)%3)*20)para remover o número 20necessário do número. Depois, verificamos que esse número não é negativo, mas não é 3.

Python 2 , 28 bytes

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

Experimente online!

Gelatina , 11 bytes

ṗ3’æ.“©µÞ‘ċ

Experimente online!

Como funciona

ṗ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 bytes

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

Experimente online!

Explicação

Esta solução é a mais simples possível. A primeira linha declara que, para qualquer número menor que 1, é um número McNugget if n==0. Ou seja, esse 0é um número McNugget e todos os números negativos não são.

A segunda linha declara que, para todos os outros números, né um número McNugget se menos um dos tamanhos de Nugget for um número McNugget.

Esta é uma pesquisa recursiva bastante simples.

Python 3 , 48 46 42 bytes

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

Experimente online!

Interruptores Truee False.

Gelatina , 11 bytes

_20$%3$¿o>3

Experimente online!

Porta da minha resposta Python , mas ligeiramente modificada: subtraia 20até ser divisível por 3, verifique se ela pertence 0,6,9,...mapeando 0a entrada (usando or) e verifique se é maior que3 .

Os únicos três números produzidos 0após a conclusão da primeira etapa são 0, 20ou 40, com a primeira fora do domínio e o restante sendo maior que 3.

Mathematica, 53 bytes

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

Mathematica, 30 bytes

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

Experimente na Wolfram Sandbox.

Mathematica, 20 bytes

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

Função anônima. Toma um número como entrada e retorna Trueou Falsecomo saída. A lógica foi copiada da resposta de Leaky Nun , com alguns abusos adicionais Inequality.

Código da máquina x86-64, 22 bytes

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

Os bytes acima definem uma função no código de máquina x86 de 64 bits que determina se o valor de entrada é um número do Chicken McNugget. O parâmetro inteiro positivo único é passado no ECXregistro, seguindo a convenção de chamada da Microsoft de 64 bits usada no Windows. O resultado é um valor booleano retornado no EAXregistro.

Mnemônicos de montagem não destruídos:

; 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

Obviamente, isso se assemelha bastante à solução de Anders Kaseorg em Python , na medida em que é baseada em um campo de bits que representa os valores que são números de Chicken McNugget. Especificamente, cada bit nesse campo que corresponde a um número válido de Chicken McNugget é definido como 1; todos os outros bits são definidos como 0. (Isso considera 0 como um número válido do Chicken McNugget, mas se você não gosta disso, sua preferência é modificar um bit).

Começamos simplesmente carregando esse valor em um registro. É um valor de 64 bits, que já leva 8 bytes para codificar, além de precisarmos de um prefixo REX.W de um byte; portanto, estamos realmente perdendo o peso em termos de bytes, mas esse é o coração da solução. Eu acho que vale a pena.

Em seguida, deslocamos o campo para a direita pelo valor de entrada. ^* Finalmente, mascaramos tudo, exceto o bit de ordem mais baixa, e isso se torna nosso resultado booleano.

No entanto, como você não pode mudar mais do que o número de bits realmente no valor, isso funciona apenas para entradas de 0 a 63. Para oferecer suporte a valores de entrada mais altos, inserimos um teste na parte superior da função que se ramifica na parte inferior do valor de entrada é> = 64. A única coisa interessante sobre isso é que pré - carregamos a constante do campo de bits em RAXe depois ramificamos até a instrução que mascara o bit de ordem mais baixa, garantindo assim que sempre retornemos 1.

Experimente online!
_{(A chamada de função C é anotada com um atributo que faz com que o GCC a chame usando a convenção de chamada da Microsoft que meu código de assembly usa. Se o TIO tivesse fornecido o MSVC, isso não seria necessário.)}

__
_{* Como alternativa a um turno, poderíamos ter usado a BTinstrução x86 , mas é um byte a mais para codificar, portanto não há vantagem. A menos que fôssemos forçados a usar uma convenção de chamada diferente que não passasse convenientemente o valor de entrada no ECXregistro. Isso seria um problema, porque SHR requer que seu operando de origem seja CLpara uma contagem de turnos dinâmicos. Portanto, uma convenção de chamada diferente exigiria que MOVeditássemos o valor de entrada de qualquer registro para o qual fosse passado ECX, o que nos custaria 2 bytes. A BTinstrução pode usar qualquer um registro como um operando de origem, a um custo de apenas 1 byte. Então, nessa situação, seria preferível.BT coloca o valor do bit correspondente no sinalizador de transporte (CF), portanto você usaria umSETCinstrução para obter esse valor em um registro inteiro, como ALpara que ele pudesse ser retornado ao chamador.}

Implementação alternativa, 23 bytes

Aqui está uma implementação alternativa que usa operações de módulo e multiplicação para determinar se o valor de entrada é um número do Chicken McNugget.

Ele usa a convenção de chamada System64 AMD64 , que passa o valor de entrada no EDIregistro. O resultado ainda é um booleano, retornado EAX.

Observe, porém, que, diferentemente do código acima, esse é um booleano inverso (para conveniência da implementação). Retorna falsese o valor de entrada for um número do Chicken McNugget ou truese o valor de entrada não for um número do Chicken McNugget.

                    ; 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

O que é feio nisso é a necessidade de lidar explicitamente com valores de entrada> = 43 por meio de uma comparação e ramificação na parte superior. Obviamente, existem outras maneiras de fazer isso que não exigem ramificação, como o algoritmo de caird coinheringaahing , mas isso levaria muito mais bytes para codificar, portanto, não é uma solução razoável. Eu acho que provavelmente estou perdendo algum truque de manipulação de bits que faria isso funcionar com mais elegância e ter menos bytes do que a solução baseada em campo de bits acima (já que a codificação do próprio campo de bits leva tantos bytes), mas eu o estudei um tempo e ainda não consigo vê-lo.

Bem, tente online de qualquer maneira!

05AB1E, 17 16 bytes

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

Experimente online!

Explicação

  Ž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 bytes

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>

Saídas falsepara números Chicken McNugget, truecaso contrário.

Java, 21 57 24 bytes

Experimente online!

Golfe:

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 graças a @LeakyNun

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

Experimente online! Rodapé imprime todos os números que não são do McNugget

Pitão , 15 bytes

fg.{CM"     "{T./

Experimente online!

A sequência contém os caracteres correspondentes aos pontos de código 6, 9 e 20.

Haskell, 64 56 bytes

Eu não fiz nenhum truque, mas olhando para as outras respostas, pode ser mais curto importar o Bitsmódulo e usar esses métodos. Essa abordagem verifica muito mais diretamente.

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

* salvou 14 bytes graças a @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])

Usa o fato de que "Todos os números inteiros são números McNugget, exceto 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34 , 37 e 43. " do comentário de @ LeakyNun

APL (Dyalog) , 19 bytes

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

com ⎕IO←0

Mesmo algoritmo com a resposta de Dennis

Experimente online!

Retina , 26 bytes

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

Experimente online!

Adicionar ++ , 35 bytes

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

Experimente online!

Olhe ma, não enquanto os loops. Ou cordas. Ou listas. Ou realmente qualquer coisa que ajude a salvar bytes. Mas principalmente porque o Add ++ não sabe o que é isso.

Três meses depois, percebi que isso era inválido e o corrigi. De alguma forma, isso aumentou em 13 bytes. Essa é uma função que pega um argumento e testa se esse argumento é ou não um número Chicken McNugget.

Como funciona

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)

Como alternativa, 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);

sai com 1para um número Chicken McNugget, caso 0contrário.

Execute como pipe -nou experimente online .

Python 2 , 61 bytes

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

Experimente online!

Mathematica, 59 bytes

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

Javascript 37 bytes

Obtém um número inteiro positivo ne gera resultados truepara números do Chicken McNugget e falsepara outros.

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

Explicação

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

A recursão nessa função é hedionda e, para qualquer suficientemente grande n, você excederá os limites da pilha de chamadas. Aqui está uma versão que evita esses limites, verificando se né maior que o maior número não-Chicken McNugget (43 bytes [pontos de bônus por ser o maior número não-Chicken McNugget?]):

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));

Resposta booleana explícita, 50 bytes:

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

Desajeitado, mas faz o trabalho. Retorna falseou 0para todo valor que não seja 0, 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34 , 37, ou 43, e true, -1, ou 1para tudo o resto.

Solução explícita retorna trueou falseapenas.

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

Uma tentativa rápida e ok: #(-> %(rem 20)(rem 9)(rem 6)(= 0))

Pari / GP , 48 bytes

0é falso. tudo o resto é verdade.

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

Experimente online!