Varias bases pero no dos veces el mismo dígito

15

Entrada

Una matriz no vacía de enteros positivos.

Tarea

Convierta cada número entero en binario, octal, decimal o hexadecimal de tal manera que cada dígito ( 0 a F ) se use como máximo una vez.

Salida

La lista de bases que se usaron para resolver el rompecabezas.

Ejemplo detallado

La salida esperada para [16, 17] es [octal, decimal] .

Aquí es por qué:

  • No podemos simplemente usar decimales para ambos números, porque ambos contienen un 1 .
  • 16 no se puede convertir a binario, porque su representación en esta base ( 10000 ) contiene varios 0 's.
  • 17 tampoco se puede convertir a binario, porque su representación en esta base ( 10001 ) contiene varios 0 's y varios 1 ' s.
  • 17 no se puede convertir a hexadecimal, porque su representación en esta base ( 11 ) consiste en dos 1 's.
  • Consideremos todas las posibilidades restantes:

                   +---------+---------+--------+
                   | oct(16) | dec(16) | hex(16)|
                   | = 20    | = 16    | = 10   |
    +--------------+---------+---------+--------+
    | oct(17) = 21 | 20,21   | 16,21   | 10,21  |
    | dec(17) = 17 | 20,17   | 16,17   | 10,17  |
    +--------------+---------+---------+--------+
    

    La única solución posible es convertir 16 en octal ( 20 ) y mantener 17 en decimal ( 17 ). De esta manera, los dígitos 0 , 1 , 2 y 7 se usan exactamente una vez.

Aclaraciones y reglas.

  • La entrada está garantizada para conducir a una solución única. Se supone que su código no admite matrices que brinden varias soluciones o ninguna solución.
  • Puede generar las bases en cualquier formato razonable, como ["bin", "oct", "dec", "hex"] , ['b', 'o', 'd', 'h'] , "BODH " , [2,8,10,16] , [0,1,2,3] etc. Pero debe explicarse claramente en su respuesta.
  • El orden de las bases en la salida debe coincidir con el orden de los enteros de entrada.
  • Si eso ayuda, puede suponer que la entrada está ordenada de menor a mayor, o de mayor a menor.
  • Este es el , por lo que gana la respuesta más corta en bytes.

Casos de prueba

No tiene que generar los resultados de conversión que se enumeran a continuación. Son puramente informativos.

Input                                  | Output          | Conversion result
---------------------------------------+-----------------+------------------------
[ 119 ]                                | O               | 167
[ 170 ]                                | D               | 170
[ 64222 ]                              | H               | FADE
[ 16, 17 ]                             | O/D             | 20/17
[ 14, 64, 96 ]                         | H/H/D           | E/40/96
[ 34, 37, 94 ]                         | O/D/H           | 42/37/5E
[ 2, 68, 82 ]                          | B/D/H           | 10/68/52
[ 22, 43, 96 ]                         | O/O/O           | 26/53/140
[ 3639, 19086, 57162 ]                 | H/D/H           | E37/19086/DF4A
[ 190, 229, 771 ]                      | O/H/O           | 276/E5/1403
[ 2, 44, 69, 99 ]                      | B/H/H/H         | 10/2C/45/63
[ 75, 207, 218, 357, 385 ]             | H/H/H/D/O       | 4B/CF/DA/357/601
[ 12, 28, 46, 78, 154, 188, 222, 240 ] | D/O/O/D/H/H/H/H | 12/34/56/78/9A/BC/DE/F0

La lista de entrada sin formato está disponible aquí .

Arnauld
fuente
¿deberíamos preocuparnos por algún aspecto de la eficiencia? (como si la matriz tiene una longitud de 1000 o algo así)
DanielIndie
3
@DanielIndie No, no tienes que hacerlo. Además, un rompecabezas de 1000 entradas incluiría muchos dígitos duplicados, sin importar las bases que se usen, por lo que no puede ser válido. (Se garantiza que esto no sucederá según la primera regla).
Arnauld
sí, tienes razón ... estúpido yo ... :)
DanielIndie
1
Estoy ansioso por encontrar una solución de Japt, porque la probé y no pude encontrar una buena.
Nit
2
@Scrooble Nope. :) ¡Buen intento!
Arnauld

Respuestas:

4

JavaScript (Node.js) , 192,155,154,152,151,145,136,113,99,92 90 bytes

  • gracias a @Arnauld por recordarme que puedo devolver [0,1,2,3] -> que es [2,8,10,16] ahorra 8 bytes, y por la brillante idea (que ayuda a reducir en 23+ bytes)
  • gracias a @Kevin Cruijssen por reducir en 1 bytes
f=([c,...a],t="")=>c?[1,4,5,8].find(b=>T=!/(.).*\1/.test(n=t+c.toString(b*2))&&f(a,n))+T:a

Pruébalo en línea!

Explicación:

[c,...a]- Truco de @Arnauld para tomar un elemento a la vez c?***:" "-> si c no está definido, logramos llegar al resultado final- [] - si pongo "", el resultado no se consideraría legítimo. ([] + 5 = "5" JS FTW) [1,4,5,8].findcada vez que encontramos la base correcta (la salida será de esta matriz (1,4,5,8) -> (2,8,10,16) es legítima. ahora cómo funciona el hallazgo -> si encuentra algo, devuelve el elemento (1-8) y luego agrego el resultado de la solución interna.Si no encuentra, devuelve indefinido + T ahora es falso -> NaN que en el la llamada de los padres se considerará falsa

!/(.).*\1/.test(n=t+b) determinar si la cadena tiene duplicados, si es así:

f(a,n)) simplemente vaya al siguiente número (a es ahora array.slice (1)) con la nueva cadena (n)

