---

The Complete Guide to Solving the Change-Making Problem in CoffeeScript

The change-making problem is a classic algorithmic puzzle that asks for the minimum number of coins to equal a target value. This is optimally solved in CoffeeScript using a Breadth-First Search (BFS) algorithm, which systematically explores all coin combinations level by level to guarantee the shortest path is found first.

---

The Baker's Dilemma: More Than Just Counting Coins

Imagine you're running a bustling bakery in the charming village of Coinholt. The aroma of fresh bread fills the air. A customer, Denara, a well-known merchant, pays for her meal—a total of 88 units—with a large 100-unit coin. You owe her 12 units in change. You glance at your cash drawer, filled with coins of various denominations: 1, 5, 10, and 25.

Your first instinct might be to grab the largest coin possible, a 10-unit piece, leaving you with 2 units to make. Then you'd add two 1-unit coins. That's three coins in total: [10, 1, 1]. It works, but is it the best way? What if your drawer had coins of values [1, 6, 10]? For a target of 12, a "greedy" approach (taking the largest coin first) would give you [10, 1, 1]. The optimal solution, however, is two 6-unit coins: [6, 6].

This is the crux of the change-making problem. It’s not just about finding a solution; it’s about finding the most efficient one. This challenge mirrors many real-world programming problems where finding the optimal path is critical. In this guide, we will deconstruct this puzzle and build a robust, elegant solution in CoffeeScript, transforming you from a simple coin counter into a master of algorithmic efficiency.

---

What is the Change-Making Problem?

The Change-Making Problem is a foundational challenge in computer science and combinatorial optimization. At its core, it poses a simple question: given a set of coin denominations and a target amount of money, what is the minimum number of coins required to make that exact amount?

This problem forces us to look beyond the most obvious "greedy" solution. A greedy algorithm makes the locally optimal choice at each step with the hope of finding a global optimum. For standard currency systems (like USD or EUR), this works perfectly. However, for arbitrary coin systems, as shown in our [1, 6, 10] example, the greedy choice can lead to a suboptimal result.

Therefore, we need a more exhaustive method that can explore all possibilities intelligently. This is where graph traversal algorithms, specifically Breadth-First Search (BFS), come into play. We can model the problem as a graph where each node is a sum of money we can achieve, and an edge is the addition of a single coin. Our goal is to find the shortest path from the starting node (0) to the target node (the total change amount).

Why a Greedy Approach Fails: A Concrete Example

Let's solidify why the simple, intuitive approach can be a trap. Consider the following scenario from the kodikra learning path:

• Available Coins: [1, 4, 5]
• Target Change: 8

A greedy algorithm would operate as follows:

1. Take the largest coin less than or equal to the remaining target (8). That's 5. Remaining target: 8 - 5 = 3.
2. Take the largest coin less than or equal to the remaining target (3). There is no 4 or 5, so take 1. Remaining target: 3 - 1 = 2.
3. Take another 1. Remaining target: 2 - 1 = 1.
4. Take one last 1. Remaining target: 1 - 1 = 0.

The greedy solution is [5, 1, 1, 1], which uses four coins. However, the truly optimal solution is [4, 4], which uses only two coins. This discrepancy proves that we need a more comprehensive strategy to guarantee the fewest number of coins every time.

---

How to Solve it Optimally with Breadth-First Search (BFS)

Breadth-First Search is the perfect tool for this job because it explores the "graph" of possible sums level by level. Think of it as sending out search parties in concentric circles. The first party to reach the destination has, by definition, taken the shortest path. In our case, the "path length" is the number of coins used.

Here’s the high-level strategy:

1. Start at Zero: We begin at our starting point, a sum of 0, which requires zero coins.
2. Use a Queue: We'll use a queue (a First-In, First-Out data structure) to keep track of the sums we need to explore. We initialize it with our starting sum of 0.
3. Track Visited Sums: To avoid redundant calculations and infinite loops, we need a way to remember which sums we've already found an optimal path to. A hash map or object is perfect for this, where the key is the sum and the value is the list of coins used to get there.
4. Explore Level by Level: We take a sum from the front of the queue. For each available coin, we calculate a new sum. If this new sum is our target, we've found our solution! If not, and if we haven't visited this new sum before, we record the path to it and add it to the back of the queue to be explored later.

