Números fáceis de multiplicar

34

Sua tarefa é determinar se é fácil multiplicar dois números . Isso significa que a multiplicação longa da base 10 não possui nenhum valor (reagrupamento) entre os valores dos locais, observando as etapas de multiplicação e a etapa de adição. Isso acontece quando cada par de dígitos multiplicado fornece 9 ou menos e a soma de cada coluna é 9 ou menos.

Por exemplo, 331e 1021são fáceis de multiplicar:

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

E o mesmo é verdade (como sempre) se multiplicarmos na outra ordem:

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

Mas, 431e 1021não é fácil multiplicar, com carregamentos acontecendo entre as colunas indicadas:

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

Além disso, 12e 16não é fácil multiplicar porque uma transferência ocorre ao multiplicar 12 * 6para obter 72, mesmo que nenhuma transferência ocorra na etapa de adição.

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

Entrada: Dois números inteiros positivos ou suas representações de sequência. Você pode assumir que eles não excederão o tipo inteiro do seu idioma, nem o produto deles.

Saída: um valor consistente, se é fácil multiplicar, e outro valor consistente, se não.

Casos de teste: os 5 primeiros são fáceis de multiplicar, os 5 últimos não.

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)]

Entre os melhores:

Mostrar snippet de código

code-golf arithmetic decision-problem xnor
fonte
1
A entrada para cada número pode ser uma lista de dígitos?
dylnan
@dylnan Não, embora uma lista de caracteres seja válida por padrão para a opção string.
Xnor

Respostas:

14

Geléia , 7 bytes

Dæc/>9Ẹ

Experimente online!

Usa convolução (que eu contribuí com Jelly: D)

Como funciona

Dæc/>9Ẹ
D        converts to decimal list
 æc      convolution
    >9Ẹ  checks if any number is greater than 9
Freira Furada
fonte
o wow convolução: DI acho que essa é a minha primeira convolução tempo vendo usado em um código-golf: D 1
HyperNeutrino
4
@HyperNeutrino codegolf.stackexchange.com/search?q=matl
Martin Ender
1
codegolf.stackexchange.com/questions/114495/topple-the-sandpile/…
Luis Mendo
@LuisMendo Não, é uma convolução diferente.
Erik the Outgolfer
BTW Você pode substituir os últimos 3 bytes <⁵Ạpor output sem um booleano NÃO executado nele.
Erik the Outgolfer
8

JavaScript (ES6), 67 bytes

Recebe entrada como 2 strings na sintaxe de currying (a)(b). Retorna falsepara fácil ou truepara não fácil.

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

Casos de teste

Mostrar snippet de código

Alt. versão (falha), 64 55 52 bytes

Salva 3 bytes usando cadeias de caracteres, conforme sugerido por @Shaggy
Como apontado por @LeakyNun, esse método falharia em alguns números inteiros grandes e específicos

Recebe entrada como 2 strings na sintaxe de currying (a)(b). Retorna truepara fácil ou falsepara não fácil.

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

Casos de teste

Mostrar snippet de código

Quão?

A idéia aqui é expor explicitamente os carregamentos inserindo zeros antes de cada dígito de cada fator.

Exemplos:

  • 331 x 1021 se torna 30301 x 1000201 , o que fornece 30307090501 em vez de 337951 . Ao adicionar um zero inicial ao resultado e agrupar todos os dígitos por 2, isso pode ser escrito como 03 03 07 09 05 01 . Todos os grupos têm menos de 10 , o que significa que não haveria nenhum resultado na multiplicação padrão.

  • 431 x 1021 torna-se 40301 x 1000201 , que fornece 40309100501 e pode ser gravado como 04 03 09 10 05 01 . Desta vez, temos um 10 que revela um carry na multiplicação padrão.

Arnauld
fonte
Podemos ... Podemos ter uma explicação básica sobre o algoritmo?
totallyhuman
@totallyhuman Adicionei uma explicação. (Oops ... e também fixa um bug.)
Arnauld
1
Parece que você deve conseguir salvar 3 bytes usando as entradas como seqüências de caracteres.
Salsicha
3
Levei uma eternidade para encontrar um contra-exemplo (teórico), que seu algoritmo falhará: tio.run/##y0rNyan8/9/l8LJk/f///… ( 108o meio bagunça seu algoritmo)
Leaky Nun
@LeakyNun Nice find. Sim, teoricamente pode transbordar.
Arnauld
6

Alice , 30 bytes

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

Experimente online!

Saídas 1para fácil e 0difícil.

Os números são fáceis de multiplicar se e somente se a soma do dígito do produto for igual ao produto da soma do dígito.

/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
fonte
4

MATL , 10 bytes

,j!U]Y+9>a

Saídas 0para fácil, 1para difícil.

Experimente online! Ou verifique todos os casos de teste .

Explicação

,       % 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
fonte
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)

Experimente online!

Recebe entrada como strings.

É feio, mas funciona ™.

Agora, ele usa uma abordagem de convolução, como na resposta de Leaky Nun , de modo que recebe entradas como números inteiros e retorna TRUEpara números difíceis de multiplicar e FALSEfáceis de multiplicar.

Eu sempre tive alguns problemas para portar abordagens de convolução no passado, mas hoje finalmente li a documentação :

Observe que a definição usual de convolução de duas seqüências xe yé dada porconvolve(x, rev(y), type = "o")

O que é bobo. Portanto, a extração de dígitos é revertida ne se transforma em um porto da resposta de Leaky Nun.

Giuseppe
fonte
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 dois números inteiros como entrada e retorna False(fácil de multiplicar) ou True(não).

