Multiplicación etíope

17

Esta pregunta está inspirada en esta respuesta . Casualmente, solía usar la multiplicación etíope cuando era niño, pero nunca había conocido el nombre del método hasta hace poco.

La multiplicación etíope es un método para multiplicar enteros utilizando solo la suma, la duplicación y la reducción a la mitad.

Método:

  1. Tome dos números para multiplicarlos y escríbalos en la parte superior de dos columnas.
  2. En la columna de la izquierda, reduzca a la mitad el último número repetidamente, descartando cualquier resto, y escriba el resultado debajo del último en la misma columna, hasta que escriba un valor de 1.
  3. En la columna de la derecha, doble el último número repetidamente y escriba el resultado a continuación. se detiene cuando agrega un resultado en la misma fila donde la columna de la izquierda muestra 1.
  4. Examine la tabla producida y descarte cualquier fila donde el valor en la columna izquierda sea par. Suma los valores en la columna de la derecha que quedan para producir el resultado de multiplicar los dos números originales juntos.

Por ejemplo: 17 x 34

17    34

Reducir a la mitad la primera columna:

17    34
 8
 4
 2
 1

Doblando la segunda columna:

17    34
 8    68
 4   136 
 2   272
 1   544

Filas tachadas cuya primera celda es par, haremos esto encerrando esos números a la derecha entre corchetes:

17    34
 8   [68]
 4  [136]
 2  [272]
 1   544

Suma los números restantes en la columna de la derecha:

17    34
 8   [68]
 4  [136]
 2  [272]
 1   544
    =====
     578

Entonces 17 multiplicado por 34, por el método etíope es 578.

La tarea:

Código de golf que toma dos números entre 1 y 1000 y realiza el mismo diseño y algoritmo, mostrando el producto a continuación.

Método de entrada: como quiera que elija ...

Entrada de ejemplo:

19 427

Resultado resultante:

19   427
 9   854
 4 [1708]
 2 [3416]
 1  6832
   ======
    8113

Tenga en cuenta la alineación de los dígitos. Esto es lo más importante en el diseño. También tenga en cuenta que la línea doble establecida por signos iguales debe ser dos caracteres más larga que la respuesta general y debe estar justificada al centro.

Pruebas

¿Cómo vas a probar esto? Al proporcionar una ejecución de su programa utilizando dos números. Estos números se pueden extraer de su número de identificación de usuario (esto se puede obtener colocando el cursor sobre su avatar en la ventana superior). Tome su número y tome los últimos tres dígitos, este será el número B, tome lo que quede en el frente, ese será el número A. Luego, pruebe A por B.

Ejemplo de prueba:

Mi número de identificación de usuario es 8555, por lo que mis números son 8 y 555. Por lo tanto, mi salida debería verse así:

8  [555]
4 [1110]
2 [2220]
1  4440
  ======
   4440

Restricciones:

Ningún operador de multiplicación nativo permitió guardar en el uso de "duplicación", como se menciona en el algoritmo. En otras palabras, si está utilizando un operador como *, solo se puede usar para multiplicar por 2 solamente.

Las entradas que no cumplan con esto no serán consideradas y el usuario será acompañado fuera de las instalaciones con una caja de cartón llena de sus pertenencias. Cada entrada tendrá un código, más la prueba basada en su número de identificación de usuario.

Este es el código de golf. El menor número de bytes recibirá el premio, la gloria y la admiración de sus compañeros ... (Y tal vez un Lamborghini ... ¡Dije "tal vez"!)

WallyWest
fuente
55
"No debe tener lugar una multiplicación real". - Esto no es observable. Puede restringir el uso de algunos caracteres (como *o x), pero es imposible detectar si se usa la multiplicación o no. Excepto esa parte, el desafío es interesante.
Tal vez debería pedir una descripción completa del código que demuestre que el algoritmo se implementa sin multiplicación O una simulación sin restricciones que proporcione el resultado deseado. Pero eso me parece dos desafíos distintos.
Arnauld
1
Como se señaló en el sandbox, relacionado, posible engaño . @FelixPalmen, sí, esta es una multiplicación larga en binario.
Peter Taylor

Respuestas:

8

Carbón , 91 bytes

≔⟦⟧τ≔⁰σNθNηWθ«⊞τ⪫  Iθ⊞υ⪫⎇﹪θ²  ¦[]Iη≔⁺σ∧﹪θ²ησ≔÷θ²θ≔⁺ηηη»⊞υ…=⁺²LIσ⊞υ⪫  Iσ←E⮌τ⮌ιM⌈EυLιLυ←E⮌υ⮌ι

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

≔⟦⟧τ≔⁰σ

Se establece ten la lista vacía y sen 0. (u ya está predeterminado en la lista vacía).

