Reto

Dada una lista de enteros positivos, encuentre si existe una permutación donde tomar hasta un bit de cada uno de los enteros, 1se puede crear un número binario que consista en todos los s.

El número de bits en el número binario resultante es igual al MSB más alto en la lista de enteros.

Salida

Su código debe generar o devolver un valor verdadero / falso que indique si existe tal permutación.

Ejemplos

Verdad:

Con la lista [4, 5, 2]y su representación binaria [100, 101, 10], podemos usar los bits tercero, primero y segundo, respectivamente, para crear 111:

4  ->  100  ->  100  ->  1
5  ->  101  ->  101  ->    1
2  ->  010  ->  010  ->   1
Result                   111

Con la lista [3, 3, 3], todos los números tienen los primeros y segundos bits configurados como 1, por lo que podemos elegir con un número de sobra:

3  ->  11  ->  11  ->  1
3  ->  11  ->  11  ->   1
3  ->  11  ->  11  ->
Result                 11

Falsey

Con la lista [4, 6, 2], ninguno de los números tiene el primer bit establecido como 1, por lo que no se puede crear el número binario:

4  ->  100
6  ->  110
2  ->  010

Con la lista [1, 7, 1], solo uno de los números tiene el segundo y tercer bit establecido como 1, y el número no se puede crear:

1  ->  001
7  ->  111
1  ->  001

Obviamente, si el número máximo de bits establecidos excede el número de enteros, el número de resultado nunca se puede crear.

Casos de prueba

Verdad:

[1]
[1, 2]
[3, 3]
[3, 3, 3]
[4, 5, 2]
[1, 1, 1, 1]
[15, 15, 15, 15]
[52, 114, 61, 19, 73, 54, 83, 29]
[231, 92, 39, 210, 187, 101, 78, 39]

Falsey

[2]
[2, 2]
[4, 6, 2]
[1, 7, 1]
[15, 15, 15]
[1, 15, 3, 1]
[13, 83, 86, 29, 8, 87, 26, 21]
[154, 19, 141, 28, 27, 6, 18, 137]

Reglas

Las lagunas estándar están prohibidas. Como se trata de código de golf , ¡la entrada más corta gana!

Jalea , 11 bytes

BUT€ŒpṬz0PẸ

Pruébalo en línea!

Cómo funciona

BUT€ŒpṬz0PẸ  Main link. Argument: A (array)

             Example: A = [4, 5, 2]