This process guarantees that when we first reach our target sum, it will be with the fewest possible coins, because we explored all 1-coin solutions before any 2-coin solutions, all 2-coin solutions before any 3-coin solutions, and so on.

Visualizing the BFS Exploration

The following diagram illustrates how BFS explores the possible sums for a target of 8 with coins [1, 4, 5]. Notice how it finds the [4, 4] path before it ever gets deep enough to find the [5, 1, 1, 1] path.

    ● Start (Sum: 0, Path: [])
    │
    ├─ Level 1 Exploration ─────────
    │
    ├─ (add 1) → ● Sum: 1, Path: [1]
    ├─ (add 4) → ● Sum: 4, Path: [4]
    └─ (add 5) → ● Sum: 5, Path: [5]
    
    │
    ├─ Level 2 Exploration ─────────
    │
    ├─ From Sum 1:
    │   ├─ (add 1) → ● Sum: 2, Path: [1, 1]
    │   ├─ (add 4) → ● Sum: 5 (ignore, already found shorter path)
    │   └─ (add 5) → ● Sum: 6, Path: [1, 5]
    │
    ├─ From Sum 4:
    │   ├─ (add 1) → ● Sum: 5 (ignore)
    │   └─ (add 4) → ◆ Sum: 8, Path: [4, 4]  <== GOAL FOUND!
    │
    └─ From Sum 5:
        └─ ... (exploration stops as goal is found)

---

The CoffeeScript Solution: A Detailed Code Walkthrough

Now, let's translate our BFS strategy into elegant and effective CoffeeScript code. CoffeeScript's clean syntax allows us to express this algorithm with remarkable clarity. We'll implement this as a static method within a Change class, as suggested by the kodikra.com module structure.

# This is our main class container for the algorithm
class Change

  # @findFewestCoins is a static method on the Change class
  # It accepts an array of coin denominations and the target amount
  @findFewestCoins: (coins, targetBalance) ->

    # 1. Handle Edge Cases
    # ---------------------
    # If the target is negative, a solution is impossible.
    throw new Error "target can't be negative" if targetBalance < 0
    # If the target is zero, the solution is an empty set of coins.
    return [] if targetBalance is 0

    # 2. Initialization
    # -----------------
    # The queue stores the balances we need to check. We start with 0.
    queue = [0]
    # The `visited` object stores the shortest coin path to each balance.
    # Key: balance (e.g., 5), Value: coin path (e.g., [5])
    visited = {0: []}

    # 3. Main BFS Loop
    # ----------------
    # Continue as long as there are balances in the queue to explore.
    while queue.length > 0
      # Dequeue the next balance to process. `shift()` removes the first element.
      initialBalance = queue.shift()

      # 4. Explore Next Moves
      # ---------------------
      # Iterate through each available coin denomination.
      for coin in coins
        updatedBalance = initialBalance + coin

        # 5. Check for Solution
        # ---------------------
        # If we hit the target, we're done! Construct the final path and return it.
        if updatedBalance is targetBalance
          # Retrieve the path to the previous balance and add the new coin.
          return visited[initialBalance].concat([coin])

        # 6. Pruning and State Update
        # ---------------------------
        # We only proceed if the new balance is valid and unvisited.
        # - `updatedBalance > targetBalance`: Prunes branches that overshoot the target.
        # - `visited[updatedBalance]`: Prunes branches that lead to a balance we've
        #   already found a shorter or equal-length path to.
        if updatedBalance < targetBalance and not visited[updatedBalance]
          # Mark this new balance as visited, storing the path to get here.
          visited[updatedBalance] = visited[initialBalance].concat([coin])
          # Enqueue this new balance for future exploration.
          queue.push updatedBalance
          
    # 7. Handle No Solution
    # ---------------------
    # If the queue empties and we never found the target, no solution exists.
    throw new Error "no solution is possible"

Line-by-Line Breakdown

