Números fáciles de multiplicar

34

Su tarea es determinar si dos números son fáciles de multiplicar . Esto significa que su multiplicación larga de base 10 no tiene ningún traspaso (reagrupación) entre los valores posicionales, observando tanto los pasos de multiplicación como el paso de suma. Esto sucede cuando cada par de dígitos que se multiplica da 9 o menos y la suma de cada columna es 9 o menos.

Por ejemplo, 331y 1021son fáciles de multiplicar:

   331
x 1021
------
+  331
  662
   0
331
------
337951

Y lo mismo es cierto (como siempre) si multiplicamos en el otro orden:

  1021
x  331
------
+ 1021
 3063
3063
------
337951

Pero, 431y 1021no son fáciles de multiplicar, con acarreos que suceden entre las columnas indicadas:

   431
x 1021
------
+  431
  862
   0
431
------
440051
 ^^^

Además, 12y 16no son fáciles de multiplicar porque se produce un traspaso al multiplicar 12 * 6para obtener 72, a pesar de que no ocurre ningún acarreo en el paso de adición.

  12
x 16
----
+ 72
 12
----
 192

Entrada: Dos enteros positivos o sus representaciones de cadena. Puede suponer que no desbordarán el tipo entero de su idioma, ni su producto.

Salida: un valor consistente si son fáciles de multiplicar, y otro valor consistente si no.

Casos de prueba: los primeros 5 son fáciles de multiplicar, los últimos 5 no lo son.

331 1021
1021 331
101 99
333 11111
243 201

431 1021
12 16
3 4
3333 1111
310 13

[(331, 1021), (1021, 331), (101, 99), (333, 11111), (243, 201)]
[(431, 1021), (12, 16), (3, 4), (3333, 1111), (310, 13)]

Tabla de clasificación:

Mostrar fragmento de código

code-golf arithmetic decision-problem xnor
fuente
1
¿Puede la entrada para cada número ser una lista de dígitos?
dylnan
@dylnan No, aunque una lista de caracteres es válida por defecto para la opción de cadena.
xnor

Respuestas:

14

Jalea , 7 bytes

Dæc/>9Ẹ

Pruébalo en línea!

Utiliza convolución (que contribuí a Jelly: D)

Cómo funciona

Dæc/>9Ẹ
D        converts to decimal list
 æc      convolution
    >9Ẹ  checks if any number is greater than 9
Monja permeable
fuente
o wow convolución: DI creo que esta es la primera vez que veo una convolución utilizada en un código de golf: D +1
HyperNeutrino
44
@HyperNeutrino codegolf.stackexchange.com/search?q=matl
Martin Ender
1
codegolf.stackexchange.com/questions/114495/topple-the-sandpile/…
Luis Mendo
@LuisMendo No, esa es una convolución diferente.
Erik the Outgolfer
Por cierto, puede reemplazar los últimos 3 bytes con <⁵Ạsalida sin un booleano NO realizado en él.
Erik the Outgolfer
8

JavaScript (ES6), 67 bytes

Toma la entrada como 2 cadenas en la sintaxis de curry (a)(b). Devoluciones falsepara fácil o trueno fácil.

a=>b=>[...a].some((x,i,a)=>[...b].some(y=>(a[-++i]=~~a[-i]+x*y)>9))

Casos de prueba

Mostrar fragmento de código

Alt. versión (defectuosa), 64 55 52 bytes

Ahorró 3 bytes al tomar cadenas, como lo sugiere @Shaggy
Como lo señaló @LeakyNun, este método fallaría en algunos enteros específicos grandes

Toma la entrada como 2 cadenas en la sintaxis de curry (a)(b). Devoluciones truepara fácil o falseno fácil.

a=>b=>/^.(0.)*$/.test((g=n=>[...n].join`0`)(a)*g(b))

Casos de prueba

Mostrar fragmento de código

¿Cómo?

La idea aquí es exponer explícitamente los acarreos insertando ceros antes de cada dígito de cada factor.

