IBM Ponder This January 2025 - Regular and Bonus Questions

The January 2025 edition of IBM’s Ponder This puzzle (IBM Research | Ponder This | January 2025 Challenge) turned out to be a fascinating (and somewhat tricky) exercise in applying search algorithms to a classic problem: measuring specific water volumes using three jugs. Even more challenging, there’s a bonus problem that requires finding an optimal rational volume for one of the jugs and demonstrating that 1 liter (with a very tight tolerance) can be measured in only 11 steps.

In this blog post, I’ll walk you through:

The puzzle description
Key insights for solving it
My C# solution (including the bonus)
How the code works under the hood

1. Puzzle Description

Here’s the short version of what the January 2025 IBM Ponder This puzzle asks:

You have three jugs:

Jug A has a volume of $\sqrt{5}$ liters.
Jug B has a volume of $\sqrt{3}$ liters.
Jug C has a volume of $\sqrt{2}$ liters.

You can do only three types of operations:

Fill a jug to the top (from a tap).
Empty a jug entirely (into a sink).
Pour water from one jug into another until either the source jug is empty or the destination jug is full.

The twist:

We want to measure exactly 1 liter, but because $\sqrt{5}$ , $\sqrt{3}$ , and $\sqrt{2}$ are all irrational, we cannot measure exactly 1 liter in a finite number of steps.
So, a tolerance is introduced: any state where one of the jugs is between 0.9997 and 1.0003 liters (that is, $1 \pm 0.0003$ ) is considered a correct measurement.
We must find a shortest sequence of operations that yields 1 liter (within the given tolerance) in one of the jugs.

Bonus Problem

The bonus problem changes jug C to a rational volume $V_C = \frac{p}{q}$ (still keeping jug A = $\sqrt{5}$ and jug B = $\sqrt{3}$ ), with the constraints:

$V_C < \sqrt{3}$ .
You must measure 1 liter (within $\pm 10^{-8}$ ) in 11 steps.
11 steps is indeed the minimum.
Among all such volumes, you want the $q$ (in $\frac{p}{q}$ ) to be as small as possible.

The result: you submit

The fraction $\frac{p}{q}$
The 11-step sequence (using the same format: a number followed by two-letter codes)

2. Key Insights

State Space Representation
Each state is uniquely defined by the exact volumes of water in jugs A, B, and C. We can store these volumes in a triple $(vol_A, vol_B, vol_C)$ . Because of floating-point imprecision, we need a careful “rounding” or discretization so we don’t accidentally visit the same state repeatedly.
Breadth-First Search (BFS)
BFS is a straightforward way to find the shortest path (in terms of steps) to reach a goal state. We place the initial state (all jugs empty) in a queue and explore moves. When a new valid state is reached, it’s enqueued. Once we find a state that meets our “1 liter ± tolerance” condition, we can reconstruct the path.
Handling Floating-Point Precision
With irrational volumes like $\sqrt{5}$ , $\sqrt{3}$ , $\sqrt{2}$ , floating-point precision is a major issue. In my code, I multiply volumes by a certain power of 10 to convert them to integers (or near-integers) so I can store them in a hash set, preventing repeated states.
Bonus Problem Strategy
For the bonus, we systematically try rational candidates $\frac{p}{q}$ for jug C, with $q$ starting at 2, 3, 4, etc., searching for the condition $V_C < \sqrt{3}$ . For each candidate, we run the BFS again with an even tighter error margin ( $\pm 10^{-8}$ ) and check if a solution can be found in exactly 11 steps. Once found, we stop.

3. My C# Solution

Here’s the full solution code. You can see that it implements a BFS over states and then either finds the minimal sequence of steps for the irrational case ( $\sqrt{2}$ jug) or tries many rational volumes for the bonus question.

Scroll down if you want to jump directly to the explanation.

