Encuentra una aguja binaria en un pajar decimal

41

El reto

Te dan:

  • una lista no ordenada no ordenada h de enteros positivos (el pajar)
  • un entero positivo n (la aguja)

Su tarea es devolver la lista de todas las concatenaciones decimales únicas de permutaciones de h cuya representación binaria contiene la representación binaria de n .

Ejemplos

  1. h = [1, 2, 3]
    n = 65

    ejemplo

    Solo hay una concatenación coincidente, por lo que el resultado esperado es [321].

  2. h = [1, 2, 3]
    n = 7

    Esta vez, hay tres concatenaciones que contienen el patrón binario 111 . La salida esperada es [123, 231, 312].

  3. h = [12, 3]
    n = 7

    Solo hay dos permutaciones disponibles y ambas coinciden. La salida esperada es [123, 312].

  4. h = [1, 2, 2]
    n = 15

    La única concatenación coincidente es 122 ( 1111010 en binario, que contiene 1111 ), por lo que la salida esperada es [122]. Tenga en cuenta que dos permutaciones en realidad conducen a 122 pero no se le permite salir [122, 122].

Aclaraciones y reglas.

  • Puede tomar la aguja como un entero ( 65), una cadena que representa un valor decimal ( "65") o una cadena que representa un valor binario ( "1000001").
  • Puede tomar el pajar como una matriz / objeto / conjunto nativo de enteros ( [11,12,13]), una matriz / objeto / conjunto nativo de cadenas que representan valores decimales ( ["11","12","13"]) o una cadena delimitada de valores decimales ( "11 12 13"o "11,12,13"). También puede optar por una variante utilizando matrices de dígitos (como [[1,1],[1,2],[1,3]]).
  • La salida debe seguir uno de los formatos descritos anteriormente para el pajar, pero no necesariamente el mismo.
  • Se supone que no debe manejar pajar cuya concatenación decimal más alta es mayor que el entero sin signo representable más alto en su idioma.
  • Aparte de eso, su código debería admitir teóricamente cualquier entrada, suponiendo que se le dé suficiente tiempo y memoria.
  • ¡Esto es SPARTA! , por lo que gana la respuesta más corta en bytes.

Casos de prueba

Haystack             | Needle   | Output
---------------------+----------+-----------------------------------
[ 1, 2, 3 ]          | 65       | [ 321 ]
[ 1, 2, 3 ]          | 7        | [ 123, 231, 312 ]
[ 12, 3 ]            | 7        | [ 123, 312 ]
[ 1, 2, 2 ]          | 15       | [ 122 ]
[ 1, 2 ]             | 7        | []
[ 12, 34, 56 ]       | 21       | [ 125634, 341256, 345612, 563412 ]
[ 1, 2, 3, 4, 5 ]    | 511      | [ 53241 ]
[ 1, 3, 5, 7, 9 ]    | 593      | [ 37519, 51793, 75913, 75931 ]
[ 11, 12, 13, 14 ]   | 12141311 | [ 12141311 ]
[ 1, 2, 1, 2, 1, 2 ] | 1015     | [ 221112 ]
Arnauld
fuente
1
La salida de mi solución es como set([(1, 2, 2)]). ¿Es válido o debo deshacerme de él set?
Dead Possum
@DeadPossum Sí, es válido.
Arnauld
¿Puede la entrada del pajar ser una sola cadena ("123")? En algunos lenguajes de una cadena es igual que una serie de caracteres, así que creo que lo haría tiene sentido
Luis Mendo
No @LuisMendo Se puede debido ["12","3"]y ["1","23"]son dos montones de heno distintas.
Arnauld
@Arnauld Ah, pensé que eran dígitos. Gracias
Luis Mendo

Respuestas:

17

05AB1E , 10 8 bytes

Toma la aguja en binario para guardar 1 byte.

-2 bytes gracias a Emigna

œJÙʒbŒIå

Pruébalo en línea!

œJÙʒbŒIå   Arguments: a, n
œJÙ        Get all unique permutations of a
   ʒ       Filter: Keep if following code returns true
    b      Convert to binary
     Œ     Get all substrings
      Iå   Check if substrings contain n
           Implicit output of filtered list
kalsowerus
fuente
1
œJÙʒbŒIå debería funcionar también.
Emigna
@Emigna Gracias, eso ahorra 2 bytes :)
kalsowerus
11

Python 2, 90 bytes

-3 bytes gracias a @ Gábor Fekete

Pruébalo en línea

Toma como matriz de entrada de cadenas, que representan entradas de heno y cadenas, que representan agujas en binario

from itertools import*
lambda H,N:{i for i in permutations(H)if N in bin(int(''.join(i)))}
Zarigüeya muerta
fuente
44
Escribir en {...}lugar de set(...)guardar 3 bytes.
Gábor Fekete
1
@ GáborFekete Siempre olvido que {} está configurado: D Gracias
Dead Possum
Creo que esto falla H=['1'], N='0'.
user2357112 es compatible con Monica
Oh, espera, se requiere que la entrada sea positiva.
user2357112 es compatible con Monica
10

