# Daily Challenge #230 - Beeramid

Daily Challenge (258 Part Series)

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!

Daily Challenge (258 Part Series)

### Discussion 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


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


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


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

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