B            Binary; convert each n in A to base 2.
                      [[1, 0, 0], [1, 0, 1], [1, 0]]
 U           Upend; reverse all arrays of binary digits.
                      [[0, 0, 1], [1, 0, 1], [0, 1]]
  T€         Truth each; for each binary array, get all indices of 1's.
                      [[3], [1, 3], [2]]
    Œp       Take the Cartesian product of all index arrays.
                      [[3, 1, 2], [3, 3, 2]
      Ṭ      Untruth; map each index array to a binary arrays with 1's at
             at the specified indices.
                      [[1, 1, 1], [0, 1, 1]]
       z0    Zip/transpose the resulting 2D array, filling shorter rows with 0's.
                      [[1, 0], [1, 1], [1, 1]]
         P   Take the columnwise product.
                      [1, 0]
          Ẹ  Any; yield 1 if any of the products is non-zero, 0 otherwise.
                      1

J , 30 bytes

Todo el crédito va para mi colega Marshall .

Función de prefijo tácito sin nombre.

[:+./ .*(1->./@${.|:)^:2@|:@#:

Pruébalo en línea!

( @es la composición de la función)

#: antibase-2

|: transponer

(... )^:2 aplique la siguiente función dos veces:

 1- Negativo booleano

 >./ el maximo

 @ del

 $ longitudes de eje

 {. tomar (relleno con ceros) de

 |: el argumento transpuesto

+./ .* "magia determinante loca" *

[: no enganchar (no-op - sirve para componer la parte anterior con el resto)

^{* En palabras de Marshall.}

JavaScript (ES6), 104 ... 93 83 bytes

Devoluciones 0o 1.

f=(a,m=Math.max(...a),s=1)=>s>m|a.some((n,i)=>n&s&&f(b=[...a],m,s*2,b.splice(i,1)))

Casos de prueba

f=(a,m=Math.max(...a),s=1)=>s>m|a.some((n,i)=>n&s&&f(b=[...a],m,s*2,b.splice(i,1)))

console.log('Truthy')
console.log(f([1]))
console.log(f([1, 2]))
console.log(f([3, 3]))
console.log(f([3, 3, 3]))
console.log(f([4, 5, 2]))
console.log(f([1, 1, 1, 1]))
console.log(f([15, 15, 15, 15]))
console.log(f([52, 114, 61, 19, 73, 54, 83, 29]))
console.log(f([231, 92, 39, 210, 187, 101, 78, 39]))

console.log('Falsy')
console.log(f([2]))
console.log(f([2, 2]))
console.log(f([4, 6, 2]))
console.log(f([1, 7, 1]))
console.log(f([15, 15, 15]))
console.log(f([1, 15, 3, 1]))
console.log(f([13, 83, 86, 29, 8, 87, 26, 21]))
console.log(f([154, 19, 141, 28, 27, 6, 18, 137]))

Método

Dada la matriz de entrada A = [a ₀ , a ₁ , ..., a _N-1 ] , buscamos una permutación [a _{p [0]} , a _{p [1]} , ..., a _{p [N- 1]} ] de A y un número entero x ≤ N tal que:

• s = 1 + (a _{p [0]} Y 2 ⁰ ) + (a _{p [1]} Y 2 ¹ ) + ... + (a _{p [x-1]} Y 2 ^x-1 ) = 2 ^x
• y s es mayor que el elemento más grande m de A

Formateado y comentado

f = (                 // f = recursive function taking:
  a,                  //   - a = array
  m = Math.max(...a), //   - m = greatest element in a
  s = 1               //   - s = current power of 2, starting at 1
) =>                  //
  s > m               // success condition (see above) which is
  |                   // OR'd with the result of this some():
  a.some((n, i) =>    // for each element n at position i in a:
    n & s &&          //   provided that the expected bit is set in n,
    f(                //   do a recursive call with:
      b = [...a],     //     b = copy of a
      m,              //     m unchanged
      s * 2,          //     s = next power of 2
      b.splice(i, 1)  //     the current element removed from b
    )                 //   end of recursive call
  )                   // end of some()

Casco , 14 bytes

SöV≡ŀToṁ∂Pmo↔ḋ

Pruébalo en línea!

Explicación

SöV≡ŀToṁ∂Pmo↔ḋ  Implicit input, say [4,5,2].
          m  ḋ  Convert each to binary
           o↔   and reverse them: x = [[0,0,1],[1,0,1],[0,1]]
         P      Take all permutations of x
      oṁ∂       and enumerate their anti-diagonals in y = [[0],[0,1],[1,0,0],[1,1],[1]..
S    T          Transpose x: [[0,1,0],[0,0,1],[1,1]]
    ŀ           Take the range up to its length: z = [1,2,3]
                Then z is as long as the longest list in x.
 öV             Return the 1-based index of the first element of y
   ≡            that has the same length and same distribution of truthy values as z,
                i.e. is [1,1,1]. If one doesn't exist, return 0.

05AB1E , 23 22 20 bytes

-1 byte gracias a Mr.Xcoder

Verdadero: 1, Falso: 0

2вí0ζœεvyƶNè})DgLQ}Z

Pruébalo en línea!

Explicaciones:

2вí0ζœεvyƶNè})DgLQ}Z   Full program (implicit input, e.g. [4, 6, 2])
2в                     Convert each to binary ([1,0,0], [1,1,0], [1,0])
  í                    Reverse each ([0,0,1], [0,1,1], [0,1])
   0ζ                  Zip with 0 as a filler ([0,0,0],[0,1,1],[1,1,0])
     œ                 Get all sublists permutations
      ε           }    Apply on each permutation...
       vyƶNè}            For each sublist...
        yƶ                  Multiply each element by its index
          Nè                Get the element at position == sublist index
             )           Wrap the result in a list
              DgLQ       1 if equal to [1,2,...,length of item]
                   Z   Get max item of the list (1 if at least 1 permutations fill the conditions)
                       -- implicit output

