Problem z ryżem i szachami


41

Indyjska legenda opowiada historię domniemanego wynalazcy szachów, który zaimponował cesarzowi Indii swoją grą tak bardzo, że otrzymał nagrodę za wszystko, o co poprosił.

Mężczyzna powiedział, że chce dostać ryż. Chciał ziarna ryżu na pierwszy kwadrat szachownicy, dwa na drugi, cztery na trzeci, osiem na czwarty i tak dalej, aż do 64. kwadratu.

Cesarz był zdumiony, że mężczyzna poprosił o tak małą nagrodę, ale kiedy jego matematycy zaczęli liczyć, ostatecznie stracił jedną ze swoich prowincji.

Zadanie

Biorąc pod uwagę długość boku hipotetycznej szachownicy (która wynosi 8 na domyślnej szachownicy) oraz mnożnik między kwadratami (który w legendzie wynosi 2), obliczyć liczbę ziaren ryżu, które cesarz musi zapłacić człowiekowi.

Notatki

  • Długość boku zawsze będzie dodatnią liczbą całkowitą. Mnożnik może być dowolną liczbą wymierną.

  • Jeśli wybrany język nie może wyświetlać bardzo dużych liczb, jest w porządku, o ile Twój program może poprawnie przetwarzać mniejsze dane.

  • Również jeśli wybrany język zaokrągla większe wartości (z notacjami wykładniczymi), nie ma problemu, jeśli te wartości są w przybliżeniu poprawne.

Przypadki testowe

Input (side length, multiplier) => Output
8, 2                            => 18446744073709551615
3, 6                            => 2015539
7, 1.5                          => 850161998.2854
5, -3                           => 211822152361
256, 1                          => 65536
2, 2                            => 15
2, -2                           => -5

Uwaga: wyraźna formuła

result = (multiplier ^ (side ^ 2) - 1) / (multiplier - 1)

Wykonuje się źle multiplier = 1, jak

1 ^ (side ^ 2) - 1 = 0
1 - 1 = 0
0 / 0 != side ^ 2 (as it should be)

Punktacja

To jest golf golfowy. Najkrótsza odpowiedź w bajtach wygrywa.


4
Prawdopodobnie potrzebujesz przypadku testowego, w którym mnożnik wynosi 1, a drugiego, gdzie wynosi 0 (przy założeniu, że oba są poprawne). Także „cokolwiek” jest dość szerokie, czy liczy się pierwiastek kwadratowy z liczby ujemnej? Co powiesz na „ziemniak”? ;) Polecam „dowolną liczbę rzeczywistą” lub coś w tym rodzaju.
FryAmTheEggman

4
If your language of choose can't display too large numbers, it's ok as long as your program can correctly process smaller inputsOstrożnie, to spowodowało problemy w przeszłości. meta.codegolf.stackexchange.com/a/8245/31716
DJMcMayhem

24
... to musiała być bogata prowincja, ponieważ nawet dzisiaj roczna światowa produkcja ryżu jest nadal mniejsza niż 2 ^ 64 ziaren.
vsz

1
@vsz Facet został zabity. Kwota dodana do króla oddającego człowiekowi całe królestwo, więc naturalnie podjęto łatwiejsze wyjście.
cst1992

1
@ cst1992 wersja, którą czytam, mówi, że mężczyzna poddał się na jego prośbę i otrzymał prowincję w prezencie.
user6245072

Odpowiedzi:



27

MATL , 6 bajtów

2^:q^s

Wypróbuj online!

2^   % Take implicit input, say N, and square it: N^2
:q   % Generate array [0 1 ... N^2-1]
^    % Take implicit input, M, and compute [M^0 M^1 ... M^(N^2-1)]
s    % Sum of the array. Implicit display

23

APL, 10 bajtów

⎕⊥1+0×⍳⎕*2

służy do dwukrotnego odczytu danych wprowadzanych przez użytkownika. Jeśli będziemy przechowywać długość boku w s i mnożnika w m , otrzymujemy następujący kod.

m⊥1+0×⍳s*2

A oto jak APL analizuje ten kod:

Objaśnienie algorytmu


4
Lub jako ciąg funkcji: ⊣⊥1⍴⍨⊢×⊢(8 bajtów) Jako interaktywne polecenie REPL ⎕⊥×⍳⎕*2działa również (7 bajtów).
Dennis

19

Python, 40 bajtów

lambda n,m:eval('1+m*('*n*n+'0'+')'*n*n)

Generuje i ocenia ciąg podobny do

1+m*(1+m*(1+m*(1+m*(0))))

która koduje sumę jako wielomian Hornerized z n*nterminami.