asignamos el resultado a T (temp) del resultado porque find se detiene cuando encuentra y, por lo tanto, sabemos que el último resultado será f (), que es el resultado B

DanielIndie
fuente
1
t="",B=""para t="",B=tahorrar un byte.
Kevin Cruijssen
@KevinCruijssen actualiza la solución, gracias :) (y tú a Arnauld)
DanielIndie
@Arnauld, tomé tu brillante idea e hice algo similar. mira la solución ahora
DanielIndie
@Arnauld pura maravilla
DanielIndie
1
¡Frio! Afeitemos 2 bytes más (y ya no es necesario trim()).
Arnauld
3

Perl 5 -alp , 55 bytes

Usos %xpara hexadecimal, %dpara decimal, %opara octal y %bpara binario

#!/usr/bin/perl -alp
($_)=grep{sprintf($_,@F)!~/(.).*\1/}glob"%{d,o,b,x}"x@F

Pruébalo en línea!

Ton Hospel
fuente
3

Ruby, 72 71 bytes

->a{a.map{%w[b o d x]}.inject(&:product).find{|c|/(.).*\1/!~[p,c]*?%%a}}

El formato de salida es una especie de monstruosidad de expresión S inversa:

f[[12, 28, 46, 78, 154, 188, 222, 240]]
=> [[[[[[["d", "o"], "o"], "d"], "x"], "x"], "x"], "x"]

En lugar de eso, separar la barra costaría 3 bytes más (anexando *?/).

Este formato proviene de la estructura de bucle, ligeramente más corta que la más idiomática repeated_combination(a.size), que genera una matriz de matrices de caracteres y luego la reduce sobre la función de productos cruzados.

Editar: Guardado 1 byte gracias a Lynn.

histocrat
fuente
2

Pyth, 21 20 bytes

f{Is.bjYNTQ^[8T2y8)l

Devuelve una lista de todas las listas posibles de bases (que siempre tiene longitud 1).
Pruébalo aquí

Explicación

f{Is.bjYNTQ^[8T2y8)l
           ^[8T2y8)lQ  Get the tuples of bases of the same length as the input.
f                      Filter to get those...
    .bjYNTQ            ... where converting bases elementwise...
   s                   ... and joining together...
 {I                    ... has no repeats.

fuente
2

Jalea , 17 16 bytes

⁴⁽%ʠḃṗL³bF⁼Q$ƲÐf

Pruébalo en línea!

Devuelve una lista de bases.

 == Explicación ==
⁴⁽% ʠḃṗL³bF⁼Q $ ƲÐf Enlace principal.
 ⁽% ʠ Un número.
    ḃ conviértalo en base biyectiva ...
⁴ 16. El resultado es [2,8,10,16].
     ṗL Potencia cartesiana por la longitud de entrada.
             Filterf Filtro, conserve los que satisfagan ...
       ³ la entrada
        b convertir a esa base
         F al aplanar (unir todos los dígitos de \
                      diferentes números juntos)
          ⁼Q $ igual a sí mismo sin calificar.
usuario202729
fuente
2

Python 2 , 128 bytes

from itertools import*
a=input()
for b in product(*['bdxo']*len(a)):
 s=''.join(map(format,a,b))
 if len(s)==len(set(s)):print b

Pruébalo en línea!

Lynn
fuente
2

05AB1E , 17 bytes

2žv8T)sgãʒIsв˜DÙQ

Pruébalo en línea!

Kaldo
fuente
No sé 05AB1E, así que tal vez debería esperar hasta que hayas agregado una explicación antes de preguntar esto, pero ¿por qué el resultado para 8el personaje '8'y los otros tres son enteros? Sin embargo, +1 parece funcionar bien, incluidos los últimos casos de prueba más largos.
Kevin Cruijssen
2
@KevinCruijssen Eso viene de "2žv8T". Los números en el código fuente se insertan como caracteres en 05AB1E, mientras que žv (16) y T (10) son elementos integrados que empujan sus respectivos números en la pila. Esto generalmente pasa desapercibido porque la visualización implícita de 05AB1E del último elemento en la pila se convierte en números, pero dado que en este caso el resultado que se muestra es una matriz de elementos, esos elementos se dejan intactos, de ahí las comillas. El comando ï, por ejemplo, se puede usar después) para convertir los dos elementos char en ints.
Kaldo
@KevinCruijssen Ejemplo de mi explicación: tio.run/##MzBNTDJM/f/fyPbQDtv//wE El código: push 2, print, wrap en una matriz, print.
Kaldo
2

Python 2 , 121 117 113 111 bytes

def f(a,d='',s=''):
 if a:
	for c in'bodx':t=format(a[0],c)+s;len(t)-len(set(t))or f(a[1:],d+c,t)
 else:print d

Pruébalo en línea!

Extremidad del sombrero a Lynn para formatque se me había olvidado!

Chas Brown
fuente
1

Casco , 19 bytes

fȯS=UΣz`B¹πmDd1458L

Pruébalo en línea!

Devuelve listas de bases

Explicación

fȯS=UΣz`B¹πmDd1458L  Implicit input
                  L  Length of input
          π          Cartesian power of
             d1458     The digits of 1458  [1,4,5,8]
           mD          Double the digits   [2,8,10,16]
fȯ                   Filter by
      z`B¹             Zip with input by converting to its base
     Σ                 Concatenate
  S=U                  Equal to itself with unique elements
Fyr
fuente