Book Store in Common-lisp: Complete Solution & Deep Dive Guide

The Complete Guide to Solving the Book Store Discount Algorithm in Common Lisp

Calculating the lowest possible price for a shopping cart with complex, tiered discounts is a classic computer science problem. This guide provides a complete solution in Common Lisp, breaking down the logic for grouping items into unique sets to maximize savings, a common challenge in e-commerce and algorithmic thinking.

Have you ever stared at a coding problem, thinking the solution was obvious, only to be stumped by a hidden edge case? You build a simple, greedy algorithm that works for most scenarios, but it fails spectacularly on a specific input, leaving you wondering where you went wrong. This is the exact experience many developers have with the Book Store discount problem.

The challenge isn't just applying discounts; it's about finding the most financially optimal way to group items before the discounts are even calculated. In this deep dive, we'll not only solve this puzzle using the power and elegance of Common Lisp but also dissect the crucial flaw in the most intuitive approach. You'll walk away with a robust solution and a deeper understanding of combinatorial optimization.

What is the Book Store Pricing Problem?

The Book Store problem, a popular module in the kodikra.com learning path, simulates a real-world e-commerce scenario. A bookstore wants to sell a popular 5-book series and offers discounts to encourage customers to buy different books from the series. The goal is to write a function that calculates the lowest possible price for any given combination of books.

The pricing rules are as follows:

One book costs $8.00.
Discounts apply only to sets of different books.
A set of 2 different books gets a 5% discount.
A set of 3 different books gets a 10% discount.
A set of 4 different books gets a 20% discount.
A set of 5 different books gets a 25% discount.

For example, if a customer buys two copies of Book 1 and one copy of Book 2, the best way to group them is one set of two different books (Book 1, Book 2) and one remaining copy of Book 1. The price would be calculated on the discounted set plus the full price of the single book.

Why This Problem is Deceptively Complex

At first glance, a simple "greedy" strategy seems logical: always create the largest possible set of unique books from the basket, calculate its price, and repeat with the remaining books until none are left. This approach feels efficient and correct.

However, this greedy algorithm has a critical flaw. Consider a basket with 8 books: two copies each of Books 1, 2, and 3, plus one copy each of Books 4 and 5.

The Greedy Approach:

Create the largest possible unique set: a 5-book set (1, 2, 3, 4, 5).
Remaining books: one copy each of Books 1, 2, and 3.
Create the next largest set: a 3-book set (1, 2, 3).
Total Price = (Price of 5-book set) + (Price of 3-book set).

The Optimal Approach:

Create a 4-book set (1, 2, 3, 4).
Remaining books: one copy each of Books 1, 2, 3, and 5.
Create another 4-book set (1, 2, 3, 5).
Total Price = (Price of 4-book set) + (Price of 4-book set).

Let's calculate the cost. The base price of a book is $8.00.

Greedy Cost: (5 * 8 * 0.75) + (3 * 8 * 0.90) = $30.00 + $21.60 = $51.60
Optimal Cost: (4 * 8 * 0.80) + (4 * 8 * 0.80) = $25.60 + $25.60 = $51.20

The optimal approach is cheaper! The core challenge is realizing that sometimes, breaking down larger groups into slightly smaller, more balanced groups yields a better overall discount. Specifically, a combination of a 5-book set and a 3-book set is always more expensive than two 4-book sets.

How to Model and Solve the Problem in Common Lisp

To solve this, we need a multi-step process. We'll first use the greedy approach to group the books and then apply a specific optimization rule to correct the "5+3 vs 4+4" scenario.

Step 1: Counting Book Frequencies