Experimente online! (muito lento para um dos casos de teste)

Dennis
fonte
Versão rápida dos maffs
Leaky Nun
len(`n+m`)na verdade falharia por 40, 30 .
Dennis
len(`n+m`)+1?
Leaky Nun
Isso falha para 400, 300 . len(`n`+`m`)deve fazer embora.
Dennis
4

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

Obrigado @ Dennis pela idéia de usar interpolação de string nesta resposta e economize 4 bytes!

Obrigado @ ØrjanJohansen por -1!

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

Experimente online!

É claro que quando a base de destino é menor que a base original (como na minha resposta Jelly, a base é 2), ela <deve ser invertida.

user202729
fonte
Parabéns por ser o primeiro a descobrir o uso da conversão de base, pela qual dou a você a recompensa!
Xnor
3

Wolfram Language (Mathematica) , 75 66 65 56 bytes

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

Experimente online!

Recebendo 2 entradas de string

Explicação:

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 mudar para usar string como entrada

-1 para usar o operador infix

-9 Obrigado @MartinEnder pela Maxfunção

Shieru Asakoto
fonte
3

Python 2 , 158 135 123 113 113 bytes

-12 bytes graças a Freira Furada -10 bytes graças 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

Experimente online! ou Experimente todos os casos de teste

Cajado
fonte
Não all(d[k]<10for k in d)funciona ou é apenas Python 3?
shooqie
1
@shooqie sim, ele faz, mas agora é uma lista c:
Rod
129 bytes
Freira vazada
3

Julia 0.6 , 30 bytes

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

Experimente online!

A entrada é uma tupla de números, a saída é truepara números difíceis de multiplicar e falsefáceis.

. é um aplicativo de função elemento a elemento.

...expande a tupla (de listas de dígitos inteiros) para duas entradas separadas da convfunção.

LukeS
fonte
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

Experimente online!

Portos a abordagem por Nitrodon . Acho que é a primeira vez que defino uma função no SNOBOL, Dpara soma 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

versão antiga, 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

Experimente online!

Entrada no STDIN separada por novas linhas, saída para STDOUT: uma única nova linha para fácil multiplicação e nenhuma saída para não fácil multiplicar.

Isso não vai ganhar nenhum prêmio, mas apresenta outra abordagem (bem, realmente essa é a abordagem ingênua). Eu não acho que poderia escrever isso no cubix, mas o SNOBOL é duro o suficiente para trabalhar como está.

Como recebe a entrada como uma sequência, isso funcionará para qualquer entrada com menos de 512 dígitos cada; Não tenho 100% de certeza de quão grande ARRAYpode ser o SNOBOL.

INPUT é armazenado em buffer nesta versão do SNOBOL para ter uma largura máxima de 1024 caracteres; todos os outros caracteres são perdidos. Parece que um ARRAY pode ser bastante grande; bem acima das 2048 células necessárias.

	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
fonte
2

Carvão , 38 bytes

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

Experimente online! Link é a versão detalhada do código. Produz a -quando os números são fáceis de multiplicar. Explicação:

≔Ｅ⁺θη⁰ζ

Inicialize zcom uma matriz de zeros grande o suficiente (soma dos comprimentos de entradas).

ＦＬθＦＬη

Faça um loop sobre os índices das entradas qe h.

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

Execute um passo da multiplicação longa.

‹⌈ζχ

Verifique se há carregamentos.

Neil
fonte
2

Haskell, 82 81 bytes

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

Os números são tomados como cadeias. Retorna Falsese os números forem fáceis de multiplicar e Truecaso contrário.

Experimente online!

Eu acho que é diferente o suficiente da resposta de @ Laikoni . Como 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
fonte
Ótima solução! Eu estava procurando maneiras de se livrar da importação, mas elas acabaram ainda mais.
Laikoni
2

Haskell , 45 44 bytes

Editar:

  • -1 byte mudando ==para <.

Pensei nisso antes de olhar para as outras respostas, depois descobri que a Alice usava a mesma idéia básica. Postando assim mesmo, já que é mais curto que as outras respostas de Haskell.

?pega dois números inteiros e retorna a Bool. Use como 331?1021. Falsesignifica que a multiplicação é fácil.

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

Experimente online!

  • sé uma função que calcula a soma dos dígitos de um número inteiro. ( read.pureconverte um caractere de um dígito em um número inteiro.)
  • Se é fácil multiplicar um par de números, a soma do dígito do produto é igual ao produto da soma dos dígitos.
  • Por outro lado, qualquer transporte durante a multiplicação longa reduzirá a soma de dígitos do produto desse ideal.
Ørjan Johansen
fonte
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

Experimente online! Exemplo de uso: "331" % "1021"rendimentos True.

Laikoni
fonte
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$\

Experimente online!

produz falso para fácil, verdadeiro para não fácil.

Xcali
fonte
1

Geléia , 8 bytes

;PDḄµṪ⁼P

Experimente online!

Uma porta da minha resposta Javascript . Não é menor do que a resposta existente da Jelly, porque a Jelly possui uma poderosa convolução incorporada.

Tome entrada como uma lista de dois números. Retorna 1para fácil, 0para não fácil.

Explicação:


;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).
user202729
fonte
1

C (gcc) , 104 bytes

Basicamente, faça uma multiplicação "à mão" em r [] e defina o valor de retorno se alguma coluna for maior que 9, pois isso significaria uma ocorrência.

Surpreendentemente, isso foi mais curto do que minha primeira tentativa, que tomou as seqüências de caracteres 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;}

Experimente online!

gastropner
fonte