Project Euler #93: Arithmetic expressions

  • + 0 comments

    import java.util.*;

    public class LongestSequence { private static final double EPSILON = 0.00001;

    // Evaluate all arithmetic operations of any two elements of "numbers", mark their result in "used" as true
    private static void eval(List<Double> numbers, boolean[] used) {
        if (numbers.size() == 1) {
            double result = numbers.get(0) + EPSILON;
            if (Math.abs(result % 1) > 10 * EPSILON) return;
            int index = (int) (result + EPSILON);
            if (index >= 0 && index < used.length) used[index] = true;
            return;
        }
    
        List<Double> next;
        for (int i = 0; i < numbers.size(); i++) {
            for (int j = i + 1; j < numbers.size(); j++) {
                double a = numbers.get(i);
                double b = numbers.get(j);
    
                next = new ArrayList<>(numbers);
                next.remove(j);
                next.remove(i);
    
                next.add(a + b);
                eval(next, used);
                next.set(next.size() - 1, a - b);
                eval(next, used);
                next.set(next.size() - 1, b - a);
                eval(next, used);
                next.set(next.size() - 1, a * b);
                eval(next, used);
                if (b != 0) {
                    next.set(next.size() - 1, a / b);
                    eval(next, used);
                }
                if (a != 0) {
                    next.set(next.size() - 1, b / a);
                    eval(next, used);
                }
            }
        }
    }
    
    // Evaluate all expressions and count how many numbers from 1 to x can be expressed without any gaps
    private static int getSequenceLength(List<Double> numbers) {
        boolean[] used = new boolean[1000];
        eval(numbers, used);
    
        int result = 0;
        while (used[result + 1]) result++;
        return result;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
    
        int numDigits = scanner.nextInt();
        List<Double> numbers = new ArrayList<>();
        for (int i = 0; i < numDigits; i++) {
            numbers.add(scanner.nextDouble());
        }
    
        System.out.println(getSequenceLength(numbers));
    
        scanner.close();
    }
    

    }