Java 10, 320 312 305 297 292 bytes

import java.util.*;Set s=new HashSet();l->n->{Long q=0;p(l,0);for(var x:s)if(q.toString(q.decode(x+""),2).contains(n))System.out.println(x);}void p(List l,int k){int i=k,x=l.size();for(Collections C=null;i<x;p(l,k+1),C.swap(l,k,i++))C.swap(l,i,k);if(k>x-2)s.add((l+"").replaceAll("\\D",""));}

Entrada como List & binary-String, salida como Strings en nuevas líneas.

Explicación:

Pruébalo aquí

import java.util.*;           // Required import for Set, HashSet, List, and Collections

Set s=new HashSet();          // Class-level Set

l->n->{                       // Method (1) with List and String parameters and no return-type
  Long q=0;                   //  Number-object is required for two static method-calls below
  p(l,0);                     //  Determine all permutations of given list and put it in the Set
  for(var x:s)                //  Loop over these permutations
    if(q.toString(q.decode(x+""),2)
                              //   If the binary String of the current permutation
        .contains(n))         //   contains the binary String of the input integer
      System.out.println(x);} //    Print this permutation

void p(List l,int k){         // Method (2) with List and integer parameters and no return-type
  int i=k,x=l.size();         //  Two temp integers
  for(Collections C;          //  Collections-object is required for two static method-calls below
      i<x                     //  Loop `i` in the range [`k`, list-size)
      ;                       //    After every iteration:
       p(l,k+1),              //     Do a recursive-call to this method with `k+1`
       Collections.swap(l,k,i++))
                              //     And swap the items at indices `k` and `i` back
    Collections.swap(l,i,k);  //   Swap the items at indices `i` and `k`
  if(k>x-2)                   //  If `k` is now equal to the size of the list - 1
    s.add((l+"").replaceAll("\\D",""));}
                              //   Add this permutation to the Set