Wiele różnych metod dawało bardzo podobne liczby bajtów:

#String evaluation
lambda n,m:eval('1+m*('*n*n+'0'+')'*n*n)   #40

#Direct summation
lambda n,m:sum(m**i for i in range(n*n))   #40
lambda n,m:sum(map(m.__pow__,range(n*n)))  #41

#Direct formula
lambda n,m:n*n*(1==m)or(m**n**2-1)/(m-1)   #40

#Iterative sequence
f=lambda n,m,j=0:j<n*n and 1+m*f(n,m,j+1)  #41
def f(n,m):s=0;exec"s=s*m+1;"*n*n;print s  #41

#Recursive expression
#Fails due to float imprecision of square root
f=lambda n,m:n and 1+m*f((n*n-1)**.5,m)    #39*

2
Ach tak, moje złe. W każdym razie bardzo lubię widzieć różne podejścia, jakie
podjąłeś


11

Haskell, 25 bajtów

n%m=sum$(m^)<$>[0..n*n-1]

Podsumowuje listę [m^0, m^1, ..., m^(n*n-1)].


11

JavaScript (ES2016 / ES7), 31 29 28 bajtów

a=>b=>(b**(a*a)-1)/--b||a*a

Tylko @Bassdrop Cumberwubwubwub i @6 wersja Kaizo ES6, ale z operatorem potęgowania. :) (Nie miałem wystarczającej reputacji, aby skomentować.)

Edycja: /+(b-1)zmieniono na /--b(dzięki @Neil).

Edycja: teraz używa curry (dzięki @MamaFunRoll).


Witamy w PPCG! Twoja odpowiedź jest całkiem dobra!
NoOneIsHere

Witamy! +Operator był test zapomniałem zmieniać się, więc można zgolić 1 bajt przez pominięcie go :)
Bassdrop Cumberwubwubwub

Formuła nie działa dla m = 1: 3
użytkownik6245072

@ user6245072 Czy jesteś na kanale Chrome? Lub w węźle? W węźle włącz flagę harmonii
NiCk Newman

Uratowałbyś /--bbajt lub dwa?
Neil



8

JavaScript ES6, 59 37 35 34 bajtów

