Łatwe do pomnożenia liczby

34

Twoim zadaniem jest ustalenie, czy dwie liczby można łatwo pomnożyć . Oznacza to, że ich długie mnożenie przez 10 zasad nie ma żadnego przeniesienia (przegrupowania) między wartościami miejsca, biorąc pod uwagę zarówno etap pomnożenia, jak i krok dodawania. Dzieje się tak, gdy każda para pomnożonych cyfr daje 9 lub mniej, a suma każdej kolumny wynosi 9 lub mniej.

Na przykład 331i 1021są łatwe do pomnożenia:

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

To samo jest prawdą (jak zawsze), jeśli pomnożymy w innej kolejności:

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

Ale 431i 1021nie są one łatwe do pomnożenia, z przeniesieniami między wskazanymi kolumnami:

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

Ponadto, 12i 16nie są one łatwe do pomnożenia, ponieważ przeniesienie następuje po pomnożeniu, 12 * 6aby uzyskać 72, mimo że w kroku dodawania nie występują przeniesienia.

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

Dane wejściowe: dwie dodatnie liczby całkowite lub ich ciągi znaków. Możesz założyć, że nie przepełnią one liczb całkowitych twojego języka, podobnie jak ich produkt.

Dane wyjściowe: Jedna stała wartość, jeśli można je łatwo pomnożyć, i inna stała wartość, jeśli nie.

Przypadki testowe: pierwszych 5 można łatwo pomnożyć, ostatnich 5 nie.

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

Tabela liderów:

xnor
źródło
1
Czy dane wejściowe dla każdej liczby mogą być listą cyfr?
dylnan,
@dylnan Nie, chociaż lista znaków jest domyślnie poprawna dla opcji ciągu.
xnor

Odpowiedzi:

14

Galaretka , 7 bajtów

Dæc/>9Ẹ

Wypróbuj online!

Wykorzystuje splot (który przyczyniłem się do Jelly: D)

Jak to działa

Dæc/>9Ẹ
D        converts to decimal list
 æc      convolution
    >9Ẹ  checks if any number is greater than 9
Leaky Nun
źródło
o wow splot: Myślę, że po raz pierwszy widzę splot użyty w golfie kodowym: D +1
HyperNeutrino,
4
@HyperNeutrino codegolf.stackexchange.com/search?q=matl
Martin Ender
@LuisMendo Nie, to inny splot.
Erik the Outgolfer,
BTW Możesz zamienić 3 ostatnie bajty <⁵Ạna dane wyjściowe bez wartości boolowskiej NIE na nim wykonanej.
Erik the Outgolfer,
8

JavaScript (ES6), 67 bajtów

Pobiera dane wejściowe jako 2 ciągi w składni curry (a)(b). Zwraca falsena łatwe lub trueniełatwe.

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

Przypadki testowe


Alt. wersja (wadliwa), 64 55 52 bajtów

Zapisano 3 bajty, biorąc ciągi znaków, jak sugeruje @Shaggy
Jak wskazał @LeakyNun, ta metoda zawiodłaby na niektórych dużych liczbach całkowitych

Pobiera dane wejściowe jako 2 ciągi w składni curry (a)(b). Zwraca truena łatwe lub falseniełatwe.

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

Przypadki testowe

W jaki sposób?

Chodzi tutaj o jawne ujawnienie przeniesień poprzez wstawienie zer przed każdą cyfrą każdego czynnika.

Przykłady:

  • 331 x 1021 staje się 30301 x 1000201 , co daje 30307090501 zamiast 337951 . Dodając wiodące zero do wyniku i grupując wszystkie cyfry według 2, można to zapisać jako 03 03 07 09 05 01 . Wszystkie grupy mają mniej niż 10 , co oznacza, że ​​nie byłoby żadnego przeniesienia w standardowym pomnożeniu.

  • 431 x 1021 staje się 40301 x 1000201 , co daje 40309100501 i może być zapisane jako 04 03 09 10 05 01 . Tym razem mamy 10, która ujawnia przeniesienie w standardowym pomnożeniu.

