Chiffres faciles à multiplier

34

Votre tâche consiste à déterminer si deux nombres sont faciles à multiplier . Cela signifie que leur multiplication longue en base 10 ne comporte pas de regroupement entre les valeurs de position, en examinant à la fois les étapes de la multiplication et l’ajout. Cela se produit lorsque chaque paire de chiffres en cours de multiplication donne 9 ou moins et que la somme de chaque colonne est égale ou inférieure à 9.

Par exemple, 331et 1021sont faciles à multiplier:

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

Et la même chose est vraie (comme toujours) si on multiplie dans l'autre ordre:

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

Mais, 431et 1021ne sont pas faciles à multiplier, avec des reports se produisant entre les colonnes indiquées:

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

En outre, 12et 16ne sont pas faciles à multiplier, car un report se produit lors de la multiplication 12 * 6pour obtenir 72, même si aucun report ne se produit dans l'étape d'addition.

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

Entrée: deux entiers positifs ou leurs représentations sous forme de chaîne. Vous pouvez supposer qu'ils ne déborderont pas du type entier de votre langue, pas plus que leur produit.

Sortie: Une valeur cohérente si elles sont faciles à multiplier, et une autre valeur cohérente sinon.

Cas de test: Les 5 premiers sont faciles à multiplier, les 5 derniers ne le sont pas.

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

Classement:

Afficher l'extrait de code

code-golf arithmetic decision-problem Xnor
la source
1
Peut-on entrer pour chaque numéro une liste de chiffres?
dylnan
@dylnan Non, bien qu'une liste de caractères soit valide par défaut pour l'option chaîne.
xnor

Réponses:

14

Gelée , 7 octets

Dæc/>9Ẹ

Essayez-le en ligne!

Utilise la convolution (que j'ai contribué à Jelly: D)

Comment ça marche

Dæc/>9Ẹ
D        converts to decimal list
 æc      convolution
    >9Ẹ  checks if any number is greater than 9
Fuite, nonne
la source
o wow convolution: Je pense que c'est la première fois que je vois une convolution utilisée dans un code-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 Non, c'est une convolution différente.
Erik the Outgolfer
BTW Vous pouvez remplacer les 3 derniers octets par <⁵Ạpour une sortie sans qu'un booléen ne soit pas effectué dessus.
Erik l'Outgolfer
8

JavaScript (ES6), 67 octets

Prend la saisie sous forme de 2 chaînes dans la syntaxe de currying (a)(b). Retours falsepour facile ou truepour pas facile.

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

Cas de test

Afficher l'extrait de code

Alt. version (défectueuse), 64 55 52 octets

Sauvegardé 3 octets en prenant des chaînes, comme suggéré par @Shaggy
Comme l'a souligné @LeakyNun, cette méthode échouerait sur certains entiers spécifiques de grande taille.

Prend la saisie sous forme de 2 chaînes dans la syntaxe de currying (a)(b). Retours truepour facile ou falsepour pas facile.

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

Cas de test

Afficher l'extrait de code

Comment?

L'idée ici est d'exposer explicitement les portées en insérant des zéros avant chaque chiffre de chaque facteur.

Exemples:

  • 331 x 1021 devient 30301 x 1000201 , ce qui donne 30307090501 au lieu de 337951 . En ajoutant un zéro au premier et en regroupant tous les chiffres par 2, vous pouvez écrire 03 03 07 09 05 01 . Tous les groupes ont moins de 10 , ce qui signifie qu'il n'y aurait pas eu de retenue dans la multiplication standard.

  • 431 x 1021 devient 40301 x 1000201 , ce qui donne 40309100501 et peut être écrit 04 03 09 10 05 01 . Cette fois, nous avons un 10 qui révèle un report dans la multiplication standard.

Arnauld
la source
Peut-on ... Pouvons-nous avoir une explication de base sur l'algorithme?
totalement humain
@totallyhuman J'ai ajouté une explication. (Oups ... et aussi corrigé un bug.)
Arnauld
1
On dirait que vous devriez pouvoir économiser 3 octets en prenant les entrées sous forme de chaînes.
Shaggy
3
Il m'a fallu une éternité pour trouver un contre-exemple (théorique) auquel votre algorithme échouera: tio.run/##y0rNyan8/9/l8LJk/f///… ( 108le milieu gâche votre algorithme)
Leaky Nun
@ LeakyNun Belle trouvaille. Oui, il peut théoriquement déborder.
Arnauld
6

Alice , 30 octets

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

Essayez-le en ligne!

Sorties 1faciles et 0difficiles.

Les nombres sont faciles à multiplier si et seulement si la somme des chiffres du produit est égale au produit des sommes des chiffres.

/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
la source
4

MATL , 10 octets

,j!U]Y+9>a