Kevin Cruijssen
fuente
Personalmente, lo pondré l->n->{...después, void p(...ya que la lambda es la respuesta a la solicitud y la función es necesaria para que la lambda funcione. El consenso sobre "expresiones de función" es algo así como "la última 'expresión' de su envío puede ser una 'expresión de función' si cuando se almacena en una variable cumple los requisitos de una respuesta de función" IIRC. Pero eso es solo un problema de formato, y uno subjetivo.
CAD97
@ CAD97 No tenía idea de que el pedido importaba. La última vez publiqué una respuesta Java 8 con dos métodos que usé voidporque era más corto que un segundo lambda y el múltiple .apply. No lo he verificado para esta respuesta (es decir, void p(List l,int k)& 2x p(l,0)versus (l,k)->& 2x p.apply(l,0)). Hmm ... el segundo parece ser 1 byte más corto en este caso. ¿Pero dice que las reglas establecen que solo se le permite tener un método lambda? Todavía un poco confundido por qué tiene que ser el último. Personalmente siempre publicar mis respuestas en este orden: imports; class-fields; main-method/lambda; other methods.
Kevin Cruijssen
De nuevo, es sobre todo una opinión, me gustaría que alguien más experimentado interviniera antes de decir realmente de una forma u otra. Sin embargo, sé que esto es cierto: si necesita llamar a un método (por ejemplo, recursivo o como ayudante), debe tener un nombre. Pero en cuanto a ordenar, realmente no importa, ya que no cambia el recuento de bytes. Pero ordeno comoimports;helper methods;lambda
CAD97
@ CAD97 Ah, por supuesto, entonces sería void p(List l,int k)& 2x f(l,0);versus f=(l,p)->& 2x en su p.apply(l,0);lugar (lo que significa que la versión actual es 1 byte más corta). En cuanto al pedido, me quedaré con esto ya que lo hice con todas mis respuestas, y también tiene sentido para mí personalmente comenzar con el método principal en la explicación, y luego el (los) método (s) auxiliar (es) si hay algunos.
Kevin Cruijssen
y desafortunadamente no puedes hacerlo f=(lambda)en Java, esjava.util.function.BiConsumer<List,Integer>f=(l,p)->{...}
CAD97
9

Japt , 15 14 13 12 10 bytes

Toma el pajar como un conjunto de enteros y la aguja como una cadena binaria. Emite una matriz de cadenas enteras.

á m¬f_°¤øV

Intentalo


Explicación

á m¬â f_°¤øV
              :Implicit input of array U=haystack and string V=needle
á             :Unique permutations of U
  m           :Map
   ¬          :  Join to a string
    f_        :Filter
      °       :  Postfix increment current element to cast it to an integer
       ¤      :  Convert to base-2 string
        øV    :  Does that contain V?
              :Implicit output of resulting array
Lanudo
fuente
Muy bien, sobre lo que habría hecho. ®¬nÃguarda un byte en el mapeo. (También me movería âa la mitad del programa para deshacerme del segundo Ã; no guarda ningún byte, pero es un poco más eficiente y se ve un poco mejor)
ETHproductions
Ajá, gracias, @ETHproductions: estaba tan concentrado en ver si podía eliminar los bytes al generar cada número como una matriz. Perdí ese simple cambio en el mapeo. El âera una solución rápida tachuelas en el final, cuando Arnauld señaló que había olvidado a eliminar los duplicados de la matriz final, pero, tienes razón, la eliminación de los duplicados antes de ejecutar el filtro sería más eficiente.
Shaggy
4

Ruby , 61 59 bytes

->a,n{a.permutation.select{|s|"%b"%s.join=~/#{"%b"%n}/}|[]}

Pruébalo en línea!

Característica genial del día: no sabía que podía generar la representación binaria de una cadena que contiene un número.

Ejemplo:

puts "%b"%"123"

-> 1111011
GB
fuente
3

JavaScript (ES6), 140 bytes

Toma la aguja como una cadena binaria.

(h,n,S=new Set,p=(a,m='')=>a.length?a.map((_,i)=>p(A=[...a],m+A.splice(i,1))):S.add(+m),_=p(h))=>[...S].filter(d=>~d.toString(2).indexOf(n))

Darrylyeo
fuente
3

Brachylog , 15 bytes

{hpc.ḃs~ḃ~t?∧}ᵘ

Pruébalo en línea!

Explicación

{            }ᵘ    Find all unique outputs, given [h, n], of:
 hpc.                The Output is the concatenation of a permutation of h
    .ḃs              Take a substring of the binary representation of the Output
       ~ḃ            Convert it back to a decimal number
         ~t?∧        This decimal number must me n
Fatalizar
fuente
2

Mathematica, 170 156 bytes

(t={};l=Length;v=IntegerDigits;j=v[#2, 2];s=FromDigits/@Flatten/@v@Permutations@#1;Table[If[l@SequenceCases[v[s[[i]],2],j]>0,t~AppendTo~s[[i]]],{i,l@s}];t)&


entrada

[{12, 34, 56}, 21]

salida

{125634, 341256, 345612, 563412}

J42161217
fuente
Hay un espacio en blanco en v[#2, 2].
Yytsi
1

CJam, 23 22 21 19 bytes

{e!{si2b1$2b#)},\;}

Este es un bloque que toma entradas n hen la pila y deja la salida como una matriz en la pila.

Explicación:

                   e# Stack:                      | 65 [1 2 3]
e!                 e# Unique Permutations:        | 65 [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
  {                e# Filter where block is true: | 65 [3 2 1]
   s               e#   Convert to string:        | 65 "321"
    i              e#   Convert to int:           | 65 321
     2b            e#   Convert to binary:        | 65 [1 0 1 0 0 0 0 0 1]
       1$          e#   Copy behind:              | 65 [1 0 1 0 0 0 0 0 1] 65
         2b        e#   Convert to binary:        | 65 [1 0 1 0 0 0 0 0 1] [1 0 0 0 0 0 1]
           #       e#   Find array in another:    | 65 2
            )      e#   Increment:                | 65 3
             },    e# End filter                  | 65 [321]
               \;  e# Delete back:                | [321]
Fruta Esolanging
fuente
1

R, 114 bytes

pryr::f(plyr::l_ply(combinat::permn(x),function(y)if(grepl(p,R.utils::intToBin(paste(y,collapse=""))))cat(y,"\n")))

Utiliza un montón de paquetes. pryr::f()crea automáticamente una función, tomando p, una cadena del patrón binario a buscar y xun vector con la otra entrada como entrada. combinat::permncrea todas las permutaciones de x. R.utils::intToBines una versión agradable y prolija para convertir un número (o representación de caracteres de un número) en un número binario, ya convenientemente almacenado como un carácter. Aplicando esto sobre todas las permutaciones y emitiéndolas si la cadena binaria pestá contenida en la versión binaria de la concatenación. Se imprime una nueva línea explícita, porque de lo contrario la salida sería 12 56 3456 34 1234 56 1234 12 56.

plyr's l_plyse usa para eliminar la salida de una lista nula, además de la salida regular. Si se permite una salida como esta:

3 2 1 
[[1]]
NULL

[[2]]
NULL

[[3]]
NULL

[[4]]
NULL

[[5]]
NULL

[[6]]
NULL

Entonces podemos guardar algunos bytes usando en su lapplylugar:

108 bytes:

pryr::f(lapply(combinat::permn(x),function(y)if(grepl(p,R.utils::intToBin(paste(y,collapse=""))))cat(y,"\n")))

Si se permite una salida como esta:

[[1]]
NULL

[[2]]
NULL

[[3]]
NULL

[[4]]
[1] 3 2 1

[[5]]
NULL

[[6]]
NULL

Entonces podemos hacerlo aún más corto:

101 bytes:

pryr::f(lapply(combinat::permn(x),function(y)if(grepl(p,R.utils::intToBin(paste0(y,collapse=""))))y))

No permitido.

JAD
fuente
0

Perl 6 , 69 bytes

{set @^a.permutations».join.grep(*.fmt('%b').contains($^b.base(2)))}
Sean
fuente