loading...

Daily Challenge #230 - Beeramid

thepracticaldev profile image dev.to staff ・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!

Posted on by:

thepracticaldev profile

dev.to staff

@thepracticaldev

The hardworking team behind dev.to ❤️

Discussion

pic
Editor guide
 

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
 

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
 

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

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:

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.