Desafio

Dada uma lista de números inteiros positivos, descubra se existe uma permutação em que, até um bit de cada um dos números inteiros, um número binário composto por todos os 1s possa ser criado.

O número de bits no número binário resultante é igual ao MSB mais alto da lista de números inteiros.

Saída

Seu código deve gerar ou retornar um valor de truthy / falsey indicando se existe uma permutação.

Exemplos

Verdade:

Com a lista [4, 5, 2]e sua representação binária [100, 101, 10], podemos usar o terceiro, o primeiro e o segundo bits, respectivamente, para criar 111:

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

Com a lista [3, 3, 3], todos os números têm o primeiro e o segundo bits definidos como 1, para que possamos escolher com um número de sobra:

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

Falsey:

Com a lista [4, 6, 2], nenhum dos números tem o primeiro bit definido como 1, portanto, o número binário não pode ser criado:

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

Com a lista [1, 7, 1], apenas um dos números tem o segundo e o terceiro bits definidos como 1e o número não pode ser criado:

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

Obviamente, se o número máximo de bits definidos exceder o número de números inteiros, o número do resultado nunca poderá ser criado.

Casos de teste

Verdade:

[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]

Regras

As brechas padrão são proibidas. Como se trata de código-golfe , a entrada mais curta ganha!

Gelatina , 11 bytes

BUT€ŒpṬz0PẸ

Experimente online!

Como 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 o crédito é do meu colega Marshall .

Função de prefixo tácito sem nome.

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

Experimente online!

( @é composição da função)

#: antibase-2

|: transpor

(… )^:2 Aplique a seguinte função duas vezes:

 1- Negar booleano

 >./ o máximo

 @ do

 $ comprimentos do eixo

 {. take (preenchimento com zeros) de

 |: o argumento transposto

+./ .* "mágica determinante louca" *

[: não ligue (no-op - serve para compor a parte anterior com o resto)

^{* Nas palavras de Marshall.}

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

Retorna 0ou 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 teste

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 a matriz de entrada A = [a ₀ , a ₁ , ..., a _N-1 ] , procuramos uma permutação [a _{p [0]} , a _{p [1]} , ..., a _{p [N- 1]} ] de A e um número inteiro x ≤ N, de modo que:

• s = 1 + (a _{p [0]} AND 2 ⁰ ) + (a _{p [1]} AND 2 ¹ ) + ... + (a _{p [x-1]} AND 2 ^x-1 ) = 2 ^x
• e s é maior do que o maior elemento de m de um

Formatado e 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()

Casca , 14 bytes

SöV≡ŀToṁ∂Pmo↔ḋ

Experimente online!

Explicação

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 graças a Mr.Xcoder

Verdadeiro: 1, Falso: 0

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

Experimente online!

Explicações:

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]&

Experimente online!

Explicação

#~IntegerDigits~2

Começamos convertendo todas as entradas em listas binárias.

n=PadLeft[...]

Em seguida, preenchemos todas essas listas com zeros à esquerda para tornar a matriz retangular. O resultado é armazenado npara mais tarde.

Permutations[...]

Bem, força bruta, vamos obter todas as permutações possíveis da entrada.

Tr/@...

Isso obtém o rastreio para cada permutação, ou seja, a soma dos elementos diagonais na permutação. Em outras palavras, adicionamos o MSB a partir do primeiro número, o próximo a MSB a partir do segundo número e assim por diante. Se a permutação for válida, todos eles serão 1 e haverá 1 s no número de entrada maior.

Max[...]

Nós obtemos o rastreamento máximo, porque o rastreamento nunca pode ser maior que o de uma permutação válida.

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

O lado direito é apenas uma versão de golfe Length @ First @ n, ou seja, obtém a largura da matriz retangular e, portanto, a largura do maior número de entrada. Queremos garantir que o traço de alguma permutação seja igual a isso.

PHP, 255 243 160 bytes

-12 bytes,
eliminou a classificação -83 bytes (!) Graças 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);}

Experimente online!

Imprime 1 para verdade, nada para falsey.

Versão original não destruída:

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

Isso define x como uma função que aceita um número variável de entradas (espera-se que sejam números inteiros de 32 bits) e imprime em stdout "true" ou "false".

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

Experimente online .

demolir

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'

Preciso contar também o 'g =.'? Estou pronto para adicioná-lo.

Um verbo explícito longo desta vez. Eu tentei um tácito para o mesmo algoritmo, mas acabou sendo ainda mais longo e mais feio do que isso. Longe da solução de Adám.

Explicação: (y é o argumento correto da função)

                                             ,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

Experimente online!

Python 3 , 126 120 bytes

Economizou 6 bytes devido ao 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)

Experimente online!

Geléia , 17 bytes

BUz0Œ!ŒD€Ẏ
ṀBo1eÇ

Um link monádico que obtém uma lista de números e retorna 1(verdade) ou 0(falsey).

Experimente online!

Isso expirará no TIO pelo mais longo de cada um dos casos de teste.

Quão?

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

Experimente online!

Versão ungolfed

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
}

Percebi que a verificação sem filas era desnecessária com os drop=Fargumentos. Também removeu algum espaço em branco traquina.

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

Não imprime nada para falso, 1 para verdadeiro.

Ungolfed:

<?

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

Geléia , 17 bytes

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

Suíte de teste.

C, 79 bytes

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