LebGeeks

m.sabra

Member

[Exercise] Cornering Lotto

So the exercise am gonna give now may be considered easy for some,but it was fun to solve for me.
so me and my friend were discussing cornering the lebanese lotto (assuring win by buying all possible tickets)so while calculating the number of possible choices was easy,writing all the actual possible combination was the hard part (we're talking about writing 5.2 million+ possible combination without a mistake or duplicate)so the challenge was making a program that will list all the ticket numbers possible.

so to the details,you have to pick 6 numbers from 1 to 42,picking the same number twice is not allowed (1-1-3-4-5-6 is invalid),the order is neglected (1-2-3-4-5-6 ; 6-5-4-3-2-1 ; 2-3-4-5-6-1 are considered the same),your program must not show any duplicates or invalid combinations (if the program shows both 1-2-3-4-5-6 and 6-5-4-3-2-1 it means that it failed).

the goal is: make a program that lists all the possible tickets verifying the rules above.

Note:i already solved it but i would like to see different approaches in solving it before posting my solution.
i used python,but feel free to use any language you like.
happy coding !

Last edited by m.sabra (October 29 2013)

user

Member

Re: [Exercise] Cornering Lotto

I think that is correct. I had to do a mass replace of variable i to o because the forum was interpreting them as formatting codes

public class main {
	public static int lotterycount = 0;

	public static void main(String args[]) {
		int[] ticket = { 1, 2, 3, 4, 5, 6 };

		while (ticket[0] != 43) {
			increment(ticket, ticket.length - 1);
			System.out.println(ticket[0] + " " + ticket[1] + " " + ticket[2]
					+ " " + ticket[3] + " " + ticket[4] + " " + ticket[5]);
			lotterycount++;
		}
		System.out.println(lotterycount + "");
	}

	public static int[] increment(int[] ticket, int position) {
		ticket[position]++;
	if(ticket[0]==43){return ticket;}//if we incremented the biggest number. return it and exit.
		if (ticket[position] == 43) {
			ticket[position] = 1;// reset the position

			if (position - 1 != -1) {// if we are not attempting to increase  a location that does not exist
				ticket = increment(ticket, position - 1);
			}
		}// increment the position to the left
		if (duplicate(ticket, position)) {// if a duplicate exists on this
											// position, increment it again
			ticket = increment(ticket, position);
		}

		return ticket;

	}

	public static boolean duplicate(int[] ticket, int position) {
		int o = 0;

		while (o < ticket.length) {
			if (ticket[o] == ticket[position] && o != position) {
				return true;
			}
			o++;
		}
		return false;// end of the loop and no duplicates, return false
	}
}

printing 5 million results takes a while. That is assuming that is all it is printing

Edit: I edited the code like 3 times after posting. The comments I do not expect to help clarify the code, they were written for me to know what I was doing.
The language is java.

edit again: damn I forgot to check for duplicates right to left left to right.

Last edited by user (October 29 2013)

samer

Admin

Re: [Exercise] Cornering Lotto

I had to do a mass replace of variable i to o because the forum was interpreting them as formatting codes

Use [ code ]  tags to avoid this.

user

Member

Re: [Exercise] Cornering Lotto

Thanks, I didn't know.

I like this problem. I haven't scratched my brain on algorithms since I graduated.

I guess the direct approach would be to store all the past results and run a comparison every time a result is generated. But that would not be an efficient code. There must be some mathematical trick to it...

jsaade

Member

Re: [Exercise] Cornering Lotto

lottolab.me check out our app :) it is 1$ but everything concerning lotto numbers is there. You can even change to any grid type or custom and set custom rules minimizing the output :)

Joe

Member

Re: [Exercise] Cornering Lotto

This is a classical application of Combinations.
Python includes a function to generate all the combinations of a set.

Here's a program that does it:

from itertools import combinations
print(list(combinations(range(1, 43), 6)))

I'm not going to show the output, because there are so many, but computing the length of the result list coincides with the results you have:

>>> len(list(combinations(range(1, 43), 6)))
5245786

It computes in less than a couple of seconds on my laptop.

Ra8

Member

Re: [Exercise] Cornering Lotto

Me too in python:

N=42
A=[0]*6
def f(n,k):
     if n>N:
          return
     if k==6:
          for i in range(0,6):
               print(A[i],end=" ")
          print("")
          return
     A[k]=n
     f(n+1,k+1)
     f(n+1,k)

f(1,0)

Last edited by Ra8 (October 29 2013)

m.sabra

Member

Re: [Exercise] Cornering Lotto

here's my solution. Python.

a=1
b=a+1
c=a+2
d=a+3
e=a+4
f=a+5
while (a <=37):
    while (b <=38):
        while (c <= 39):
            while(d <=40):
                while(e<=41):
                    while(f<=42):
                        print(a,b,c,d,e,f)
                        f=f+1
                    e=e+1
                    f=e+1
                d=d+1
                e=d+1
                f=e+1
            c=c+1
            d=c+1
            e=d+1
            f=e+1
        b=b+1
        c=b+1
        d=c+1
        e=d+1
        f=e+1
    a=a+1
    b=a+1
    c=b+1
    d=c+1
    e=d+1
    f=e+1

arithma

Member

Re: [Exercise] Cornering Lotto

>>> from math import factorial
>>> factorial(42)/factorial(6)/factorial(42-6)
5245786L

Another one in Haskell

Prelude> (foldl (*) 1 [42-5..42]) / (foldl (*) 1 [1..6])
5245786.0

Joe

Member

Re: [Exercise] Cornering Lotto

arithma, technically the exercise is about printing all the combinations, not just the number of them.

arithma

Member

Re: [Exercise] Cornering Lotto

arithma, technically the exercise is about printing all the combinations, not just the number of them.

I definitely don't care :)

longbit

Member

Re: [Exercise] Cornering Lotto

not the smartest yet it works...

class Loto{
	public static void main(String lonbit []){
		int n1, n2, n3, n4, n5, n6;
		n1=1;
		for(n1=1; n1<38; n1++)
			for(n2=n1+1; n2<39; n2++)
				for(n3=n2+1; n3<40; n3++)
					for(n4=n3+1; n4<41; n4++)
						for(n5=n4+1; n5<42; n5++)
							for(n6=n5+1; n6<43; n6++){
								System.out.println(n1+" "+ n2+" "+ n3+" "+ n4+" "+ n5+" "+ n6);
								}
	}
}

Last edited by longbit (November 7 2013)