KataPotter

_kata.rb

# http://codingdojo.org/kata/Potter/

UNIT_PRICE = 8
DISCOUNTS = [0, 0.05, 0.1, 0.2, 0.25]

def price(books)
  # Count the number of occurences of each book
  counts = books.group_by(&:itself).values.map(&:size)

  raise if counts.size > DISCOUNTS.size

  # Calculate how many groups of different books we can make, maximising
  # the number of groups containing the most books
  groups = counts.sort.reverse.push(0).each_cons(2).map { |a, b| a - b }

  # There is a better discount on 2 groups of 4 books than on one group
  # of 5 books and another group of 3 books. (This is because 2 * 0.2 is
  # greater than 0.1 + 0.25.) Thus, merge as many groups of 5 books and
  # 3 books as possible into groups of 4 books.
  if groups[4]
    # Calculate the number of groups of 5 books and 3 books that can be
    # merged into groups of 4 books.
    n = [groups[4], groups[2]].min
    
    groups[4] -= n
    groups[2] -= n
    groups[3] += 2 * n
  end
  
  # Calculate total price
  groups.map.with_index { |c, i| c * (i + 1) * (1 - DISCOUNTS[i]) }.sum * UNIT_PRICE
end

price([1, 1, 2, 2, 3, 3, 4, 5]) # 51.2

kata-naive.js

// http://codingdojo.org/kata/Potter/
// Naive implementation

DISCOUNTS = [0, 0.05, 0.1, 0.2, 0.25]
PRICE = 8
function price(books) {
  const counts = new Map()
  for (book of books) {
    const count = counts.get(book) || 0
    counts.set(book, count + 1)
  }

  return PRICE * [...counts.values()]
    .sort((a, b) => b - a)
    .reduce((sum, c, i, groups) => sum + (c - (groups[i + 1] || 0)) * (i + 1) * (1 - DISCOUNTS[i]), 0)
}

price([1, 1, 2, 2, 3, 3, 4, 5]) // 51.6

kata-naive.rb

# http://codingdojo.org/kata/Potter/
# Naive implementation

DISCOUNTS = [0, 0.05, 0.1, 0.2, 0.25]
PRICE = 8
def price(books)
  books.group_by(&:itself).values.map(&:size).sort.reverse.push(0).each_cons(2).map { |a, b| a - b }.map.with_index { |c, i| c * (i + 1) * (1 - DISCOUNTS[i]) }.sum * PRICE
end

price([1, 1, 2, 2, 3, 3, 4, 5]) # 51.6