Combinations?!

How does one compute them?

Seriously as a newb it's my first time dealing with this problem.

I would appreciate some help.

The problem I was to solve is Euler's Problem 15.

This is my code.

It works like a charm of 2x2 grid.

It gives an out of memory error (even with 3GB of memory dedicated to it) with a 20x20 grid. How I suspect it's more the fault of the String's immutability.


class prob15{
   
        public static String generateCondition(String t, byte x, byte y){
   
    String w = new String("");

    byte k = 0;
    for(byte i = 0; i < t.length(); i++)
        if (t.charAt(i)=='_')
        {
            k = i;
            break;           
        }
       else
           if (i==(t.length()-1))
           w+=t;
   
    if (x<20){
        byte c=x;
        c++;
        String a = t.replaceFirst("_","x");
        w+=" "+generateCondition(a, c, y);
        }

    if (y<20){
        byte d=y;
        d++;
        String a = t.replaceFirst("_","y");
        w+=" "+generateCondition(a, x, d);        
     }

     return w;        
    }
     
   
    public static void main(String args[]){
    String face1 = new String(generateCondition("x_______________________________________",(byte)1,(byte)0));
    String face2 = new String();
    byte counter = 0;
    char last = 'p';
    for (int i = 0; i<face1.length(); i++){
        if (face1.charAt(i)=='x')
        face2+="y";
        else if (face1.charAt(i)=='y')
            face2+="x";
            else face2+=" ";
        if ( (last==' ') && ( (face1.charAt(i)=='y') || (face1.charAt(i)=='x') ) )
        counter++;       
        last = face1.charAt(i);
    }
    System.out.println(face1+face2);
        System.out.println("Count: "+counter*2);
    }

}

I would like an opinion of efficiency please!

And some links to some know methods of computing combinations!

Thanks!

And don't be picking on me. Java is the most powerful language I know. I don't have any time to learn anything else right now.

Thanks!

Recursion is your friend.

In a 1x1 grid, there are 0 moves to make.
In a 2x2 grid, there is {down,right}, and {right,down}, 2 possibilities.
In a 3x3 grid, there how many ways to get to a 2x2 grid, which we've already calculated?
In a 4x4 grid, there are how many ways to get to a 3x3 grid, which we've already calculated?

Etc.

http://en.wikipedia.org/wiki/Permutation#Permutations_in_computing

>>1
And don't be picking on me. Java is the most powerful language I know. I don't have any time to learn anything else right now.
Fuck you. If you have time to do Project Euler problems, you have time to pick up another language. I know you're a slow learner, but you're just making excuses for laziness.

>>2

I'm already using recursion.

Also I believe you are not familiar with the problem.

As specified by the problem, in a 1x1 there are 2 ways.

In a 2x2 there are 6 ways.

In a 3x3 there are 20 ways (just computed now).

I'm however trying to figure out the pattern so as not to have to compute 20x20 which I believe is what you meant by recursion!

Thanks!

>>4

I need to familiarize myself with Java (hence Euler...) because I'll hopefully will join a team for an internship a few weeks from now and they use JAVA...

I know you're a slow learner

I'm not.

>>5
I am familiar with the problem. I solved it long ago. I described the problem in recursion. Then I asked myself what I was doing mathematically. Then I wrote a program for the math. It took milliseconds.

>>7

Thanks!

Good Advise.

I always forget to try to "simplify" the algorithm after getting it working!

>>8
ProjectEuler is fun for a bit, but pretty much you will find this is how every problem works. Almost all naive solutions to the problems will not finish, you have to flex your math muscles before you start coding.

http://dis.4chan.org/read/prog/1280144047/13

Here's my answer from the last time we had this thread.

Java is the most powerful language I know. I don't have any time to learn anything else right now.

I will hopefully will join a team for an internship a few weeks from now and they use JAVA

Is http://dis.4chan.org/read/prog/1280791251/1 the same guy?

>>12
Great job on being the last one to have figured it out. Retard.

>>1
http://www.oracle.com/technetwork/java/codeconvtoc-136057.html

You still haven't read this.

>>14
Perhaps he's just trolling. Otherwise, why ask a Java question on /prog/?

>>13

lol i trol u

>>2
I like you, you have shown me a new way to live.

>>12

Yes

>>13

There's no need to be hostile.

>>14

It's emacs who's messing with my indentation but I admit it's my fault in not having read the basic introduction first.

>>18
Perhaps instead of reading the introduction, you should just use vi instead. Didn't Skynet teach you that sentient programs are a bad idea?

>>18
M-x c-set-style and when prompted, type java