In the 1980s the game show Countdown was one of the most popular British TV programs. This article aims to solve its numbers game challenge using Java 21’s language constructs.

The Countdown Problem

One of the challenges of the Countdown game show was to find a way to create a number using other numbers and basic mathematical operators:

• You are given a list of natural numbers and a target natural number. In this hypothesis, we assume that the set of natural numbers does not include 0.
• You can use addition, subtraction, multiplication and division operators.
• You should combine the given numbers and operators to write an expression that evaluates to the given target number.
• A number from the list can be used at most once.
• All intermediate expressions should evaluate to natural numbers.
• Not any target number can be represented using the Countdown challenge conditions.

For example, let’s assume [1, 3, 5, 7, 10, 25, 50] are the list of natural numbers given. The target number to achieve is 765. One possible solution is (25 - 10)*(50 + 1). If we change the target number to 831 then the problem has no solutions. As manually calculating all solutions will take us time, let’s create a simple Java program that finds all the expressions for the given list of numbers and target number.

A simple and elegant solution to the Countdown problem, written in Haskell programming language, is presented in a youtube video by Prof Graham Hutton. However, in the next sections we will port the Haskell solution to Java 21 language constructs.

Note

Knowing Haskell is not mandatory to understand the Java port. If you do know Haskell, the Java solution includes comments about the corresponding Haskell expression.

Java Implementation

We can start by representing the supported operations (addition, subtraction, multiplication and division) as enum:

// data Op = Add | Sub | Mul | Div
   enum Op {
       Add, Sub, Mul, Div;

       // instance show Op
       @Override
       public String toString() {
          return switch (this) {
             case Add -> "+";
             case Sub -> "-";
             case Mul -> "*";
             case Div -> "/";
          };
       }
   }
}

Next, we need to define an expression, that can be either a number, or two sub-expressions combined with an operator. In Java, we can represent the expression as a sealed interface and its components as record subtypes.

Certain common operations are allowed in the Val and App record subtypes, so the Expr sealed interface defines the behavior of brak and toStr functions. These methods allow us to construct strings and properly place parenthesis around mathematical terms.

  // data Expr = Val Int | App Op Expr Expr
   sealed interface Expr {
      // brak helper for instance Show Expr
      static String brak(Expr expr) {
         return switch (expr) {
            // brak (Val n) = show n
            case Val(var n) -> Integer.toString(n);

            // brak e       = "(" ++ show e ++ ")"
            default -> "(" + toStr(expr) + ")";
         };
      }

      // instance Show Expr
      static String toStr(Expr expr) {
         return switch (expr) {
            // show (Val n)     = show n
            case Val(var n) -> Integer.toString(n);

            // show (App o l r) = brak l ++ show o ++ brak r
            //          where
            //             brak (Val n) = show n
            //             brak e       = "(" ++ show e ++ ")"
            case App(var op, var l, var r) -> brak(l) + op + brak(r);
         };
      }
   }

Each of the records that implements the Expr interface calls toStr method inside their toString() implementation.

    record Val(int v) implements Expr {
      // instance Show Expr
      @Override
      public String toString() {
         return Expr.toStr(this);
      }
   }

   record App(Op op, Expr l, Expr r) implements Expr {
      // instance Show Expr
      @Override
      public String toString() {
         return Expr.toStr(this);
      }
   }

Lastly, we can represent valid expressions and their values as Java records.

// type Result = (Expr,Int)
record Result(Expr expr, int value) {
	@Override
	public String toString() {
		return expr.toString() + " = " + value;
	}
} 

The Haskell implementation defines some utility functions:

• to check if an expression is valid and
• to apply an expression and get its result.

We can write a switch expression to check if an expression is valid:

   // valid' :: Op -> Int -> Int -> Bool
   static boolean isValid(Op op, int x, int y) {
      return switch (op) {
         case Add -> x <= y;
         case Sub -> x > y;
         case Mul -> x != 1 && y != 1 && x <= y;
         case Div -> y != 1 && x % y == 0;
      };
   }

To apply an expression and get its result we will use pattern matching for switch and record patterns:

 // apply :: Op -> Int -> Int -> Int
   static int apply(Op op, int x, int y) {
      return switch (op) {
         case Add -> x + y;
         case Sub -> x - y;
         case Mul -> x * y;
         case Div -> x / y;
      };
   }

Finally, we need to combine generation and evaluation for all the possible solutions. In Haskell, this following piece of code achieves that:

   eval (Val n)     = [n | n > 0]
   eval (App o l r) = [apply o x y | x <- eval l,
                                  y <- eval r,
                                  valid o x y]

In Java, we can use again pattern matching for switch and record patterns:

   // Using OptionalInt instead of List<Integer>
   static OptionalInt eval(Expr expr) {
      return switch (expr) {
         // eval (Val n)     = [n | n > 0]
         case Val(var n) -> n > 0 ? OptionalInt.of(n) : OptionalInt.empty();


         // eval (App o l r) = [apply o x y | x <- eval l,
         //                                   y <- eval r,
         //                                   valid o x y]
         case App(var op, var l, var r) -> {
            var x = eval(l);
            var y = eval(r);
            yield (x.isPresent() && y.isPresent() &&
                   isValid(op, x.getAsInt(), y.getAsInt())) ?
               OptionalInt.of(apply(op, x.getAsInt(), y.getAsInt())) :
               OptionalInt.empty();
         }
      };
   }

Running the Java program without compilation

You can find the complete example of CountDownProblem.java in the samples repository. Since the example requires JDK 21, you can run it without compilation using the source launcher support.

  java CountDownProblem.java 1,3,7,10,25,50 765

To conclude, Java is an expressive language and using its latest language constructs helped us represent the data and operations of the Countdown problem in a natural way.