/* IBM Ponder This January 2025, by Marcelo De Barros
 * Approach:
 * 1. BFS
 * 2. State is the three jugs
 * 3. Helper functions to deal with floating point numbers
 * 4. DFS to print final path
 * 5. State key calculate based on current volumes
 * 6. Bonus question requires brute force to find the final ratio
**/

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main(string[] args)
    {
        if (args.Length != 1 || (!args[0].Equals("regular") && !args[0].Equals("bonus")))
        {
            Console.WriteLine("Usage: IBMPonderThisJan.exe <regular OR bonus>");
            return;
        }

        bool regularQuestion = args[0].Equals("regular");

        double ERR = 3.0 / 10000.0;  // 0.0003
        if (!regularQuestion) 
            ERR = 1.0 / 100000000.0; // 1e-8 for the bonus

        double CalculatePrecision()
        {
            double dec = 0;
            double tempErr = ERR;

            while (tempErr < 1)
            {
                dec++;
                tempErr *= 10;
            }

            return (double)Math.Pow(10, dec + 1);
        }

        double PRECISION = CalculatePrecision();

        if (!regularQuestion)
        {
            Console.WriteLine("Started processing for Bonus question at time: {0}", DateTime.Now.ToLongTimeString());
            bool foundSolution = false;
            int MAX = 10000;
            for (int q = 2; !foundSolution && q < MAX; q++)
            {
                for (int p = q + 1; !foundSolution && p < MAX; p++)
                {
                    double jugC = 1.0 * p / q;
                    if (jugC >= Math.Sqrt(3))
                        break;
                    int nSteps = Process(p, q, ERR, PRECISION);
                    if (nSteps == 11)
                    {
                        foundSolution = true;
                        Console.WriteLine("Solution: {0}/{1}", p, q);
                        Console.WriteLine("Finished processing for Bonus question at time: {0}", DateTime.Now.ToLongTimeString());
                        break;
                    }
                }
            }
        }
        else
        {
            // For the regular puzzle, pass sentinel p=-1, q=1 so the Jug constructor reverts to sqrt(2)
            Process(-1, 1, ERR, PRECISION);
        }
    }

    static int Process(int p, int q, double ERR, double PRECISION)
    {
        Queue<JugQueueItem> queue = new Queue<JugQueueItem>();
        HashSet<string> configVisited = new HashSet<string>();

        Jug jugA = new Jug('A'); // sqrt(5)
        Jug jugB = new Jug('B'); // sqrt(3)
        Jug jugC = new Jug('C', (double)1.0 * p / q); // either sqrt(2) or rational

        // Pre-initialize BFS with each jug individually tapped
        jugA.Tap();
        JugQueueItem jqi = new JugQueueItem(null, "TA", jugA, jugB, jugC, 1, PRECISION, p, q);
        queue.Enqueue(jqi);
        configVisited.Add(jqi.key);
        jugA.Empty();

        jugB.Tap();
        jqi = new JugQueueItem(null, "TB", jugA, jugB, jugC, 1, PRECISION, p, q);
        queue.Enqueue(jqi);
        configVisited.Add(jqi.key);
        jugB.Empty();

        jugC.Tap();
        jqi = new JugQueueItem(null, "TC", jugA, jugB, jugC, 1, PRECISION, p, q);
        queue.Enqueue(jqi);
        configVisited.Add(jqi.key);
        jugC.Empty();

        while (queue.Count > 0)
        {
            JugQueueItem currentJqi = queue.Dequeue();

            // Check if current state is a solution (within ERR of 1 liter)
            if ((currentJqi.jugA.currentVolume >= 1 - ERR && currentJqi.jugA.currentVolume <= 1 + ERR) ||
                (currentJqi.jugB.currentVolume >= 1 - ERR && currentJqi.jugB.currentVolume <= 1 + ERR) ||
                (currentJqi.jugC.currentVolume >= 1 - ERR && currentJqi.jugC.currentVolume <= 1 + ERR))
            {
                string path = "";
                BuildPath(currentJqi, ref path);
                Console.WriteLine("Found Solution for error threshold = {0}:", ERR);
                Console.WriteLine("{0} {1}", currentJqi.numberSteps, path);
                return currentJqi.numberSteps;
            }

            // For the bonus, skip if we're over 11 steps
            if (p > 0 && currentJqi.numberSteps > 11) 
                return 0;

            // Enqueue all possible moves from here...
            // [Empty, Tap, Transfer between jugs]
            // ...
            // (Code that systematically tries each of the 9 possible moves)
            // ...
            EnqueueNextStates(currentJqi, queue, configVisited, p, q, ERR, PRECISION);
        }

        return 0; // If no solution found
    }

    static void EnqueueNextStates(JugQueueItem currentJqi,
                                  Queue<JugQueueItem> queue,
                                  HashSet<string> configVisited,
                                  int p, int q,
                                  double ERR, double PRECISION)
    {
        // This function handles:
        // 1) Emptying each jug
        // 2) Filling each jug (tap)
        // 3) Transferring water between pairs of jugs
        // ...
        // (Implementation omitted in this snippet for brevity,
        // but it's essentially what we posted in the original code)
    }

    static void BuildPath(JugQueueItem jugItem, ref string path)
    {
        if (jugItem != null)
        {
            path = jugItem.configFrom + " " + path;
            BuildPath(jugItem.jqiFrom, ref path);
        }
    }

    static bool IsZero(double val, double PRECISION)
    {
        return Math.Abs(val) <= 1.0 / PRECISION;
    }
}

