Descripción

Los números de Chicken McNugget son números que se pueden expresar como una suma de 6, 9 o 20, los tamaños iniciales de las famosas cajas de Chicken McNugget vendidas por McDonald's. En esa suma, un número puede aparecer más de una vez, también lo 6 + 6 = 12es, y el número debe "contener" al menos uno de los tamaños mencionados. Los primeros números de Chicken McNugget son:

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

Reto

Su tarea es escribir un programa o función, que, dado un número entero positivo, determina si este número puede expresarse de la manera descrita, por lo tanto, es un número de Chicken McNugget. Luego debería generar un valor verdadero o falso basado en su decisión.

Casos de prueba

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

Este es el código de golf , por lo que gana la respuesta más corta en bytes y se aplican las lagunas estándar.

Python, 27 bytes

lambda n:0x82492cb6dbf>>n&1

Pruébalo en línea!

Python 3 , 24 bytes

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

Pruébalo en línea!

Explicación

Con 6y 9solos, se puede hacer todos los números enteros divisibles por 3lo que son mayores que 3, como se dice en el comentario de ovs al desafío . Se supone que también se puede hacer 0. En conclusión, uno puede hacer 0,6,9,12,15,....

Con una instancia de 20, uno puede hacer: 20,26,29,32,35,....

Con dos instancias de 20, uno puede hacer: 40,46,49,52,55,....

Tres instancias nunca son necesarias, para 3 x 20 = 10 x 6.

Tenga en cuenta que los casos en los que no 20se necesita también es divisible por 3; los casos donde 20se necesita uno deja un resto de 2; los casos en que 20se necesitan dos dejan un resto de 1.

Por lo tanto, el número de 20necesarios puede calcularse mediante (-n)%3. Luego, hacemos n-(((-n)%3)*20)para eliminar el número de 20necesarios del número. Luego verificamos que este número no es negativo, pero no lo es 3.

Python 2 , 28 bytes

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

Pruébalo en línea!

Jalea , 11 bytes

ṗ3’æ.“©µÞ‘ċ

Pruébalo en línea!

Cómo 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]

Pruébalo en línea!

Explicación

Esta solución es tan sencilla como puede ser. La primera línea declara que para cualquier número menor que 1 es un número de McNugget si n==0. Es decir que 0es un número de McNugget y todos los números negativos no lo son.

La segunda línea declara que para todos los demás números, nes un número de McNugget si menos uno de los tamaños de Nugget es un número de McNugget.

Esta es una búsqueda recursiva bastante simple.

Python 3 , 48 46 42 bytes

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

Pruébalo en línea!

Interruptores Truey False.

Jalea , 11 bytes

_20$%3$¿o>3

Pruébalo en línea!

Puerto de mi respuesta de Python , pero ligeramente modificado: reste 20hasta que sea divisible por 3, luego verifique si pertenece al 0,6,9,...mapeo 0a la entrada (usando or), y luego verifique si es mayor que 3.

Los únicos tres números que se producen 0al completar el primer paso son 0, 20o 40, con el primero fuera del dominio, y el resto es mayor que 3.

Mathematica, 53 bytes

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

Mathematica, 30 bytes

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

Pruébalo en Wolfram Sandbox.

Mathematica, 20 bytes

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

Función anónima. Toma un número como entrada y devuelve Trueo Falsecomo salida. Lógica copiada de la respuesta de Leaky Nun , con algún abuso adicional de Inequality.

Código de 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

Los bytes anteriores definen una función en el código de máquina x86 de 64 bits que determina si el valor de entrada es un número Chicken McNugget. El parámetro entero positivo único se pasa en el ECXregistro, siguiendo la convención de llamadas de Microsoft de 64 bits utilizada en Windows. El resultado es un valor booleano devuelto en el EAXregistro.

Mnemónicos de ensamblaje sin golf:

; 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, esto juega mucho con la solución de Anders Kaseorg en Python , ya que se basa en un campo de bits que representa los valores que son números de Chicken McNugget. Específicamente, cada bit en este campo que corresponde a un número válido de Chicken McNugget se establece en 1; todos los demás bits se establecen en 0. (Esto considera que 0 es un número válido de Chicken McNugget, pero si no le gusta, su preferencia es una modificación de un solo bit).

Comenzamos simplemente cargando este valor en un registro. Es un valor de 64 bits, que ya requiere 8 bytes para codificar, además de que necesitamos un prefijo REX.W de un byte, por lo que realmente estamos siendo bastante derrochadores en términos de bytes, pero este es el corazón de la solución, por lo que Supongo que vale la pena.

Luego cambiamos el campo a la derecha por el valor de entrada. ^* Finalmente, enmascaramos todo excepto el bit de orden inferior, y ese se convierte en nuestro resultado booleano.

Sin embargo, dado que no puede cambiar más de la cantidad de bits realmente en el valor, esto solo funciona para entradas de 0 a 63. Para admitir valores de entrada más altos, insertamos una prueba en la parte superior de la función que se bifurca en la parte inferior del valor de entrada es> = 64. Lo único interesante de esto es que precargamos la constante del campo de bits RAXy luego se bifurca hasta la instrucción que enmascara el bit de orden más bajo, asegurando así que siempre devolvamos 1.