Sorties 0faciles, 1difficiles.

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

,       % 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
la source
4

R , 135 110 109 86 octets

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

Essayez-le en ligne!

Prend les entrées sous forme de chaînes.

C'est moche mais ça marche ™.

Cela utilise maintenant une approche de convolution, comme dans la réponse de Leaky Nun , de sorte que les entrées sont entrées sous forme d'entiers, et renvoie TRUEles nombres difficiles à multiplier et ceux FALSEfaciles à multiplier.

J'ai toujours eu du mal à porter les approches de convolution dans le passé, mais aujourd'hui, j'ai enfin lu la documentation :

Notez que la définition habituelle de convolution de deux séquences xet yest donnée parconvolve(x, rev(y), type = "o")

Ce qui est juste idiot. Ainsi, l'extraction de chiffres est inversée net se résout en réponse du port de Leaky Nun.

Giuseppe
la source
4

Python 2 , 88 octets

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

Prend deux nombres entiers en entrée et retourne False(facile à multiplier) ou True(non).

Essayez-le en ligne! (trop lent pour l'un des cas de test)

Dennis
la source
Quick maffs version
Leaky Nun
len(`n+m`)serait effectivement échouer pour 40, 30 .
Dennis
len(`n+m`)+1?
Leaky Nun
Cela échoue pour 400, 300 . len(`n`+`m`)devrait faire si.
Dennis
4

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

Merci @ Dennis pour l'idée d'utiliser l'interpolation de chaîne dans cette réponse et économisez 4 octets!

Merci @ ØrjanJohansen pour -1!

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

Essayez-le en ligne!

Bien sûr, lorsque la base de destination est inférieure à la base d'origine (comme dans ma réponse à la gelée, la base est égale à 2), elle <doit être inversée.

utilisateur202729
la source
Félicitations pour avoir été le premier à comprendre comment utiliser la conversion de base, pour laquelle je vous donne la prime!
xnor
3

Wolfram Language (Mathematica) , 75 66 65 56 octets

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

Essayez-le en ligne!

Recevoir 2 entrées de chaîne

Explication:

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 pour changer pour utiliser une chaîne en tant qu'entrée

-1 pour utiliser infixer l'opérateur

-9 Merci @MartinEnder pour la Maxfonction

Shieru Asakoto
la source
3

Python 2 , 158 135 123 113 octets

-12 octets grâce à Leaky Nun -10 octets grâce aux 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

Essayez-le en ligne! ou Essayez tous les cas de test

Barre
la source
Ne all(d[k]<10for k in d)fonctionne pas ou est-ce juste Python 3?
Shooqie
1
@shooqie oui, c'est vrai, mais maintenant c'est une liste c:
Rod
129 octets
Leaky Nun
3

Julia 0.6 , 30 octets

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

Essayez-le en ligne!

L'entrée est un tuple de nombres, la sortie est truedifficile à multiplier et falsefacile.

. est une application de fonction élémentaire.

...étend le tuple (de listes de chiffres entiers) à deux entrées distinctes de la convfonction.

LukeS
la source
3

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

	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

Essayez-le en ligne!

Ports l'approche par Nitrodon . Je pense que c'est la première fois que je définis une fonction dans SNOBOL, Dpour la somme des chiffres.

	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

ancienne version, 243 octets:

	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

Essayez-le en ligne!

Entrée sur STDIN séparée par des retours à la ligne, sortie vers STDOUT: une nouvelle ligne pour faciliter la multiplication et aucune sortie pour non facile à multiplier.

Cela ne va pas gagner de prix, mais cela présente une autre approche (enfin, c'est vraiment l'approche naïve). Je ne pense pas que je pourrais écrire cela dans Cubix, mais SNOBOL est assez dur pour fonctionner tel quel.

Puisqu'il prend l'entrée sous forme de chaîne, cela fonctionnera pour toute entrée de moins de 512 chiffres chacun; Je ne suis pas sûr à 100% de l’importance ARRAYde SNOBOL.

INPUT est mis en mémoire tampon dans cette version de SNOBOL pour avoir une largeur maximale de 1024 caractères; tous les autres personnages sont alors perdus. Il semble qu'un ARRAY peut être assez volumineux; bien au-dessus des 2048 cellules nécessaires.

	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
la source
2

Charbon de bois , 38 octets

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

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Sorties a -quand les nombres sont faciles à multiplier. Explication:

≔Ｅ⁺θη⁰ζ

Initialisez zsur un tableau de zéros suffisant (somme des longueurs des entrées).

ＦＬθＦＬη

Boucle sur les indices des entrées qet h.

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

Effectuer une étape de la multiplication longue.

‹⌈ζχ

Vérifiez les porte.

Neil
la source
2

Haskell, 82 81 octets

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

Les nombres sont pris comme des chaînes. Retourne Falsesi les nombres sont faciles à multiplier et Truesinon.

Essayez-le en ligne!

Je pense que c'est assez différent de la réponse de @ Laikoni . Comment ça marche:

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
la source
Belle solution! Je cherchais des moyens de supprimer l'importation, mais ils ont été encore plus longs.
Laikoni
2

Haskell , 45 44 octets

Modifier:

  • -1 octet changeant == à <.

J'y ai pensé avant de regarder les autres réponses, puis j'ai découvert que celle d'Alice utilisait la même idée de base. De toute façon, car c'est plus court que les autres réponses de Haskell.

?prend deux entiers et retourne a Bool. Utiliser comme 331?1021. Falsesignifie que la multiplication est facile.

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

Essayez-le en ligne!

  • sest une fonction qui calcule la somme des chiffres d'un entier. ( read.pureconvertit un caractère à un chiffre en un entier.)
  • Si une paire de nombres est facile à multiplier, la somme en chiffres du produit est égale au produit des sommes en chiffres.
  • Inversement, tout report pendant la multiplication longue réduira la somme des chiffres du produit par rapport à cet idéal.
Ørjan Johansen
la source
1

Haskell , 123 octets

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

Essayez-le en ligne! Exemple d'utilisation: "331" % "1021"rendements True.

Laikoni
la source
1

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

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

Essayez-le en ligne!

sorties false pour facile, vrai pour pas facile.

Xcali
la source
1

Gelée , 8 octets

;PDḄµṪ⁼P

Essayez-le en ligne!

Un port de ma réponse javascript . Pas plus court que la réponse Jelly existante car Jelly possède une puissante convolution intégrée.

Prendre l'entrée comme une liste de deux nombres. Retours 1pour facile, 0pour pas facile.

Explication:


;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).
utilisateur202729
la source
1

C (gcc) , 104 octets

Fondamentalement, faites une multiplication "à la main" dans r [] et définissez la valeur de retour si une colonne dépasse 9, car cela signifierait qu'un report est survenu.

Étonnamment, c'était plus court que ma première tentative qui prenait les chaînes comme arguments.

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;}

Essayez-le en ligne!

gastropner
la source