a=>b=>(Math.pow(b,a*a)-1)/--b||a*a` 

Dzięki @Kaizo za wygolenie aż 19 bajtów, @Neil za kolejne 2 i @gcampbell za jeszcze 1!

Wypróbuj tutaj

Alternatywne uszkodzone wersje

32 bajty

(a,b)=>(Math.pow(b,a*a)-1)/(b-1)

Przyczyny NaNdla b==1.

30 bajtów

(a,b)=>(Math.pow(b,a*a)-1)/~-b

Przyczyny Infinitydla b==1.5.

28 bajtów

(a,b)=>~-Math.pow(b,a*a)/~-b

Dane wyjściowe 1dla niektórych prawidłowych przypadków testowych.

Stara wersja na 59 bajtów

(a,b)=>Array(a*a).fill``.reduce((c,d,i)=>c+Math.pow(b,i),0)


Dlaczego nie potraktowałeś właśnie przypadku b == 1 w przypadku 32 bajtów? 40 bajtów: (a, b) => b-1? (Math.pow (b, a * a) -1) / (b-1): a * a
Kaizo

@Kaizo masz rację, jestem idiotą: D
Bassdrop Cumberwubwubwub

/~-boczywiście nie jest dobre na ułamkowe b, ale czy /--bpowinno działać, nie?
Neil

Nawiasem mówiąc, grałem w golfa w starej wersji do 47 bajtów:(a,b)=>[...Array(a*a-1)].reduce(s=>s+=p*=b,p=1)
Neil

@Nie masz racji, oczywiście. Właśnie to dostajesz, kiedy spiesz się z odpowiedziami: p Dzięki!
Bassdrop Cumberwubwubwub

6

Java, 132 bajty

import java.math.*;Object e(int n,BigDecimal m){BigDecimal r=BigDecimal.ONE,a=r;for(n*=n;n>1;n--)r=r.add(a=a.multiply(m));return r;}

Bez golfa

import java.math.*;

Object e(int n, BigDecimal m) {
    BigDecimal r = BigDecimal.ONE, a = r;
    for (n *= n; n > 1; n--)
        r = r.add(a = a.multiply(m));
    return r;
}

Notatki

  • Będzie to działać dla dowolnie dużych wyników, zgodnie z wymaganiami OP (Szkoda, że ​​Java obsługuje duże liczby, w przeciwnym razie byłoby to krótsze).

Wyjścia

Input:      8 2.0
Expected:   18446744073709551615
Actual:     18446744073709551615

Input:      3 6.0
Expected:   2015539
Actual:     2015539

Input:      7 1.5
Expected:   850161998.2854
Actual:     850161998.285399449204543742553141782991588115692138671875

Input:      5 -3.0
Expected:   211822152361
Actual:     211822152361

Input:      256 1.0
Expected:   65536
Actual:     65536

Input:      2 2.0
Expected:   15
Actual:     15

Input:      2 -2.0
Expected:   -5
Actual:     -5

Input:      263 359.9
Expected:   ?
Actual:     9709...[176798 digits]...7344.7184...[69160 digits]...6291

6

R, 18 bajtów

sum(m^(1:s^2-1))

Wyjaśnienie:

sum(               # Calculate sum
    m              # Multiplier
     ^             # Exponentiate
      (1:s^2-1))   # Generate sequence from 1 to s(ide)^2-1

5

05AB1E , 5 bajtów

Kod:

nL<mO

Wyjaśnienie:

n      # Compute i ** 2
 L     # Push the list [1, ..., i ** 2]
  <    # Decrement by 1, [0, ..., i ** 2 - 1]
   m   # Power function with implicit input, [0 ** j, ..., (i ** 2 - 1) ** j]
    O  # Sum that all up

Wypróbuj online! .


4

Haskell, 30 bajtów

n#m=sum$take(n^2)$iterate(*m)1

lub równie długi

n%1=n^2
n%m=(m**(n*n)-1)/(m-1)

Pierwsza wersja zaczyna się od 1wielokrotnego mnożenia przez m. Następnie sumuje pierwsze n^2liczby tej sekwencji. Druga wersja to wyraźna formuła, jak widać w innych odpowiedziach.


Nie możesz po prostu zrobić n#m=sum$(m^)<$>[0..n*n-1]?
xnor

@xnor: och, to miłe. Myślę, że jest wystarczająco inny, by uzyskać osobną odpowiedź. Proszę, opublikuj to sam.
nimi

4

J, 10 bajtów

+/@:^i.@*:

Stosowanie

Zaznaczam niektóre liczby całkowite xsufiksem, aby użyć rozszerzonych liczb całkowitych, aby uzyskać dokładne wyniki.

   f =: +/@:^i.@*:
   2x f 8
18446744073709551615
   3x f 6
75047317648499560
   6x f 3
2015539
   1.5 f 7
8.50162e8
   _3x f 5
211822152361
   1 f 256
65536
   2 f 2
15
   _2 f 2
_5

Wyjaśnienie

+/@:^i.@*:
        *:  Square the value s to get s^2
     i.@    Make a range from 0 to s^2 exclusive, [0, 1, ..., s^2-1]
    ^       Using m as the base, calculate the power with the range
            [m^0, m^1, ..., m^(s^2-1)]
+/@:        Sum the entire list and return it

6 bajtów #.*:$*według APL Dude.
FrownyFrog

4

Mathcad, [tbd] bytes (~ 11)

wprowadź opis zdjęcia tutaj

Wykorzystuje wbudowany operator sumowania Mathcada. Pokazuje także symboliczne uproszczenie procesora w celu wygenerowania dokładnej formuły.

Mathcad skutecznie obsługuje dwa silniki przetwarzania równolegle - jeden standardowy zmiennoprzecinkowy IEEE 64/80 bitów, a drugi proces symboliczny o dowolnej długości (MuPad). Standardowa ocena numeryczna jest oznaczona znakiem równości (=), a strzałka w prawo wskazuje ocenę symboliczną.


Schemat zliczania Mathcad jeszcze nie został ustalony, więc nie podano liczby bajtów.

ctl- $ wchodzi do operatora sumowania (Sigma), w tym pustych symboli zastępczych, aby wstawić zmienną sumowania, wartość początkową, wartość końcową i wyrażenie. Przybliżona liczba bajtów = 11.


gdzie jest kod
Abr001am

1
„Kod” rzeczywistego wyzwania jest pierwszym znakiem sumowania (wielka Sigma), który widzisz pod nagłówkiem „Rozwiązanie wyzwania”. Pozostałe bity „kodu” podane są pod nagłówkiem „Warianty rozwiązania”. To, co widzisz na obrazie, jest dokładnie tym, co zapisano w arkuszu Mathcad - Mathcad używa symboli matematycznych do różnych operacji, takich jak suma lub produkt wektorowy, integracja lub różnicowanie funkcji lub operacje logiczne. Większość operatorów można wprowadzać za pomocą kombinacji klawiszy (na przykład ctl-4 dla niejawnej sumy wektorowej lub ctl- & dla iterowanej sumy) lub za pomocą menu lub paska narzędzi.
Stuart Bruff

4

PostgreSQL, 67 66 bajtów

SELECT SUM(m^v)FROM(VALUES(3,6))t(s,m),generate_series(0,s*s-1)s(v)

SqlFiddleDemo

Wejście: VALUES(side, multiplier)


EDYTOWAĆ:

Przeniesiono dane wejściowe do tabeli, wszystkie przypadki jednocześnie:

SELECT s,m,SUM(m^v)FROM i,generate_series(0,s*s-1)s(v)GROUP BY s,m

SqlFiddleDemo

Wynik:

╔══════╦══════╦══════════════════════╗
║  s   ║  m   ║         sum          ║
╠══════╬══════╬══════════════════════╣
║   7  ║ 1.5  ║ 850161998.2853994    ║
║   2  ║ 2    ║ 15                   ║
║   2  ║ -2   ║ -5                   ║
║ 256  ║ 1    ║ 65536                ║
║   5  ║ -3   ║ 211822152361         ║
║   8  ║ 2    ║ 18446744073709552000 ║
║   3  ║ 6    ║ 2015539              ║
╚══════╩══════╩══════════════════════╝

3

TI-Basic, 19 bajtów

Sma długość boku i Mjest mnożnikiem.

Prompt S,M:Σ(M^I,I,0,S²-1

3

Python, 40 bajtów

lambda l,m:sum(m**i for i in range(l*l))

1
lambda l,m:(m**(l*l)-1)/(m-1)
Leaky Nun

W zwykłych językach użycie formuły byłoby krótsze. Użyłem mapy, ponieważ w esolangach mapy byłyby krótsze.
Leaky Nun

Gdzie jest przekreślenie?
Leaky Nun

@KennyLau Nadal pracowałem nad moją odpowiedzią, opublikowałem ją przed zobaczeniem Twojego komentarza.
lub

W porządku, (zostanie jeszcze 7 ...)
Leaky Nun

3

Rubin: 39 bajtów

->s,m{(0...s*s).reduce(0){|a,b|a+m**b}}

Test:

f = ->s,m{(0...s*s).reduce(0){|a,b|a+m**b}}

f[8,2]   # 18446744073709551615
f[3,6]   # 2015539
f[7,1.5] # 850161998.2853994
f[5,-3]  # 211822152361
f[256,1] # 65536
f[2,2]   # 15
f[2,-2]  # -5
f[1,1]   # 1

Kiedy Ruby dostała sumfunkcję? To się zmienia
Value Ink

O nie! To, co uważałem za metodę rubinową, jest w rzeczywistości metodą smutną . Zaktualizowałem odpowiedź.
br3nt

Czy możesz po prostu zmienić język na Rails? Nie wiem o żadnym imporcie, którego byś potrzebował
Value Ink

3

Python, 41 bajtów

Zupełnie nowy w tej grze w golfa, krytyka mile widziana!

lambda n,m:sum(m**i for i in range(n**2))

To jest naprawdę całkiem dobre; )
user6245072

Haha dzięki. Musiałem ponownie znaleźć w Google, jak zrobić lambda w pythonie, ponieważ od jakiegoś czasu nie dotykałem Pythona.
Lang Tran

Witamy w Programowaniu Puzzle i Code Golf! To ładna odpowiedź, ale jest raczej podobna do tej .
Dennis

Ach, nie widziałem, czy są jakieś inne rozwiązania. Czy uratował bajt, robiąc l**lzamiast tego, co zrobiłem?
Lang Tran

l*lw rzeczywistości, co jest krótsze niż l**2.
Dennis

2

Jolf, 18 15 10 bajtów

Dzięki Cᴏɴᴏʀ O'Bʀɪᴇɴ za uratowanie 3 bajtów i skierowanie mnie w kierunku mapowania

uΜzQjd^JwH

Wypróbuj tutaj!

 ΜzQj       Map over an array of 1 -> square(side length)
     d^JwH  Set the current array value to multiplier^(current value - 1)
u           Sum the array

Dobra robota! Możesz usunąć a przed zeta, ponieważ jest to domyślnie wyłączone. Możesz także użyć Mu (mapy) zamiast dla każdego i myślę, że możesz zastąpić literę D reklamą i usunąć zakończenie}.
Conor O'Brien

1
@ Cᴏɴᴏʀ O'Bʀɪᴇɴ Schludnie, wciąż zapominaj o ukrytych częściach Jolfa, są to z pewnością jedne z najlepszych sposobów na pozbycie się kilku bajtów.
puchnie

2

CJam , 9 bajtów

q~2#,f#:+

Wejścia są w odwrotnej kolejności oddzielone znakiem nowej linii lub spacją.

Wypróbuj online!

q~    e# Read input. Evaluate: pushes the two numbers, M and N, onto the stack
2#    e# Square: compute N^2
,     e# Range: generates array [0 1 ... N^2-1]
f#    e# Compute M raised to each element of the array [0 1 ... N^2-1]
:+    e# Fold addition: compute sum of the array [M^0 M^1 ... M^(N^2-1)]

2

PHP, 58 54 bajtów

<?function a($n,$m){$n*=$n;echo(1-$m**$n)/(1-$m)?:$n;}

To po prostu używa formuły sumowania, aby pokazać wartość, po sprawdzeniu, czy mnożnik wynosi 1 (co zwraca NAN w formule).


2

Mathematica, 22 bajty

Tr[#^(Range[#2^2]-1)]&

Tworzy zakres {1, 2, ... s^2}, odejmuje 1, aby utworzyć {0, 1, ..., s^2-1}. Następnie podnieś każdego do mocy mrobienia {m^0, m^1, ..., m^(s^2-1)}i zwróć sumę.

Alternatywnie, Mathematica może użyć jawnej formuły, biorąc swój limit. Wymaga to 29 bajtów.

Limit[(s^#^2-1)/(s-1),s->#2]&

Możesz napisać swoją pierwszą wersję jakoTr[#^Range[#2^2]/#]&
Simon Woods,

1

PARI / GP , 25 bajtów

f(s,m)=sum(i=0,s^2-1,m^s)

Dłuższe, ale szybsze (35 bajtów):

f(s,m)=if(m==1,s^2,(m^s^2-1)/(m-1))

Słodkie (30 bajtów):

f(s,m)=vecsum(powers(m,s^2-1))


1

Lua, 54 47 bajtów

r=0l,m=...for i=0,l^2-1 do r=r+m^i end print(r)

Uruchom z linii poleceń z długością boku tablicy jako pierwszym argumentem i mnożnikiem jako drugim.

Podziękowania dla user6245072 za zapisanie 6 bajtów i Katenkyo za zapisanie dodatkowego 1.


Oryginalna wersja 54-bajtowa:

a,b=...c=1 d=1 for i=2,a^2 do c=c*b d=d+c end print(d)

Witaj i witaj w PPCG! Świetna odpowiedź!
NoOneIsHere

l,m=...r=0 for i=0,l^2 do r=r+m^i end print(r)
user6245072

To powinno zaoszczędzić niektóre bajty.
user6245072

zmiana nazwy d powoduje zapisanie jednego bajtu, ponieważ pozwala pominąć spację w c=1 d=1=> a,b=...c=1g=1 for i=2,a^2 do c=c*b g=g+c end print(g). jeśli sugestia @ user6245072 działa, możesz zapisać bajt na tej samej zasadzie =>r=0l,m=...for i=0,l^2 do r=r+m^i end print(r)
Katenkyo

Biała spacja między r=0i l,m=...jest w każdym razie obowiązkowa, więc się nie zmienia. Pętla powinna być, for i=0,l^2-1ale to moja wina lol.
user6245072

1

𝔼𝕊𝕄𝕚𝕟, 11 znaków / 14 bajtów

⨭⩥ î²)ⓜⁿ⁽í$

Try it here (Firefox/WebKit Nightly only).

Tak, 𝔼𝕊𝕄𝕚𝕟 działa teraz w WebKit Nightly! Obsługa Chrome jest następna.

Wyjaśnienie

⨭⩥ î²)ⓜⁿ⁽í$ // implicit: î = input1, í = input2
   ⩥ î²)       // generate a range [0..î^2)
                     ⓜ      // map over range ($ is mapitem):
        ⁿ⁽í$  //   í^$
⨭            // sum resulting range
              // implicit output

1

ZWROT , 32 bajty

[a:2^0\
{[$¥][a;\^]#[¤¥][+]#]!

Try it here.

Anonimowa lambda, która pozostawia wynik na Stack2. Stosowanie:

8 2[a:2^0\
{[$¥][a;\^]#[¤¥][+]#]!

Wyjaśnienie

[                              ]!  lambda
 a:                                store multiplier to a
   2^                              square side-length
     0\␊                           create range [0..result)
        {                          set current stack to range
         [  ][     ]#              while loop
          $¥                         check if TOS is truthy
              a;\^␌                  if so, push a^TOS to Stack2
                     ␁            set current stack to Stack2
                       [¤¥][+]#    sum Stack2
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.