Solving hard 3rd-grade math

Question

This is a problem proposed by Vietnamese for a 3rd-grade student international contest in Malaysia, 2017. You have to find 3 numbers with conditions:

[][][][] - [][][][] - [] = 2017.

Each digit in each cell range from 1 to 9 and they must be different each other.

I can't solve by hand, so I have made a program to find results. My code works but is too long, so does anyone have a shorter way?

public class Third_gradeProblem {
public static void main(String[] args) {
int a,b,c,d,e,f,g,h,i;
int so1,so2,so3;
for(a=1;a<=9;a++) {
    for(b=1;b<=9;b++) {
        for(c=1;c<=9;c++) {
            for(d=1;d<=9;d++) {
                for(e=1;e<=9;e++) {
                    for(f=1;f<=9;f++) {
                        for(g=1;g<=9;g++) {
                            for(h=1;h<=9;h++) {
                                for(i=1;i<=9;i++) {
                                    so1=a*1000+b*100+c*10+d;
                                    so2=e*1000+f*100+g*10+h;
                                    so3=i;
                                    if((so1-so2-so3==2017)&&(a!=b)&&(a!=c)&&
(a!=d)&&(a!=e)&&(a!=f)&&(a!=g)&&(a!=h)&&(a!=i)&&(b!=c)&&(b!=d)&&(b!=e)&&
(b!=f)&&(b!=g)&&(b!=h)&&(b!=i)&&(c!=d)&&(c!=e)&&(c!=f)&&(c!=g)&&(c!=h)&&
(c!=i)&&(d!=e)&&(d!=f)&&(d!=g)&&(d!=h)&&(d!=i)&&(e!=f)&&(e!=g)&&(e!=h)&&
(e!=i)&&(f!=g)&&(f!=h)&&(f!=i)&&(g!=h)&&(g!=i)&&(h!=i)) {
                                        System.out.println(so1+" "+so2+" 
"+so3);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

}
}

}

Results:

4613 2587 9;
4613 2589 7;
7412 5386 9;
7412 5389 6;
7421 5396 8;
7421 5398 6;

Answer 1

The main performance problem of your code is that you check for duplicate digits only in the innermost loop, although a collision between e.g. a and b can be detected already in the second loop.

This way you generate 387420489 digit combinations and throw away 99.9% of them (it's only 362880 permutations of 9 digits). Moving the duplicates checks to the outermost place possible can potentially speed up your program by a factor of 1000.

And there might be better algorithms, but on Code Review we concentrate on improving your original code instead of inventing something new.

Answer 2

Your solution starts a at 1. But you know that abcd - efgh - i = 2017 which means that a must be >2. That's 20% of your search space gone, and it's the 20% you execute first!

Also, there are relationships between the numbers that you are ignoring. Again, for example, a-e must be either 2 or 3 (because a high f could cause a borrow, like 42 - 19). So you could rewrite your loops as:

for (a = 3; a <= 9; a++) {
    ...
        for (e = a - 3; e <= a - 2; e++) {

(Also worth noting: removing spaces from your code doesn't actually make it go faster. But it does make it harder to read.)

And given that you always use the same digits in the same places, there's really no point in doing the multiplication over and over again. You should just pre-multiply:

for (a = 2000; a <= 9000; a += 1000) {
    for (b = 100; b <= 900; b += 100) { 
        for (c = 10; c <= 90; c += 10) { 

Answer 3

You should compute the permutations and filter those out which satisfy your condition. You can find a comprehensive article about permutations with code example here.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;



public class Permutations {
    public static void main(String[] args) {    
        Integer[] arr = {1,2,3,4,5,6,7,8,9}; 
        Permutations.of(Arrays.asList(arr)).map(s->s.collect(Collectors.toList())).filter(i->equals2017(i)).forEach(System.out::println);
    }  

    public static boolean equals2017(List<Integer> list){
        int x = Integer.parseInt(list.subList(0, 4).stream().map(String::valueOf).collect(Collectors.joining()));
        int y = Integer.parseInt(list.subList(4, 8).stream().map(String::valueOf).collect(Collectors.joining()));
        int z = list.get(8);
        return x-y-z == 2017;
    }
     public static <T> Stream<Stream<T>> of(final List<T> items) {
        return IntStream.range(0, factorial(items.size())).mapToObj(i -> permutation(i, items).stream());
    }

    private static int factorial(final int num) {
        return IntStream.rangeClosed(2, num).reduce(1, (x, y) -> x * y);
    }

    private static <T> List<T> permutation(final int count, final LinkedList<T> input, final List<T> output) {
        if (input.isEmpty()) { return output; }

        final int factorial = factorial(input.size() - 1);
        output.add(input.remove(count / factorial));
        return permutation(count % factorial, input, output);
    }

    private static <T> List<T> permutation(final int count, final List<T> items) {
        return permutation(count, new LinkedList<>(items), new ArrayList<>());
    }
}

(Code taken from here)