Ejemplos:

  • 331 x 1021 se convierte en 30301 x 1000201 , lo que da 30307090501 en lugar de 337951 . Al agregar un cero inicial al resultado y agrupar todos los dígitos por 2, esto se puede escribir como 03 03 07 09 05 01 . Todos los grupos tienen menos de 10 , lo que significa que no habría habido ningún acarreo en la multiplicación estándar.

  • 431 x 1021 se convierte en 40301 x 1000201 , lo que da 40309100501 y se puede escribir como 04 03 09 10 05 01 . Esta vez, tenemos un 10 que revela un carry en la multiplicación estándar.

Arnauld
fuente
¿Puede ... podemos tener una explicación básica sobre el algoritmo?
totalmente humano
@totallyhuman He agregado una explicación. (Vaya ... y también arregló un error.)
Arnauld
1
Parece que debería poder guardar 3 bytes tomando las entradas como cadenas.
Shaggy
3
Me llevó una eternidad encontrar un contraejemplo (teórico) en el que su algoritmo fallará: tio.run/##y0rNyan8/9/l8LJk/f///… ( 108el medio estropea su algoritmo)
Leaky Nun
@LeakyNun Buen hallazgo. Sí, teóricamente puede desbordarse.
Arnauld
6

Alice , 30 bytes

