| 8 | 9 | * @return {number} - in cents |
| 9 | 10 | */ |
| 10 | 11 | export const cost = (books) => { |
| 11 | | throw new Error('Remove this line and implement the function'); |
| 12 | // Edge Case: Empty basket |
| 13 | if (books.length === 0) { |
| 14 | return 0; |
| 15 | } |
| 16 | |
| 17 | // Count how many of each book we have (books are 1-5, so we use index 0-4) |
| 18 | const counts = Array(5).fill(0); |
| 19 | for (const book of books) { |
| 20 | counts[book - 1]++; |
| 21 | } |
| 22 | |
| 23 | // Edge Case: All same books (no discount possible) |
| 24 | const maxSameBooks = Math.max(...counts); |
| 25 | if (counts.filter(count => count > 0).length === 1) { |
| 26 | return maxSameBooks * 800; // 800 cents = $8 |
| 27 | } |
| 28 | |
| 29 | // Convert to a list of counts and sort in descending order |
| 30 | const sortedCounts = counts.filter(count => count > 0).sort((a, b) => b - a); |
| 31 | |
| 32 | // Edge Case: Single book purchase |
| 33 | if (sortedCounts.length === 1) { |
| 34 | return sortedCounts[0] * 800; |
| 35 | } |
| 36 | |
| 37 | // For optimization, we try different grouping strategies |
| 38 | // The key insight is that we want to maximize the number of larger sets |
| 39 | // but sometimes breaking a 3+3 into 4+2 gives better results |
| 40 | |
| 41 | // We'll use a recursive approach with memoization to find the minimum cost |
| 42 | const memo = new Map(); |
| 43 | |
| 44 | function calculateMinCost(countsArray) { |
| 45 | // Normalize the counts array by sorting in descending order |
| 46 | const key = [...countsArray].sort((a, b) => b - a).join(','); |
| 47 | if (memo.has(key)) { |
| 48 | return memo.get(key); |
| 49 | } |
| 50 | |
| 51 | // Edge Case: No books left |
| 52 | if (countsArray.every(count => count === 0)) { |
| 53 | memo.set(key, 0); |
| 54 | return 0; |
| 55 | } |
| 56 | |
| 57 | let minCost = Infinity; |
| 58 | |
| 59 | // Try all possible set sizes (from 1 to number of unique books available) |
| 60 | const uniqueBooks = countsArray.filter(count => count > 0).length; |
| 61 | for (let setSize = 1; setSize <= uniqueBooks; setSize++) { |
| 62 | // Try to form a set of this size by selecting setSize different books |
| 63 | function tryFormSet(counts, targetSize, startIdx, selected) { |
| 64 | if (selected.length === targetSize) { |
| 65 | return [selected.slice()]; |
| 66 | } |
| 67 | |
| 68 | const combinations = []; |
| 69 | for (let i = startIdx; i < counts.length; i++) { |
| 70 | if (counts[i] > 0) { |
| 71 | selected.push(i); |
| 72 | combinations.push(...tryFormSet(counts, targetSize, i + 1, selected)); |
| 73 | selected.pop(); |
| 74 | } |
| 75 | } |
| 76 | |
| 77 | return combinations; |
| 78 | } |
| 79 | |
| 80 | const combinations = tryFormSet(countsArray, setSize, 0, []); |
| 81 | |
| 82 | // Try each combination |
| 83 | for (const combination of combinations) { |
| 84 | const newCounts = [...countsArray]; |
| 85 | let canFormSet = true; |
| 86 | |
| 87 | // Take one book from each index in the combination |
| 88 | for (const bookIndex of combination) { |
| 89 | if (newCounts[bookIndex] > 0) { |
| 90 | newCounts[bookIndex]--; |
| 91 | } else { |
| 92 | canFormSet = false; |
| 93 | break; |
| 94 | } |
| 95 | } |
| 96 | |
| 97 | if (canFormSet) { |
| 98 | // Calculate discount based on set size |
| 99 | let discount = 0; |
| 100 | if (setSize === 2) discount = 0.05; |
| 101 | else if (setSize === 3) discount = 0.10; |
| 102 | else if (setSize === 4) discount = 0.20; |
| 103 | else if (setSize === 5) discount = 0.25; |
| 104 | |
| 105 | const setCost = setSize * 800 * (1 - discount); |
| 106 | const remainingCost = calculateMinCost(newCounts); |
| 107 | const totalCost = setCost + remainingCost; |
| 108 | |
| 109 | if (totalCost < minCost) { |
| 110 | minCost = totalCost; |
| 111 | } |
| 112 | } |
| 113 | } |
| 114 | } |
| 115 | |
| 116 | memo.set(key, minCost); |
| 117 | return minCost; |
| 118 | } |
| 119 | |
| 120 | // Edge Case: Large quantities of books - handled by memoization |
| 121 | return Math.round(calculateMinCost(sortedCounts)); |
| 12 | 122 | }; |
| 123 | |
| 124 | // Handled Edge Cases: empty basket, single book purchase, all books are the same title, multiple copies of each book type, large quantities of books |
| 125 | } |