drlobo drlobo - 2 years ago 87
Java Question

How to design an algorithm to calculate countdown style maths number puzzle

I have always wanted to do this but every time I start thinking about the problem it blows my mind because of its exponential nature.

The problem solver I want to be able to understand and code is for the countdown maths problem:

Given set of number X1 to X5 calculate how they can be combined using mathematical operations to make Y.
You can apply multiplication, division, addition and subtraction.

So how does

1,3,7,6,8,3
make
348
?

Answer:
(((8 * 7) + 3) -1) *6 = 348
.

How to write an algorithm that can solve this problem? Where do you begin when trying to solve a problem like this? What important considerations do you have to think about when designing such an algorithm?

Answer Source

Very quick and dirty solution in Java:

public class JavaApplication1
{

    public static void main(String[] args)
    {
        List<Integer> list = Arrays.asList(1, 3, 7, 6, 8, 3);
        for (Integer integer : list) {
            List<Integer> runList = new ArrayList<>(list);
            runList.remove(integer);
            Result result = getOperations(runList, integer, 348);
            if (result.success) {
                System.out.println(integer + result.output);
                return;
            }
        }
    }

    public static class Result
    {

        public String output;
        public boolean success;
    }

    public static Result getOperations(List<Integer> numbers, int midNumber, int target)
    {
        Result midResult = new Result();
        if (midNumber == target) {
            midResult.success = true;
            midResult.output = "";
            return midResult;
        }
        for (Integer number : numbers) {
            List<Integer> newList = new ArrayList<Integer>(numbers);
            newList.remove(number);
            if (newList.isEmpty()) {
                if (midNumber - number == target) {
                    midResult.success = true;
                    midResult.output = "-" + number;
                    return midResult;
                }
                if (midNumber + number == target) {
                    midResult.success = true;
                    midResult.output = "+" + number;
                    return midResult;
                }
                if (midNumber * number == target) {
                    midResult.success = true;
                    midResult.output = "*" + number;
                    return midResult;
                }
                if (midNumber / number == target) {
                    midResult.success = true;
                    midResult.output = "/" + number;
                    return midResult;
                }
                midResult.success = false;
                midResult.output = "f" + number;
                return midResult;
            } else {
                midResult = getOperations(newList, midNumber - number, target);
                if (midResult.success) {
                    midResult.output = "-" + number + midResult.output;
                    return midResult;
                }
                midResult = getOperations(newList, midNumber + number, target);
                if (midResult.success) {
                    midResult.output = "+" + number + midResult.output;
                    return midResult;
                }
                midResult = getOperations(newList, midNumber * number, target);
                if (midResult.success) {
                    midResult.output = "*" + number + midResult.output;
                    return midResult;
                }
                midResult = getOperations(newList, midNumber / number, target);
                if (midResult.success) {
                    midResult.output = "/" + number + midResult.output;
                    return midResult
                }
            }

        }
        return midResult;
    }
}

UPDATE

It's basically just simple brute force algorithm with exponential complexity. However you can gain some improvemens by leveraging some heuristic function which will help you to order sequence of numbers or(and) operations you will process in each level of getOperatiosn() function recursion.

Example of such heuristic function is for example difference between mid result and total target result.

This way however only best-case and average-case complexities get improved. Worst case complexity remains untouched.

Worst case complexity can be improved by some kind of branch cutting. I'm not sure if it's possible in this case.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download