Daily Challenge #111 - 99 Bottles of Beer

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)
}

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

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]