Let's dissect this code to understand every piece of the machinery.

• class Change: This simply acts as a namespace or container for our logic, a common practice for organizing code.
• @findFewestCoins: ...: The @ symbol in CoffeeScript is shorthand for this. When used in a class body like this, it defines a static method on the Change class itself, so you can call it directly via Change.findFewestCoins(...) without creating an instance.
• throw new Error "..." if targetBalance < 0: This is a postfix conditional, a syntactic sugar in CoffeeScript. It's a clean way to handle a simple guard clause. Trying to make negative change is a logical impossibility.
• return [] if targetBalance is 0: Another guard clause. The change for 0 is nothing, an empty array. The is keyword in CoffeeScript compiles to JavaScript's strict equality operator ===.
• queue = [0]: Our queue is initialized with the starting "state," which is a balance of 0.
• visited = {0: []}: This is our state-tracking powerhouse. We mark the starting balance of 0 as "visited" and note that the path to get there is an empty array of coins [].
• while queue.length > 0: The heart of the BFS. The loop continues as long as there are potential paths to explore.
• initialBalance = queue.shift(): This is the "dequeue" operation. We take the oldest-added item from the front of the queue to ensure level-by-level exploration.
• for coin in coins: For the current balance, we try adding every possible coin to it.
• if updatedBalance is targetBalance: The success condition! We've reached our goal.
• return visited[initialBalance].concat([coin]): This is the path reconstruction step. We look up the coin path that got us to initialBalance and concatenate the final coin to it. Using .concat() is a safe way to create a new array without modifying the original.
• if updatedBalance < targetBalance and not visited[updatedBalance]: This is the crucial optimization. We check two things:
  1. Does the new balance overshoot the target? If so, ignore it.
  2. Have we seen this updatedBalance before? If so, the previous time we saw it must have been via an equal or shorter path (due to the nature of BFS), so we ignore this longer path.
• visited[updatedBalance] = ... and queue.push updatedBalance: If the new path is valid and optimal so far, we record it in our visited map and add the new balance to the queue for the next level of exploration.
• throw new Error "no solution is possible": If the while loop finishes, it means our queue is empty. We have explored every possible path from 0 without ever reaching the target. Therefore, a solution is impossible with the given coins (e.g., trying to make a change of 3 with only coins of value [2, 4]).

Data Flow within the Algorithm

This diagram shows how the queue and visited data structures interact during the execution of the algorithm.

    ● Start
    │
    ▼
  ┌────────────────────────┐
  │ Initialize:            │
  │ queue = [0]            │
  │ visited = { 0: [] }    │
  └──────────┬─────────────┘
             │
             ▼
  ┌────────────────────────┐
  │ while queue is not empty │
  └──────────┬─────────────┘
             │
             ├─▶ Dequeue `initialBalance` from queue
             │
             ▼
      ┌────────────────┐
      │ for each `coin`│
      └───────┬────────┘
              │
              ├─▶ Calculate `updatedBalance`
              │
              ▼
        ◆ Is it the target? ────────── Yes ─▶ ● Return Path & End
        │
        No
        │
        ▼
        ◆ Is it valid & unvisited? ── No ─▶ (Loop to next coin)
        │
        Yes
        │
        ├─▶ Update `visited` with new path
        │
        └─▶ Enqueue `updatedBalance`
             │
             └────────────────────────────┘ (Loop to next `while` iteration)

---

Pros, Cons, and Performance Considerations

Every algorithm comes with trade-offs. The BFS approach is powerful, but it's essential to understand its strengths and weaknesses.

Pros	Cons / Risks
Guaranteed Optimality: BFS always finds the shortest path in an unweighted graph. This means it will always return the solution with the fewest number of coins.	Memory Usage: The visited object can grow very large if the targetBalance is high, as it needs to store a path for every reachable sum up to the target.
Conceptually Simple: The logic of exploring level by level is intuitive and easier to reason about compared to more complex dynamic programming solutions.	Slower for Certain Inputs: For problems where the optimal solution uses many small coins, BFS might explore a large number of suboptimal paths before finding the solution.
Handles All Coin Systems: Unlike a greedy algorithm, this BFS approach works correctly for any arbitrary set of coin denominations.	No Partial Solution: The algorithm only produces a result once the absolute final answer is found. It cannot provide a "good enough" solution midway through.

