Daily Challenge #111 - 99 Bottles of Beer

You all know the lyrics to the song "99 Bottles of Beer on the Wall", right? If not check out this link.

Instead of removing just one bottle in each iteration, we want to remove one more bottle than in the previous iteration (i.e. start with 99, then 98, then 96, 93, 89, etc.)

The Challenge: Write a method that takes the initial number of beers on the wall and returns the number of iterations needed to remove all the bottles, in addition to providing the number of bottles removed in the last iteration. (as a tuple or as a string).

Bonus — do the math, not just a simple loop (because that wouldn't be much of a challenge, would it?)

Good luck!

---

This challenge comes from @peledzohar here on DEV. Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[kesprit]

My solution in Swift (without Bonus it's saturday 😛) :

func numberOfBottles(numberOfBottle: Int) -> (restOfBottles: Int, loop:Int) {
    guard numberOfBottle > 0 else { return (0,0) }
    guard numberOfBottle != 1 else { return (1,1) }
    var number = 1
    var loop = 0
    var numberOfBottle = numberOfBottle

    while (numberOfBottle - number) > 0 {
        loop += 1
        numberOfBottle -= number
        number += 1
    }
    return (numberOfBottle,loop)
}

Edit: Thank you to @vo_kononenko for to find my mistake

[Vitaliy Kononenko]

It looks like number *= 2 at the end of the loop should be replaced with number += 1, because the number of removed bottles on each iteration increases by 1, not doubles.

[kesprit]

It's right ! I do that too fastly. Thank you for your attention.

[Vitaliy Kononenko]

Here is O(log(n)) solution using Kotlin. We use the arithmetic progression formula to calculate the sum from 1 to n without a loop with O(1) complexity. And after we use the binary search to find the number of iterations needed with O(log(n)) complexity. This will work for very large values of n, although I do not think anybody will have such a big number of beers on the wall:)

Result for n=Long.MAX_VALUE=9223372036854775807 is (4294967296, 2147483647).

import java.math.BigInteger

/**
 * @param n initial number of beers on the wall
 * @return Pair(number of iterations needed to remove all the bottles, number of bottles removed in the last iteration)
 */
fun bottlesOfBeer(n: BigInteger): Pair<BigInteger, BigInteger> {
    require(n >= BigInteger.ZERO)

    if (n == BigInteger.ZERO) return Pair(BigInteger.ZERO, BigInteger.ZERO);
    if (n == BigInteger.ONE) return Pair(BigInteger.ONE, BigInteger.ONE);

    val numberOfIterations = findIndex(n);
    val sum = sumFromOneTo(numberOfIterations);

    return if (sum != n) {
        Pair(numberOfIterations.inc(), n - sum);
    } else {
        Pair(numberOfIterations, n - sumFromOneTo(numberOfIterations.dec()))
    }
}

/**
 * Calculate the sum using arithmetic progression formula (a1=1, d=1) with O(1) complexity
 * @param n positive number
 * @return sum of all numbers from 1 to n inclusive (1+2+...+(n-1)+n)
 */
fun sumFromOneTo(n: BigInteger): BigInteger {
    require(n >= BigInteger.ONE);

    return n * (n + BigInteger.ONE) / (2.toBigInteger());
}

/**
 * @param n positive number
 * @return i: (sumFromOneTo(i) <= n) and (sumFromOneTo(i + 1) > n)
 */
private fun findIndex(n: BigInteger): BigInteger {
    require(n >= BigInteger.ONE);

    return binarySearchIndex(BigInteger.ONE, n, n);
}

private fun checkIndex(i: BigInteger, n: BigInteger): Boolean {
    require(i >= BigInteger.ONE);
    require(n >= BigInteger.ONE);

    return (sumFromOneTo(i) <= n) && (sumFromOneTo(i.inc()) > n);
}

/**
 * @param start start of the search interval
 * @param end end of the search interval
 * @param n positive number
 * @return i: (sumFromOneTo(i) <= n) and (sumFromOneTo(i + 1) > n) and (start <= i <= end)
 */
private fun binarySearchIndex(start: BigInteger, end: BigInteger, n: BigInteger): BigInteger {
    require(start >= BigInteger.ONE);
    require(start <= end);
    require(n >= BigInteger.ONE);

    if (checkIndex(start, n)) return start;
    if (checkIndex(end, n)) return end;

    require(start != end) { "Index does not exist" };

    val mid = (start + end) / 2.toBigInteger();
    val sumToMid = sumFromOneTo(mid);

    return if (sumToMid > n) {
        binarySearchIndex(start, mid, n);
    } else {
        binarySearchIndex(mid, end, n);
    }
}

[Jon Bristow]

This is as close as I can get to “no string declared more than once”

module Beer
  ( song
  ) where

import qualified Data.Char as Char
import qualified Data.List as List

bottlesOfBeer :: Int -> String
bottlesOfBeer n = " bottle" ++ plural ++ " of beer"
  where
    plural =
      case n of
        1 -> ""
        _ -> "s"

onTheWall :: Int -> String
onTheWall n = howMany n ++ " on the wall"

howMany :: Int -> String
howMany n = countStr ++ bottlesOfBeer n
  where
    countStr =
      case n of
        0 -> "no more"
        _ -> show n

capitalize :: String -> String
capitalize (h:r) = Char.toUpper h : r

line2start :: Int -> String
line2start 0 = "Go to the store and buy some more"
line2start n = "Take " ++ theOne ++ " down and pass it around"
  where
    theOne =
      case n of
        1 -> "it"
        _ -> "one"

next 0 = 99
next n = pred n

outputLine :: [Int -> String] -> Int -> String
outputLine fs = List.intercalate ", " . sequence fs

verse :: Int -> String
verse =
  List.intercalate "" .
  map (++ ".\n") .
  mapM
    outputLine
    [[capitalize . onTheWall, howMany], [line2start, onTheWall . next]]

song :: String
song = List.intercalate "\n" $ map verse [99,98 .. 0]