Pruébalo en línea!
_{(La llamada de función C allí está anotada con un atributo que hace que GCC lo llame usando la convención de llamadas de Microsoft que usa mi código de ensamblaje. Si TIO hubiera proporcionado MSVC, esto no sería necesario).}

__
_{* Como alternativa a un cambio, podríamos haber usado la BTinstrucción x86 , pero eso es 1 byte más para codificar, por lo que no es una ventaja. A menos que nos veamos obligados a usar una convención de llamada diferente que no pasa convenientemente el valor de entrada en el ECXregistro. Esto sería un problema porque SHR requiere que su operando de origen sea CLpara un conteo de desplazamiento dinámico. Por lo tanto, una convención de llamada diferente requeriría que MOVeditemos el valor de entrada del registro al que se pasó ECX, lo que nos costaría 2 bytes. La BTinstrucción puede usar cualquier registro como operando de origen, a un costo de solo 1 byte. Entonces, en esa situación, sería preferible.BTcoloca el valor del bit correspondiente en el indicador de acarreo (CF), por lo que usaría una SETCinstrucción para obtener ese valor en un registro entero como ALpara que pueda devolverse al llamante.}

Implementación alternativa, 23 bytes

Aquí hay una implementación alternativa que usa operaciones de módulo y multiplicación para determinar si el valor de entrada es un número Chicken McNugget.

Utiliza la convención de llamadas System V AMD64 , que pasa el valor de entrada en el EDIregistro. El resultado sigue siendo un booleano, devuelto en EAX.

Sin embargo, tenga en cuenta que, a diferencia del código anterior, este es un booleano inverso (por conveniencia de implementación). Devuelve falsesi el valor de entrada es un número de Chicken McNugget, o truesi el valor de entrada no es un número de 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

Lo feo de esto es la necesidad de manejar explícitamente los valores de entrada> = 43 mediante una comparación y ramificación en la parte superior. Obviamente, hay otras formas de hacerlo que no requieren ramificación, como el algoritmo de caird coinheringaahing , pero esto requeriría muchos más bytes para codificar, por lo que no es una solución razonable. Supongo que probablemente me estoy perdiendo algún truco que hace que esto funcione de manera más elegante y tenga menos bytes que la solución basada en el campo de bits anterior (ya que codificar el campo de bits en sí toma tantos bytes), pero he estudiado esto para un rato y todavía no puedo verlo.

Oh, bueno, pruébalo en línea de todos modos

05AB1E, 17 16 bytes

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

Pruébalo en línea!

Explicación

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

Salidas falsepara números de Chicken McNugget, de lo truecontrario.

Java, 21 57 24 bytes

Pruébalo en línea!

Golfizado:

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

Sin golf:

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 gracias a @LeakyNun

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

Pruébalo en línea! El pie de página imprime todos los números que no son de McNugget

Pyth , 15 bytes

fg.{CM"     "{T./

Pruébalo en línea!

La cadena contiene los caracteres correspondientes a los puntos de código 6, 9 y 20.

Haskell, 64 56 bytes

No hice ningún truco, pero al mirar las otras respuestas, en realidad podría ser más corto importar el Bitsmódulo y usar esos métodos. Este enfoque verifica mucho más directamente.

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

* guardado 14 bytes gracias 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])

Utiliza el hecho de que "Todos los enteros son números de McNugget, excepto 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34 , 37 y 43. " del comentario de @ LeakyNun

APL (Dyalog) , 19 bytes

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

con ⎕IO←0

Mismo algoritmo con la respuesta de Dennis

Pruébalo en línea!

Retina , 26 bytes

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

Pruébalo en línea!

Agregar ++ , 35 bytes

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

Pruébalo en línea!

Mira ma, no mientras bucles. O cuerdas. O listas. O realmente cualquier cosa que ayude a guardar bytes. Pero principalmente porque Add ++ no sabe cuáles son esos.

3 meses después, me di cuenta de que esto no era válido y lo solucioné. De alguna manera, eso lo jugó por 13 bytes. Esta es una función que toma un argumento y prueba si ese argumento es un número de Chicken McNugget o no.

Cómo 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)

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

sale con 1un número de Chicken McNugget, de lo 0contrario.

Ejecutar como tubería -no probarlo en línea .

Python 2 , 61 bytes

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

Pruébalo en línea!

Mathematica, 59 bytes

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

Javascript 37 bytes

Toma un entero positivo ny genera resultados truepara los números de Chicken McNugget y falsepara otros.

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

Explicación

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

La recurrencia en esta función es atroz, y para cualquier lo suficientemente grande n, excederá los límites de la pila de llamadas. Aquí hay una versión que evita esos límites al verificar si nes mayor que el número más grande que no es Chicken McNugget (43 bytes [¿puntos de bonificación por ser el número más grande que no es 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));

Respuesta booleana explícita, 50 bytes:

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

Torpe, pero hace el trabajo. Devuelve falseo 0para cada valor que no sea 0, 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34 , 37, o 43, y true, -1o 1para todo lo demás.

La solución explícita devuelve trueo falsesolo.

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

Un intento rápido de ok: #(-> %(rem 20)(rem 9)(rem 6)(= 0))

Pari / GP , 48 bytes

0es falso todo lo demás es verdad.

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

Pruébalo en línea!