import java.util.ArrayList;

import java.util.List;

import java.util.OptionalInt;

import java.util.Set;

import java.util.stream.Stream;

/*

* This program is Java port of the Haskell example at

* https://www.cs.nott.ac.uk/~pszgmh/pgp-countdown.hs

*

* The problem and the solution approaches are explained

* in Prof. Graham Hutton's youtube video at

* https://youtu.be/CiXDS3bBBUo?list=PLF1Z-APd9zK7usPMx3LGMZEHrECUGodd3

*

* This Java program requires JDK 21+

*/

class CountDownProblem {

// 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 -> "/";

};

}

}

// cache enum value array

static final Op[] operators = Op.values();

// 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;

};

}

// 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;

};

}

// 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);

};

}

}

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);

}

}

// eval :: Expr -> [Int]

// 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();

}

};

}

// type Result = (Expr,Int)

record Result(Expr expr, int value) {

@Override

public String toString() {

return expr.toString() + " = " + value;

}

}

// combine'' :: Result -> Result -> [Result]

static List<Result> combine(Result lx, Result ry) {

// (l,x), (r,y) pattern

var l = lx.expr();

var x = lx.value();

var r = ry.expr();

var y = ry.value();

// combine'' (l,x) (r,y) = [(App o l r, apply o x y) | o <- ops, valid' o x y]

return Stream.of(operators).

filter(op -> isValid(op, x, y)).

map(op -> new Result(new App(op, l, r), apply(op, x, y))).

toList();

}

// results' :: [Int] -> [Result]

static List<Result> results(List<Integer> ns) {

// results' [] = []

if (ns.isEmpty()) {

return List.of();

}

// results' [n] = [(Val n,n) | n > 0]

if (ns.size() == 1) {

var n = head(ns);

return n > 0 ? List.of(new Result(new Val(n), n)) : List.of();

}

// results' ns = [res | (ls,rs) <- split ns,

// lx <- results' ls,

// ry <- results' rs,

// res <- combine'' lx ry]

var res = new ArrayList<Result>();

// all possible non-empty splits of the input list

// split :: [a] -> [([a],[a])] equivalent for-loop

for (int i = 1; i < ns.size(); i++) {

var ls = ns.subList(0, i);

var rs = ns.subList(i, ns.size());

var lxs = results(ls);

var rys = results(rs);

for (Result lx : lxs) {

for (Result ry : rys) {

res.addAll(combine(lx, ry));

}

}

}

return res;

}

// List utilities

// : operator

static <T> List<T> cons(T head, List<T> tail) {

final var tailLen = tail.size();

return switch (tailLen) {

case 0 -> List.of(head);

case 1 -> List.of(head, tail.get(0));

case 2 -> List.of(head, tail.get(0), tail.get(1));

case 3 -> List.of(head, tail.get(0), tail.get(1), tail.get(2));

default -> {

var res = new ArrayList<T>(1 + tailLen);

res.add(head);

res.addAll(tail);

yield res;

}

};

}

static <T> T head(List<T> list) {

return list.get(0);

}

static <T> List<T> tail(List<T> list) {

final var len = list.size();

return len == 1 ? List.of() : list.subList(1, len);

}

// subs :: [a] -> [[a]]

static List<List<Integer>> subs(List<Integer> ns) {

// subs [] = [[]]

if (ns.isEmpty()) {

return List.of(List.of());

}

// subs (x:xs)

var x = head(ns);

var xs = tail(ns);

// where yss = sub(xs)

var yss = subs(xs);

// yss ++ map (x:) yss

var res = new ArrayList<List<Integer>>();

res.addAll(yss);

yss.stream().

map(l -> cons(x, l)).

forEach(res::add);

return res;

}

// interleave :: a -> [a] -> [[a]]

// Using Stream<List<Integer> instead of List<List<Integer>>

static Stream<List<Integer>> interleave(int x, List<Integer> ns) {

// interleave x [] = [[x]]

if (ns.isEmpty()) {

return Stream.of(List.of(x));

}

// interleave x (y:ys)

var y = head(ns);

var ys = tail(ns);

// outer : translated as Stream.concat

// (x:y:ys) : map (y:) (interleave x ys)

return Stream.concat(

// x:y:ys == x:ns

Stream.of(cons(x, ns)),

// map (y:) (interleave x ys)

interleave(x, ys).map(l -> cons(y, l))

);

}

// perms :: [a] -> [[a]]

// Using Stream<List<Integer> instead of List<List<Integer>>

static Stream<List<Integer>> perms(List<Integer> ns) {

// perms [] = [[]]

if (ns.isEmpty()) {

return Stream.of(List.of());

}

// perms (x:xs)

var x = head(ns);

var xs = tail(ns);

// concat (map ...) is translated as flatMap

// concat (map (interleave x) (perms xs))

return perms(xs).flatMap(l -> interleave(x, l));

}

// choices :: [a] -> [[a]]

// Using Stream<List<Integer> instead of List<List<Integer>>

static Stream<List<Integer>> choices(List<Integer> ns) {

// concat . map is translated as flatMap

// choices = concat . map perms . subs

return subs(ns).stream().flatMap(CountDownProblem::perms);

}

// solutions'' :: [Int] -> Int -> [Expr]

// Using Stream<Expr> instead of List<Expr>

static Stream<Expr> solutions(List<Integer> ns, int n) {

// solutions'' ns n = [e | ns' <- choices ns, (e,m) <- results' ns', m == n]

return choices(ns).

flatMap(choice -> results(choice).stream()).

filter(res -> res.value() == n).

map(Result::expr);

}

/*

* usage example:

*

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

*/

public static void main(String[] args) {

if (args.length != 2) {

System.err.println("usage: java CountDownProblem.java <comma-separated-values> <target>");

System.exit(1);

}

int target = Integer.parseInt(args[1]);

List<Integer> numbers = Stream.of(args[0].split(",")).map(Integer::parseInt).toList();

// uniqueness check

try {

Set.of(numbers.toArray());

} catch (IllegalArgumentException iae) {

System.err.println(iae);

System.exit(2);

}

var start = System.currentTimeMillis();

solutions(numbers, target).forEach(e -> {

System.out.println(e);

});

System.out.println("Time taken (ms): " + (System.currentTimeMillis() - start));

}

}