Monday, March 05, 2007

Mega Millions

In case you haven't heard... tomorrow night's Mega Millions jackpot is $340 million. My family is playing a bunch of tickets, so I wrote a little program designed to maximize the chance of our ticket being the only winning ticket. It's pretty crude, but it was fun to code it up in C++.


#include <iostream>
#include <string>
#include <cstdlib>
#include <list>
#include <vector>
#include <sstream>
#include <time.h>

using namespace std;

class Lotto{
private :
int length;
int maxNum;
int maxMegaNum;
int minNum;
int numTickets;

string ticketString(int *ticket){
ostringstream str;
for (int i=0; i<= this->length ; i++){
str << *ticket << " ";
ticket++;
}
return str.str();
}

/*
This is very crude. Multiply all the numbers in the first
ticket together. Go through the second ticket and make
sure that each of its numbers divides evenly into the product.
This wouldn't work if the maxNum was huge, but it is fast
and effective for small maxNum.
*/
int sameTickets(int *t1, int *t2){
int *runner = t1;
int prod = 1;
for (int i=0;i< this->length; i++){
prod *= *runner;
runner++;
}
runner = t2;
for (int i=0;i< this->length; i++){
if (prod % *runner != 0){
return 0;
}
runner++;
}
return 1;
}

int* generateTicket(){
const int delta = this->maxNum - this->minNum;
int *picked = new int[delta];
for (int j=0; j< delta; j++){
picked[j] = 0;
}
int i =0;
int *ticket = new int[this->length + 1];
while (i < this->length){
int num = rand() % delta;
int ticketNum= num + this->minNum;
if (picked[num] == 0){
ticket[i] = ticketNum;
i++;
picked[num] = 1;
}
}
// calc mega
ticket[this->length] = this->minNum + (rand() % (this->maxMegaNum - this->minNum));
free(picked);
return ticket;
}

public:
Lotto(int length, int maxNum, int maxMega, int minNum, int numTickets){
this->length = length;
this->maxNum = maxNum;
this->maxMegaNum = maxMega;
this->minNum = minNum;
this->numTickets = numTickets;
srand(time(NULL));
}
~Lotto(){
}

list<string> generateTickets(){
list<string> l;
vector<int*> v;
for (int i=0; i < this->numTickets ; i++){
int *ticket = this->generateTicket();
// check if same ticket already exists
int comparison = 0;
for (int j=0; j< v.size() ; j++){
comparison = this->sameTickets(ticket, v[j]);
if (comparison == 1){
break;
}
}
if (comparison == 0){
string str = this->ticketString(ticket);
l.push_front(str);
v.push_back(ticket);
} else {
// dupe tickets, decrement counter to generate new ticket
i--;
}
}
return l;
}


};

int main () {
cout << "How many (non-Mega) numbers on a ticket?" << endl;
int tixSize;
scanf("%d",&tixSize);

cout << "What's the largest number you can play?" << endl;
int tixMax;
scanf("%d",&tixMax);

cout << "What's the max Mega number you can play?" << endl;
int mega;
scanf("%d",&mega);

cout << "How many tickets do you want?" << endl;
int numTix;
scanf("%d",&numTix);

Lotto lotto = Lotto(tixSize, tixMax, mega, 32, numTix);
list<string> tickets = lotto.generateTickets();
int size = tickets.size();
for (int i=0; i < size ; i++){
string ticket = tickets.front();
tickets.pop_front();
cout << "Ticket: " << ticket << endl;
}
string text;
cout << "Press return to exit.." << endl;
getline(cin,text);
getline(cin,text);
return 0;
}

technorati tags:, ,

No comments:

Post a Comment