// Helper classes: JugQueueItem, Jug
// ...
// (Same code as in the original for Jug, JugQueueItem)

You’ll notice in the code:

Process(p, q, ERR, PRECISION) is the BFS “engine.”
Before we start BFS, we add three initial states to our queue: one in which jug A is filled, one in which jug B is filled, and one in which jug C is filled. This ensures we explore all possibilities quickly.
For the bonus, we loop over integer pairs $(p, q)$ to define a rational volume $\frac{p}{q}$ for jug C, check if it’s < $\sqrt{3}$ , then run BFS. If we get a solution in exactly 11 steps, we print it.

4. How the Code Works

Initialization
- Read args[0]: either “regular” or “bonus”.
- Set the error margin (ERR) accordingly:
  - $0.0003$ for the main puzzle
  - $10^{-8}$ for the bonus
Precision Calculation
- We determine how many digits we need to multiply volumes by to avoid floating-point collisions. For instance, if ERR is $3 \times 10^{-4}$ , we might multiply volumes by $10^4$ or $10^5$ .
BFS
- We create a queue of states. A state is captured in a JugQueueItem, which has:
  - References to the volumes in jugs A, B, C
  - A pointer to the previous state (so we can reconstruct the path once we find the solution)
  - The operation (configFrom) that led to this state (e.g., “TA” for Tap Jug A)
- We pop items off the queue, check if they meet the solution condition (jug volume is between 1 - ERR and 1 + ERR). If they do, we reconstruct the path and print the result.
- Otherwise, we enqueue all neighboring states, i.e., all possible single-step moves from that state.
Rational Jug
- For the bonus question, jugC is replaced by a rational volume $\frac{p}{q}$ .
- We systematically increment q and p to explore rational volumes below $\sqrt{3}$ .
- If BFS finds a solution in 11 steps, we’ve met the puzzle’s bonus criteria.
Early Stop
- For the bonus puzzle, if our BFS goes beyond 11 steps, we stop searching with that (p, q) because we only care about sequences of exactly 11 steps.

Wrapping Up

Performance:
The BFS does a tremendous amount of exploration, especially in the bonus question while searching for the right fraction. Caching states by using a hashed “state key” (rounded volumes) is essential to avoid exponential blowups.
The Bonus:
It does take a while for the bonus solution to run - takes about ~3h in my Costco laptop. I'm sure there are better ways to optimize the archaic brute-force approach.

Thanks, ACC

Search This Blog

Another Casual Coder