DEV Community

loading...

Daily Challenge #230 - Beeramid

dev.to staff
The hardworking team behind dev.to ❤️
・1 min read

Let's pretend your company just hired your friend from college and paid you a referral bonus. Awesome! To celebrate, you're taking your team out to the terrible dive bar next door and using the referral bonus to buy, and build, the largest three-dimensional beer can pyramid you can. And then probably drink those beers, because let's pretend it's Friday too.

A beer can pyramid will square the number of cans in each level - 1 can in the top level, 4 in the second, 9 in the next, 16, 25...

Complete the beeramid function to return the number of complete levels of a beer can pyramid you can make, given the parameters of:

1) your referral bonus, and

2) the price of a beer can

For example:

beeramid(1500, 2); // should === 12
beeramid(5000, 3); // should === 16

Tests:
beeramid(9, 2)
beeramid(21, 1.5)
beeramid(-1, 4)


This challenge comes from kylehill on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Discussion (6)

Collapse
roberthparry profile image
roberthparry • Edited

Here's my C solution,
Notice that there is no need for any iteration because (taking number of cans = N and number of levels = L)

N=1+22+32+...+L2=L(L+1)(2L+1)/6    L3/3<N<(L+1)3/3    L<(3N)1/3<L+1    L=(3N)1/3orL=(3N)1/31 N = 1 + 2^2 + 3^2 + ... + L^2 = L(L+1)(2L+1)/6 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \newline \implies L^3/3 < N < (L+1)^3/3 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \newline \implies L < (3N)^{1/3} < L+1 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \newline \implies L = \lfloor (3N)^{1/3} \rfloor \quad or \quad L = \lfloor (3N)^{1/3} \rfloor - 1 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad

int beeramid(double bonus, double price) {
    if (bonus < price) return 0;
    int cans = floor(bonus / price);
    int levels = floor(cbrt(3.0*cans));
    return levels*(levels + 1)*(2*levels + 1) > 6*cans ? levels - 1 : levels;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
vidit1999 profile image
Vidit Sarkar

Here is a Python Solution,

def beeramid(bonus, price):
    canCount = int(bonus/price)
    level = 0

    while((level+1)**2 <= canCount):
        level += 1
        canCount -= level*level

    return level

Test Cases,

print(beeramid(1500, 2)) # output -> 12
print(beeramid(5000, 3)) # output -> 16
print(beeramid(9, 2)) # output -> 1
print(beeramid(21, 1.5)) # output -> 3
print(beeramid(-1, 4)) # output -> 0
Collapse
citizen428 profile image
Michael Kohl • Edited

Ruby, using a lazy, infinite enumerator:

ROWS = (1..).lazy.map { |n| n * n }

def beeramid(bonus, price)
  cans = bonus / price
  ROWS.take_while { |n| (cans -= n) >= 0 }.count
end
Collapse
cipharius profile image
Valts Liepiņš • Edited

Haskell solution using lazy, infinite list of cans:

import Data.List (findIndex)

beeramid :: Double -> Double -> Int
beeramid m p = 
  case findIndex (> cans) levels of
    Just level -> level
    Nothing    -> 0
  where
    cans = m / p
    levels = scanl1 (+) . fmap (^2) $ [1..]
Collapse
quoll profile image
Paula Gearon • Edited

Clojure. Not very terse, but it gets a solution in constant time

(defn faul [n] 
  (let [n2 (* n n) 
        n3 (* n2 n)] 
    (/ (+ n3 n3 n2 n2 n2 n) 6)))

(defn layers [n]
  (let [est (int (Math/pow (* 3 n) (/ 1 3)))]
    (first (filter #(>= n (faul %)) (range est 0 -1)))))

(defn beeramid [bonus price] (or (layers (/ bonus price)) 0))

Testing:

=> (beeramid 1500 2)
12
=> (beeramid 5000 3)
16
=> (beeramid 9 2)
1
=> (beeramid 21 1.5)
3
=> (beeramid -1 4)
0
Collapse
quoll profile image
Paula Gearon

To follow up on my solution, I borrowed from the Wikipedia article on Square Pyramidal Numbers. This provides a formula for the sum of squares as a special case of Faulhaber's formula:

Pn=k=1nk2=2n3+3n2+n6 P_n = \sum_{k=1}^n k^2 = \frac {2n^3 + 3n^2 + n} 6
So if we have n layers, then that will have a total of Pn cups.
As n becomes large then: 2n3 ≫ 3n2 + n
Pn=2n36+(3n2+n6)Pn>n33P_n = \frac {2n^3} 6 + \Big( \frac {3n^2 + n} 6 \Big) \newline P_n > \frac {n^3} 3 \newline
Since the layers is n and the cups in the pyramid is Pn then this gives a bound of:
layers<3cups3layers < \sqrt[3]{3 \cdot cups}
Consequently, my code creates an estimate of the number of layers using this formula, and counts down from there applying the Faulhaber formula to check if the result is less than or equal to the provided number of cups.

Using this method, a small numbers of cups will require 2 guesses, but as the number of cups gets higher (and n3n2) then it is more likely to get it on the first guess. I told it to keep testing while the number of layers until 1, but it never actually gets beyond 2 attempts.