Future-Proofing Your Knowledge: While we're implementing this in CoffeeScript, the core BFS algorithm is timeless. This exact logic is used in network routing (finding the fewest hops), web crawlers (exploring sites closest to the root first), and pathfinding in games and robotics. Understanding it deeply will serve you well in any language, from Python and Go to Rust and modern JavaScript/TypeScript.

Looking ahead, the next step in optimization for this class of problems is often Dynamic Programming. A DP solution typically builds a table of optimal solutions for all amounts from 1 up to the target, often resulting in better time complexity and sometimes more optimized space complexity, though it can be less intuitive to grasp initially.

---

Frequently Asked Questions (FAQ)

1. What happens if no solution is possible?

If the `queue` becomes empty before the `targetBalance` is reached, it means every possible combination of coins has been explored without success. In this case, our code correctly throws an error stating that "no solution is possible".

2. Why sort the coins? Is it necessary?

In this specific BFS implementation, sorting the coins is not strictly necessary for correctness. The algorithm will explore all paths regardless of order. However, sorting can sometimes act as a micro-optimization, as it may structure the search in a slightly more orderly fashion, but it does not change the Big O complexity or the final result.

3. How does the performance of this algorithm scale?

The time complexity is roughly O(T * C), where T is the target amount and C is the number of coin denominations. This is because, in the worst case, we might visit every sum from 1 to T, and for each sum, we iterate through all C coins. The space complexity is O(T) to store the `visited` map.

4. Can this problem be solved with recursion?

Yes, it can be solved recursively, often with memoization to avoid re-computing results for the same subproblems (which is essentially a form of dynamic programming). A naive recursive solution without memoization would be extremely inefficient due to recalculating the same states over and over.

5. Is this related to the Knapsack problem?

It's very similar! This is specifically an instance of the Unbounded Knapsack Problem, where you can take an unlimited number of each item (coin). The goal is to fill the "knapsack" (the target value) exactly, minimizing the number of items used.

6. What's the difference between is and == in CoffeeScript?

CoffeeScript's is compiles to JavaScript's strict equality operator (===), which checks for value and type equality without type coercion. The == operator compiles to JavaScript's loose equality operator (==), which performs type coercion and can lead to unexpected behavior (e.g., 0 == "0" is true).

7. Are there more optimized solutions than BFS?

Yes, for many competitive programming scenarios, a Dynamic Programming (DP) approach is preferred. A DP solution would build an array, say `dp`, where `dp[i]` stores the minimum number of coins to make change for amount `i`. This bottom-up approach can be more efficient in terms of execution speed, though it often uses a similar amount of memory.

---

Conclusion: From Theory to Practical Mastery

We've journeyed from a simple baker's dilemma to a robust, optimal algorithmic solution in CoffeeScript. By rejecting a naive greedy approach and embracing the systematic exploration of Breadth-First Search, we built a function that can solve the change-making problem for any set of coins. This process highlights a fundamental lesson in software engineering: the most intuitive solution is not always the most correct or efficient one.

The true value of mastering this kodikra module lies not just in solving this specific puzzle, but in internalizing the BFS pattern. This powerful algorithm is a cornerstone of computer science that you will encounter again and again. By understanding its mechanics, trade-offs, and implementation details, you have added a vital tool to your problem-solving arsenal.

To continue your journey, we highly recommend exploring other algorithmic challenges and solidifying your understanding of fundamental data structures. The path to becoming an expert developer is paved with challenges like these.

Disclaimer: All code in this article is written to be compatible with modern CoffeeScript (v2.x) and assumes compilation to a modern JavaScript environment (ES6+).

Ready for your next challenge? Explore our complete CoffeeScript 8 learning path to build on these concepts. Or, if you want to review the fundamentals, dive deeper into our CoffeeScript language guide.

---

Published by Kodikra — Your trusted Coffeescript learning resource.