Se le dan como entrada dos cadenas que representan enteros positivos en la base 10, como "12345"
y "42"
. Su tarea es generar una cadena que contenga su producto, "518490"
en este caso.
El giro es que no puede usar ningún tipo numérico en su código. No ints
, float
s, unsigned long
s, etc., no hay tipos de números complejos integrados o enteros de precisión arbitrarios, ni nada por el estilo. Es posible que no utilice literales de esos tipos, ni ninguna función, método, operador, etc. que los devuelva.
Usted puede utilizar cadenas, booleanos, matrices, o cualquier otra cosa que normalmente no se utiliza para representar un número. (Pero tenga en cuenta que es probable que no sea posible indexar en una matriz ni obtener su longitud sin invocar un tipo numérico). char
S están permitidos, pero no puede realizar ninguna operación aritmética o bit a bit ni tratarlos como algo más que no sea una ficha que representa parte de una cadena. ( char
Se permite la comparación lexicográfica de s).
Es posible que no evite la restricción. Esto incluye (pero no se limita a) el uso de tipos numéricos dentro de una eval
función de tipo, conversiones de tipo implícitas en tipos numéricos, el uso de operadores numéricos o bit a bit en tipos no numéricos que los admiten, el uso de tipos numéricos almacenados dentro de tipos de contenedor, o funciones de llamada o programas externos que devuelven resultados numéricos en forma de cadena. (Me reservo el derecho de agregar a esta lista si aparecen otras soluciones en las respuestas). Debe implementar la multiplicación usted mismo utilizando solo tipos no numéricos.
La entrada y salida pueden realizarse por cualquier método conveniente, siempre que los datos ingresen y salgan de su código en forma de cadena. Puede suponer que cada uno de los dos argumentos de entrada contiene solo los caracteres ASCII [0-9]
y no comenzará con 0
. Su salida tampoco debería tener ceros a la izquierda.
Una cosa más: su código debe manejar correctamente las entradas de al menos 10 caracteres de longitud y debe ejecutarse en menos de un minuto en una computadora moderna para todas las entradas en ese rango. Antes de publicar, verifique que cuando reciba entradas 9999999999
y 9999999999
, su programa dé una salida de 99999999980000000001
, en menos de un minuto. Esta restricción existe específicamente para evitar respuestas que funcionen al asignar una matriz de tamaño a*b
y luego iterar sobre ella, así que tenga en cuenta que las respuestas de esa forma no serán elegibles para ganar.
Este es el código de golf , por lo que gana la solución válida más corta (en bytes).
fuente
"12345"
de STDIN en lugar de12345
? ¿O podemos aceptar ambos números como"12345", "42"
?m
yn
y devolver un argumento de longitudm*n
. Pero como las cadenas tienen que contener literalmente la representación ASCII de los números, supongo que eso va en contra de las reglas.a,b="0123456789x".split('0');c=iter(b).next()
if c=='x':
c='0'
a,b="0123456789x".split(x);c,*d=b
if c=='x':
c='0'
d='123456789';I=dict(zip('0'+d,d+'0'))
Respuestas:
Haskell 180 180
214Implementa la multiplicación a través de la suma repetida, y todo tipo de magia de dígitos se maneja cambiando y filtrando la
['0'..'9']
lista. Define un operador#
del tipoString -> String -> String
:fuente
"0123456789"
es la lista['0'..'9']
. Segundo, en Haskell [a..b] es una enumeración, los tipos que han declarado instancias de laEnum
clase de tipos se pueden enumerar así, y la declaración describe cómo funciona la enumeración.Bool
, el tipo booleano también tiene una instancia y, por lo tanto, también puede hacerlo[False..True]
. Apenas hay números involucrados.sed,
339338 bytesSé que este es viejo, pero estaba navegando y despertó mi interés. ¡Suficiente para registrarse como usuario! Supongo que me influyó " Me gustaría ver una solución sed completa - Nathaniel " ...
Este script sed espera dos números decimales como entrada, separados por un espacio
pruebas:
Puede reconocer los dos últimos como RSA-100 (50 x 50 dígitos) y RSA-768 (116 x 116 dígitos).
El uso de GNU sed en un no muy moderno (Intel Core 2 de la era 2007), el último de ellos lleva más de un minuto, pero llega más rápido en un procesador más nuevo:
La pequeña multiplicación de 10 dígitos especificada en la pregunta lleva bastante menos de un segundo en cualquiera de estos (a pesar de estar llena de nueves patológicas).
Creo que es sed estándar, sin extensiones. POSIX garantiza un espacio de espera de solo 8192 bytes, lo que nos limita a multiplicar números de 400x400 dígitos, pero las implementaciones pueden proporcionar más. GNU sed está limitado solo por la memoria disponible, por lo que podría administrar algo mucho más grande, si está dispuesto a esperar.
Y estoy seguro de que he cumplido con las reglas, eso es casi un hecho en un idioma que no tiene números. :-)
Explicación
Utilizo un híbrido unario / decimal, convirtiendo números decimales en una secuencia de unario:
En decimal unario, la suma es fácil. Repetimos desde el dígito menos significativo al más significativo, concatenando las x:
Luego eliminamos los espacios en blanco, y tratamos con el transporte convirtiendo 10 x consecutivas en una de las siguientes unidades:
Una vez que tenemos la suma, la multiplicación es posible. Multiplicamos x * y considerando el último dígito de y. Agregue x al acumulador muchas veces, luego pase al siguiente dígito y desplace x un decimal a la izquierda. Repita hasta que y sea cero.
Código expandido
fuente
sed, 379 bytes
El crédito por esta brillante respuesta es para @LuigiTiburzi en Unix y Linux.SE: https://unix.stackexchange.com/a/37213/34061 . Me topé con esto hace unos días:
Amplia explicación
12*3
convierte<1<2*<3
|
caracteres. Así se<1<2*<3
convierte<|<||*<|||
|<
con<||||||||||
el fin de desplazar más altas cifras decimales todo se debe a la posición de las unidades. Así se<|<||*<|||
convierte<||||||||||||*<|||
<
. Así se<||||||||||||*<|||
convierte||||||||||||*|||
|
del RHS de la*
. Así se||||||||||||*|||
convierte||||||||||||*||
|
en el RHS con todos los|
del LHS. Esto tiene el efecto de multiplicar el número de LHS y RHS|
para dar el número de producto de|
Así se||||||||||||*||
convierte||||||||||||||||||||||||||||||||||||*
*
. Así se||||||||||||||||||||||||||||||||||||*
convierte||||||||||||||||||||||||||||||||||||
|
vuelta a decimal por el reverso de los primeros pasos. Así se||||||||||||||||||||||||||||||||||||
convierte36
.Salida:
Desafortunadamente, falla miserablemente en el requisito de tiempo:
200*1000
toma 41 segundos en mi Ubuntu VM, y el tiempo de ejecución empíricamente parece aumentar con el cuadrado del producto final.fuente
length()
que devuelve un número. Este utiliza la sustitución puramente regex sin tipos numéricos. Sin embargo, creo que su respuesta es potencialmente ganadora si puede eliminar ellength()
- ¿tal vez podría hacer una sustitución de expresiones regulares similar?Python -
312286273Si se permiten (muchos) ceros iniciales, no se necesitan los últimos 12 caracteres.
Esto esencialmente realiza la multiplicación estándar a mano. Los dígitos se representan como cadenas de
I
s repetidas (como números romanos primitivos). Los números se representan como listas de dígitos en orden inverso. La adición de un solo dígito se realiza cocatenando cadenas y eliminando diezI
s si es necesario.Aquí hay una versión sin golf:
fuente
def A(x,y):\n S=[];o=""
->def A(x,y,S=[],o=""):
. Además, desafortunadamente,["","1"][t in i]
no está permitido; está usando un bool para indexar, tratándolo como un número. Sint in i and"1"or""
embargo, creo que debería funcionar.S
como un argumento con un valor predeterminado no habría funcionado, ya que siempre sería la misma lista incluso para diferentes llamadas de la función y, por lo tanto, no se restablecería[]
. Tenías razón["","1"][t in i]
, lo arreglé. También agregué una explicación.Rubí:
752698Esto es solo para obtener una respuesta, solo por curiosidad. Editado: ahora jugaba un poco al golf.
Uso: Tenía esto en un archivo llamado peasant.rb:
Explicación: es la multiplicación campesina, por lo que reduzco a la mitad y el doble. La reducción a la mitad se realiza dividiendo a la mitad los dígitos y marcando los restos de la siguiente manera: 1234 -> 0b1a1b2a; luego busque y reemplace en las b: 06a17a; luego limpiar -> 617.
La suma se hace así ... en primer lugar, coloco ambas cuerdas a la misma longitud y hago pares a partir de los dígitos. Luego agrego los dígitos construyendo una cadena que tiene la longitud de cada dígito y concatenando; Elimino una cadena de esa longitud desde el inicio de '0123456789abcdefghij', y luego mantengo el primer carácter. Entonces, por ejemplo, "9" + "9" -> "i". Nota: evito usar funciones de longitud aquí para evitar los tipos de números por completo; la eliminación del prefijo se realiza con una expresión regular en su lugar.
Así que ahora tengo una cadena que contiene una combinación de dígitos y letras. Las letras representan números con un dígito de acarreo; Antepongo 0 al número, luego reemplazo repetidamente patrones de letras y dígitos con el resultado del acarreo hasta que se completa la adición.
fuente
Brainfuck (1328 bytes)
Consideraciones al principio:
Solo probé el programa con mi propio intérprete, puedes encontrarlo aquí .
La entrada debe ser ambos números separados por un solo espacio ASCII.
Golfizado:
Sin golf:
He tomado el código para la salida del valor de esta respuesta , ¡gracias al autor por eso!
El programa puede no ser válido, pero de cualquier manera quería compartirlo con usted ^^
Actualización: ¡Ahora puedes probarlo (solo para pequeñas multiplicaciones) aquí, gracias a la respuesta de @ Sp3000 a este concurso y a los nuevos fragmentos de pila de SE!
fuente
Python,
394349340 caracteresCorre como:
Tarda 50 milisegundos.
Utiliza la multiplicación campesina rusa . Al agregar dígitos, los convertimos a unarios ('5' => [R, R, R, R, R]), concatenamos las listas y luego las convertimos de nuevo.
U
se convierte en unario, utilizandoR
como dígito unario. Calculamosb/=2
comob=b*5/10
.fuente
def A(a,b):\n r='';c=[]
->def A(a,b,r='',c=[]):
, de manera similar paradef M
. Es posible que pueda cambiarfor z in D:d.pop()\n c=['X']
a[d.pop()for z in D];c=['X']
, en cuyo caso incluso podría colapsarlo sobre el anteriorif
. Además, ¿puedeif list(b).pop()in'13579'
serif b[:].pop()in'13579'
?b
hay una cadena, no una lista.M
y escribir un programa completo;a,b=input()
esta permitido.reduce
, lo que le permite nicenA(b,A(b,A(b,A(b,b))))
areduce(A,[b,b,b,b,b])
. Lamentablemente, esto no afecta el recuento de caracteres.JavaScript (E6) 375
395 411 449Edit Golfed
Edit Bug solucionado: falta borrar una bandera de acarreo
Se puede hacer con solo la manipulación de símbolos en un tiempo cercano a 0.
En esta versión, puede usar cualquier carácter en lugar de los dígitos, siempre que el símbolo esté en orden ascendente.
Notas: uso de cadenas, hashmap con clave de cadena, matrices utilizadas como lista. Sin indexación, las matrices se recorren usando 'map' o se giran usando push & shift.
Todos los '+' son concatenación de cadenas.
Menos golf (tal vez agregaré una explicación mañana)
Prueba en la consola FireFox / FireBug
Salida
fuente
9999999999
caso debería ser99999999980000000001
, no99999999980000000081
Haskell, 231 bytes
Esto define un operador # que multiplica dos representaciones de cadena de números naturales. Funciona definiendo una operación elemental de incremento / decremento en cadenas, luego la usa para construir la suma y la multiplicación. Un poco de magia extra da algunas aceleraciones exponenciales que lo hacen posible.
Este enfoque es lo suficientemente rápido como para que incluso en una computadora portátil 2008 en el ghci REPL no optimizado, el caso de prueba tome solo una fracción de segundo:
Aquí hay una comprobación de que todos los productos de dos dígitos son correctos:
fuente
Bash + ImageMagick: 52
Espera que la entrada esté en las variables de shell
a
yb
. No es particularmente inteligente o eficiente, pero hace el trabajo. Probablemente ya se haya hecho antes.Tenga en cuenta que
x
denota las dimensiones de la imagen; No es un operador aritmético en este contexto.No he probado esto, pero estoy dispuesto a asumir que para una entrada no extrema, se completará en menos de un minuto. Puedo probarlo mañana.
En caso de que haya algún negocio divertido con las versiones de ImageMagick, este es el que estoy usando:
ImageMagick 6.7.7-10
fuente
9999999999
y9999999999
.dd if=/dev/zero bs=$a count=$b 2>&-|wc -c
.9999999999x9999999999
imagen en formato de 8 bits ocupará todo el espacio en el disco duro que existe actualmente en la Tierra. Por supuesto, un png sería mucho más pequeño, si puede crearlo sin crear primero la imagen en bruto. (Aunque sospecho que tendrías problemas de desbordamiento de enteros con una imagen de ese tamaño). Sin embargo, tal método casi con certeza no entraría en la laguna de llamar a las cosas que devuelven resultados numéricos como cadenas.$b
lugar de${b}
.grep -vc g
lugar degrep -v g|wc -l
.Python 2 (prueba de concepto)
Esta solución funciona solo con cadenas y listas, y un poco de expresión regular. Creo que se ajusta completamente a las especificaciones, excepto que no hay forma de que pueda hacerlo
9999999999x9999999999
en un minuto. Aunque con tiempo suficiente funcionaría. Puede multiplicar números de 4 dígitos con bastante rapidez.Como es técnicamente inválido, aún no me he molestado en jugarlo por completo. Lo haré si cambian las reglas.
Ejemplos:
fuente
Pitón 2 (555)
Normalmente no respondería mi propio desafío tan rápido (o en absoluto), pero quería demostrar que se podía hacer. (Afortunadamente, algunas otras respuestas lo hicieron antes de esta, pero no pude evitar querer terminarlo). Se podrían hacer más juegos de golf, pero creo que esto es razonable. Maneja el
9999999999x9999999999
caso en menos de 0.03s en mi máquina.Ejemplo de uso:
m("12345","42")
Funciona haciendo multiplicaciones largas usando manipulaciones de cuerdas. Algunas veces las variables son cadenas y otras son iteradores sobre cadenas, lo que hace posible obtener el primer elemento sin usar un literal entero. Todo se almacena con los dígitos invertidos, de modo que el primer elemento es el dígito menos significativo.
Aquí hay una explicación de función por función:
r
ys
son funciones de contabilidad. (r
es solo un alias parareversed
, que hace un iterador inverso ys
convierte los iteradores en cadenas).i
incrementa el número en una cadena en 1, incluidos casos como39+1=40
y99+1=100
.b
agregax
yy
, peroy
debe ser solo un dígito. Funciona incrementando losx
y
tiempos.a
agrega dos números juntos que pueden tener varios dígitos, llamandob
a cada dígito eny
.n
multiplicax
yy
, peroy
debe tener solo un dígito. Funciona agregandox
a sí mismoy
tiempos.o
multiplicax
yy
, donde ambos argumentos pueden tener múltiples dígitos. Utiliza la multiplicación larga clásicam
simplemente convierte sus entradas de cadena en iteradores inversos y las entregao
, luego invierte el resultado y lo convierte en una cadena.fuente
def a(x,y):
->def a(x,y,z=''):
y eliminar la siguiente línea; trucos similares para otras funciones, endef o(x,y):
, cambiar elx=s(x)
ax=s(x);l='';z=''
, en ese bucle for, eliminar de manera similar newline + ritmos; en lugar de usar;
. Además, creo queif h!='0':h+=s(x)\nelse:h+=i(x)
simplemente puede serh+=h!='0'and i(x)or s(x)
; tal vez inclusoh+=(h!='0'and i or s)(x)
; de lo contrario, simplemente cambie aif'0'!=h
. También cosas comodef r(x):return reversed(x)
->r=reversed
s
,m
:s=lambda x:''.join(x)
,m=lambda x,y:s(r(o(r(x),r(y))))
en lugar de toda la declaración de la función. Con solo las cosas que sé que funcionan, esto reduce su cuenta de bytes a 521.for
bucles:for c in'0'+d:\nif c==y:break\nz=a(iter(z),x)
->for c in'0'+d:\nif c!=y:z=a(iter(z),x)
, aunque esto podría cambiar significativamente la velocidad de tu programa.JavaScript:
37103604 bytesGolf:
Sin golfista con las pruebas:
Esto produce:
fuente
Haskell
507496Esto funciona para enteros arbitrariamente grandes. Defino representaciones personalizadas para los números naturales del 0 al 18 (el número natural más grande igual a la suma de dos dígitos), y defino la multiplicación little-endian en términos de multiplicación dígito * número, que defino en términos de suma número + número , que defino en términos de suma dígito + dígito. Tengo una función de reducción que expande 10-18 valores en su descomposición digital. Esto solo lee e invierte las dos cadenas, se traduce en los enlaces personalizados, se multiplica y se traduce hacia atrás, invirtiendo para obtener el resultado correcto.
Editar 2
Me salvó un par de caracteres mediante la creación de alias locales cortos para los comandos de varios caracteres que utilizo más de una vez, así como la eliminación de los espacios y los paréntesis, y mediante la sustitución
(
-)
pares con los$
que sea posible.Como referencia, S es el tipo de datos tipo entero personalizado,
p
es 'más' (suma dígito + dígito),s
se resta (para reducción),r
se reduce (se expande en descomposición digital),a
es suma (suma número + número),m
es multiplicar (multiplicación de dígitos * números),t
es veces (multiplicación de números * números),i
es 'interpretar' (convertir cadena a lista deS
),b
es 'atrás' (lista de S a cadena), y f y g son solo abreviaturas para jugar al golf propósitos No utilicé números, ni siquiera implícitamente; lo más cerca que estuve fue usar sucesores y predecesores, que son conceptos matemáticos de un nivel mucho más alto que la suma y multiplicación de números naturales.Editar
Olvidé incluir el perfil de tiempo.
Solo por si acaso:
¡Vamos a volvernos locos!
confirmación
fuente
Python 2 -
1165, 712, 668664Tenga en cuenta que no estoy usando indexación lógica como
Z = [X, Y][N == "0"]
, porque esto podría interpretarse como un booleano convertido a un índice numérico.Sin golf:
fuente
Scala, 470 caracteres
(
⇒
son scala estándar pero se pueden reemplazar de manera equivalente=>
si contamos bytes)Aquí estamos emulando dígitos usando la longitud de las listas, teniendo cuidado de no usar ninguna operación numérica, solo pliegues, mapas, cremalleras y similares. Un número es una lista de estos dígitos (orden estratégicamente invertido a la mitad del cálculo); multiplicamos dígitos individuales con
flatMap
y nuestras filas conreduce
.u
maneja averiguar el acarreo (haciendo coincidir directamente una lista de> 10 elementos y recurriendo) y convirtiendo los dígitos nuevamente en caracteres, y usamos a/:
para avanzar a través de la pila con eso. El ejemplo requerido se completa en menos de un segundo.fuente