Multiplica dos números sin usar ningún número

30

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, floats, unsigned longs, 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). charS 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. ( charSe 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 evalfunció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 9999999999y 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*by luego iterar sobre ella, así que tenga en cuenta que las respuestas de esa forma no serán elegibles para ganar.

Este es el , por lo que gana la solución válida más corta (en bytes).

Nathaniel
fuente
¿Podemos aceptar "12345"de STDIN en lugar de 12345? ¿O podemos aceptar ambos números como "12345", "42"?
Justin
Mi primer pensamiento fue escribir una función de tomar argumentos de cadena de longitud my ny devolver un argumento de longitud m*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.
Level River St
1
@xnor en muchos idiomas puede ser más corto escribir todos los casos. Pero encontré esta manera en Python:a,b="0123456789x".split('0');c=iter(b).next() if c=='x': c='0'
Nathaniel
1
o en Python 3,a,b="0123456789x".split(x);c,*d=b if c=='x': c='0'
Nathaniel
2
@Nathanield='123456789';I=dict(zip('0'+d,d+'0'))
Justin

Respuestas:

6

Haskell 180 180 214

r=reverse
f=filter
z=['0'..'9']
a?f|f="1"!a
a?_=a
(a:b)!(c:d)=e:b!d?(e<a)where e=fst$last$zip(f(>=c)z++z)$f(<=a)z
a!c=a++c
a%(b:c)=foldr(!)('0':a%c)$f(<b)z>>[a]
_%b=b
a#b=r$r a%r b

Implementa 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 tipo String -> String -> String:

*> :set +s
*> "9990123456789"#"9999876543210"
"99900001219316321126352690"
(0.02 secs, 9862288 bytes)
mniip
fuente
¡Parece que tenemos un nuevo ganador! (Aunque como antes, no puedo leer a Haskell sobre este grado de sofisticación, ¿alguien puede verificar de forma independiente si cumple con las especificaciones?)
Nathaniel
(También el ['0' .. '9'] se siente un poco como tratar implícitamente los caracteres como números que se pueden iterar, ¿hay alguna forma corta de generar esa lista a partir de la cadena "0123456789"?)
Nathaniel
@Nathaniel Bueno, en primer lugar, la cadena "0123456789" es la lista ['0'..'9']. Segundo, en Haskell [a..b] es una enumeración, los tipos que han declarado instancias de la Enumclase 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.
mniip
14

sed, 339 338 bytes

Sé 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 " ...

s/[1-9]/0&/g
s/[5-9]/4&/g
y/8/4/
s/9/4&/g
s/4/22/g
s/[37]/2x/g
s/[26]/xx/g
s/[1-9]/x/g
:o
s/\( .*\)0$/0\1/
/x$/{
x
G
s/ .*/\n/
:a
s/\(.*\)0\(x*\)\n\(.*\)0\(x*\)\n/\1\n\3\n0\2\4/
ta
s/\n//g
:c
s/^x/0x/
s/0xxxxxxxxxx/x0/
tc
x
s/x$//
}
/ 0/bo
g
s/0x/-x/g
s/xx/2/g
y/x/1/
s/22/4/g
s/44/8/g
s/81/9/g
s/42/6/g
s/21/3/g
s/61/7/g
s/41/5/g
s/-//g

Este script sed espera dos números decimales como entrada, separados por un espacio

pruebas:

time test 518490 = $(./40297.sed <<<)"12345 42" || echo fail
time test 99999999980000000001 = $(./40297.sed <<<"9999999999 9999999999") || echo fail
time test 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 = $(./40297.sed <<<"37975227936943673922808872755445627854565536638199 40094690950920881030683735292761468389214899724061") || echo fail
time test 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413 = $(./40297.sed <<<"33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917") || echo fail

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:

  • Q6600:> 1 minuto
  • i7-3770: 26 segundos
  • i7-6700: 22 segundos

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:

 42 => _xxxx_xx

En decimal unario, la suma es fácil. Repetimos desde el dígito menos significativo al más significativo, concatenando las x:

   X=965                   Y=106                                 SUM
   _xxxxxxxxx_xxxxxx_xxxxx _x__xxxxxx
   _xxxxxxxxx_xxxxxx       _x_                          _xxxxxxxxxxx
   _xxxxxxxxx              _x                    _xxxxxx_xxxxxxxxxxx
                                      _xxxxxxxxxx_xxxxxx_xxxxxxxxxxx

Luego eliminamos los espacios en blanco, y tratamos con el transporte convirtiendo 10 x consecutivas en una de las siguientes unidades:

 _xxxxxxxxxx_xxxxxx_xxxxxxxxxxx       10.6.11
 _xxxxxxxxxx_xxxxxxx_x                10.7.1
 _x__xxxxxxx_x                        1.0.7.1 

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

#!/bin/sed -f

# Convert to unary decimal.  We save two or three bytes of code by
# reusing 0 as the digit separator.
s/[1-9]/0&/g
s/[5-9]/4&/g
y/8/4/
s/9/4&/g
s/4/22/g
s/[37]/2x/g
s/[26]/xx/g
s/[1-9]/x/g

# until y==0

:one

# y ends in zero => x *= 10 and y /= 10
s/\( .*\)0$/0\1/

# while y%10, acc += x, y -= 1
/x$/{
x
G
s/ .*/\n/
# Add x
:add
s/\(.*\)0\(x*\)\n\(.*\)0\(x*\)\n/\1\n\3\n0\2\4/
tadd
s/\n//g
:carry
s/^x/0x/
s/0xxxxxxxxxx/x0/
tcarry

# repeat for each unit of y
x
s/x$//
}

# y?
/ 0/bone


# convert hold space to decimal
g
s/0x/-x/g
s/xx/2/g
y/x/1/
s/22/4/g
s/44/8/g
s/81/9/g
s/42/6/g
s/21/3/g
s/61/7/g
s/41/5/g
s/-//g
Toby Speight
fuente
1
Respuesta muy satisfactoria, gracias!
Nathaniel
9

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:

s/[0-9]/<&/g
s/0//g
s/1/|/g
s/2/||/g
s/3/|||/g
s/4/||||/g
s/5/|||||/g
s/6/||||||/g
s/7/|||||||/g
s/8/||||||||/g
s/9/|||||||||/g
:t
s/|</<||||||||||/g
tt
s/<//g
s/.*\*$/0/
s/^\*.*/0/
s/*|/*/
:m
s/\(|*\)\*|/\1<\1*/
tm
s/*//g
s/<//g
:b
s/||||||||||/</g
s/<\([0-9]*\)$/<0\1/
s/|||||||||/9/
s/||||||||/8/
s/|||||||/7/
s/||||||/6/
s/|||||/5/
s/||||/4/
s/|||/3/
s/||/2/
s/|/1/
s/</|/g
tb

Amplia explicación

  • Separa cada dígito. Así se 12*3convierte<1<2*<3
  • Convierta cada dígito a ese número de |caracteres. Así se <1<2*<3convierte<|<||*<|||
  • Repetidamente sustituir |<con <||||||||||el fin de desplazar más altas cifras decimales todo se debe a la posición de las unidades. Así se <|<||*<|||convierte<||||||||||||*<|||
  • Remover <. Así se <||||||||||||*<|||convierte||||||||||||*|||
  • Eliminar 1 |del RHS de la *. Así se ||||||||||||*|||convierte||||||||||||*||
  • Reemplace repetidamente cada uno |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||||||||||||||||||||||||||||||||||||*
  • Remover *. Así se ||||||||||||||||||||||||||||||||||||*convierte||||||||||||||||||||||||||||||||||||
  • convertir el número de |vuelta a decimal por el reverso de los primeros pasos. Así se ||||||||||||||||||||||||||||||||||||convierte 36.

Salida:

$ echo "04*3
4*3
40*3
42*32
150*20
1*3
3*1
0*3
3*0" | sed -f mult.sed
12
12
120
1344
3000
3
3
0
0
$

Desafortunadamente, falla miserablemente en el requisito de tiempo: 200*1000toma 41 segundos en mi Ubuntu VM, y el tiempo de ejecución empíricamente parece aumentar con el cuadrado del producto final.

Trauma digital
fuente
1
Esto es casi algorítmicamente equivalente a mi respuesta JS eliminada, excepto por la conversión a la parte numérica.
Optimizador
@Optimizer De acuerdo. La diferencia es que el tuyo usa el 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 el length()- ¿tal vez podría hacer una sustitución de expresiones regulares similar?
Trauma digital
1
Muy agradable, pero la restricción de un minuto está específicamente destinada a evitar soluciones que funcionen contando hasta la respuesta. Sin embargo, me gustaría ver una solución sed completa.
Nathaniel
1
Tengo una respuesta que funciona con números grandes (por ejemplo, más grande que el espacio de direcciones del sistema).
Toby Speight
@TobySpeight sí, muy bien. Creo que ya debo haber votado el tuyo hace un tiempo :)
Digital Trauma
9

Python - 312 286 273

D={}
e=t=""
N=[e]
for c in"0123456789":D[c]=t;D[t]=c;t+="I";N+=N
B=lambda s:[D[c]for c in reversed(s)]
Y=B(input())+N
for a in B(input())+N:
 for c in a:
    s=[];o=e
    for a,b in zip(N,Y):i=a+b+o;o=t<=i and"I"or e;s+=i.replace(t,e),;N=s
 Y=[e]+Y
print e.join(B(N)).lstrip("0")

Si 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 Is 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 diez Is si es necesario.

Aquí hay una versión sin golf:

N = [""] # zero object: list with a lot of empty strings
D = {}   # dictionary for conversion from and to digits
i = ""   # iterates over digits
for c in "0123456789":
    D[c] = i  # map digit to Roman digit
    D[i] = c  # and vice versa
    i += "I"  # increments Roman digit
    N += N    # add leading zeros to zero

ten = "IIIIIIIIII" # Roman digit ten

# Conversion function
B = lambda s: [D[c] for c in reversed(s)]

def Add(x,y):
    Sum = []
    carryover = ""
    for a,b in zip(x,y):
        increment = a+b+carryover
        carryover = "I" if ten in increment else ""
        increment = increment.replace(ten,"") # take increment modulo ten
        Sum += [increment]
    return Sum

def M(x,y):
    Sum = N[:] # Initiate Sum as zero
    X = B(x)+N # Convert and add leading zeros
    Y = B(y)+N
    for a in X:
        for c in a:
            Sum = Add(Sum,p+Y)
        Y = [""] + Y # multiply Y by 10
    return "".join(B(Sum)).lstrip("0") # Convert back and to string, remove leading zeros.

M(input(),input())
Wrzlprmft
fuente
1
¡Qué es esta hechicería! ¡Como funciona! Guau. Además, aquí hay otro golf que podría hacer: 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. Sin t in i and"1"or""embargo, creo que debería funcionar.
Justin
@Quincunx: Definir Scomo 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.
Wrzlprmft
Esto es bastante asombroso. Obtiene la marca verde por ahora. (He editado la pregunta para aclarar que los ceros iniciales en la salida no están permitidos, ¡lo siento!)
Nathaniel
7

Rubí: 752 698

Esto es solo para obtener una respuesta, solo por curiosidad. Editado: ahora jugaba un poco al golf.

$F='0123456789'
$G="#{$F}abcdefghij"
def x(a,b);p(a=~/[13579]$/?b:"",a==""?"":x(Hash[*%w(b0 5 b1 6 b2 7 b3 8 b4 9)].to_a.inject(a.tr($F,'0011223344').chars.zip(a.tr($F,'ababababab').chars).flatten.join("")){|n,q|k,v=q;n.gsub(k,v)}.gsub(/[ab]/,'').sub(/^0*/,''),p(b,b)));end
def p(a,b);j,k=["0#{a}","0#{b}"].map{|c|c.gsub(/./,'0')};c="#{k}#{a}".chars.zip("#{j}#{b}".chars).drop_while{|z|z==%w(0 0)}.map{|m|$G.sub(/#{m.map{|n|"122333444455555666666777777788888888999999999".chars.select{|c|c==n}}.flatten.map{|c|'.'}.join("")}/,"").chars.first}.flatten.join("");d=nil;
while c!=d
 d=c;c="0#{d}".gsub(/[0-9][a-j]/) {|m| m.tr($G,"123456789a#{$F}")}.sub(/^0/,'')
end;c;end
puts x(ARGV.shift,ARGV.shift)

Uso: Tenía esto en un archivo llamado peasant.rb:

$ time ruby peasant.rb 9999999999 9999999999
99999999980000000001

real    0m0.129s
user    0m0.096s
sys 0m0.027s

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.

bazzargh
fuente
1
Respuesta muy inteligente, ¡exactamente el tipo de cosas que esperaba ver!
Nathaniel
1
¡De hecho, espero que alguien publique uno con los números de la Iglesia!
bazzargh
Eso sería genial, aunque no estoy seguro de si funcionaría con el requisito de eficiencia: creo que la conversión entre cadenas y números de la Iglesia implicaría contar hasta 99999999980000000001.
Nathaniel
7

Brainfuck (1328 bytes)

Consideraciones al principio:

  • No estoy seguro de si Brainfuck es una respuesta válida a estas preguntas, ya que no estoy seguro de si considera los valores de las celdas como 'tipos numéricos' o no. No lo creo, ya que bf no conoce tipos, pero esa es mi opinión, corrígeme si me equivoco.
  • Es necesaria una implementación que soporte (casi) valores ilimitados.
  • Puede ser demasiado lento, según la implementación.

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:

,
>++++++[<----->-]<--
[                                           # read input until space
    >,
    >++++++[<----->-]<--                    # decrease cell by 32 to check if it's a space
]
>>>+<<<<                                    # set multiplier to 1

[

    >>++++[<<---->>-]<<                     # decrease by 16 to get cell value of number

    [>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]        # multiply value by multiplier
    >>>>>[<<<<<+>>>>>-]                     # copy value back
    <[>++++++++++<-]>[<<+>>-]               # multiply multiplier by 10
    <<<<<                                   # go back to number

    [->+<]>[-<+>]                           # add value to next cell and move sum to previous cell

    <<                                      # go to next number
]

>>>>[-]<                                    # delete old multiplier

,[>,]                                       # read second number until end of input
>>>+<<<<                                    # set new multiplier

[

    >>+++++++[<<------->>-]<<+              # decrease by 48 to get cell value of number

    [>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]        # multiply value by multiplier
    >>>>>[<<<<<+>>>>>-]                     # copy value back
    <[>++++++++++<-]>[<<+>>-]               # multiply multiplier by 10
    <<<<<                                   # go back to number

    [->+<]>[-<+>]                           # add value to next cell and move sum to previous cell

    <<                                      # go to next number
]

>>>>[-]<<<<<                                # delete multiplier

[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>          # multiply both values

# magical algorithm for printing cell value as number taken from Cedric Mamo's code from a previous question
[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]

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!

var NUM_CELLS = 30000;var ITERS_PER_SEC = 100000;var TIMEOUT_MILLISECS = 5000;function clear_output(){document.getElementById("output").value="";document.getElementById("stderr").innerHTML=""}function stop(){running=false;document.getElementById("run").disabled=false;document.getElementById("stop").disabled=true;document.getElementById("clear").disabled=false;document.getElementById("wrap").disabled=false;document.getElementById("timeout").disabled=false;document.getElementById("eof").disabled=false}function interrupt(){error(ERROR_INTERRUPT)}function error(e){document.getElementById("stderr").innerHTML=e;stop()}function run(){clear_output();document.getElementById("run").disabled=true;document.getElementById("stop").disabled=false;document.getElementById("clear").disabled=true;document.getElementById("wrap").disabled=true;document.getElementById("timeout").disabled=true;document.getElementById("eof").disabled=true;code=document.getElementById("code").value;input=document.getElementById("input").value;wrap=document.getElementById("wrap").value;timeout=document.getElementById("timeout").checked;eof=document.getElementById("eof").value;loop_stack=[];loop_map={};for(var e=0;e<code.length;++e){if(code[e]=="["){loop_stack.push(e)}else if(code[e]=="]"){if(loop_stack.length==0){error(ERROR_BRACKET);return}else{var t=loop_stack.pop();loop_map[t]=e;loop_map[e]=t}}}if(loop_stack.length>0){error(ERROR_BRACKET);return}running=true;start_time=Date.now();code_ptr=0;input_ptr=0;cell_ptr=Math.floor(NUM_CELLS/2);cells={};iterations=0;bf_iter(1)}function bf_iter(e){if(code_ptr>=code.length||!running){stop();return}var t=Date.now();for(var n=0;n<e;++n){if(cells[cell_ptr]==undefined){cells[cell_ptr]=0}switch(code[code_ptr]){case"+":if(wrap=="8"&&cells[cell_ptr]==255||wrap=="16"&&cells[cell_ptr]==65535||wrap=="32"&&cells[cell_ptr]==2147483647){cells[cell_ptr]=0}else{cells[cell_ptr]++}break;case"-":if(cells[cell_ptr]==0){if(wrap=="8"){cells[cell_ptr]=255}if(wrap=="16"){cells[cell_ptr]=65535}if(wrap=="32"){cells[cell_ptr]=2147483647}}else{cells[cell_ptr]--}break;case"<":cell_ptr--;break;case">":cell_ptr++;break;case".":document.getElementById("output").value+=String.fromCharCode(cells[cell_ptr]);break;case",":if(input_ptr>=input.length){if(eof!="nochange"){cells[cell_ptr]=parseInt(eof)}}else{cells[cell_ptr]=input.charCodeAt(input_ptr);input_ptr++}break;case"[":if(cells[cell_ptr]==0){code_ptr=loop_map[code_ptr]}break;case"]":if(cells[cell_ptr]!=0){code_ptr=loop_map[code_ptr]}break}code_ptr++;iterations++;if(timeout&&Date.now()-start_time>TIMEOUT_MILLISECS){error(ERROR_TIMEOUT);return}}setTimeout(function(){bf_iter(ITERS_PER_SEC*(Date.now()-t)/1e3)},0)}var ERROR_BRACKET="Mismatched brackets";var ERROR_TIMEOUT="Timeout";var ERROR_INTERRUPT="Interrupted by user";var code,input,wrap,timeout,eof,loop_stack,loop_map;var running,start_time,code_ptr,input_ptr,cell_ptr,cells,iterations
<div style="font-size:12px;font-family:Verdana, Geneva, sans-serif;"> <div style="float:left; width:50%;"> Code: <br> <textarea id="code" rows="4" style="overflow:scroll;overflow-x:hidden;width:90%;">,>++++++[<----->-]<--[>,>++++++[<----->-]<--]>>>+<<<<[>>++++[<<---->>-]<<[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<,[>,]>>>+<<<<[>>+++++++[<<------->>-]<<+[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<<<<<[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]</textarea> <br>Input: <br> <textarea id="input" rows="2" style="overflow:scroll;overflow-x:hidden;width:90%;">7 6</textarea> <p> Wrap: <select id="wrap"> <option value="8">8-bit</option> <option value="16">16-bit</option> <option value="32" selected="selected">32-bit</option> </select> &nbsp; Timeout: <input id="timeout" type="checkbox"></input>&nbsp; EOF: <select id="eof"> <option value="nochange">Same</option> <option value="0" selected="selected">0</option> <option value="-1">-1</option> </select> </p> </div> <div style="float:left; width:50%;"> Output: <br> <textarea id="output" rows="6" style="overflow:scroll;width:90%;"></textarea> <p> <input id="run" type="button" value="Run" onclick="run()"></input> <input id="stop" type="button" value="Stop" onclick="interrupt()" disabled="true"></input> <input id="clear" type="button" value="Clear" onclick="clear_output()"></input> &nbsp; <span id="stderr" style="color:red"></span></p></div></div>

Cifrar
fuente
¡No sé si es válido tampoco! Supongo que o todo es un número en Brainfuck, o nada lo es.
Nathaniel
Me gusta esta respuesta He estado jugando con mi novio últimamente. De alguna manera, arroja luz sobre el hecho de que, a nivel de máquina, todo es solo fichas de todos modos. Es difícil decir si esto realmente sigue las reglas o no.
Octopus
6

Python, 394 349 340 caracteres

D='0123456789'
R=reversed
U=lambda x:[R for y in D if y<x]
T=U(':')
def A(a,b,r='',c=[]):
 for x,y in map(None,R(a),R(b)):
    d=U(x)+U(y)+c;t=T;c=[R]
    if d<T:t=c=[]
    r=min(k for k in D if U(k)+t>=d)+r
 if c:r='1'+r
 return r
a,b=input()
m=''
while b:
 if list(b).pop()in'13579':m=A(m,a)
 b=list(A(b,A(b,A(b,A(b,b)))));b.pop();a=A(a,a)
print m

Corre como:

echo '"9999999999","9999999999"' | ./mulstr.py

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. Use convierte en unario, utilizando Rcomo dígito unario. Calculamos b/=2como b=b*5/10.

Keith Randall
fuente
Un par de campos de golf: def A(a,b):\n r='';c=[]-> def A(a,b,r='',c=[]):, de manera similar para def M. Es posible que pueda cambiar for 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 anterior if. Además, ¿puede if list(b).pop()in'13579'ser if b[:].pop()in'13579'?
Justin
@Quincunx: Gracias. El último no funcionará porque en la primera iteración bhay una cadena, no una lista.
Keith Randall
Puede omitir My escribir un programa completo; a,b=input() esta permitido.
Justin
1
b * 5/10 es un buen truco.
bazzargh
Me tropecé reduce, lo que le permite nicen A(b,A(b,A(b,A(b,b))))a reduce(A,[b,b,b,b,b]). Lamentablemente, esto no afecta el recuento de caracteres.
Wrzlprmft
5

JavaScript (E6) 375 395 411 449

Edit 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.

M=(x,y,S=a=>a.shift()||z,R=a=>[...a].reverse(),e=R('9876543210'),d=[...e])=>
  R(y)[T='map'](b=>
     R(x)[T](a=>(
       u=R[e[a+=b]+v],
       v=R[S[a]+(u<v?'1':z)],
       p[P](t=R[S(o)+u]),
       t<u?v=R[v+'1']:v
     ),o=p,p=[])
    +(v>z&&p[P](v),x+=v=z),
    d[T](a=>d[T](b=>e[P='push'](R[a+b]=S(e)))+e[P](S(e))),  
    d[T](a=>d[T](b=>e[d[T](c=>v=c<a?(u=R[u+b])<b?R[v+'1']:v:v,v=u=z='0'),S[a+b]=v,a+b]=u)),
    p=[v=z]
  )&&R(p).join(o)

Menos golf (tal vez agregaré una explicación mañana)

M=(x,y)=>(
  R=a=>[...a].reverse(),
  // Addition table s 
  s={},
  e=[...'9012345678'],
  [for(a of(d='0123456789'))for(b of(e.push(e.shift()),d))e.push(s[a+b]=c=e.shift())],
  // Multiplication table m,n
  m={},n={},
  [for(a of d)for(b of d)(
     [for(c of(z=u=v='0',d))
     c<a&&(t=s[u+b],t<u?v=s[v+'1']:v,u=t)
     ],m[a+b]=u,n[a+b]=v
  )],
  x=R(x),v=z,o=[],p=[],
  [for(b of R(y))(
     [for(a of x)(
       u=s[m[a+b]+v],v=s[n[a+b]+(u<v?'1':z)],
       p.push(t=s[(o.shift()||z)+u]),
       t<u?v=s[v+'1']:v
     )],
     v>z?p.push(v):o,o=p,p=[],x.unshift(v=z)
  )],
  R(o).join('')
)

Prueba en la consola FireFox / FireBug

t0=-new Date
r=M('9999999999','9999999999')
t1=-new Date
console.log("Result",r, "time ms", t0-t1)

Salida

Result 99999999980000000001 time ms 14
edc65
fuente
Posiblemente haya un pequeño error: la salida del 9999999999caso debería ser 99999999980000000001, no99999999980000000081
Nathaniel
:( va a comprobar
edc65
Si está usando tablas de multiplicar, ¿cómo está evitando el hecho de que la suma no está permitida?
COTO
1
Se permite la suma usando una tabla hash (s en el código). Ex. s ['34 '] ->' 7 '. Solo símbolos, no números. Podría ser s ['cd'] -> 'g'
edc65
5

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.

r=reverse
n="9876543210"
t=True
c&(x:y)|c==x=head y|t=c&y
m%[]="1";m%(c:s)|c==last m=head m:m%s|t=c&m:s
[]!y=y;x![]=x;(x:a)!('0':b)=x:a!b;x!y=(r n%x)!(n%y)
"0"?_="0";x?('0':y)|all(=='0')y="0"|t=('0':x)?y;x?y=x?(n%y)!x
x#y=r$r x?r y

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:

λ> :set +s
λ> let test = replicate 10 '9'
(0.00 secs, 0 bytes)
λ> test
"9999999999"
(0.00 secs, 1069784 bytes)
λ> test # test
"99999999980000000001"
(0.06 secs, 13451288 bytes)

Aquí hay una comprobación de que todos los productos de dos dígitos son correctos:

λ> and [ show (x * y) == (show x # show y) | x <- [0..100], y <- [0..100] ]
True
Matt Noonan
fuente
¡Parece que tenemos un nuevo líder! (Sin embargo, no puedo leer Haskell, ¿alguien puede confirmar de forma independiente que se ajusta a las especificaciones?)
Nathaniel
1
Sí, es un haskell perfectamente cromulent, se ajusta a las especificaciones y funciona como se anuncia. ¡Buen trabajo!
bazzargh
4

Bash + ImageMagick: 52

convert -size ${a}x${b} xc:red txt:-|grep -v g|wc -l

Espera que la entrada esté en las variables de shell ay b. No es particularmente inteligente o eficiente, pero hace el trabajo. Probablemente ya se haya hecho antes.

Tenga en cuenta que xdenota 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

Millinon
fuente
Buen intento, pero estoy seguro de que esto no funcionará en menos de un minuto (o de hecho en cualquier máquina existente) para las entradas 9999999999y 9999999999.
Nathaniel
44
Esto también funciona: dd if=/dev/zero bs=$a count=$b 2>&-|wc -c.
jimmy23013
1
Una 9999999999x9999999999imagen 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.
Nathaniel el
1
Puede guardar 2 bytes utilizando en $blugar de ${b}.
nyuszika7h
1
Además, puede guardar 5 bytes utilizando en grep -vc glugar de grep -v g|wc -l.
nyuszika7h
2

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 9999999999x9999999999en 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.

import re
D='123456789'
D=dict(zip('0'+D,D+'0'))

def toRlist(s):
    if s:t,h=re.match(r'(\d*)(\d)',s).groups();return[h,toRlist(t)]
    return''

def increment(r):
    if not r:return['1','']
    h,t=r
    return[D[h],increment(t)if h=='9'else t]

def toString(r):
    if not r:return''
    h,t=r
    return h+toString(t)

def listify(r,L):
    if not r:return
    h,t=r
    if h=='1':L.append('')
    if h=='2':L.extend(['',''])
    if h=='3':L.extend(['','',''])
    if h=='4':L.extend(['','','',''])
    if h=='5':L.extend(['','','','',''])
    if h=='6':L.extend(['','','','','',''])
    if h=='7':L.extend(['','','','','','',''])
    if h=='8':L.extend(['','','','','','','',''])
    if h=='9':L.extend(['','','','','','','','',''])
    listify(t,L);listify(t,L);listify(t,L);listify(t,L);listify(t,L)
    listify(t,L);listify(t,L);listify(t,L);listify(t,L);listify(t,L)

def add(r1,r2):
    L=[];listify(r2,L)
    for _ in L:r1=increment(r1)
    return r1

def multiply(a,b):
    total=''
    r=toRlist(a)
    L=[];listify(toRlist(b),L)
    for _ in L:total=r if total=='' else add(total,r)
    return''.join(reversed(toString(total)))

Ejemplos:

multiply('12','5') #returns the string 60

multiply('1869','1243') #returns the string 2323167
Pasatiempos de Calvin
fuente
1
+1 porque cumple con las especificaciones (aparte del requisito de eficiencia) por lo que puedo decir
Nathaniel
2

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 9999999999x9999999999caso en menos de 0.03s en mi máquina.

d="123456789";I=dict(zip('0'+d,d+'0'))
def r(x):return reversed(x)
def s(x):return''.join(x)
def i(x):
    try:
        h=I[x.next()]
        if h!='0':h+=s(x)
        else:h+=i(x)
        return h
    except:return'1'
def b(x,y):
    for c in'0'+d:
        if c==y:break
        x=iter(i(x))
    return x
def a(x,y):
    z=''
    for c in y:
        x=b(x,c)
        try:z+=x.next()
        except:z+='0'
    return z+s(x)
def n(x,y):
    z='0'
    for c in'0'+d:
        if c==y:break
        z=a(iter(z),x)
    return z
def o(x,y):
    x=s(x)
    l='';z=''
    for c in y:
        z=a(iter(z),l+s(n(x,c)))
        l+='0'
    return z
def m(x,y):
    return s(r(o(r(x),r(y))))

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:

  • ry sson funciones de contabilidad. ( res solo un alias para reversed, que hace un iterador inverso y sconvierte los iteradores en cadenas).

  • iincrementa el número en una cadena en 1, incluidos casos como 39+1=40y 99+1=100.

  • bagrega xy y, pero ydebe ser solo un dígito. Funciona incrementando los x ytiempos.

  • aagrega dos números juntos que pueden tener varios dígitos, llamando ba cada dígito en y.

  • nmultiplica xy y, pero ydebe tener solo un dígito. Funciona agregando xa sí mismo ytiempos.

  • omultiplica xy y, donde ambos argumentos pueden tener múltiples dígitos. Utiliza la multiplicación larga clásica

  • msimplemente convierte sus entradas de cadena en iteradores inversos y las entrega o, luego invierte el resultado y lo convierte en una cadena.

Nathaniel
fuente
Golf par: def a(x,y):-> def a(x,y,z=''):y eliminar la siguiente línea; trucos similares para otras funciones, en def o(x,y):, cambiar el x=s(x)a x=s(x);l='';z='', en ese bucle for, eliminar de manera similar newline + ritmos; en lugar de usar ;. Además, creo que if h!='0':h+=s(x)\nelse:h+=i(x)simplemente puede ser h+=h!='0'and i(x)or s(x); tal vez incluso h+=(h!='0'and i or s)(x); de lo contrario, simplemente cambie a if'0'!=h. También cosas como def r(x):return reversed(x)->r=reversed
Justin
Además, se me olvidó mencionar a 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.
Justin
Ah, y uno más: para tus forbucles: 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.
Justin
@Quincunx gracias! También puedo ver algunas otras mejoras esta mañana. (Principalmente anidando los bucles en lugar de definir funciones). Haré estos cambios si aparecen algunas respuestas más competitivas, lo que parece probable, actualmente me pondrían a la cabeza, lo que parece un poco injusto ya que era mi pregunta y yo ' he tenido más tiempo para pensarlo.
Nathaniel
2

JavaScript: 3710 3604 bytes

  • Usar tablas de búsqueda de cadenas con multiplicación de 1 dígito y sumar con acarreo.
  • La multiplicación se realiza por dígito x dígito en lugar de dígito x línea.

Golf:

var M={
'00':'0','01':'0','02':'0','03':'0','04':'0','05':'0','06':'0','07':'0','08':'0','09':'0',
'10':'0','11':'1','12':'2','13':'3','14':'4','15':'5','16':'6','17':'7','18':'8','19':'9',
'20':'0','21':'2','22':'4','23':'6','24':'8','25':'10','26':'12','27':'14','28':'16','29':'18',
'30':'0','31':'3','32':'6','33':'9','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
'40':'0','41':'4','42':'8','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
'50':'0','51':'5','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
'60':'0','61':'6','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
'70':'0','71':'7','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
'80':'0','81':'8','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
'90':'0','91':'9','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81'
};
var A={
'000':'0','001':'1','002':'2','003':'3','004':'4','005':'5','006':'6','007':'7','008':'8','009':'9',
'010':'1','011':'2','012':'3','013':'4','014':'5','015':'6','016':'7','017':'8','018':'9','019':'10',
'020':'2','021':'3','022':'4','023':'5','024':'6','025':'7','026':'8','027':'9','028':'10','029':'11',
'030':'3','031':'4','032':'5','033':'6','034':'7','035':'8','036':'9','037':'10','038':'11','039':'12',
'040':'4','041':'5','042':'6','043':'7','044':'8','045':'9','046':'10','047':'11','048':'12','049':'13',
'050':'5','051':'6','052':'7','053':'8','054':'9','055':'10','056':'11','057':'12','058':'13','059':'14',
'060':'6','061':'7','062':'8','063':'9','064':'10','065':'11','066':'12','067':'13','068':'14','069':'15',
'070':'7','071':'8','072':'9','073':'10','074':'11','075':'12','076':'13','077':'14','078':'15','079':'16',
'080':'8','081':'9','082':'10','083':'11','084':'12','085':'13','086':'14','087':'15','088':'16','089':'17',
'090':'9','091':'10','092':'11','093':'12','094':'13','095':'14','096':'15','097':'16','098':'17','099':'18',
'100':'1','101':'2','102':'3','103':'4','104':'5','105':'6','106':'7','107':'8','108':'9','109':'10',
'110':'2','111':'3','112':'4','113':'5','114':'6','115':'7','116':'8','117':'9','118':'10','119':'11',
'120':'3','121':'4','122':'5','123':'6','124':'7','125':'8','126':'9','127':'10','128':'11','129':'12',
'130':'4','131':'5','132':'6','133':'7','134':'8','135':'9','136':'10','137':'11','138':'12','139':'13',
'140':'5','141':'6','142':'7','143':'8','144':'9','145':'10','146':'11','147':'12','148':'13','149':'14',
'150':'6','151':'7','152':'8','153':'9','154':'10','155':'11','156':'12','157':'13','158':'14','159':'15',
'160':'7','161':'8','162':'9','163':'10','164':'11','165':'12','166':'13','167':'14','168':'15','169':'16',
'170':'8','171':'9','172':'10','173':'11','174':'12','175':'13','176':'14','177':'15','178':'16','179':'17',
'180':'9','181':'10','182':'11','183':'12','184':'13','185':'14','186':'15','187':'16','188':'17','189':'18',
'190':'10','191':'11','192':'12','193':'13','194':'14','195':'15','196':'16','197':'17','198':'18','199':'19'
} 
Array.prototype.e=function(){return(''+this)==='';}
String.prototype.s=function(){return this.split('').reverse();}
function B(a,b,c) {
var r='',s='';
a=a.s();
b=b.s();
while (!a.e()||!b.e()||c!=='0') {
x=a.e()?'0':a.shift();
y=b.e()?'0':b.shift();
s=A[c+x+y];
s=s.s();
r=s.shift()+r;
c=s.e()?'0':'1';
}
return r;
}
function m(a,b) {
var s='0',m='';
b.split('').reverse().forEach(function(e){
var z=m;
a.split('').reverse().forEach(function(f){s=B(s,M[e+f]+z,'0');z+='0';});
m+='0';
});
return s;
}

Sin golfista con las pruebas:

var mul = {
'00':'0','01':'0','02':'0','03':'0','04':'0','05':'0','06':'0','07':'0','08':'0','09':'0',
'10':'0','11':'1','12':'2','13':'3','14':'4','15':'5','16':'6','17':'7','18':'8','19':'9',
'20':'0','21':'2','22':'4','23':'6','24':'8','25':'10','26':'12','27':'14','28':'16','29':'18',
'30':'0','31':'3','32':'6','33':'9','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
'40':'0','41':'4','42':'8','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
'50':'0','51':'5','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
'60':'0','61':'6','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
'70':'0','71':'7','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
'80':'0','81':'8','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
'90':'0','91':'9','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81'
};

var adc = {
'000':'0','001':'1','002':'2','003':'3','004':'4','005':'5','006':'6','007':'7','008':'8','009':'9',
'010':'1','011':'2','012':'3','013':'4','014':'5','015':'6','016':'7','017':'8','018':'9','019':'10',
'020':'2','021':'3','022':'4','023':'5','024':'6','025':'7','026':'8','027':'9','028':'10','029':'11',
'030':'3','031':'4','032':'5','033':'6','034':'7','035':'8','036':'9','037':'10','038':'11','039':'12',
'040':'4','041':'5','042':'6','043':'7','044':'8','045':'9','046':'10','047':'11','048':'12','049':'13',
'050':'5','051':'6','052':'7','053':'8','054':'9','055':'10','056':'11','057':'12','058':'13','059':'14',
'060':'6','061':'7','062':'8','063':'9','064':'10','065':'11','066':'12','067':'13','068':'14','069':'15',
'070':'7','071':'8','072':'9','073':'10','074':'11','075':'12','076':'13','077':'14','078':'15','079':'16',
'080':'8','081':'9','082':'10','083':'11','084':'12','085':'13','086':'14','087':'15','088':'16','089':'17',
'090':'9','091':'10','092':'11','093':'12','094':'13','095':'14','096':'15','097':'16','098':'17','099':'18',
'100':'1','101':'2','102':'3','103':'4','104':'5','105':'6','106':'7','107':'8','108':'9','109':'10',
'110':'2','111':'3','112':'4','113':'5','114':'6','115':'7','116':'8','117':'9','118':'10','119':'11',
'120':'3','121':'4','122':'5','123':'6','124':'7','125':'8','126':'9','127':'10','128':'11','129':'12',
'130':'4','131':'5','132':'6','133':'7','134':'8','135':'9','136':'10','137':'11','138':'12','139':'13',
'140':'5','141':'6','142':'7','143':'8','144':'9','145':'10','146':'11','147':'12','148':'13','149':'14',
'150':'6','151':'7','152':'8','153':'9','154':'10','155':'11','156':'12','157':'13','158':'14','159':'15',
'160':'7','161':'8','162':'9','163':'10','164':'11','165':'12','166':'13','167':'14','168':'15','169':'16',
'170':'8','171':'9','172':'10','173':'11','174':'12','175':'13','176':'14','177':'15','178':'16','179':'17',
'180':'9','181':'10','182':'11','183':'12','184':'13','185':'14','186':'15','187':'16','188':'17','189':'18',
'190':'10','191':'11','192':'12','193':'13','194':'14','195':'15','196':'16','197':'17','198':'18','199':'19'
} 

Array.prototype.isEmpty = function() {
  return (''+this) === '';
}

function add(a, b, c) {
  var r = '', s = '';
  a = a.split("").reverse();
  b = b.split("").reverse();
  while (!a.isEmpty() || !b.isEmpty() || c !== '0') {
    x = a.isEmpty() ? '0' : a.shift();
    y = b.isEmpty() ? '0' : b.shift();
    s = adc[c + x + y];
    s = s.split("").reverse();
    r = (s.shift()) + r;
    c = (s.isEmpty()) ? '0' : '1';
  }
  return r;
}

function mult(a, b) {
  var s = '0';
  var m = '';
  b.split('').reverse().forEach(function(e) {
    var z = m;
    a.split('').reverse().forEach(function(f) {
      s = add(s, mul[e + f] + z, '0');
      z = z + '0';
    });
    m = m + '0';
  } );
  return s;
}

function test(a, b) {
  var t0 = (new Date()).getTime();
  var r = mult(a,b);
  var t1 = (new Date()).getTime();
  var e = t1 - t0;
  console.log('mult ' + a + ' * ' + b + ' = ' + r + " (" + e + " ms)");
}

test('12345', '42');
test('9999999999', '9999999999');

Esto produce:

mult 12345 * 42 = 518490 (3 ms) 
mult 9999999999 * 9999999999 = 99999999980000000001 (47 ms) 
Stephen Quan
fuente
2

Haskell 507 496

Esto 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.

data S=Z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R deriving(Enum, Ord, Eq)
p Z=id
p x=succ.p(pred x)
s Z=id
s x=pred.s(pred x)
z=s J
r[]=[]
r(x:y)|x<J=x:r y
r(x:[])=z x:[A]
r(x:y)=z x:(r$p A a:b)where(a:b)=r y
a x y=r$w(r x)(r y)
m Z _=[]
m _[]=[]
m x y=r$a y(m(pred x)y)
t[]_=[Z]
t _[]=[Z]
t(x:z)y=r$a(m x y)(Z:r(t z y))
i '0'=Z
i x=succ.i.pred$x
b Z='0'
b x=succ.b.pred$x
w[]y=y
w x[]=x
w(x:c)(y:d)=p x y:(w c d)
o=map
v=reverse
f=(o i).v
g=v.o b
main=getLine>>=putStrLn.(\[x,y]->g$t(f x)(f y)).words

Como referencia, S es el tipo de datos tipo entero personalizado, pes 'más' (suma dígito + dígito), sse resta (para reducción), rse reduce (se expande en descomposición digital), aes suma (suma número + número), mes multiplicar (multiplicación de dígitos * números), tes veces (multiplicación de números * números), ies 'interpretar' (convertir cadena a lista de S),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.

> time echo "9999999999 9999999999" | runhaskell multnonum.hs
99999999980000000001

real    0m0.246s
user    0m0.228s
sys     0m0.012s

Solo por si acaso:

> time echo "99999999980000000001 99999999980000000001" | runhaskell multnonum.hs
9999999996000000000599999999960000000001

real    0m0.244s
user    0m0.224s
sys     0m0.016s

¡Vamos a volvernos locos!

> time echo "9999999996000000000599999999960000000001 9999999996000000000599999999960000000001" | runhaskell multnonum.hs
99999999920000000027999999994400000000699999999944000000002799999999920000000001

real    0m0.433s
user    0m0.424s
sys     0m0.004s

confirmación

Archaephyrryx
fuente
1

Python 2 - 1165, 712, 668 664

I,T,V,N,X,J=raw_input,dict,reversed,None,zip,''.join
D='0123456789'
z,o='01'
A,B=I(),I()
r=i=""
K=map(J,X('666622222222911111551111555884444447773333333','678945672389954132987698765898967457989837654'))
P=T(X(K,map(J,X('344501110011800000440000332673322124652202211','628480244668154132507698505422648609367491852'))))
S=T(X(K,'cdef678945abi65243ed87a9cbaghcdab89egfcb6a987'))
for d in D:P[z+d]=z;S[z+d]=d
def Z(A,B,R=r):
 for a,b in V(map(N,V(z+A),V(z+B))):c=(a or z)+(b or z);s=S[min(c)+max(c)];R=Z(R,o)+T(X('abcdefghi',D))[s]if s>"?"else R+s
 return R
for a in V(A):
 j=""
 for b in V(B):r=Z(r,P[min(a+b)+max(a+b)]+i+j).lstrip(z);j+=z
 i+=z
print r if r else z

Tenga 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:

A = raw_input()
B = raw_input()

P = {'00':'00','01':'00','02':'00','03':'00','04':'00','05':'00','06':'00','07':'00','08':'00','09':'00',
     '10':'00','11':'01','12':'02','13':'03','14':'04','15':'05','16':'06','17':'07','18':'08','19':'09',
     '20':'00','21':'02','22':'04','23':'06','24':'08','25':'10','26':'12','27':'14','28':'16','29':'18',
     '30':'00','31':'03','32':'06','33':'09','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
     '40':'00','41':'04','42':'08','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
     '50':'00','51':'05','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
     '60':'00','61':'06','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
     '70':'00','71':'07','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
     '80':'00','81':'08','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
     '90':'00','91':'09','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81',
     }
S = {'00':'0','01':'1','02':'2','03':'3','04':'4','05':'5','06':'6','07':'7','08':'8','09':'9',
     '10':'1','11':'2','12':'3','13':'4','14':'5','15':'6','16':'7','17':'8','18':'9','19':'a',
     '20':'2','21':'3','22':'4','23':'5','24':'6','25':'7','26':'8','27':'9','28':'a','29':'b',
     '30':'3','31':'4','32':'5','33':'6','34':'7','35':'8','36':'9','37':'a','38':'b','39':'c',
     '40':'4','41':'5','42':'6','43':'7','44':'8','45':'9','46':'a','47':'b','48':'c','49':'d',
     '50':'5','51':'6','52':'7','53':'8','54':'9','55':'a','56':'b','57':'c','58':'d','59':'e',
     '60':'6','61':'7','62':'8','63':'9','64':'a','65':'b','66':'c','67':'d','68':'e','69':'f',
     '70':'7','71':'8','72':'9','73':'a','74':'b','75':'c','76':'d','77':'e','78':'f','79':'g',
     '80':'8','81':'9','82':'a','83':'b','84':'c','85':'d','86':'e','87':'f','88':'g','89':'h',
     '90':'9','91':'a','92':'b','93':'c','94':'d','95':'e','96':'f','97':'g','98':'h','99':'i',
     }
L = {'a':'0','b':'1','c':'2','d':'3','e':'4','f':'5','g':'6','h':'7','i':'8'}

def strSum(A, B):
    R = ""
    for a, b in reversed(map(None, reversed("0" + A), reversed("0" + B))):
        if a == None: a = '0'
        if b == None: b = '0'
        s = S[a + b]
        if s.isdigit():
            R += s
        else:
            R = strSum(R, "1") + L[s]
    return R

i = ""
r = "0"
for a in reversed(A):
    j = ""
    for b in reversed(B):
        p = P[a + b] + i + j
        r = strSum(r, p)
        j += "0"
    i += "0"

r = r.lstrip("0")
if r == "":
    r = "0"

print r
Falko
fuente
Diría que no debería permitirse el uso de las funciones min () y max () porque están comparando valores enteros reales, ¿no es así?
WorldSEnder
@WorldSEnder: Diría que comparan personajes, lo cual está permitido en este desafío. ("Se permite la comparación lexicográfica de caracteres")
Falko
1

Scala, 470 caracteres

( son scala estándar pero se pueden reemplazar de manera equivalente =>si contamos bytes)

def p(a: String,b: String)={type D=List[Char]
val d="0123456789".toList
def v(s: String)=s.toList.map{c⇒d.takeWhile(c.!=)}
def u(l:D, a:D):(Char,D)=l match {
case _::_::_::_::_::_::_::_::_::_::m⇒u(m,'a'::a)
case _⇒(('a'::l).zip(d).last._2,a)}
val o=(("", List[Char]())/:v(a).tails.toList.init.map{l⇒(v(b) map {_.flatMap(_⇒l.head)})++l.tail.map(_⇒Nil) reverse}.reduce(_.zipAll(_, Nil, Nil).map{t⇒t._1++t._2}))({(t,e)⇒val s=u(t._2++e,Nil);(s._1+t._1,s._2)})
u(o._2, Nil)._1+o._1}

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 flatMapy nuestras filas con reduce. umaneja 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.

lmm
fuente