NθNη

Ingresa los dos números.

Wθ«

Se repite mientras q no es cero.

   ⊞τ⪫  Iθ

Envuelva el qrelleno y añádalo a la listat .

   ⊞υ⪫⎇﹪θ²  ¦[]Iη

Envuelva hen relleno o []dependiendo de si qes impar, y añádalo a la listau .

   ≔⁺σ∧﹪θ²ησ

Agregar ha ssi qes extraño.

   ≔÷θ²θ

Entero dividido qpor 2.

   ≔⁺ηηη»

Añadir ha sí mismo.

⊞υ…=⁺²LIσ

Agregue una cadena adecuada de =signos a la lista u.

⊞υ⪫  Iσ

Agregue la suma rellenada sa la lista u.

←E⮌τ⮌ι

Gire la lista t180 ° e imprímala al revés, justificándola a la derecha.

M⌈EυLιLυ←E⮌υ⮌ι

Mueva el cursor de modo que cuando uesté justificado a la derecha, su esquina superior izquierda se alinee con la esquina superior derecha que acabamos de alcanzar e imprima ujustificado a la derecha.

Neil
fuente
Increíble trabajo. Tienes el liderazgo hasta ahora, @Neil. ¿Dónde puedo encontrar más información sobre el idioma? ¿Hay un enlace?
WallyWest
1
@WallyWest El título está vinculado a la página de GitHub y desde allí puede leer el wiki para obtener más información.
Neil
8

Python 2 , 203 202 187 133 bytes

a,b=input()
s=0
while a:print'%3s%9s'%(a,'[ %%dd] '[a%2::2]%b);s+=[0,b][a%2];a/=2;b*=2
print'%10s==\n%11s'%(''.rjust(len(`s`),'='),s)

Pruébalo en línea!

Si puedo usar *para la multiplicación de cadenas ( '='*R) y como 'selector' (b*(a%2) lugar de [0,b][a%2]), obtengo:

118 bytes

a,b=input()
s=0
while a:print'%3s%9s'%(a,'[ %%dd] '[a%2::2]%b);s+=a%2*b;a/=2;b*=2
print'%10s==\n%11s'%('='*len(`s`),s)

Pruébalo en línea!


Explicación:

a,b=input()                   #Get input
L=len(`a`)                    #Get length of first number for adjusting text
l=[]                          #Output list
s=0                           #Sum
while a:
 B=['[%d]',' %d '][a%2]%b     #B is either '[b]' or ' b ' depending on if a is odd/even
 l+=[(`a`,B)]                 #Add a,B to output list
 s+=[0,b][a%2]                #Add b to sum if a is odd
 a/=2;                        #Halve a
 b*=2;                        #Double b
R=len(B)                      #Length of last B for adjusting output
l+=[('',''.rjust(R,'='))]     #Add double line ==== to output list
l+=[('','%d '%s)]             #Add sum to output list
for x,y in l:
 print x.rjust(L),y.rjust(R)  #Print adjusted numbers
TFeld
fuente
189 bytes
Sr. Xcoder
4

Java (OpenJDK 8) , 353 316 267 214 210 bytes

(a,b)->{int g=0;for(;a>0;g+=a%2*b,a/=2,b*=2)System.out.printf("%1$8d%2$10s\n",a,a%2<1?"["+b+"]":b+" ");System.out.printf("%1$19s%2$18s","".valueOf(new char[(int)Math.log10(g)+3]).replace("\0","=")+"\n",g+" ");}

Pruébalo en línea!

Roberto Graham
fuente
1
214 bytes:(a,b)->{int g=0;for(;a>0;g+=a%2*b,a/=2,b*=2)System.out.printf("%1$8d%2$10s\n",a,a%2<1?"["+b+"]":" "+b+" ");System.out.printf("%1$19s%2$18s","".valueOf(new char[(int)Math.log10(g)+3]).replace("\0","=")+"\n",g+" ");}
Nevay
@Nevay a%2*bagradable y simple, gracias
Roberto Graham
4

Mathematica, 264 bytes

(s=#;k=(i=IntegerLength)@s;t=#2;w=0;P=Print;T=Table;While[s>0,If[OddQ@s,P[""<>T[" ",k-i@s],s,"  ",""<>T[" ",i[s(t)]-i@t],t];w=w+t,P[""<>T[" ",k-i@s],s,""<>T[" ",i[s(t)]-i@t]," [",t,"]"]];s=Quotient[s,2];t=2t];P[" "<>T[" ",k],""<>T["=",i@w+2]];P["  "<>T[" ",k],w])&


entrada

[19,427]

salida

19   427  
 9   854  
 4 [1708]  
 2 [3416]  
 1  6832  
   ======  
    8113  
J42161217
fuente
Probablemente se podría guardar la friolera de un byte mediante el uso de la notación infija en s=Quotient[s,2]:)
numbermaniac
3

