## DEV Community is a community of 662,276 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Daily Challenge #230 - Beeramid

dev.to staff
The hardworking team behind dev.to ❤️

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:

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)

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

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

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

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

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

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:

$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
$P_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 < \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.