Arnauld
źródło
Czy ... Czy możemy uzyskać podstawowe wyjaśnienie algorytmu?
całkowicie ludzki,
@ totalniehuman Dodałem wyjaśnienie. (Ups ... i także naprawiłem błąd.)
Arnauld,
1
Wygląda na to, że powinieneś być w stanie zapisać 3 bajty, przyjmując dane wejściowe jako ciągi znaków.
Kudłaty
3
Wieczność zajęło mi znalezienie (teoretycznego) kontrprzykładu, którego twój algorytm zawiedzie: tio.run/##y0rNyan8/9/l8LJk/f///… ( środek pośpiesza108 twój algorytm)
Leaky Nun
@LeakyNun Ładne znalezisko. Tak, teoretycznie może się przepełnić.
Arnauld,
6

Alice , 30 bajtów

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

Wypróbuj online!

Wyjścia są 1łatwe i 0trudne.

Liczby można łatwo pomnożyć tylko wtedy, gdy suma cyfr iloczynu jest równa iloczynowi sum cyfr.

/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
źródło
4

MATL , 10 bajtów

,j!U]Y+9>a

Wyjścia 0na łatwe, 1na trudne.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

,       % 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
źródło
4

R , 135 110 109 86 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe jako ciągi znaków.

Jest brzydki, ale działa ™.

To teraz wykorzystuje podejście splotowe, jak w odpowiedzi Leaky Nun , więc przyjmuje dane wejściowe jako liczby całkowite i zwraca wartości TRUEtrudne do pomnożenia i liczby FALSEłatwe do pomnożenia.

W przeszłości zawsze miałem problemy z przenoszeniem podejść do splotu, ale dziś w końcu przeczytałem dokumentację :

Należy zauważyć, że zwykle definicji splotu dwóch sekwencji xi yjest przezconvolve(x, rev(y), type = "o")

Co jest po prostu głupie. Więc wyodrębnianie cyfr jest odwrócone ni przekształca się w port odpowiedzi Dziurawej Zakonnicy.

Giuseppe
źródło
4

Python 2 , 88 bajtów

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

Pobiera na wejściu dwie liczby całkowite i zwraca False(łatwe do pomnożenia) lub True(nie).

Wypróbuj online! (zbyt wolny dla jednego z przypadków testowych)

Dennis
źródło
len(`n+m`)w rzeczywistości wypadłby dla 40, 30 .
Dennis,
len(`n+m`)+1?
Leaky Nun
To się nie powiedzie dla 400, 300 . len(`n`+`m`)powinien zrobić.
Dennis,
4

JavaScript (Node.js) , 43 41 37 36 bajtów

Dzięki @ Dennis za pomysł użycia interpolacji łańcuchów w tej odpowiedzi i zaoszczędzić 4 bajty!

Dzięki @ ØrjanJohansen za -1!

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

Wypróbuj online!

Oczywiście, gdy baza docelowa jest mniejsza niż oryginalna baza (jak w mojej odpowiedzi Jelly, podstawa to 2), <należy ją odwrócić.

użytkownik202729
źródło
Gratulacje, że jako pierwszy wymyśliłem konwersję podstawową, za którą daję wam nagrodę!
xnor
3

Wolfram Language (Mathematica) , 75 66 65 56 bajtów

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

Wypróbuj online!

Odbieranie 2 ciągów wejściowych

Wyjaśnienie:

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 do zmiany na użycie łańcucha jako danych wejściowych

-1 do używania operatora infix

-9 Dzięki @MartinEnder za Maxfunkcję

Shieru Asakoto
źródło
3

Python 2 , 158 135 123 113 bajtów

-12 bajtów dzięki Leaky Nun. -10 bajtów dzięki 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

Wypróbuj online! lub Wypróbuj wszystkie przypadki testowe

Pręt
źródło
Nie all(d[k]<10for k in d)działa, czy jest to po prostu Python 3?
shooqie,
1
@shooqie tak, tak, ale teraz jest to lista c:
Rod
129 bajtów
Leaky Nun
3

Julia 0.6 , 30 bajtów

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

Wypróbuj online!

Dane wejściowe to krotka liczb, dane wyjściowe truesłużą do mnożenia liczb trudnych i falsełatwych.

. jest aplikacją funkcji elementarnych.

...rozszerza krotkę (list liczb całkowitych) do dwóch osobnych wejść convfunkcji.

Łukasza
źródło
3

SNOBOL4 (CSNOBOL4) , 268 264 247 246 243 131 bajtów

	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

Wypróbuj online!

Przenosi podejście Nitrodona . Myślę, że po raz pierwszy zdefiniowałem funkcję w SNOBOL, Ddla sumy cyfr.

	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

