M. kay M. kay - 2 months ago 8
Java Question

Go through every combination of 1s and 2s to add to 11.

This is the exam question that I'm trying to make a program for:

You decide to take the stairs and to climb either 1 or 2 stairs at a time, at any given time. In how many different ways can you get up a flight of 11 stairs?




I'm fairly new to programming. Although I understand most things within Java, I can't really think in the way that I need to in order to solve problems like these. What advice would you give me to help me to improve the way in which I tackle these problems. Also, I have a week to get decent at programming, what would you advise me to do in order to get to this?

Like I said, I do have a very solid understanding of Java. It's just the way that I think about problems. I'm also pretty good at Maths. I just can't get everything to click. I'm bad at solving even the simplest of problems when programming, often writing things which are long and unnecessary. Any help would be much appreciated.

Thanks.

Answer

Well, what do you want to program? If you want to solve mathematical problems, you could have a look a Project Euler. That is a collection of problems similar to that one you posted. If the exam consists of such questions, this is the way to go.

That said, when doing enterprise programming (with Spring, Hibernate, zillions of frameworks) it is possible to avoid such kind of problems. You won't need it very much, although can be useful to learn about abstractions.

For your problem: a (very inefficient) first attempt could be:

public static int a1(List<Integer> l ){
    if (l.stream().mapToInt(Integer::intValue).sum() > 11){
        return 0;
    }
    if (l.stream().mapToInt(Integer::intValue).sum()== 11){
        System.out.println("l = " + l);
        return 1;
    }
    List<Integer> l1 = Stream.concat(l.stream(), Stream.of(1)).collect(Collectors.toList());
    List<Integer> l2 = Stream.concat(l.stream(), Stream.of(2)).collect(Collectors.toList());
    return a1(l1) + a1(l2);
}

You can call that with

int rec = a1(Collections.emptyList());

Obviously, it is very inefficient to do the summing every time. It could be improved by using a second parameter which does the summing and remembers it. Also, using a language which allows to express List operations more succinctly, the code will be more elegant.

public static int a2(List<Integer> l , int sum){
        if (sum > 11){
            return 0;
        }
        if (sum== 11){
            System.out.println("l = " + l);
            return 1;
        }
        final List<Integer> l1 = Stream.concat(l.stream(), Stream.of(1)).collect(Collectors.toList());
        final List<Integer> l2 = Stream.concat(l.stream(), Stream.of(2)).collect(Collectors.toList());
        return a2(l1,sum+1) + a2(l2,sum+2);
    }

Call it with

int rec2 = a2(Collections.emptyList(),0);

Now, we might have realized that is not necessary to create all those lists. Of course, if you create them, it allows you to print them and debug your program to see it the results it gets are reasonable.

public static int a3(int sum){
    if (sum > 11){
        return 0;
    }
    if (sum== 11){
        return 1;
    }

    return a3(sum+1)
            + a3(sum+2);
}

Call that with

int rec3 = a3(0);

By now, we might have realized that (or looked it up on Math SE) this is equivalent to the fibonacci sequence. So although the last version is much more efficient without creating the lists, it still gets unfeasible for large numbers. An efficient fibonacci implementation also can be found here: Fast Fibonacci recursion