Chicken McNugget Numbers

29

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 é , então a resposta mais curta em bytes vence e as brechas padrão se aplicam!

racer290
fonte
15
Note-se 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. " ( mathworld )
Leaky Nun
11
Bem, então vamos levá-la como um desafio de compressão, mas graças para a nota
racer290
3
Alguém tem um link OEIS para isso ???
CraigR8806
2
O que você tem contra o pacote de pepitas de 4 peças? mcdonalds.com/us/en-us/product/chicken-mcnuggets-4-piece.html
Dan Neely
2
numberphile ...
Jason C

Respostas:

37

Python, 27 bytes

lambda n:0x82492cb6dbf>>n&1

Experimente online!

Anders Kaseorg
fonte
11
O que é este código mágico o_O isso é incrível
HyperNeutrino
Você pode remover o ~porque você pode trocar as saídas.
Leaky Nun
11
Além disso, 8953174650303tem exatamente o mesmo comprimento de 0x82492cb6dbf(embora menos legível).
Leaky Nun
2
@HyperNeutrino, o número mágico tem apenas os bits definidos que correspondem a números que não são números Chicken McNugget. Olhe para a sua representação binária e será muito mais clara.
David Z
11
Pena que você não pode facilmente usar esta mesma ideia com base 64
Jacob Garby
29

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.

Freira Furada
fonte
39 bytes
Sr. Xcoder
@ Mr.Xcoder atualizado.
Freira vazando
f=lambda n:n%3<1<n-2or n>20and f(n-20)isso funciona?
Zacharý
@ Zacharý obrigado, atualizado.
Freira vazando
11
Você pode remover o f=agora, pois não é recursivo.
notjagan
8

Python 2 , 28 bytes

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

Experimente online!

xnor
fonte
Usando algumas tentativas e erros e mapeando a primeira parte do intervalo, tenho uma idéia aproximada de como isso funciona. No entanto, gostaria de saber como você criou esta solução.
Leaky Nun
@LeakyNun Engraçado, eu pensei que este era o método natural e o seu era o mais inteligente :). Observei os possíveis valores da (n%3,n/20)sua lista de excluídos {(2, 0), (1, 0), (1, 1)}. Usar em -n%3vez disso deu uma desigualdade n/20>=(-n)%3. A partir daí, dediquei um tempo para reverter {3,23,43}3 mod 20 sem afetar 63,83 ... Descobri que mudar o ponto final da desigualdade para esses funcionava melhor.
Xnor
Bem, o meu método envolve realmente resolver o problema enquanto que o seu método é mexer com os valores na lista de excluídos, então eu diria que meu método é mais natural :)
Leaky Nun
7

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).
Dennis
fonte
4
Frango McNuggets ™ e geléia! Mmmm !!!
CJ Dennis
@CJDennis Na verdade, é Chicken McNuggets © e Jelly.
caird coinheringaahing
@cairdcoinheringaahing Na verdade, são Chicken McNuggets® e Jelly.
Dan
5

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.

Assistente de Trigo
fonte
3

Python 3 , 48 46 42 bytes

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

Experimente online!

Interruptores Truee False.

notjagan
fonte
Você pode alternar Truee, Falsepor padrão
Sr. Xcoder
3

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.

Freira Furada
fonte
Eu não entendo como inserir a entrada ..
racer290
@ racer290 Argumento da linha de comandos.
Erik the Outgolfer
3

Mathematica, 53 bytes