The input is a list of book identifiers (e.g., '(1 2 1 3 4)). The first step is to count how many copies of each unique book we have. A hash table is the perfect data structure for this task in Common Lisp, offering efficient key-value storage and lookup.

(defun count-frequencies (books)
  "Counts the frequency of each book in the list.
   Returns a hash-table mapping book-id -> count."
  (let ((counts (make-hash-table)))
    (dolist (book books counts)
      (incf (gethash book counts 0)))))

Step 2: Forming Greedy Groups

Next, we'll iterate as long as there are books left in our frequency map. In each iteration, we'll form a new group by taking one of each available book type. The size of this new group is simply the number of unique book types that had a count greater than zero.

This logic effectively "peels off" one layer of unique books at a time, forming the largest possible sets first.

● Start with book list
│
▼
┌──────────────────┐
│ count-frequencies │
└────────┬─────────┘
         │
         ▼
┌──────────────────┐
│  Create Groups   │
│ (Greedy Strategy)│
└────────┬─────────┘
         │
         ▼
┌──────────────────┐
│ Optimize Groups  │
│ (5+3 -> 4+4)     │
└────────┬─────────┘
         │
         ▼
┌──────────────────┐
│ Calculate Price  │
└────────┬─────────┘
         │
         ▼
● End with final cost

Step 3: The Critical Optimization

After forming the initial groups (represented as a list of their sizes, e.g., '(5 3)), we apply our correction. We check if a group of size 5 and a group of size 3 exist. If they do, we remove them and add two groups of size 4 instead. We repeat this process until no more 5-and-3 pairs can be found.

Step 4: Calculating the Final Price

Finally, we iterate through our optimized list of group sizes and calculate the price for each using the specified discount rates. Summing these up gives us the final, minimal price.

The Complete Common Lisp Solution

Here is the full implementation, combining all the steps into a cohesive solution. This code is designed to be clear, idiomatic, and robust, following best practices from the kodikra.com Common Lisp curriculum.

;;; This solution is part of the exclusive kodikra.com learning path.

(defpackage #:book-store
  (:use #:cl)
  (:export #:calculate-price))

(in-package #:book-store)

(defconstant +book-price+ 800
  "The base price of a single book in cents to avoid floating point issues.")

(defun get-discount (group-size)
  "Returns the discount percentage for a given group size."
  (case group-size
    (2 0.05)
    (3 0.10)
    (4 0.20)
    (5 0.25)
    (otherwise 0.0)))

(defun calculate-group-price (group-size)
  "Calculates the price for a single group of books."
  (let* ((total-price (* group-size +book-price+))
         (discount (get-discount group-size))
         (discount-amount (* total-price discount)))
    (- total-price discount-amount)))

(defun count-book-frequencies (books)
  "Counts frequencies of each book and returns a hash-table."
  (let ((counts (make-hash-table)))
    (dolist (book books counts)
      (incf (gethash book counts 0)))))

(defun create-greedy-groups (counts)
  "Creates groups based on a greedy algorithm: always form the largest set possible.
   Returns a list of group sizes."
  (loop
    ;; Get all books that are still in stock (count > 0)
    for available-books = (loop for k being the hash-keys of counts
                                when (> (gethash k counts) 0)
                                collect k)
    ;; If no books are available, stop the loop
    while available-books
    ;; The size of the new group is the number of unique available books
    collect (length available-books)
    ;; Decrement the count for each book used in this new group
    do (dolist (book available-books)
         (decf (gethash book counts)))))

(defun optimize-groups (groups)
  "Optimizes the groups by replacing any 5-book and 3-book set
   with two 4-book sets, as this is always cheaper."
  (let ((group-list (copy-list groups)))
    (loop
      while (and (find 5 group-list) (find 3 group-list))
      do (progn
           (setf group-list (remove 5 group-list :count 1))
           (setf group-list (remove 3 group-list :count 1))
           (push 4 group-list)
           (push 4 group-list)))
    group-list))

(defun calculate-price (books)
  "Calculates the minimum price for a given list of books.
   The final result is divided by 100 to convert from cents to dollars."
  (if (null books)
      0.0
      (let* ((counts (count-book-frequencies books))
             (initial-groups (create-greedy-groups counts))
             (optimized-groups (optimize-groups initial-groups))
             (total-price-in-cents
               (reduce #'+ (mapcar #'calculate-group-price optimized-groups))))
        (/ total-price-in-cents 100.0))))

Code Walkthrough

Constants and Helpers:
- +book-price+ is set to 800 (cents) to completely avoid floating-point inaccuracies during intermediate calculations. This is a common and robust practice in financial software.
- get-discount uses a case statement for a clean and efficient way to map group sizes to their respective discount percentages.
- calculate-group-price is a straightforward helper that computes the final price for a single group after applying its discount.
count-book-frequencies:
This function takes the raw list of books. It initializes an empty hash-table and iterates through the list. For each book, it increments its count in the hash table using incf and gethash. The 0 in (gethash book counts 0) provides a default value if the book isn't yet in the table.
create-greedy-groups:
This is the heart of the initial grouping logic. It uses a loop that continues as long as there are books with counts greater than zero. Inside the loop, it first builds a list of available-books. The size of this list becomes the size of our new group. It then collects this size and, crucially, decrements the count for each book that was just added to the group.
optimize-groups:
This function implements the key insight of the problem. It runs a loop that checks for the presence of both a 5 and a 3 in the list of group sizes. If found, it uses remove with :count 1 to remove one instance of each, then adds two 4s to the list. This continues until no more such pairs can be found.
calculate-price (Main Function):
This function orchestrates the entire process. It handles the edge case of an empty book list. Otherwise, it calls the helper functions in sequence: count frequencies, create greedy groups, optimize the groups, and finally, calculate the total price. mapcar applies calculate-group-price to each size in the final group list, and reduce #'+ sums up the results. The final value is divided by 100.0 to return the price in dollars.

Running the Code and Seeing it in Action

You can test this solution in a Common Lisp REPL (Read-Eval-Print Loop), such as one provided by SBCL (Steel Bank Common Lisp).

First, save the code as a file, for example, book-store.lisp. Then, start your REPL and load the file.


$ sbcl
* (load "book-store.lisp")
T
* (in-package #:book-store)
#<PACKAGE "BOOK-STORE">

Now you can call the function with different test cases:


;; Simple case: one of each book
BOOK-STORE> (calculate-price '(1 2 3 4 5))
30.0

;; The tricky case: 2x(1,2,3) and 1x(4,5)
BOOK-STORE> (calculate-price '(1 1 2 2 3 3 4 5))
51.2

;; Another complex case
BOOK-STORE> (calculate-price '(1 1 2 2 3 3 4 4 5 5))
60.0

;; Four groups of four is cheaper than two groups of five and two groups of three
BOOK-STORE> (calculate-price '(1 1 1 1 2 2 2 2 3 3 3 3 4 4 5 5))
102.4

The output confirms that our optimization logic correctly handles the critical edge case, providing the true minimum price.

Alternative Approaches and Considerations

While our heuristic-based solution is elegant and correct for the specific rules of this problem, it's worth considering other algorithmic paradigms for more complex scenarios.

Dynamic Programming

For a generalized version of this problem with more complex discount rules, a dynamic programming (DP) approach might be necessary. DP would involve building up a solution by solving smaller subproblems first. You could, for instance, calculate the minimum price for all subsets of the book basket, storing the results (memoization) to avoid re-computation. This would be more computationally expensive but could handle rules our current heuristic doesn't cover.

Recursive Search

Another approach is a recursive search (or backtracking) algorithm that explores all possible valid groupings of books. At each step, the algorithm would try to form a group of size 1, 2, 3, 4, or 5, and then recursively call itself on the remaining books. This would guarantee the optimal solution but could be very slow for large baskets due to the combinatorial explosion of possibilities.

The logic flow for a recursive search would look something like this:

● start_price(books)
│
├─ books empty? ─→ return 0
│
▼
┌──────────────────────────┐
│ Generate all possible    │
│ next valid groups (g1, g2, ...) │
└────────────┬─────────────┘
             │
             ▼
min( price(g1) + start_price(books - g1),
     price(g2) + start_price(books - g2),
     ... )

Pros and Cons of Our Chosen Method

Aspect	Pros	Cons
Performance	Very fast. The greedy grouping and single optimization pass are efficient, avoiding exponential complexity.	May not be optimal if discount rules change (e.g., if two 5-book sets were cheaper than a 4-book and a 6-book set).
Simplicity	The logic is relatively straightforward and easy to understand compared to full DP or recursive solutions.	The need for the "5+3 -> 4+4" special case feels like a patch rather than a generalized algorithm.
Maintainability	Code is clean, well-structured, and easy to modify for the existing rules.	Adding new discount rules might require re-evaluating the optimization logic completely.

Frequently Asked Questions (FAQ)

Why can't I just apply a discount based on the total number of unique books?: The discounts are specifically defined for "sets" of different books. If you have two copies of Book 1 and two of Book 2, you have two sets of two different books, not one set of four. The grouping is the most important part of the problem.
Is this a dynamic programming problem?: It has the properties of an optimization problem where DP could be used (optimal substructure). However, due to the specific discount structure, a simpler greedy approach with a single corrective heuristic is sufficient and much more performant. A full DP solution would be overkill but would be a valid way to solve it.
How does Common Lisp's functional nature help here?: Functions like mapcar and reduce allow for expressive and concise data transformation. For example, (reduce #'+ (mapcar #'calculate-group-price optimized-groups)) is a very clear, functional way to say "apply the price calculation to every group size, then sum the results." This avoids manual loops and accumulator variables.
Why use cents (e.g., 800) instead of dollars (8.0) for the price?: Using integers for monetary calculations is a standard best practice in software engineering. Floating-point numbers (like 8.0) can introduce tiny precision errors (e.g., 29.9999999997) that accumulate over many calculations. By working with cents, we ensure all math is exact until the final division.
What is the performance complexity of this solution?: Let N be the total number of books and K be the number of unique book types (max 5). Counting frequencies is O(N). The greedy grouping loop runs at most N times, and inside it, we iterate over K keys, so it's roughly O(N*K). The optimization loop is very fast as the number of groups is small. The overall performance is very efficient and largely linear with the number of books.
Could this logic be adapted for a different number of books in the series?: Yes, but you would need to re-evaluate the optimization heuristics. If the series had 7 books, you'd have to check if a 7+5 set is better or worse than two 6-book sets, and so on. The core structure of counting, grouping, and optimizing would remain, but the specific optimization rules would change.

Conclusion

The Book Store discount problem is a perfect illustration of how the most intuitive algorithm isn't always the most optimal one. By diving deep into the problem's constraints, we uncovered a subtle but critical edge case that required a specific heuristic to solve correctly. Our Common Lisp solution effectively balances readability and performance, using a greedy approach followed by a targeted optimization to achieve the correct result every time.

This challenge, featured in the kodikra.com Common Lisp module, teaches more than just syntax; it forces a deeper consideration of algorithmic design. The final code is a testament to Common Lisp's strength in symbolic manipulation and data processing, allowing for an elegant and powerful solution.

Disclaimer: The code in this article is written for modern Common Lisp implementations (tested on SBCL 2.4.0). While it uses standard features, behavior in older or different Lisp environments may vary. To learn more about the language, explore our complete Common Lisp guide.

Published by Kodikra — Your trusted Common-lisp learning resource.

kodikra

Search this blog