stara wersja, 243 bajty:

	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

Wypróbuj online!

Wejście na STDIN oddzielone znakami nowej linii, wyjście na STDOUT: pojedynczy znak nowej linii dla łatwego pomnożenia i brak wyjścia na trudny do pomnożenia.

To nie zdobędzie żadnych nagród, ale przedstawia inne podejście (cóż, tak naprawdę jest to naiwne podejście). Nie sądzę, bym mógł napisać to w cubix, ale SNOBOL jest wystarczająco twardy, aby z nim pracować.

Ponieważ pobiera dane wejściowe jako ciąg znaków, będzie to działać dla każdego wejścia zawierającego mniej niż 512 cyfr; Nie jestem w 100% pewien, jak dużyARRAY mogą być wartości w SNOBOL.

INPUT jest buforowany w tej wersji SNOBOL, aby mieć maksymalną szerokość 1024 znaków; wszystkie pozostałe postacie zostaną utracone. Wydaje się, że tablica może być dość duża; konieczne ponad 2048 komórek.

	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
źródło
2

Węgiel drzewny , 38 bajtów

≔E⁺θη⁰ζFLθFLη§≔ζ⁺ικ⁺§ζ⁺ικ×I§θιI§ηκ‹⌈ζχ

Wypróbuj online! Link jest do pełnej wersji kodu. Wyprowadza a, -gdy liczby są łatwe do pomnożenia. Wyjaśnienie:

≔E⁺θη⁰ζ

Zainicjuj zwystarczająco dużą (sumę długości danych wejściowych) tablicę zer.

FLθFLη

Pętla nad wskaźnikami danych wejściowych qi h.

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

Wykonaj jeden krok długiego mnożenia.

‹⌈ζχ

Sprawdź, czy nie ma.

Neil
źródło
2

Haskell, 82 81 bajtów

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

Liczby przyjmowane jako ciągi znaków. Zwraca, Falsejeśli liczby są łatwe do pomnożenia i Trueinaczej.

Wypróbuj online!

Myślę, że to wystarczająco różni się od odpowiedzi @ Laikoni . Jak to działa:

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
źródło
Fajne rozwiązanie! Szukałem sposobów na pozbycie się importu, ale skończyły one jeszcze dłużej.
Laikoni,
2

Haskell , 45 lat 44 bajtów

Edytować:

  • -1 bajt zmienia się ==na <.

Pomyślałem o tym, zanim spojrzałem na inne odpowiedzi, a potem odkryłem, że Alice użyła tego samego podstawowego pomysłu. Publikowanie i tak, ponieważ jest krótsze niż inne odpowiedzi Haskell.

?bierze dwie liczby całkowite i zwraca a Bool. Użyj jako 331?1021. Falseoznacza, że ​​mnożenie jest łatwe.

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

Wypróbuj online!

  • sto funkcja obliczająca sumę cyfr liczby całkowitej. ( read.purekonwertuje znak jednocyfrowy na liczbę całkowitą).
  • Jeśli parę liczb można łatwo pomnożyć, suma cyfr iloczynu jest równa iloczynowi sum cyfr.
  • I odwrotnie, każde przeniesienie podczas długiego pomnożenia zmniejszy sumę cyfr produktu od tego ideału.
Ørjan Johansen
źródło
1

Haskell , 123 bajty

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

Wypróbuj online! Przykładowe użycie: "331" % "1021"daje True.

Laikoni
źródło
1

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

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

Wypróbuj online!

wyprowadza fałsz dla łatwego, prawda dla łatwego

Xcali
źródło
1

Galaretka , 8 bajtów

;PDḄµṪ⁼P

Wypróbuj online!

Port mojej odpowiedzi Javascript . Nie krótszy niż istniejąca odpowiedź na galaretkę, ponieważ galaretka ma wbudowany potężny splot.

Weź dane jako listę dwóch liczb. Zwraca 1za łatwe, 0za niełatwe.


Wyjaśnienie:


;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).
użytkownik202729
źródło
1

C (gcc) , 104 bajty

Zasadniczo wykonaj mnożenie „ręcznie” przez r [] i ustaw wartość zwracaną, jeśli jakaś kolumna przekroczy 9, ponieważ oznaczałoby to przeniesienie.

Co zaskakujące, było to krótsze niż moja pierwsza próba, w której argumentami były łańcuchy.

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

Wypróbuj online!

gastropner
źródło