Perl 5 , 157 bytes

155 bytes de código + 2 banderas de línea de comando ( -nl)

$\=<>;$w=y///c;$y=2+length$\<<((log)/log 2);while($_){$s+=$\if$_%2;printf"%${w}s %${y}s\n",$_,$_%2?$\.$":"[$\]";$_>>=1;$\<<=1}say$"x++$w,'='x$y;say$"x++$w,$s

Pruébalo en línea!

Xcali
fuente
3

JavaScript 2017, 221 bytes

Principalmente un problema de formato de salida

(a,b)=>{for(t=b,r=0,l=[],w=`${a}`.length;a;l.push([a,t]),a>>=1,t+=t)z=`${r+=a&1&&t}`.length+2;P=(s,w)=>`${s}`.padStart(w);return[...l.map(([a,b])=>P(a,w)+P(a&1?b+' ':`[${b}]`,z+1)),P('='.repeat(z),z-~w),P(r,z+w)].join`
`}

Menos golf

(a, b) => {
  var w=`${a}`.length, r=0, l=[]
  while(a) {
    r += a&1 && b
    l.push([a,b])
    a >>= 1
    b += b
  }
  // algo complete, result in r, now display it and the steps in l[]
  var z=`${r}`.length+2
  var P= (s,w) => `${s}`.padStart(w)
  return [... l.map( ([a,b]) => P(a,w) + P(a&1?b+' ' : `[${b}]`, z+1) )
    , P('='.repeat(z), z+w+1)
    , P(r, z+w)
  ].join`\n`
}

Prueba

var F=
(a,b)=>{for(t=b,r=0,l=[],w=`${a}`.length;a;l.push([a,t]),a>>=1,t+=t)z=`${r+=a&1&&t}`.length+2;P=(s,w)=>`${s}`.padStart(w);return[...l.map(([a,b])=>P(a,w)+P(a&1?b+' ':`[${b}]`,z+1)),P('='.repeat(z),z-~w),P(r,z+w)].join`
`}

function update(){
  var i=I.value, [a,b]=i.match(/\d+/g)
  O.textContent=F(+a,+b)
}

update()
<input id=I value='21x348' oninput='update()'><pre id=O></pre>

edc65
fuente
simplemente revisando esta pregunta ... ¿qué hace padStart exactamente? No reconozco este método ...
WallyWest
Sería un asco ejecutar esto en IE! ;)
WallyWest
3

C, C ++, 319 313 301 299 bytes

-8 bytes gracias a Zacharý

Gracias a la printfmagia que aprendí en 60 minutos entre las ediciones.

#include<string.h>
#include<stdio.h>
#define O printf("%*d %c%*d%c\n",5,a,a%2?32:91,9,b,a%2?32:93);
void m(int a,int b){int r=0,i=0;O while(a>1){r+=a%2*b;a/=2;b*=2;O}r+=b;char t[20],p[20];memset(t,0,20);memset(p,0,20);sprintf(t,"%d",r);memset(p,61,strlen(t)+2);printf("%*c%*s\n%*d",5,32,12,p,16,r);}

Optimización de C ++, reemplazar encabezado stdio.hpor cstdioy string.hporcstring , ahorra 2 bytes

La compilación con MSVC requiere agregar #pragma warning(disable:4996)para poder usarsprintf

Prueba con mi ID de PPCG:

72 x 535 =>

   72 [      535]
   36 [     1070]
   18 [     2140]
    9       4280
    4 [     8560]
    2 [    17120]
    1      34240
          =======
           38520

Respeta las reglas, los dígitos están alineados y los signos iguales siempre serán 2 caracteres más grandes que el número final. Ejemplo con 17 x 34 =>

   17         34
    8 [       68]
    4 [      136]
    2 [      272]
    1        544
            =====
             578
HatsuPointerKun
fuente
Creo que puedes cambiar las dos últimas líneas a #define O printf("%*d %c%*d%c\n",5,a,a%2?' ':'[',9,b,a%2?' ':']');yvoid m(int a,int b){int r=0,i=0;O while(a>1){r+=a%2*b;a/=2;b*=2;O}r+=b;char t[20],p[20];memset(t,0,20);memset(p,0,20);sprintf(t,"%d",r);for(;i<strlen(t)+2;++i)p[i]='=';printf("%*c%*s\n%*d",5,' ',12,p,16,r);}
Zacharý
Sí, lo sé, pero ¿por qué importa eso? Anuncio también, la precedencia de %y *son los mismos, por lo que r+=a%2*bdebería funcionar.
Zacharý
@ Zacharý, de hecho, estaba equivocado, tienes razón
HatsuPointerKun
¿Necesitas incluso incluir <cstdio>, no puedes usar el mismo truco que hiciste aquí ?
Zacharý
240 bytes
ceilingcat el
3

