dev.to staff

Posted on Apr 21, 2020

Daily Challenge #230 - Beeramid

#challenge

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!

Top comments (5)

Paula Gearon • Apr 22 '20 • 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 • Apr 22 '20

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 P_n cups.
As n becomes large then: 2n³ ≫ 3n² + 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 P_n 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 n³ ≫ n²) 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.

roberthparry • Dec 7 '20 • 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 + 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 • Apr 21 '20

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

Valts Liepiņš • Apr 21 '20 • 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..]

DEV Community

Daily Challenge #230 - Beeramid

Top comments (5)

Read next

Navigating Concurrency for Large-Scale Systems

Connecting database with API

Consumer tech problem, developer's solution: A new smartphone, an old bug

Download MODIS files Using PyModis Part2