!Flatten@Table[Tr/@Tuples[{6,9,20},i],{i,#}]~FreeQ~#&
J42161217
fonte
Talvez você possa usar a FrobeniusSolvefunção
Alephalpha
3

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.

LegionMammal978
fonte
3

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!

Cody Gray
fonte
3

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
rev
fonte
11
Você tem links TIO duplicados.
Realização da ignorância
11
Boa resposta. Bem-vindo ao PPCG e ao mundo do 05AB1E. :) Uma coisa a golfe é a utilização para a cadeia (existem buitins para cordas 1-, 2-, e 3-carvão animal, sendo ', e, respectivamente). Acho que mais pode ser jogado, talvez usando uma abordagem diferente, mas, independentemente disso, essa é uma boa primeira resposta. +1 de mim.
Kevin Cruijssen 13/03
11
Estava de fato correto. Encontrado um 12-Byter utilizando o embutido Åœ: … ÇIÅœåPOĀ. É uma abordagem completamente diferente. Se você quiser que eu a publique como uma resposta separada, e não como um golfe seu, informe-me. PS: Não tenho 100% de certeza se os imprimíveis são permitidos na página de códigos 05AB1E . Pode ser necessário que haja uma codificação diferente nesse caso, o que faria com que alguns caracteres contassem com 2 bytes cada um. Nesse caso, ŽBo21вpoderia ser uma alternativa para +1 byte.
Kevin Cruijssen 13/03
Como Kevin menciona, nenhum dos 3 bytes na sua string está na página de código 05ab1e e, portanto, não pode ser usado sem contar todo o programa no utf-8, o que o tornaria muito mais longo. No entanto, você pode usar em ŽGç₂вvez da string e, ao mesmo tempo, salvar um byte no processo.
Emigna 13/03
Kevin, vá em frente. Seria bom ver abordagens diferentes. Emigna, obrigado pela sugestão, farei a alteração
rev
2

JavaScript (ES6), 69 64 bytes

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

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

darrylyeo
fonte
Eu gostaria, pelo menos, um "try-no" relação ..
racer290
@ racer290 Adicionado.
darrylyeo
n=>~'ABCDEFHIKLNOQRTWXZ]`cfl'.search(String.fromCharCode(n+65))para 63 bytes
Oki
2

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

fonte
O resultado está errado para 26 = 20 + 6.
Leaky Nun
O algoritmo @LeakyNun era muito ingênuo. Eu tive que seguir o plano B, que adicionou alguns bytes, mas parece produzir resultados corretos o tempo todo agora. Eu deveria ter iterado todos os valores para começar, em vez de confiar nos casos de teste da pergunta.
35 bytes
Freira com vazamento
11
24 bytes (veja acima)
Leaky Nun
11
@LeakyNun thanks! Ainda tenho muito a aprender sobre golfe.
1

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

ovs
fonte
n%3só pode ser 0 ou 1 ou 2, portanto n%3==2é equivalente a n%3>1.
Freira vazando
1

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.

notjagan
fonte
1

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]
qfwfq
fonte
11
A contagem de bytes 66não é 64. Mas você pode salvar muitos parênteses e colocar uma x/=0proteção para salvar alguns bytes, veja aqui .
ბიმო
1

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

SuperStormer
fonte
usando uma matriz simples seria salvar os bytes para .Split ...
Jonas Wilms
@ Jonas matriz é de 108 bytes, corda dividido é de 73 bytes
SuperStormer
hum jsbin.com/bucihuqefi/edit?console -11 bytes ...
Jonas Wilms
1

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]
caird coinheringaahing
fonte
1

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))
Wernisch
fonte
1

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 .

Titus
fonte
0

Python 2 , 61 bytes

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

Experimente online!

Chas Brown
fonte
Ou você pode usar pontos de código e descomprimir com chr.
Freira vazando
0

Mathematica, 59 bytes

!Select[IntegerPartitions@#,{6,9,20}~SubsetQ~#&]=={}&&#!=0&
J42161217
fonte
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)))

asgallant
fonte
0

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
ricdesi
fonte
0

Clojure 33 bytes

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

MONODA43
fonte
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!

alefalpha
fonte
Comentário irrelevante: qual foi o problema com esta resposta? # ~ SetPrecision ~ 1 &?
J42161217
@Jenny_mathy Falha no 0.25caso de teste.
alephalpha