Escriba un programa para encontrar un número que consta de 9 dígitos en el que cada uno de los dígitos del 1 al 9 aparece solo una vez. Este número también debe cumplir estos requisitos de divisibilidad:
- El número debe ser divisible por 9.
- Si se elimina el dígito más a la derecha, el número restante debe ser divisible por 8.
- Si se elimina el dígito más a la derecha del nuevo número, el número restante debe ser divisible por 7.
- Y así sucesivamente, hasta que solo haya un dígito (que necesariamente será divisible por 1).
Crédito Dávid Németh
Respuestas:
CJam - 26
Es aleatorio pero funciona bastante rápido con el intérprete de Java . Puede tomar un par de minutos con el intérprete en línea .
Explicación:
1
empuja 1 (que se explicará más adelante){…}g
es un ciclo do-while;
elimina un valor de la pila (inicialmente el 1 con el que comenzamos)9,
hace que la matriz [0 ... 8]:)
incremente los elementos de la matriz, lo que resulta en [1 ... 9]_
duplica la matrizmr
baraja, la matrizs
convierte en cadena0@
empuja 0 y luego trae la otra copia de la matriz en la parte superior{…}/
es un bucle for-each (sobre los números 1 ... 9)_
duplica el número actual (vamos a llamarlo "k" )3$
copia la cadena numérica de la pila,<i
obtiene la subcadena con los primeros k caracteres, luego los convierte en\%
intercambios de enteros con la otra copia de k y luego obtiene el resto (% k)+
agrega el resto al valor anterior en la pila (inicialmente 0 desde arriba) )En este punto, tenemos la cadena numérica en la pila, seguida de un 0 si el número coincide con todos los requisitos (es decir, todos los restantes fueron 0) o un valor distinto de 0 de lo contrario.
La parte superior de la pila se convierte en la condición de bucle do-while. Se abre y el bucle continúa si la condición era verdadera.
Si encontramos la solución, la condición es 0 (falso), el ciclo termina y se imprime el resto de la pila (la cadena numérica).
Si no es la solución, la condición es el valor distinto de 0 (verdadero) y el ciclo continúa con la cadena en la pila. La cadena aparece al comienzo de la siguiente iteración (por lo que el ciclo espera un valor en la pila, y esa es la razón del 1 inicial).
Gracias Dennis por hacer el código más corto y más complicado: p
fuente
0{;9,:)_mrsT@{_3$<i\%+}/}g
Javascript (E6)
105125134Construcción recursiva del número, cada paso verifica la divisibilidad.
Tiempo de ejecución cerca de 0 segundos
Sin E / S esta vez, ya que el OP solicitó un programa para encontrar el número, y el número se encuentra y se registra automáticamente en la consola
Golfed más Cortesía de MT0
Golfed
Feo
Prima
Con 3 pequeños cambios, puede usar la misma función para encontrar números más largos usando base> 10. Por ejemplo, en base 14 ...
Sin golf
fuente
(Q=(n,d,b)=>([(m=n+(s=[...b]).splice(i,1))%d||Q(m,d+1,s)for(i in b)],d>9&&(Q.z=n),Q.z))('',1,'123456789')
(Q=(n,d,b)=>Math.max(...[(m=n+(s=[...b]).splice(i,1))%d||Q(m,d+1,s)for(i in b)],n))('',1,'123456789')
Perl, 56
Uso:
perl -E '...'
Salida:
381654729
Este programa es realmente lento . Como en más de 3.5 horas.
Como ejercicio más divertido, decidí desarrollar un algoritmo extremadamente rápido:
Lo anterior se ejecuta en .00095 segundos y confirma que solo hay una solución para este problema.
fuente
Python3,
214,199,184,176,174,171,165,150146salida:
Este es mi primer guión de golf. Espero que te guste :)
fuente
Pyth , 33 caracteres
Para probarlo, coloque el código anterior como entrada estándar en el enlace del título.
Después de compilar en Python 3.4:
Explicación:
=Y]k
:Y=['']
FkY
: para k en F:~Y
: Agregar a Yf
: Filtrado por>ql{TlT
: Todos los elementos únicos y%vTlT
: eval (elemento)% len (elemento) = 0m+k
`d
En la lista de k + repr (d)r1T
: para d de 1 a 9.)
: Fin del ciclopk
: imprimir kfuente
Rubí, 66
78caracteresEl tiempo de ejecución es de ~ 8 segundos (salida impresa después de 3 s).
Esto no se detiene después de encontrar el primer número, por lo que técnicamente imprime todos los números que cumplen con los criterios, pero como solo hay uno de esos números, no hace la diferencia.
Rubí 1.8, 63
Esencialmente la misma solución que la anterior. En Ruby 1.8, las matrices se convierten en cadenas al invocarlas implícitamente
Array#join
, por lo que podemos guardar la llamada en eso. Curiosamente, el código también se ejecuta mucho más rápido en Ruby 1.8 que 2.0 (tiempo de ejecución total de 4.5 segundos, salida impresa después de 1.6 s).fuente
GolfScript (35 caracteres)
Demostración en línea
Esto construye prefijos que satisfacen la condición.
fuente
Haskell
129 129121Aquí está mi intento de Haskell aficionado (sugerencias / mejoras serían muy apreciadas). Puede que no sea el más corto, pero solo se ejecuta en
.19.65 segundos después de los cambios de Flonk en mi sistema.fuente
<!-- language: lang-haskell -->
dos líneas antes de su código para resaltar la sintaxis!foldl1
Sin embargo, separando el en una función, puede usar eso en lugar desum
oany
.import Data.List;f=foldl1$(+).(*10);main=print$[f x|x<-permutations[1..9],f[mod(read.take y.show$f x)y|y<-[9,8..1]]<1]!!0
f
función en elmod
predicado para evitar escribir foldl1, aunque los ciclos adicionales obstaculizan severamente el rendimiento.!!0
con una llamada af
, lo que funciona ya que solo hay un elemento en la lista. La lista[9,8..1]
también se puede reemplazar porx
, porque el orden no importa. Hable acerca de la reutilización de código!Javascript 75 (terminando)
Solución de fuerza bruta (súper lenta)
Si desea ver el resultado en esta vida útil, actualice el valor inicial a algo como
a=c=38e7
Javascript 70 (sin terminación)
Y solo por diversión, una fuerza bruta aleatoria que funciona mucho más rápido: (solo ES6)
fuente
Pitón,
142,139,125124Esencialmente igual que la solución de @ Ventero si entendí su código correctamente, pero en Python. (Gran parte del crédito va a @Greg Hewgill).
fuente
r(9,1,-1)
conr(9)
, como el orden de iteración en realidad no importa.r(1,9)
porque%0
es un error.r(1, 9)
en Python.permutations("123456789")
y''.join(s[:i])
es probablemente más corto de lo que tienes (y luego puedes eliminarr=range
)Scala (128 caracteres)
Mi puñalada por esto ...
fuente
(2 to 8)
yforall
.Perl, 72
Uso:
perl -M5.010 find-9-digits.pl
Salida:
381654729
Este programa es lento . Puede tomar más de 10 segundos, ya que baraja los dígitos "123456789", pero la barajadura tiene un defecto.
Sin golf:
Golfé el código que baraja la matriz de dígitos 1..9:
use List'Util shuffle;shuffle 1..9
(34 caracteres)sort{(-1,1)[rand 2]}1..9
(24 caracteres)sort{.5<=>rand}1..9
(19 caracteres)sort(2-rand 4}1..9
(18 caracteres)sort{4-rand 8}1..9
(18 caracteres)Perl espera que el bloque de clasificación compare $ a y $ b de manera consistente. Mis bloques de clasificación nunca miran $ a y $ b . Devuelven una ordenación aleatoria, por lo que la clasificación se convierte en un aleatorio.
Si lo usara
sort{.5<=>rand}1..9
, mi programa se ejecutaría más rápido. Ese compara 0.5 con un flotante aleatorio de 0.0 a 1.0, excluyendo 1.0, para una probabilidad de 1/2 de que $ a <$ b , y una probabilidad de casi 1/2 de que $ a> $ b . ( Cuidado: este es un "Microsoft shuffle" , que no es un shuffle justo. Esto tiene un sesgo porque.5<=>rand
no proporciona un orden consistente).Supongamos que juego con un personaje y uso el peor
sort(2-rand 4}1..9
. Perl espera que el bloque de clasificación devuelva un número entero, pero2-rand 4
es flotante. Es un flotante aleatorio de -2.0 a 2.0, excluyendo -2.0. Perl trunca este flotador hacia cero, con estos resultados:Cuando $ a == $ b , Perl no baraja bien. Entonces, mi programa haría más barajaduras, hasta que obtenga suficientes barajaduras en las
2-rand 4
que no devuelva 0 con demasiada frecuencia. Mi programa correría tan lento que podría tomar más de un minuto.Yo uso
sort{4-rand 8}1..9
, por lo que solo hay una probabilidad de 1/4 de que $ a == $ b , y mi programa usa menos barajaduras.fuente
CJam, 35 bytes
Después de aproximadamente 27 minutos, esto produce el siguiente resultado:
Cómo funciona
fuente
Pitón 2 (78)
No es necesario generar permutaciones, solo pruebe cada número y verifique si sus dígitos más 0 son distintos. Toma un tiempo correr.
fuente
SWI-Prolog 84
Es un poco engañoso, porque la lista de dígitos debe ser proporcionada en la consulta:
Sin embargo, es lo que hace que este código sea interesante: puede resolver el problema para cualquier lista de dígitos. Por ejemplo:
fuente
Python 2 - 114
Ni siquiera la solución Python más corta, pero la comparto de todos modos:
fuente
Bash + coreutils, 159 bytes
Esto es un poco largo, pero creo que el algoritmo es quizás uno de los más rápidos, teniendo en cuenta que este es un script de shell (generalmente lento) que se ejecuta en menos de 0.1 segundo.
El algoritmo va más o menos así:
grep
)$d
(el número de dígito) usandobc
, con una expresión generada porprintf
Tenga en cuenta que tomamos un par de atajos, pero creo que estos son matemáticamente sólidos:
fuente
C ++, 187
Solo tenía que probar esto en C ++. Obviamente, no será la solución más corta, pero aquí está:
devuelve el número en lugar de imprimirlo para guardar algunos caracteres (maldita sea). En los sistemas POSIX, esto se convertirá, por supuesto, en un bit sin signo de 8 bits y, por lo tanto, no será correcto, pero el programa calculará un número correcto.
Sin golf (requiere C ++ 11):
fuente
T-SQL 2005+ - 203
T-sql no es un lenguaje de golf muy competitivo ...
Debe ejecutarse en la base de datos maestra. Puede reemplazar el primer CTE con esto para que sea independiente de la base de datos, pero luego usa algunos caracteres más (y requiere 2008)
Formación legible:
Básicamente, seguimos agregando dígitos al reverso del
r
número que aún no hemos visto en la cadena, y nos aseguramos de que la nueva cadena siga siendo el módulo 0 del nivel actual. Inicializamos R a\
, este es realmente el único truco en este código. Lo cual es una forma loca de establecerlo en 0 en elmoney
tipo de datos. Supongo que es una forma de permitirte escribir en\
lugar de moneda.$
también hace lo mismo en T-SQL, pero$l
intentaría interpretar una pseudo columna que no existe y arrojará un error. Esto nos permite evitar la preocupación de usarint
lo que causaría un desbordamiento normalmente en la décima concatenación, lo que nos obliga a verificar el nivel. Editar: Dato curioso T-sql, incluso en 2014, no tiene una forma integrada de convertir una cadena en una tabla de valores (por ejemplo, sin función dividida), por lo que en realidad también podemos reutilizar nuestraA
tabla dos veces para iterar los caracteres en el R. stringifiedLas reglas de precedencia de T-Sql son molestas, por lo que debemos utilizar la concatenación numérica (* 10 + n), en lugar de la concatenación de cadenas.
fuente
with A as(select 1n union all select n+1 from A where n<9),
PHP, 89 bytes
versión aleatoria, 89 bytes:
baraja una cadena que contiene los dígitos, luego prueba la divisibilidad en un bucle.
Corre con
-nr
.bucle de fuerza bruta, 90 bytes, muy lento:
bucles de 100000001, prueba la divisibilidad en el bucle interno y sale cuando encuentra una solución.
función recursiva, 94 bytes, muy rápida:
agrega un dígito que aún no está en el número, si se da la divisibilidad por longitud, recurse (o imprima).
Esto explota que solo hay una solución. sin eso,
print$e>8?$x:f($x,$e+1)
tenía que serprint$e>8?"$x\n":f($x,$e+1)
(+3 bytes, imprimir todas las soluciones) o($e>8?die("$x"):f($x,$e+1))
(+4 bytes, salir en la primera solución) o las soluciones se imprimirían sin un delimitador.Llamar con
f();
-
TiO
La versión de fuerza bruta no tiene TiO por razones obvias, pero puedes probar las otras dos .
El tiempo de ejecución de la llamada de función se mide en línea (en algún lugar entre 2 y 4 milisegundos);
El sitio web mide el tiempo de ejecución total (generalmente entre 50 y 500 ms).
fuente