Placas de licencia perfectas
Comenzando hace unos años, hice un pequeño juego mientras conducía: comprobar si las placas cercanas son "perfectas". Es relativamente raro, pero emocionante cuando encuentras uno.
Para verificar si una placa es perfecta:
- Resume los caracteres, con A = 1, B = 2, ... Z = 26.
- Tome cada trozo consecutivo de números y sume; multiplique cada una de estas sumas juntas.
Si los valores en la parte 1 y la parte 2 son iguales, ¡felicidades! ¡Has encontrado una matrícula perfecta!
Ejemplos
License plate: AB3C4F
Digits -> 3 * 4
= 12
Chars -> A + B + C + F
= 1 + 2 + 3 + 6
= 12
12 == 12 -> perfect!
License plate: G34Z7T
Digits -> (3 + 4) * 7
= 49
Chars -> G + Z + T
= 7 + 26 + 20
= 53
49 != 53 -> not perfect!
License plate: 10G61
Digits -> (1 + 0) * (6 + 1)
= 7
Chars -> G
= 7
7 == 7 -> perfect!
El reto
Usé placas de longitud 5 y 6 como ejemplos, pero este procedimiento es válido para cualquier longitud de placa. Su desafío es, para una longitud N dada, devolver el número de placas perfectas de esa longitud. Para los propósitos del desafío, una placa válida es cualquier combinación de dígitos 0-9 y caracteres AZ. La placa debe contener tanto un carácter como un número para que se considere potencialmente perfecta. Para fines de verificación, aquí están los valores que obtuve (aunque no puedo estar al 100% sobre su corrección, jajaja)
N < 2: 0
N = 2: 18
N = 3: 355
N = 4: 8012
Notas
Si de alguna manera el problema se simplifica en su idioma, puede generar la proporción de matrículas perfectas para un N dado, por lo menos a 2 dígitos significativos.
N < 2: 0
N = 2: 0.0138888...
N = 3: 0.0076088...
N = 4: 0.0047701...
O, puede generar el valor equivalente mod 256
N < 2: 0
N = 2: 18
N = 3: 99
N = 4: 76
¡Las victorias más cortas!
N
.Respuestas:
Python 3.6, 150 bytes
resultados:
Versión sin golf con explicación:
El problema se reduce a buscar un árbol en el que cada nivel del árbol corresponde a una posición en un número de placa y cada nodo tiene 36 hijos (10 dígitos y 26 letras). La función realiza una búsqueda recursiva del árbol, acumulando los valores de los dígitos y letras a medida que avanza.
Golf incluido, convirtiendo los bucles for en sumas de generadores:
Luego combinando los generadores. Codifique las letras, de la A a la Z, como -1 a -26 y los dígitos como 0 a 9. Entonces la suma se convierte en:
donde args es:
El resto del golf está convirtiendo la función en una lambda, acortando nombres de variables y simplificando expresiones.
fuente
n*n*log(n)
¿o algo similar?Dyalog APL,
5756 bytes(asume
⎕io←0
)a
matriz de todas las placas válidas (excepto00...0
) codificadas con: 0-9 para dígitos, 10-35 para letrasb
máscara de bits para donde ocurren los dígitosc
máscara de bits para el último dígito en cada grupo de dígitos consecutivosfuente
Python 2,
359295bytesMás bien largo; Esta es la solución trivial. Estoy seguro de que esto es correcto, aunque no coincide con los casos de prueba en el desafío. Las soluciones que estoy obteniendo coinciden con las respuestas de Dada.
-64 bytes gracias a las sugerencias de @numbermaniac
fuente
for
; entremap(ord,x)
yif
; y en la última línea, entre.join(x)
yfor
. Creo que también puede ahorrar aún más si redefine las funciones a lambdas.Python 2 ,
291287276273 bytesPruébalo en línea!
Resultados:
fuente
Perl 5 , 117 bytes
116 bytes de código +
-p
bandera.Pruébalo en línea!
Se siente bastante subóptimo, pero estoy sin ideas en este momento.
El código en sí es muy ineficiente, ya que calcula cada permutación de
a..z,0..9
longitudn
(tarda aproximadamente 1 segundo duranten=3
, ~ 15 segundosn=4
y ~ 7 minutosn=5
).El algoritmo es bastante sencillo: para cada placa de tamaño posible
n
(generada conglob"{@F}"x$_
- elglob
operador es bastante mágico),$r*=eval s/./+$&/gr for/\d+/g;
calcula el producto de cada trozo de dígitos y le$r+=64-ord for/\pl/g
resta el peso de las letras. Luego, incrementamos el contador$\
si el$r
es0
(!$r
) y si la placa contiene números y letras (/\pl/*/\d/
).$\
se imprime implícitamente al final gracias a-p
flag.Tenga en cuenta que los números obtengo son
n=2 -> 18
,n=3 -> 355
,n=4 -> 8012
,n=5 -> 218153
. Estoy bastante seguro de que estos son los correctos, pero podría estar equivocado, en cuyo caso avíseme y eliminaré esta respuesta.fuente
APL (Dyalog) , 71 bytes
Programa completo del cuerpo. Las solicitudes de N. N≥4 requieren grandes cantidades de memoria y cálculo.
Pruébalo en línea!
fuente
Scala, 265 bytes
Explicaciones:
Notas:
-64
y-48
se utilizan para transformar unaChar
(respectivamente letra y dígitos) a suInt
valor ('A' - 64 = 1
,'B' - 64 = 2
, ...,'9' - 48 = 9
)l.split("[A-Z]").filter(""<)
se usa para eliminar""
valores sil
comienza con una letra (ejemplo:)"A1".split("[A-Z]") => Array("", 1)
. Puede haber una solución mejor y más cortaCasos de prueba :
Resultados:
La función es bastante lenta
n > 4
ya que se deben generar todas las combinaciones.fuente
Java,
382365 bytesGolfed
Detallado
fuente
n
como entrada.int h(String s){int m=0;for(int c:s.toCharArray())m+=c-48;return m;}int g(String t){int d=1,c=0;for(String s:t.split("[^0-9]"))d*=h(s);for(String s:t.split("[^A-Z]"))c+=s.charAt(0)-65;return d==c?1:0;}int f(String t,int n){int m=0;if(t.length()==n)return g(t);for(int d=48;d<58;)m+=f(t+d++,n);for(int c=65;c<91;)m+=f(t+c++,n);return m;}int s(int n){return f("",n);}
( 365 bytes ) Puede comparar su versión actual con esta para ver los cambios que hice (demasiado para el resto de este comentario). :)GAP , 416 bytes
No ganará en tamaño de código, y lejos del tiempo constante, ¡pero usa las matemáticas para acelerar mucho!
Para exprimir el espacio en blanco innecesario y obtener una línea con 416 bytes, canalice esto:
Mi vieja computadora portátil "diseñada para Windows XP" puede calcular
f(10)
en menos de un minuto e ir mucho más lejos en menos de una hora:Cómo funciona
Supongamos que primero solo queremos saber el número de placas perfectas que se ajustan al patrón
LDDLLDL
, dondeL
denota una letra yD
denota un dígito. Supongamos que tenemos una listal
de números quel[i]
da la cantidad de formas en que las letras pueden dar el valori
, y una lista similard
para los valores que obtenemos de los dígitos. Entonces, el número de placas perfectas con valor comúni
es justol[i]*d[i]
, y obtenemos el número de todas las placas perfectas con nuestro patrón sumando esto sobre todoi
. Denotemos la operación de obtener esta sumal@d
.Ahora, incluso si la mejor manera de obtener estas listas era probar todas las combinaciones y contar, podemos hacer esto independientemente para las letras y los dígitos, mirando los
26^4+10^3
casos en lugar de los26^4*10^3
casos cuando simplemente pasamos por todas las placas que se ajustan al patrón. Pero podemos hacerlo mucho mejor: aquíl
es solo la lista de coeficientes de(x+x^2+...+x^26)^k
dóndek
está el número de letras4
.Del mismo modo, obtenemos el número de formas de obtener una suma de dígitos en una serie de
k
dígitos como los coeficientes de(1+x+...+x^9)^k
. Si hay más de una serie de dígitos, necesitamos combinar las listas correspondientes con una operaciónd1#d2
que en la posicióni
tenga como valor la suma de todos losd1[i1]*d2[i2]
lugaresi1*i2=i
. Esta es la convolución de Dirichlet, que es solo el producto si interpretamos las listas como coeficientes de las series de Dirchlet. Pero ya los hemos usado como polinomios (series de potencia finita), y no hay una buena manera de interpretar la operación para ellos. Creo que este desajuste es parte de lo que hace que sea difícil encontrar una fórmula simple. Usémoslo en polinomios de todos modos y usemos la misma notación#
. Es fácil de calcular cuando un operando es un monomio: tenemosp(x) # x^k = p(x^k)
. Junto con el hecho de que es bilineal, esto proporciona una forma agradable (pero no muy eficiente) de calcularlo.Tenga en cuenta que las
k
letras dan un valor de como máximo26k
, mientras quek
dígitos individuales pueden dar un valor de9^k
. Por lo tanto, a menudo obtendremos altos poderes innecesarios en eld
polinomio. Para deshacernos de ellos, podemos calcular el módulox^(maxlettervalue+1)
. Esto da una gran velocidad y, aunque no me di cuenta de inmediato, incluso ayuda al golf, porque ahora sabemos que el grado ded
no es mayor que el del
, lo que simplifica el límite superior en la finalSum
. Obtenemos una velocidad aún mejor al hacer unmod
cálculo en el primer argumento deValue
(ver comentarios), y hacer todo el#
cálculo a un nivel inferior da una velocidad increíble. Pero todavía estamos tratando de ser una respuesta legítima a un problema de golf.Así que tenemos nuestro
l
yd
podemos usarlos para calcular el número de matrículas perfectas con patrónLDDLLDL
. Ese es el mismo número que para el patrónLDLLDDL
. En general, podemos cambiar el orden de las corridas de dígitos de diferente longitud como queramos,NrArrangements
da el número de posibilidades. Y aunque debe haber una letra entre las series de dígitos, las otras letras no son fijas. ElBinomial
cuenta estas posibilidades.Ahora queda por recorrer todas las formas posibles de tener longitudes de dígitos de ejecución.
r
recorre todos los números de carreras,c
todos los números totales de dígitos yp
todas las particiones dec
conr
sumandos.El número total de particiones que vemos es dos menos que el número de particiones
n+1
, y las funciones de partición crecen comoexp(sqrt(n))
. Por lo tanto, aunque todavía hay formas fáciles de mejorar el tiempo de ejecución reutilizando los resultados (ejecutando las particiones en un orden diferente), para una mejora fundamental, debemos evitar mirar cada partición por separado.Calcularlo rápido
Tenga en cuenta que
(p+q)@r = p@r + q@r
. Por sí solo, esto solo ayuda a evitar algunas multiplicaciones. Pero junto con(p+q)#r = p#r + q#r
esto significa que podemos combinar mediante polinomios de suma simple correspondientes a diferentes particiones. No podemos simplemente agregarlos a todos, porque aún necesitamos saber con quél
tenemos que@
combinar, qué factor tenemos que usar y qué#
extensiones aún son posibles.Combinemos todos los polinomios correspondientes a particiones con la misma suma y longitud, y ya tenga en cuenta las múltiples formas de distribuir las longitudes de las series de dígitos. A diferencia de lo que especulé en los comentarios, no necesito preocuparme por el valor usado más pequeño o con qué frecuencia se usa, si me aseguro de no extenderme con ese valor.
Aquí está mi código C ++:
Esto usa la biblioteca GNU MP. En debian, instale
libgmp-dev
. Compilar cong++ -std=c++11 -O3 -o pl pl.cpp -lgmp -lgmpxx
. El programa toma su argumento de stdin. Para el tiempo, useecho 100 | time ./pl
.Al final
a[sum][length][i]
da el número de formas en que lossum
dígitos en laslength
corridas pueden dar el númeroi
. Durante el cálculo, al comienzo delm
ciclo, proporciona la cantidad de formas que se pueden hacer con números mayores quem
. Todo comienza cona[0][0][1]=1
. Tenga en cuenta que este es un superconjunto de los números que necesitamos para calcular la función para valores más pequeños. Entonces, casi al mismo tiempo, podríamos calcular todos los valores hastan
.No hay recursión, por lo que tenemos un número fijo de bucles anidados. (El nivel de anidamiento más profundo es 6.) Cada ciclo pasa por una serie de valores que son lineales
n
en el peor de los casos. Entonces solo necesitamos tiempo polinomial. Si miramos más de cerca los anidadosi
y losj
buclesextend
, encontramos un límite superior paraj
el formularioN/i
. Eso solo debería dar un factor logarítmico para elj
bucle. El bucle más interno enf
(consumn
etc.) es similar. También tenga en cuenta que calculamos con números que crecen rápidamente.Tenga en cuenta también que almacenamos
O(n^3)
estos números.Experimentalmente, obtengo estos resultados en hardware razonable (i5-4590S):
f(50)
necesita un segundo y 23 MB,f(100)
necesita 21 segundos y 166 MB,f(200)
necesita 10 minutos y 1.5 GB, yf(300)
necesita una hora y 5.6 GB. Esto sugiere una complejidad temporal mejor queO(n^5)
.fuente
n=5
, no hay caso con una corrida de dos dígitos y dos dígitos simples, porque entonces no tenemos suficientes letras para separar los números. Esto es lo que hacen los tresfor
bucles externos : ejecutar todas las particiones útiles de números<n
. (Y me acabo de dar cuenta de que también permiton
dígitos. Por pura suerte, otra optimización cuenta esto como 0).<n/2
, todas las particiones son útiles. Y los cálculos restantes aún toman su tiempo no constante. Para ver qué está sucediendo, puede agregarPrint(p,"\n");
al comienzo del cuerpo delfor p...
bucle. - Tengo una idea para usar un bucle menos, pero solo ayudará al tamaño del código.mod
(que ya ayudó mucho)Value
, cambiándolo aValue(d mod x^(1+QuoInt(s(l)-1,i-1)),x^(i-1))
. Eso solo permite calcularf(15)
en 80 segundos.Pyth, 55 bytes
fuente