Wolfram Language (Mathematica) , 65 bytes

Max[Tr/@Permutations[n=PadLeft[#~IntegerDigits~2]]]==Tr[1^#&@@n]&

Pruébalo en línea!

Explicación

#~IntegerDigits~2

Comenzamos por convertir todas las entradas a listas binarias.

n=PadLeft[...]

Luego rellenamos todas esas listas con ceros a la izquierda para hacer que la matriz sea rectangular. El resultado se almacena npara más tarde.

Permutations[...]

Yay, fuerza bruta, obtengamos todas las permutaciones posibles de la entrada.

Tr/@...

Esto obtiene el rastro para cada permutación, es decir, la suma de los elementos diagonales en la permutación. En otras palabras, sumamos el MSB del primer número, el siguiente al MSB del segundo número y así sucesivamente. Si la permutación es válido, todo esto habrá 1 y habrá tantas 1 s como el número de entrada más grande es amplia.

Max[...]

Obtenemos la traza máxima, porque la traza nunca puede ser más que la de una permutación válida.

...==Tr[1^#&@@n]

El lado derecho es solo una versión de golf Length @ First @ n, es decir, obtiene el ancho de la matriz rectangular y, por lo tanto, el ancho del número de entrada más grande. Queremos asegurarnos de que el rastro de alguna permutación sea igual a esto.

PHP, 255 243 160 bytes

-12 bytes, sacó la clasificación
-83 bytes (!) Gracias a Titus

<?function f($a,$v=NULL,$b=[]){($v=$v??(1<<log(max($a),2)+1)-1)||die("1");if($p=array_pop($a))while($p-=$i)($b[$i=1<<log($p,2)]|$v<$i)||f($a,$v-$i,[$i=>1]+$b);}

Pruébalo en línea!

Imprime 1 para la verdad, nada para falsey.

Versión original sin golf:

<?php
unset($argv[0]);                                                   // remove filename from arguments
$max = pow(2,floor(log(max($argv),2))+1)-1;                        // get target number (all bits set to 1)
solve($argv,$max,[]);
function solve($array,$value,$bits){
  if(!$value){                                                     // if we've reached our target number (actually subtracted it to zero)
    die("1");                                                      // print truthy
  }
  if(count($array)){                                               // while there are arguments left to check
    $popped = array_pop($array);                                   // get the largest argument
    while($popped > 0 && ($mybit = pow(2,floor(log($popped,2))))){ // while the argument hasn't reached zero, get the highest power of 2 possible
      $popped -= $mybit;                                           // subtract power from argument
      if($value >= $mybit && !$bits[$i]){                          // if this bit can be subtracted from our argument, and we haven't used this bit yet
        $copy = $bits;                                             // create a copy to pass to the function
        $copy[$mybit] = 1;                                         // mark the bit as used in the copy
        solve($array,$value-$mybit,$copy);                         // recurse
      }
    }
  }
}

Lua 5.2, 85 bytes

m=math
x=function(...)print(bit32.bor(...)==2^(m.floor(m.log(m.max(...),2))+1)-1)end

Esto establece que x es una función que acepta un número variable de entradas (se espera que sean enteros de 32 bits), y se imprime en stdout "verdadero" o "falso".

Uso:

x(13, 83, 86, 29, 8, 87, 26, 21) -- Prints "false"

PHP, 121 bytes

function f($a,$s=0){($v=array_pop($a))||(0|$g=log($s+1,2))-$g||die("1");for($b=.5;$v<=$b*=2;)$v&$b&&~$s&$b&&f($a,$s|$b);}

Pruébalo en línea .

Descompostura

function f($a,$s=0)
{
    ($v=array_pop($a))          # pop element from array
    ||                          # if nothing could be popped (empty array)
    (0|$g=log($s+1,2))-$g       # and $s+1 is a power of 2
        ||die("1");                 # then print "1" and exit
    for($b=.5;$v>=$b*=2;)       # loop through the bits:
        $v&$b                       # if bit is set in $v
        &&~$s&$b                    # and not set in $s
            &&f($a,$s|$b);              # then set bit in $s and recurse
}

J , 49 bytes

g=.3 :'*+/*/"1+/"2((#y){.=i.{:$#:y)*"2#:(i.!#y)A.,y'

¿Necesito contar también la 'g =.'? Estoy listo para agregarlo.

Un largo verbo explícito esta vez. Probé uno tácito para el mismo algoritmo, pero resultó ser aún más largo y más feo que esto. Lejos de la solución de Adám.

Explicación: (y es el argumento correcto de la función)

                                             ,y - adds a leading axis to the argument 
                                             (if it's scalar becomes an array of length 1)
                                          .A    - finds the permutations according to the left argument
                                   (i.!#y)      - factorial of the length of the argument, for all permutations
                                 #:             - convert each element to binary
                             *"2                - multiply each cell by identity matrix
           (                )                   - group 
                   =i.{:$#:y                    - identity matrix with size the length
                                                  of the binary representation of the argument 
             (#y){.                             - takes as many rows from the identity matrix 
                                                  as the size of the list (pad with 0 if neded)
    */"1+/"2                                    - sums the rows and multiplies the items
                                                  to check if forms an identity matrix
 *+/                                            - add the results from all permutations and
                                                  returns 1 in equal or greater then 1

Pruébalo en línea!

Python 3 , 126 120 bytes

Guardado 6 bytes debido al Sr. Xcoder

lambda x:g(x,max(map(len,map(bin,x)))-3)
g=lambda x,n:n<0 or any(g(x[:i]+x[i+1:],n-1)for i in range(len(x))if x[i]&2**n)

Pruébalo en línea!

Jalea , 17 bytes

BUz0Œ!ŒD€Ẏ
ṀBo1eÇ

Un enlace monádico que toma una lista de números y regresa 1(verdad) o 0(falsey).

Pruébalo en línea!

Esto expirará en TIO por el mayor tiempo de cada caso de prueba.

¿Cómo?

BUz0Œ!ŒD€Ẏ - Link 1, possibilities (plus some shorter ones & duplicates): list of numbers
                                     e.g. [4, 5, 2]
B          - to binary list (vectorises)  [[1,0,0],[1,0,1],[1,0]]
 U         - upend                        [[0,0,1],[1,0,1],[0,1]]
   0       - literal zero                  0
  z        - transpose with filler        [[0,1,0],[0,0,1],[1,1,0]]
    Œ!     - all permutations             [[[0,1,0],[0,0,1],[1,1,0]],[[0,1,0],[1,1,0],[0,0,1]],[[0,0,1],[0,1,0],[1,1,0]],[[0,0,1],[1,1,0],[0,1,0]],[[1,1,0],[0,1,0],[0,0,1]],[[1,1,0],[0,0,1],[0,1,0]]]
      ŒD€  - diagonals of €ach            [[[0,0,0],[1,1],[0],[1],[0,1]],[[0,1,1],[1,0],[0],[0],[1,0]],[[0,1,0],[0,0],[1],[1],[0,1]],[[0,1,0],[0,0],[1],[0],[1,1]],[[1,1,1],[1,0],[0],[0],[0,0]],[[1,0,0],[1,1],[0],[0],[0,1]]]
         Ẏ - tighten                      [[0,0,0],[1,1],[0],[1],[0,1],[0,1,1],[1,0],[0],[0],[1,0],[0,1,0],[0,0],[1],[1],[0,1],[0,1,0],[0,0],[1],[0],[1,1],[1,1,1],[1,0],[0],[0],[0,0],[1,0,0],[1,1],[0],[0],[0,1]]

ṀBo1eÇ - Main link: list of numbers  e.g. [4, 5, 2]
Ṁ      - maximum                           5
 B     - to binary list                   [1,0,1]
   1   - literal one                       1
  o    - or (vectorises)                  [1,1,1]
     Ç - last link as a monad             [[0,0,0],[1,1],[0],[1],[0,1],[0,1,1],[1,0],[0],[0],[1,0],[0,1,0],[0,0],[1],[1],[0,1],[0,1,0],[0,0],[1],[0],[1,1],[1,1,1],[1,0],[0],[0],[0,0],[1,0,0],[1,1],[0],[0],[0,1]]
    e  - exists in?                        1    --------------------------------------------------------------------------------------------------------------^

R , 247 bytes 221 bytes

function(i){a=do.call(rbind,Map(`==`,Map(intToBits,i),1));n=max(unlist(apply(a,1,which)));any(unlist(g(a[,1:n,drop=F],n)))}
g=function(a,p){if(p==1)return(any(a[,1]));Map(function(x){g(a[x,,drop=F],p-1)},which(a[,p])*-1)}

Pruébalo en línea!

Versión sin golf

f=function(i){                                   #anonymous function when golfed
  a=do.call(rbind,Map(`==`,Map(intToBits,i),1))  #convert integers to binary, then logical
                                                 #bind results together in matrix
  n=max(unlist(apply(a,1,which)))                #determine max number of bits
  any(unlist(g(a[,1:n,drop=F],n)))               #apply recursive function
}

g=function(a,p){
  if(p==1)return(any(a[,1]))                   #check if first bit is available still
  Map(function(x){g(a[x,,drop=F],p-1)},which(a[,p])*-1) #strip row used for current bit
                                                        #and apply the function recursively
}

Me di cuenta de que la verificación sin filas era innecesaria con los drop=Fargumentos. También se eliminó un poco de espacio en blanco molesto.

PHP, 152 bytes

<?function b($a,$b,$s){$a[$s]=0;$r=$b-1;foreach($a as$i=>$v)if($v&1<<$b)$r=max(b($a,$b+1,$i),$r);return$r;}$g=$argv;$g[0]=0;echo!(max($g)>>b($g,0,0)+1);

No imprime nada para falso, 1 para verdadero.

Sin golf:

<?

// Search an array for a value having a bit set at the given bit index.
// For each match, search for a next higher bit index excluding the current match.
// This way it "climbs up" bit by a bit, finally returning the highest bit index reached.
function bitSearch($valArr, $bitInd, $skipInd) {
    unset($valArr[$skipInd]);
    $result = $bitInd - 1;
    foreach ($valArr as $ind => $v) {
        if ($v & (1 << $bitInd)) {
            $result = max(bitSearch($valArr, $bitInd + 1, $ind), $result);
        }
    }
    return $result;
}

$argv[0] = 0;
$r = bitSearch($argv, 0, 0);
// Check if the highest bit index reached was highest in the largest value given.
if (max($argv) >> ($r + 1)) {
    echo("False\n");
} else {
    echo("True\n");
}

Jalea , 17 bytes

BUz0×J$€ŒpṢ=JPƲ€Ẹ

Banco de pruebas.

C, 79 bytes

b,i;main(a){for(;~scanf("%d",&a);i++)b|=a;puts("false\0true"+(b==(1<<i)-1)*6);}