/Q.\d3-&+k!*?-n/ o @
\ic/*2&w~

Pruébalo en línea!

Salidas 1para fácil y 0para difícil.

Los números son fáciles de multiplicar si y solo si la suma de dígitos del producto es igual al producto de las sumas de dígitos.

/i    Input both numbers as a single string
.     Duplicate this string
/*    Coerce into two integers and multiply
2&w   Push return address twice (do the following three times)
~\Q     Swap the top two stack entries, then reverse the stack
        This produces a 3-cycle, and the first iteration coerces
        the original input string into two integers
c       Convert into individual characters
\d3-&+  Add all numbers on the stack except the bottom two (i.e., add all digits)
k     Return to pushed address (end loop)
      At this point, all three numbers are replaced by their digit sums
!*?   Multiply the digit sums of the original two numbers
-     Subtract the digit sum of the product
n     Logical negate: convert to 1 or 0
/o@   Output as character and terminate
Nitrodon
fuente
4

MATL , 10 bytes

,j!U]Y+9>a

Salidas 0para fácil, 1para difícil.

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

,       % Do twice
  j     %   Input as a string
  !     %   Transpose into a column vector of characters
  U     %   Convert each character to number. Gives a numeric column vector
]       % End
Y+      % Convolution, full size
9>      % Greatear than 1? Element-wise
a       % Any: true if there is some true entry. Implicitly display
Luis Mendo
fuente
4

R , 135 110 109 86 bytes

function(m,n)any(convolve(m%/%10^(nchar(m):1-1)%%10,n%/%10^(1:nchar(n)-1)%%10,,"o")>9)

Pruébalo en línea!

Toma la entrada como cadenas.

Es feo pero funciona ™.

Esto ahora utiliza un enfoque de convolución, como en la respuesta de Leaky Nun , por lo que toma la entrada como números enteros y devuelve TRUElos números difíciles de multiplicar y los FALSEfáciles de multiplicar.

Siempre he tenido algunos problemas para portar enfoques de convolución en el pasado, pero hoy finalmente leí la documentación :

Tenga en cuenta que la definición habitual de convolución de dos secuencias xy yestá dada porconvolve(x, rev(y), type = "o")

Lo cual es una tontería. Entonces la extracción de dígitos se invierte ny se resuelve en un puerto de la respuesta de Leaky Nun.

Giuseppe
fuente
4

Python 2 , 88 bytes

lambda n,m:any(sum(n/10**(k-j)%10*(m/10**j%10)for j in range(k+1))>9for k in range(n+m))

Toma dos enteros como entrada y devuelve False(fácil de multiplicar) o True(no).

Pruébalo en línea! (demasiado lento para uno de los casos de prueba)

Dennis
fuente
Versión de maffs rápidos
Leaky Nun
len(`n+m`)en realidad fallaría por 40, 30 .
Dennis
len(`n+m`)+1?
Leaky Nun
Eso falla para 400, 300 . len(`n`+`m`)aunque debería hacerlo.
Dennis
4

JavaScript (Node.js) , 43 41 37 36 bytes

¡Gracias @ Dennis por la idea de usar interpolación de cadenas en esta respuesta y ahorrar 4 bytes!

Gracias @ ØrjanJohansen por -1!

a=>b=>eval(`0x${a}*0x${b}<0x${a*b}`)

Pruébalo en línea!

Por supuesto, cuando la base de destino es menor que la base original (como en mi respuesta de Jelly, la base es 2), <debe voltearse.

usuario202729
fuente
¡Felicidades por ser el primero en descubrir el uso de la conversión base, por lo que te doy la recompensa!
xnor
3

Wolfram Language (Mathematica) , 75 66 65 56 bytes

f:=#~FromDigits~x&
g:=Max@CoefficientList[f@#2f@#,x]<=9&

Pruébalo en línea!

Recibiendo 2 entradas de cadena

Explicación:

f:=#~FromDigits~x&                      (* Turns the number to a polynomial
                                           with the digits as coefficients      *)
g:=Max@CoefficientList[f@#2f@#,x]<=9&   (* Polynomial multiplication, and check
                                           whether all coefficients are smaller
                                           than 10                              *)

-9 para cambiar el uso de cadena como entrada

-1 para usar el operador infijo

-9 Gracias @MartinEnder por la Maxfunción

Shieru Asakoto
fuente
3

Python 2 , 158 135 123 113 bytes

-12 bytes gracias a Leaky Nun -10 bytes gracias a ovs 

a,b=input()
e=enumerate
l=[0,0]*len(a+b)
for i,x in e(a):
 for j,y in e(b):l[i-~j]+=int(x)*int(y)
print max(l)<10

Pruébalo en línea! o Pruebe todos los casos de prueba

Barra
fuente
¿No all(d[k]<10for k in d)funciona o es solo Python 3?
shooqie
1
@shooqie sí, lo hace, pero ahora es una lista c:
Rod
129 bytes
Leaky Nun
3

Julia 0.6 , 30 bytes

~x=any(conv(digits.(x)...).>9)

Pruébalo en línea!

La entrada es una tupla de números, la salida es truepara números difíciles de multiplicar y falsepara números fáciles.

. es la aplicación de función de elemento inteligente.

...expande la tupla (de listas de dígitos enteros) a dos entradas separadas de la convfunción.

Lucas
fuente
3

SNOBOL4 (CSNOBOL4) , 268 264 247 246 243 131 bytes

	DEFINE('D(A)')
	M =INPUT
	N =INPUT
	OUTPUT =EQ(D(M) * D(N),D(M * N)) 1	:(END)
D	A LEN(1) . X REM . A	:F(RETURN)
	D =D + X	:(D)
END

Pruébalo en línea!

Puertos el acercamiento por Nitrodon . Creo que esta es la primera vez que he definido una función en SNOBOL, Dpara suma de dígitos.

	DEFINE('D(A)')					;* function definition
	M =INPUT					;* read input
	N =INPUT					;* read input
	OUTPUT =EQ(D(M) * D(N),D(M * N)) 1	:(END)	;* if D(M)*D(N)==D(M*N),
							;* print 1 else print nothing. Goto End
D	A LEN(1) . X REM . A	:F(RETURN)		;* function body
	D =D + X	:(D)				;* add X to D
END

versión anterior, 243 bytes:

	M =INPUT
	N =INPUT
	P =SIZE(M)
	Q =SIZE(N)
	G =ARRAY(P + Q)
Z	OUTPUT =LE(P)	:S(E)
	M LEN(P) LEN(1) . A
	J =Q
Y	GT(J)	:F(D)
	N LEN(J) LEN(1) . B
	W =I + J
	X =G<W> + A * B
	G<W> =LE(A * B,9) LE(X,9) X	:F(E)
	J =J - 1	:(Y)
D	P =P - 1	:(Z)
E
END

Pruébalo en línea!

Entrada en STDIN separada por nuevas líneas, salida a STDOUT: una sola nueva línea para multiplicar fácilmente y sin salida para no multiplicar fácilmente.

Esto no va a ganar ningún premio, pero presenta otro enfoque (bueno, realmente este es el enfoque ingenuo). No creo que pueda escribir esto en cubix, pero SNOBOL es lo suficientemente resistente como para funcionar como es.

Como toma la entrada como una cadena, esto funcionará para cualquier entrada con menos de 512 dígitos cada una; No estoy 100% seguro de qué tan grande ARRAYpuede ser SNOBOL.

INPUT se almacena en esta versión de SNOBOL para tener un ancho máximo de 1024 caracteres; todos los demás personajes se pierden. Parece que un ARRAY puede ser bastante grande; bien por encima de las 2048 células necesarias.

	M =INPUT				;*read input
	N =INPUT				;*read input
	P =SIZE(M)				;*P = number of M's digits, also iteration counter for outer loop
	Q =SIZE(N)				;*Q = number of N's digits
	G =ARRAY(P + Q)				;*G is an empty array of length P + Q
Z	GE(P)	:F(T)				;*if P<0, goto T (outer loop condition)
	M LEN(P) LEN(1) . A			;*A = P'th character of M
	J =Q					;*J is the iteration counter for inner loop
Y	GT(J)	:F(D)				;*if J<=0, goto D (inner loop condition)
	N LEN(J) LEN(1) . B			;*B = J'th character of N
	W =I + J				;*W=I+J, column number in multiplication
	X =G<W> + A * B				;*X=G[W]+A*B, temp variable for golfing
	G<W> =LE(A * B,9) LE(X,9) X	:F(END)	;*if A*B<=9 and X<=9, G[W]=X otherwise terminate with no output
	J =J - 1	:(Y)			;*decrement J, goto Y
D	P =P - 1	:(Z)			;*decrement P, goto Z
T	OUTPUT =				;*set output to ''; OUTPUT automatically prints a newline.
END
Giuseppe
fuente
2

Carbón , 38 bytes

≔Ｅ⁺θη⁰ζＦＬθＦＬη§≔ζ⁺ικ⁺§ζ⁺ικ×Ｉ§θιＩ§ηκ‹⌈ζχ

Pruébalo en línea! El enlace es a la versión detallada del código. Emite a -cuando los números son fáciles de multiplicar. Explicación:

≔Ｅ⁺θη⁰ζ

Inicialice za una matriz de ceros lo suficientemente grande (suma de longitudes de entradas).

ＦＬθＦＬη

Recorrer los índices de las entradas qy h.

§≔ζ⁺ικ⁺§ζ⁺ικ×Ｉ§θιＩ§ηκ

Realiza un paso de la multiplicación larga.

‹⌈ζχ

Verifique si hay acarreos.

Neil
fuente
2

Haskell, 82 81 bytes

q=map$read.pure
f a=any(>9).concat.scanr((.(0:)).zipWith(+).(<$>q a).(*))(0<$a).q

Los números se toman como cadenas. DevolucionesFalse si los números son fáciles de multiplicar y de lo Truecontrario.

Pruébalo en línea!

Creo que es lo suficientemente diferente de la respuesta de @ Laikoni . Cómo funciona:

q                    -- helper function to turn a string into a list of digits

f a =                -- main function, first number is parameter 'a' 
      scanr    .q    -- fold the following function from the right (and collect
                     -- the intermediate results in a list) into the list of
                     -- digits of the second number
            0<$a     --   starting with as many 0s as there are digits in 'a'
                     -- the function is, translated to non-point free:
  \n c->zipWith(+)((*n)<$>q a)$0:c 
                     -- 'n': next digit of 'b'; 'c': value so far
        (*n)<$>a     --    multiplay each digit in 'a' with 'n'
        0:c          --    prepend a 0 to 'c'
        zipWith(+)   --    add both lists element wise
                     --    (this shifts out the last digit of 'c' in every step)
   concat            -- flatten the collected lists into a single list
 any(>9)             -- check if any number is >9
nimi
fuente
Buena solución! Estaba buscando formas de deshacerme de la importación, pero terminaron aún más.
Laikoni
2

Haskell , 45 44 bytes

Editar:

  • -1 byte cambiando ==a <.

Pensé en esto antes de mirar las otras respuestas, luego descubrí que la de Alice usaba la misma idea básica. Publicar de todos modos ya que es más corto que las otras respuestas de Haskell.

?toma dos enteros y devuelve a Bool. Usar como 331?1021. Falsesignifica que la multiplicación es fácil.

a?b=s(a*b)<s a*s b
s=sum.map(read.pure).show

Pruébalo en línea!

  • ses una función que calcula la suma de los dígitos de un entero. ( read.pureconvierte un carácter de un solo dígito en un entero).
  • Si un par de números es fácil de multiplicar, la suma de dígitos del producto es igual al producto de las sumas de dígitos.
  • Por el contrario, cualquier acarreo durante la multiplicación larga reducirá la suma de dígitos del producto de ese ideal.
Ørjan Johansen
fuente
1

Haskell , 123 bytes

import Data.List
r=read.pure
a%b|l<-transpose[reverse$map((*r d).r)b++(0<$e)|d:e<-scanr(:)""a]=all(<10)$concat l++map sum l

Pruébalo en línea! Ejemplo de uso: "331" % "1021"rendimientos True.

Laikoni
fuente
1

Perl 5 , 100 + 2 ( -F) = 102 bytes

push@a,[reverse@F]}{map{for$j(@{$a[0]}){$b[$i++].='+'.$_*$j}$i=++$c}@{$a[1]};map$\||=9>eval,@b;say$\

Pruébalo en línea!

salidas falsas para fácil, verdadero para no fácil.

Xcali
fuente
1

Jalea , 8 bytes

;PDḄµṪ⁼P

Pruébalo en línea!

Un puerto de mi respuesta Javascript . No más corto que la respuesta Jelly existente porque Jelly tiene una convolución poderosa incorporada.

Tome la entrada como una lista de dos números. Devoluciones 1para fácil, 0para no fácil.

Explicación:


;PDḄµṪ⁼P     Main link. Let input = [101, 99]
;P           Concatenate with product. Get [101, 99, 9999]
  D          Convert to decimal. Get [[1,0,1], [9,9], [9,9,9,9]]
   Ḅ         Convert from binary. Get [1 * 2^2 + 0 * 2^1 + 1 * 2^0, 
             9 * 2^1 + 9 * 2^0, 9 * 2^3 + 9 * 2^2 + 9 * 2^1 + 9 * 2^0]
             = [5, 27, 135]
    µ        With that value,
     Ṫ       Take the tail from that value. Get 135, have [5, 27] remain.
      ⁼      Check equality with...
       P       The product of the remaining numbers (5 and 17).
usuario202729
fuente
1

C (gcc) , 104 bytes

Básicamente, haga una multiplicación "a mano" en r [] y establezca el valor de retorno si alguna columna es superior a 9, ya que eso significaría que se ha producido un acarreo.

Sorprendentemente, esto fue más corto que mi primer intento que tomó los hilos como argumentos.

f(a,b){int*q,r[10]={0},*p=r,R=0,B;for(;a;a/=10)for(q=p++,B=b;B;B/=10)R|=(*q+++=a%10*(B%10))>9;return R;}

Pruébalo en línea!

gastropner
fuente