[Bash], 144 142 140 131 128 bytes

Mejor respeto de la visualización, tenga en cuenta que hay un carácter de espacio final

read a b;for((;a;));{ ((a%2))&&((r+=b))&&x=$b\ ||x=[$b];printf %3s%9s\\n $a "$x"
((a/=2,b+=b));};printf %12s\\n =${r//?/=}= $r\ 

Primera respuesta

read a b;while((a));do ((a%2))&&((r+=b))&&printf "%6s  %6s
" $a $b||printf "%6s [%6s]
" $a $b;((a/=2,b+=b));done;printf "%6s %7s
" \  ==== \  $r
Nahuel Fouilleul
fuente
2

Haskell , 305 bytes

i=iterate
s=show
l=length.s
a!b=zip((takeWhile(>0).i(`div`2))a)(i(*2)b)
a?b=sum[y|(x,y)<-a!b,rem x 2>0]
a%b=l(snd.last$a!b)
a#b=unlines$[(' '<$[1..l a-l x])++s x++(' '<$[-1..a%b-l y])++if mod x 2<1then show[y]else(' ':s y)|(x,y)<-a!b]++map((++)(' '<$[-1..l a+a%b-l(a?b)]))['='<$[1..l a+1+a%b],' ':(s$a?b)]

Pruébalo en línea!

El !operador crea las dos listas, ?calcula el producto. %y #se usan para el diseño ascii.

jferard
fuente
1

C, 205 201 190 183 156 150 143 bytes

Esto compilará con advertencias como C89, y no creo que sea C99 válido, pero termina siendo más pequeño que la versión de HatsuPointerKun, ya que ahorra bytes al omitir #include's, no usar longitudes dinámicas para imprimir, ya que no son necesarios, & usando log10()para calcular el número de ='s necesarios:

r;m(a,b){r=0;while(a){printf(a%2?"%4d%10d\n":"%4d [%8d]\n",a,b);r+=a%2?b:0;a/=2;b<<=1;}printf("%15.*s\n%14d",(int)log10(r)+3,"==========",r);}

Como mi número es 64586, utilicé este programa de prueba para calcular 64 * 586:

#include <stdio.h>
int m(int a, int b);
int main(void)
{
    m(64, 586);
    putchar('\n');
}

y sale:

  64 [     586]
  32 [    1172]
  16 [    2344]
   8 [    4688]
   4 [    9376]
   2 [   18752]
   1     37504
        =======
         37504

editar

guardado 4 bytes por la regla "int implícito"

editar 2

ahorró 11 bytes cambiando a un do...while()bucle y moviendo el printf al bucle desde una macro. También debería funcionar correctamente si a=1.

editar 3

ahorró 7 bytes e hizo que el código funcionara correctamente.

editar 4

Guardado 26 bytes con algunos trucos printf.

editar 5

ahorró 6 bytes al contraer el relleno adicional en 1 número.

editar 6

ahorró 7 bytes mediante el truco printf con el operador ternario y no declaró una variable no utilizada

JustinCB
fuente
¡Buen trabajo, Justin! ¡Esperamos ver más de ti en las próximas semanas!
WallyWest
Gracias. Espero hacer más en las próximas semanas también.
JustinCB
1

Excel VBA, 183 bytes

Una función de ventana inmediata anónima VBE que toma la entrada del rango [A1:B1]y las salidas a la consola.

a=[A1]:b=[B1]:While a:c=a Mod 2=0:?Right(" "& a,2);Right("   "&IIf(c,"["&b &"]",b &" "),7):s=s+IIf(c,0,b):a=Int(a/2):b=b*2:Wend:?Right("     "&String(Len(s)+2,61),9):?Right("    "&s,8)

Sin golf

Sub EthiopianMultiply(ByVal a As Integer, b As Integer)
    While a
        Let c = a Mod 2 = 0
        Debug.Print Right(" " & a, 2);
        Debug.Print Right("    " & IIf(c, "[" & b & "]", b & " "), 7)
        Let s = s + IIf(c, 0, b)
        Let a = Int(a / 2)
        Let b = Int(b * 2)
    Wend
    Debug.Print Right("     " & String(Len(s) + 2, 61), 9)
    Debug.Print Right("     " & s, 8)
End Sub

Salida

61   486 
30  [972]
15  1944 
 7  3888 
 3  7776 
 1 15552 
  =======
   29646
Taylor Scott
fuente