As I’ve never won the National Lottery jackpot, I’m pretty sure the whole thing is rigged.
If you were in charge of taking peoples hard earned cash off of them and redistributing it back to a few of them, I bet you’d try and minimize the pay-out and pocket as much as you could. Now I’m not saying Camelot UK Lotteries Limited actually does this and The National Lottery is rigged, but you know, they definitely do and it is.
On draw nights, you can’t buy tickets between 7.30pm and 9.00pm before the winning balls are selected. Have you ever wondered what goes on for that hour and a half? I’ll tell you what; they are calculating which balls to select to give you the least money possible.
To minimize the pay-out you would need to compare all the possible combinations of six main balls plus the bonus ball, with all the entry lines which players have picked. Each comparison would check to see how many entry numbers matched the draw numbers, and the number of matches counted for all the entry lines. Finally, for each of the draw ball combinations, the total prize cost can be calculated using the stored matches count and the prize value for that number of matches.
Looking at the lotto prize breakdown from a past week (http://www.national-lottery.co.uk/player/lotto/results/prizeBreakdown.ftl):
| Matches | No. of winners | £s per winner | Prize fund |
|---|---|---|---|
| Match 6 | 1 | £7,959,312 | £7,959,312 |
| Match 5 plus Bonus | 7 | £68,525 | £479,675 |
| Match 5 | 176 | £2,314 | £407,264 |
| Match 4 | 12,448 | £173 | £2,153,504 |
| Match 3 | 256,646 | £25 | £6,416,150 |
| Lotto Raffle | 100 | £20,000 | £2,000,000 |
| Totals | 269,378 | £19,415,905 |
The total prize fund was about £20,000,000. From the Lotto website (http://www.national-lottery.co.uk/player/p/goodcausesandwinners/wherethemoneygoes.ftl), 50% of the money spent goes to the prize fund, which means the total money spent buying tickets was about £40,000,000, which at £2 per ticket gives us:
£40,000,000 / £2 = 20,000,000 entries.
Even if we could compare one entry line to all combinations of draw numbers every second, this would still take:
20,000,000 seconds / (60 * 60 * 24) ~ 232 days
Way too long to process in 90 minutes.
To rig the lotto draw, we're going to need some serious speed. The following is an unoptimised implementation in Java to process ten randomly generated entry lines, to use as a base line benchmark:
Lotto1.java
package org.adrianwalker.lotto;
import java.util.Random;
public final class Lotto1 {
/*
* Estimated lotto prizes:
* https://www.national-lottery.co.uk/player/p/help/aboutlotto/prizecalculation.ftl
*/
private static final int MATCH_6_PRIZE = 5000000;
private static final int MATCH_5_PLUS_BONUS_PRIZE = 50000;
private static final int MATCH_5_PRIZE = 1000;
private static final int MATCH_4_PRIZE = 100;
private static final int MATCH_3_PRIZE = 25;
// match types
private static final int MATCH_5_PLUS_BONUS = 7;
private static final int MATCH_6 = 6;
private static final int MATCH_5 = 5;
private static final int MATCH_4 = 4;
private static final int MATCH_3 = 3;
// define lowest and highest ball numbers
private static final int LOW_BALL = 1;
private static final int HIGH_BALL = 49;
// array sizes
private static final int MAIN_BALLS_SIZE = 6;
private static final int ENTRY_BALLS_SIZE = 6;
private static final int ENTRIES_SIZE = 10;
public static void main(final String[] args) {
// lotto entries, could be read from a database or file?
int[][] entries = new int[ENTRIES_SIZE][ENTRY_BALLS_SIZE];
// draw balls for random entries
int[] balls = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48, 49
};
// create random entries for testing
for (int i = 0; i < ENTRIES_SIZE; i++) {
shuffle(balls);
entries[i][0] = balls[0];
entries[i][1] = balls[1];
entries[i][2] = balls[2];
entries[i][3] = balls[3];
entries[i][4] = balls[4];
entries[i][5] = balls[5];
}
long start = System.currentTimeMillis();
// minimum values
long minCost = Long.MAX_VALUE;
int[] minCostMainBalls = new int[MAIN_BALLS_SIZE];
int minCostBonusBall = -1;
// maximum values
long maxCost = Long.MIN_VALUE;
int[] maxCostMainBalls = new int[MAIN_BALLS_SIZE];
int maxCostBonusBall = -1;
// iterate over main ball combinations
int[] mainBalls = new int[MAIN_BALLS_SIZE];
for (mainBalls[0] = LOW_BALL; mainBalls[0] <= HIGH_BALL; mainBalls[0]++) {
for (mainBalls[1] = mainBalls[0] + 1; mainBalls[1] <= HIGH_BALL; mainBalls[1]++) {
for (mainBalls[2] = mainBalls[1] + 1; mainBalls[2] <= HIGH_BALL; mainBalls[2]++) {
for (mainBalls[3] = mainBalls[2] + 1; mainBalls[3] <= HIGH_BALL; mainBalls[3]++) {
for (mainBalls[4] = mainBalls[3] + 1; mainBalls[4] <= HIGH_BALL; mainBalls[4]++) {
for (mainBalls[5] = mainBalls[4] + 1; mainBalls[5] <= HIGH_BALL; mainBalls[5]++) {
// iterate over bonus balls
for (int bonusBall = LOW_BALL; bonusBall <= HIGH_BALL; bonusBall++) {
// skip bonus ball if its in the main balls
if (contains(mainBalls, bonusBall)) {
continue;
}
// init match counts to zero
int[] matchesCount = {0, 0, 0, 0, 0, 0, 0, 0};
// iterate over entries
for (int[] entry : entries) {
// count matches
int matches = matches(entry, mainBalls, bonusBall);
// increment matches for number of balls matched
matchesCount[matches]++;
}
// get total cost of draw
long cost = cost(matchesCount);
// keep track of highest/lowest draw costs
if (cost < minCost) {
minCost = cost;
minCostMainBalls = mainBalls.clone();
minCostBonusBall = bonusBall;
} else if (cost > maxCost) {
maxCost = cost;
maxCostMainBalls = mainBalls.clone();
maxCostBonusBall = bonusBall;
}
}
}
}
}
}
}
}
long end = System.currentTimeMillis();
print(start, end,
minCost, minCostMainBalls, minCostBonusBall,
maxCost, maxCostMainBalls, maxCostBonusBall);
}
private static boolean contains(final int[] a, final int key) {
for (int x : a) {
if (x == key) {
return true;
}
}
return false;
}
private static void shuffle(final int[] a) {
Random rand = new Random(System.currentTimeMillis());
for (int i = 0; i < a.length; i++) {
int index = rand.nextInt(i + 1);
int x = a[index];
a[index] = a[i];
a[i] = x;
}
}
private static int matches(final int[] entry, final int[] mainBalls, final int bonusBall) {
int matches = 0;
boolean bonusMatch = false;
for (int entryNumber : entry) {
for (int mainBall : mainBalls) {
if (mainBall == entryNumber) {
matches++;
} else if (entryNumber == bonusBall) {
bonusMatch = true;
}
}
}
if (matches == MATCH_5 && bonusMatch) {
matches = MATCH_5_PLUS_BONUS;
}
return matches;
}
private static long cost(final int[] matchesCount) {
long cost = 0;
// add jackpot prize
if (matchesCount[MATCH_6] > 0) {
cost = MATCH_6_PRIZE;
}
// add lesser prizes, multiplied by number of winners
cost += matchesCount[MATCH_5_PLUS_BONUS] * MATCH_5_PLUS_BONUS_PRIZE
+ matchesCount[MATCH_5] * MATCH_5_PRIZE
+ matchesCount[MATCH_4] * MATCH_4_PRIZE
+ matchesCount[MATCH_3] * MATCH_3_PRIZE;
return cost;
}
private static void print(
final long start, final long end,
final long minCost, final int[] minCostMainBalls, final int minCostBonusBall,
final long maxCost, final int[] maxCostMainBalls, final int maxCostBonusBall) {
System.out.printf("\n--- entries ---\n");
System.out.printf("random entries processed = %s\n", ENTRIES_SIZE);
System.out.printf("\n--- time ---\n");
System.out.printf("elapsed time = %s seconds\n", (end - start) / 1000);
System.out.printf("\n--- min ---\n");
System.out.printf("minimum cost = %s\n", minCost);
System.out.printf("minimum main balls = %s,%s,%s,%s,%s,%s\n",
minCostMainBalls[0],
minCostMainBalls[1],
minCostMainBalls[2],
minCostMainBalls[3],
minCostMainBalls[4],
minCostMainBalls[5]);
System.out.printf("minimum bonus ball = %s\n",
minCostBonusBall == -1 ? "any" : minCostBonusBall);
System.out.printf("\n--- max ---\n");
System.out.printf("maximum cost = %s\n", maxCost);
System.out.printf("maximum main balls = %s,%s,%s,%s,%s,%s\n",
maxCostMainBalls[0],
maxCostMainBalls[1],
maxCostMainBalls[2],
maxCostMainBalls[3],
maxCostMainBalls[4],
maxCostMainBalls[5]);
System.out.printf("maximum bonus ball = %s\n",
maxCostBonusBall == -1 ? "any" : maxCostBonusBall);
}
}
On my very old L7500 1.60GHz laptop the output looks like this:
--- entries --- random entries processed = 10 --- time --- elapsed time = 636 seconds --- min --- minimum cost = 0 minimum main balls = 1,2,3,4,5,6 minimum bonus ball = 7 --- max --- maximum cost = 5000000 maximum main balls = 1,6,8,15,22,37 maximum bonus ball = 2
636 seconds for ten entries! Way too slow! There are some optimisations we can perform to make this faster:
- We only care about the bonus ball if we have 5 matching main balls - this loop can be executed only when we need it.
- An intersection of arrays can be used to count the main ball array/entry array matches.
- Sorted entry arrays can be used with a binary search to find bonus ball matches.
Lotto2.java
package org.adrianwalker.lotto;
import java.util.Arrays;
import java.util.Random;
public final class Lotto2 {
/*
* Estimated lotto prizes:
* https://www.national-lottery.co.uk/player/p/help/aboutlotto/prizecalculation.ftl
*/
private static final int MATCH_6_PRIZE = 5000000;
private static final int MATCH_5_PLUS_BONUS_PRIZE = 50000;
private static final int MATCH_5_PRIZE = 1000;
private static final int MATCH_4_PRIZE = 100;
private static final int MATCH_3_PRIZE = 25;
// match types
private static final int MATCH_5_PLUS_BONUS = 7;
private static final int MATCH_6 = 6;
private static final int MATCH_5 = 5;
private static final int MATCH_4 = 4;
private static final int MATCH_3 = 3;
// define lowest and highest ball numbers
private static final int LOW_BALL = 1;
private static final int HIGH_BALL = 49;
// array sizes
private static final int MAIN_BALLS_SIZE = 6;
private static final int ENTRY_BALLS_SIZE = 6;
private static final int ENTRIES_SIZE = 10;
public static void main(final String[] args) {
// lotto entries, could be read from a database or file?
int[][] entries = new int[ENTRIES_SIZE][ENTRY_BALLS_SIZE];
// draw balls for random entries
int[] balls = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48, 49
};
// create random entries for testing
for (int i = 0; i < ENTRIES_SIZE; i++) {
shuffle(balls);
entries[i][0] = balls[0];
entries[i][1] = balls[1];
entries[i][2] = balls[2];
entries[i][3] = balls[3];
entries[i][4] = balls[4];
entries[i][5] = balls[5];
Arrays.sort(entries[i]);
}
long start = System.currentTimeMillis();
// minimum values
long minCost = Long.MAX_VALUE;
int[] minCostMainBalls = new int[MAIN_BALLS_SIZE];
int minCostBonusBall = -1;
// maximum values
long maxCost = Long.MIN_VALUE;
int[] maxCostMainBalls = new int[MAIN_BALLS_SIZE];
int maxCostBonusBall = -1;
// iterate over main ball combinations
int[] mainBalls = new int[MAIN_BALLS_SIZE];
for (mainBalls[0] = LOW_BALL; mainBalls[0] <= HIGH_BALL; mainBalls[0]++) {
for (mainBalls[1] = mainBalls[0] + 1; mainBalls[1] <= HIGH_BALL; mainBalls[1]++) {
for (mainBalls[2] = mainBalls[1] + 1; mainBalls[2] <= HIGH_BALL; mainBalls[2]++) {
for (mainBalls[3] = mainBalls[2] + 1; mainBalls[3] <= HIGH_BALL; mainBalls[3]++) {
for (mainBalls[4] = mainBalls[3] + 1; mainBalls[4] <= HIGH_BALL; mainBalls[4]++) {
for (mainBalls[5] = mainBalls[4] + 1; mainBalls[5] <= HIGH_BALL; mainBalls[5]++) {
// init match counts to zero
int[] matchesCount = {0, 0, 0, 0, 0, 0, 0, 0};
// init bonus ball
int bonusBall = -1;
// iterate over entries
for (int[] entry : entries) {
// count matches
int matches = intersection(entry, mainBalls);
// if 5 matches check the bonus ball
if (matches == MATCH_5) {
// iterate over bonus balls
for (bonusBall = LOW_BALL; bonusBall <= HIGH_BALL; bonusBall++) {
// skip bonus ball if its in the main balls
if (contains(mainBalls, bonusBall)) {
continue;
}
// break if the entries contain the bonus ball
if (contains(entry, bonusBall)) {
matches = MATCH_5_PLUS_BONUS;
break;
}
}
}
// increment matches for number of balls matched
matchesCount[matches]++;
}
// get total cost of draw
long cost = cost(matchesCount);
// keep track of highest/lowest draw costs
if (cost < minCost) {
minCost = cost;
minCostMainBalls = mainBalls.clone();
minCostBonusBall = bonusBall;
} else if (cost > maxCost) {
maxCost = cost;
maxCostMainBalls = mainBalls.clone();
maxCostBonusBall = bonusBall;
}
}
}
}
}
}
}
long end = System.currentTimeMillis();
print(start, end,
minCost, minCostMainBalls, minCostBonusBall,
maxCost, maxCostMainBalls, maxCostBonusBall);
}
private static boolean contains(final int[] a, final int key) {
return Arrays.binarySearch(a, key) != -1;
}
private static void shuffle(final int[] a) {
Random rand = new Random(System.currentTimeMillis());
for (int i = 0; i < a.length; i++) {
int index = rand.nextInt(i + 1);
int x = a[index];
a[index] = a[i];
a[i] = x;
}
}
private static int intersection(final int[] a1, final int[] a2) {
int count = 0;
int i = 0;
int j = 0;
int a1length = a1.length;
int a2length = a2.length;
while (i < a1length && j < a2length) {
if (a1[i] == a2[j]) {
count++;
i++;
j++;
} else if (a1[i] < a2[j]) {
i++;
} else if (a1[i] > a2[j]) {
j++;
}
}
return count;
}
private static long cost(final int[] matchesCount) {
long cost = 0;
// add jackpot prize
if (matchesCount[MATCH_6] > 0) {
cost = MATCH_6_PRIZE;
}
// add lesser prizes, multiplied by number of winners
cost += matchesCount[MATCH_5_PLUS_BONUS] * MATCH_5_PLUS_BONUS_PRIZE
+ matchesCount[MATCH_5] * MATCH_5_PRIZE
+ matchesCount[MATCH_4] * MATCH_4_PRIZE
+ matchesCount[MATCH_3] * MATCH_3_PRIZE;
return cost;
}
private static void print(
final long start, final long end,
final long minCost, final int[] minCostMainBalls, final int minCostBonusBall,
final long maxCost, final int[] maxCostMainBalls, final int maxCostBonusBall) {
System.out.printf("\n--- entries ---\n");
System.out.printf("random entries processed = %s\n", ENTRIES_SIZE);
System.out.printf("\n--- time ---\n");
System.out.printf("elapsed time = %s seconds\n", (end - start) / 1000);
System.out.printf("\n--- min ---\n");
System.out.printf("minimum cost = %s\n", minCost);
System.out.printf("minimum main balls = %s,%s,%s,%s,%s,%s\n",
minCostMainBalls[0],
minCostMainBalls[1],
minCostMainBalls[2],
minCostMainBalls[3],
minCostMainBalls[4],
minCostMainBalls[5]);
System.out.printf("minimum bonus ball = %s\n",
minCostBonusBall == -1 ? "any" : minCostBonusBall);
System.out.printf("\n--- max ---\n");
System.out.printf("maximum cost = %s\n", maxCost);
System.out.printf("maximum main balls = %s,%s,%s,%s,%s,%s\n",
maxCostMainBalls[0],
maxCostMainBalls[1],
maxCostMainBalls[2],
maxCostMainBalls[3],
maxCostMainBalls[4],
maxCostMainBalls[5]);
System.out.printf("maximum bonus ball = %s\n",
maxCostBonusBall == -1 ? "any" : maxCostBonusBall);
}
}
The output from this optimised version looks like this:
--- entries --- random entries processed = 10 --- time --- elapsed time = 17 seconds --- min --- minimum cost = 0 minimum main balls = 1,2,3,4,5,6 minimum bonus ball = any --- max --- maximum cost = 5000025 maximum main balls = 4,7,31,34,36,43 maximum bonus ball = any
17 seconds is a massive performance improvement over the previous code, but still not the sub second per entry speed we require.
The following code uses a long integer to represent the main balls as a bit mask, each 1 bit's position representing a main ball number. This bit mask can be used as a lookup to check entry numbers against:
Lotto3.java
package org.adrianwalker.lotto;
import java.util.Random;
public final class Lotto3 {
/*
* Estimated lotto prizes:
* https://www.national-lottery.co.uk/player/p/help/aboutlotto/prizecalculation.ftl
*/
private static final int MATCH_6_PRIZE = 5000000;
private static final int MATCH_5_PLUS_BONUS_PRIZE = 50000;
private static final int MATCH_5_PRIZE = 1000;
private static final int MATCH_4_PRIZE = 100;
private static final int MATCH_3_PRIZE = 25;
// match types
private static final int MATCH_5_PLUS_BONUS = 7;
private static final int MATCH_6 = 6;
private static final int MATCH_5 = 5;
private static final int MATCH_4 = 4;
private static final int MATCH_3 = 3;
// define lowest and highest ball numbers
private static final int LOW_BALL = 1;
private static final int HIGH_BALL = 49;
// array sizes
private static final int MAIN_BALLS_SIZE = 6;
private static final int ENTRY_BALLS_SIZE = 6;
private static final int ENTRIES_SIZE = 10;
public static void main(final String[] args) {
// lotto entries, could be read from a database or file?
int[][] entries = new int[ENTRIES_SIZE][ENTRY_BALLS_SIZE];
// draw balls for random entries
int[] balls = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48, 49
};
// create random entries for testing
for (int i = 0; i < ENTRIES_SIZE; i++) {
shuffle(balls);
entries[i][0] = balls[0];
entries[i][1] = balls[1];
entries[i][2] = balls[2];
entries[i][3] = balls[3];
entries[i][4] = balls[4];
entries[i][5] = balls[5];
}
long start = System.currentTimeMillis();
// minimum values
long minCost = Long.MAX_VALUE;
int[] minCostMainBalls = new int[MAIN_BALLS_SIZE];
int minCostBonusBall = -1;
// maximum values
long maxCost = Long.MIN_VALUE;
int[] maxCostMainBalls = new int[MAIN_BALLS_SIZE];
int maxCostBonusBall = -1;
// iterate over main ball combinations
int[] mainBalls = new int[MAIN_BALLS_SIZE];
for (mainBalls[0] = LOW_BALL; mainBalls[0] <= HIGH_BALL; mainBalls[0]++) {
for (mainBalls[1] = mainBalls[0] + 1; mainBalls[1] <= HIGH_BALL; mainBalls[1]++) {
for (mainBalls[2] = mainBalls[1] + 1; mainBalls[2] <= HIGH_BALL; mainBalls[2]++) {
for (mainBalls[3] = mainBalls[2] + 1; mainBalls[3] <= HIGH_BALL; mainBalls[3]++) {
for (mainBalls[4] = mainBalls[3] + 1; mainBalls[4] <= HIGH_BALL; mainBalls[4]++) {
for (mainBalls[5] = mainBalls[4] + 1; mainBalls[5] <= HIGH_BALL; mainBalls[5]++) {
// create bitmask for match lookup
long mainBallsBitmask = bitmask(mainBalls);
// init match counts to zero
int[] matchesCount = {0, 0, 0, 0, 0, 0, 0, 0};
// init bonus ball
int bonusBall = -1;
// iterate over entries
for (int[] entry : entries) {
// count matches
int matches = matches(entry, mainBallsBitmask);
// if 5 matches check the bonus ball
if (matches == MATCH_5) {
// iterate over bonus balls
for (bonusBall = LOW_BALL; bonusBall <= HIGH_BALL; bonusBall++) {
// skip bonus ball if its in the main balls
if (bitSet(mainBallsBitmask, bonusBall)) {
continue;
}
long entryBitmask = bitmask(entry);
// break if the entries contain the bonus ball
if (bitSet(entryBitmask, bonusBall)) {
matches = MATCH_5_PLUS_BONUS;
break;
}
}
}
// increment matches for number of balls matched
matchesCount[matches]++;
}
// get total cost of draw
long cost = cost(matchesCount);
// keep track of highest/lowest draw costs
if (cost < minCost) {
minCost = cost;
minCostMainBalls = mainBalls.clone();
minCostBonusBall = bonusBall;
} else if (cost > maxCost) {
maxCost = cost;
maxCostMainBalls = mainBalls.clone();
maxCostBonusBall = bonusBall;
}
}
}
}
}
}
}
long end = System.currentTimeMillis();
print(start, end,
minCost, minCostMainBalls, minCostBonusBall,
maxCost, maxCostMainBalls, maxCostBonusBall);
}
private static void shuffle(final int[] a) {
Random rand = new Random(System.currentTimeMillis());
for (int i = 0; i < a.length; i++) {
int index = rand.nextInt(i + 1);
int x = a[index];
a[index] = a[i];
a[i] = x;
}
}
private static boolean bitSet(final long bitMask, final int i) {
return (bitMask & (1L << i)) > 0;
}
private static long setBit(final long bitmask, final int i) {
return bitmask | (1L << i);
}
private static long bitmask(final int[] a) {
long bitmask = 0;
for (int i : a) {
bitmask = setBit(bitmask, i);
}
return bitmask;
}
private static int matches(final int[] entry, final long mainBallsBitmask) {
int matches = 0;
for (int number : entry) {
if (bitSet(mainBallsBitmask, number)) {
matches++;
}
}
return matches;
}
private static long cost(final int[] matchesCount) {
long cost = 0;
// add jackpot prize
if (matchesCount[MATCH_6] > 0) {
cost = MATCH_6_PRIZE;
}
// add lesser prizes, multiplied by number of winners
cost += matchesCount[MATCH_5_PLUS_BONUS] * MATCH_5_PLUS_BONUS_PRIZE
+ matchesCount[MATCH_5] * MATCH_5_PRIZE
+ matchesCount[MATCH_4] * MATCH_4_PRIZE
+ matchesCount[MATCH_3] * MATCH_3_PRIZE;
return cost;
}
private static void print(
final long start, final long end,
final long minCost, final int[] minCostMainBalls, final int minCostBonusBall,
final long maxCost, final int[] maxCostMainBalls, final int maxCostBonusBall) {
System.out.printf("\n--- entries ---\n");
System.out.printf("random entries processed = %s\n", ENTRIES_SIZE);
System.out.printf("\n--- time ---\n");
System.out.printf("elapsed time = %s seconds\n", (end - start) / 1000);
System.out.printf("\n--- min ---\n");
System.out.printf("minimum cost = %s\n", minCost);
System.out.printf("minimum main balls = %s,%s,%s,%s,%s,%s\n",
minCostMainBalls[0],
minCostMainBalls[1],
minCostMainBalls[2],
minCostMainBalls[3],
minCostMainBalls[4],
minCostMainBalls[5]);
System.out.printf("minimum bonus ball = %s\n",
minCostBonusBall == -1 ? "any" : minCostBonusBall);
System.out.printf("\n--- max ---\n");
System.out.printf("maximum cost = %s\n", maxCost);
System.out.printf("maximum main balls = %s,%s,%s,%s,%s,%s\n",
maxCostMainBalls[0],
maxCostMainBalls[1],
maxCostMainBalls[2],
maxCostMainBalls[3],
maxCostMainBalls[4],
maxCostMainBalls[5]);
System.out.printf("maximum bonus ball = %s\n",
maxCostBonusBall == -1 ? "any" : maxCostBonusBall);
}
}
The output from the bit mask optimised version looks like this:
--- entries --- random entries processed = 10 --- time --- elapsed time = 4 seconds --- min --- minimum cost = 0 minimum main balls = 1,2,4,5,6,8 minimum bonus ball = any --- max --- maximum cost = 5000025 maximum main balls = 2,20,27,43,46,47 maximum bonus ball = any
Four seconds for ten entries is approaching the sub second per entry performance we would need.
Obviously a faster algorithm is preferable to throwing more CPU at a problem, but porting the above Java code to C allows us to more effectively use the CPU we have, and gives us some speed improvement for free:
lotto.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <time.h>
#define FALSE 0
#define TRUE !FALSE
#define SIZEOF(a) (sizeof a / sizeof a[0])
/*
* Estimated lotto prizes:
* https://www.national-lottery.co.uk/player/p/help/aboutlotto/prizecalculation.ftl
*/
#define MATCH_6_PRIZE 5000000
#define MATCH_5_PLUS_BONUS_PRIZE 50000
#define MATCH_5_PRIZE 1000
#define MATCH_4_PRIZE 100
#define MATCH_3_PRIZE 25
// match types
#define MATCH_5_PLUS_BONUS 7
#define MATCH_6 6
#define MATCH_5 5
#define MATCH_4 4
#define MATCH_3 3
// define lowest and highest ball numbers
#define LOW_BALL 1
#define HIGH_BALL 49
// array sizes
#define MAIN_BALLS_SIZE 6
#define ENTRY_BALLS_SIZE 6
#define MATCHES_COUNT_SIZE 8
#define ENTRIES_SIZE 10
void shuffle(int a[], int size);
int bitSet(long bitMask, int i);
long setBit(long bitmask, int i);
long bitmask(int a[], int size);
int matches(int entry[ENTRY_BALLS_SIZE], long mainBallsBitmask);
long cost(int matchesCount[MATCHES_COUNT_SIZE]);
void print(
time_t start, time_t end,
long minCost, int minCostMainBalls[MAIN_BALLS_SIZE], int minCostBonusBall,
long maxCost, int maxCostMainBalls[MAIN_BALLS_SIZE], int maxCostBonusBall);
int main(int argc, char** argv) {
// lotto entries, could be read from a database or file?
int entries[ENTRIES_SIZE][ENTRY_BALLS_SIZE];
// draw balls for random entries
int balls[] = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48, 49
};
// create random entries for testing
int i;
for (i = 0; i < ENTRIES_SIZE; i++) {
shuffle(balls, SIZEOF(balls));
entries[i][0] = balls[0];
entries[i][1] = balls[1];
entries[i][2] = balls[2];
entries[i][3] = balls[3];
entries[i][4] = balls[4];
entries[i][5] = balls[5];
}
time_t start = time(NULL);
// minimum values
long minCost = LONG_MAX;
int minCostMainBalls[MAIN_BALLS_SIZE];
int minCostBonusBall = -1;
// maximum values
long maxCost = LONG_MIN;
int maxCostMainBalls[MAIN_BALLS_SIZE];
int maxCostBonusBall = -1;
// iterate over main ball combinations
int mainBalls[MAIN_BALLS_SIZE];
for (mainBalls[0] = LOW_BALL; mainBalls[0] <= HIGH_BALL; mainBalls[0]++) {
for (mainBalls[1] = mainBalls[0] + 1; mainBalls[1] <= HIGH_BALL; mainBalls[1]++) {
for (mainBalls[2] = mainBalls[1] + 1; mainBalls[2] <= HIGH_BALL; mainBalls[2]++) {
for (mainBalls[3] = mainBalls[2] + 1; mainBalls[3] <= HIGH_BALL; mainBalls[3]++) {
for (mainBalls[4] = mainBalls[3] + 1; mainBalls[4] <= HIGH_BALL; mainBalls[4]++) {
for (mainBalls[5] = mainBalls[4] + 1; mainBalls[5] <= HIGH_BALL; mainBalls[5]++) {
// create bitmask for match lookup
long mainBallsBitmask = bitmask(mainBalls, SIZEOF(mainBalls));
// init match counts to zero
int matchesCount[MATCHES_COUNT_SIZE] = {0, 0, 0, 0, 0, 0, 0, 0};
//init bonus ball
int bonusBall = -1;
// iterate over entries
int i;
for (i = 0; i < ENTRIES_SIZE; i++) {
// count matches
int m = matches(entries[i], mainBallsBitmask);
// if 5 matches check the bonus ball
if (m == MATCH_5) {
// iterate over bonus balls
for (bonusBall = LOW_BALL; bonusBall <= HIGH_BALL; bonusBall++) {
// skip bonus ball if its in the main balls
if (bitSet(mainBallsBitmask, bonusBall)) {
continue;
}
long entryBitmask = bitmask(entries[i], SIZEOF(entries));
// break if the entries contain the bonus ball
if (bitSet(entryBitmask, bonusBall)) {
m = MATCH_5_PLUS_BONUS;
break;
}
}
}
// increment matches for number of balls matched
matchesCount[m]++;
}
// get total cost of draw
long c = cost(matchesCount);
// keep track of highest/lowest draw costs
if (c < minCost) {
minCost = c;
memcpy(minCostMainBalls, mainBalls, MAIN_BALLS_SIZE * sizeof (int));
minCostBonusBall = bonusBall;
} else if (c > maxCost) {
maxCost = c;
memcpy(maxCostMainBalls, mainBalls, MAIN_BALLS_SIZE * sizeof (int));
maxCostBonusBall = bonusBall;
}
}
}
}
}
}
}
time_t end = time(NULL);
print(start, end, minCost, minCostMainBalls, minCostBonusBall,
maxCost, maxCostMainBalls, maxCostBonusBall);
return (EXIT_SUCCESS);
}
void shuffle(int a[], int size) {
srand(time(NULL));
int i;
for (i = 0; i < size; i++) {
int index = rand() % (i + 1);
int x = a[index];
a[index] = a[i];
a[i] = x;
}
}
int bitSet(long bitMask, int i) {
return (bitMask & (1L << i)) > 0;
}
long setBit(long bitmask, int i) {
return bitmask | (1L << i);
}
long bitmask(int a[], int size) {
long bitmask = 0;
int i;
for (i = 0; i < size; i++) {
bitmask = setBit(bitmask, a[i]);
}
return bitmask;
}
int matches(int entry[ENTRY_BALLS_SIZE], long mainBallsBitmask) {
int matches = 0;
int i;
for (i = 0; i < ENTRY_BALLS_SIZE; i++) {
if (bitSet(mainBallsBitmask, entry[i])) {
matches++;
}
}
return matches;
}
long cost(int matchesCount[MATCHES_COUNT_SIZE]) {
long cost = 0;
// add jackpot prize
if (matchesCount[MATCH_6] > 0) {
cost = MATCH_6_PRIZE;
}
// add lesser prizes, multiplied by number of winners
cost += matchesCount[MATCH_5_PLUS_BONUS] * MATCH_5_PLUS_BONUS_PRIZE
+ matchesCount[MATCH_5] * MATCH_5_PRIZE
+ matchesCount[MATCH_4] * MATCH_4_PRIZE
+ matchesCount[MATCH_3] * MATCH_3_PRIZE;
return cost;
}
void print(
time_t start, time_t end,
long minCost, int minCostMainBalls[MAIN_BALLS_SIZE], int minCostBonusBall,
long maxCost, int maxCostMainBalls[MAIN_BALLS_SIZE], int maxCostBonusBall) {
printf("\n--- entries ---\n");
printf("random entries processed = %d\n", ENTRIES_SIZE);
printf("\n--- time ---\n");
printf("elapsed time = %lu seconds\n", (end - start));
printf("\n--- min ---\n");
printf("minimum cost = %lu\n", minCost);
printf("minimum main balls = %d,%d,%d,%d,%d,%d\n",
minCostMainBalls[0],
minCostMainBalls[1],
minCostMainBalls[2],
minCostMainBalls[3],
minCostMainBalls[4],
minCostMainBalls[5]);
printf("minimum bonus ball = %d\n", minCostBonusBall);
printf("\n--- max ---\n");
printf("maximum cost = %lu\n", maxCost);
printf("maximum main balls = %d,%d,%d,%d,%d,%d\n",
maxCostMainBalls[0],
maxCostMainBalls[1],
maxCostMainBalls[2],
maxCostMainBalls[3],
maxCostMainBalls[4],
maxCostMainBalls[5]);
printf("maximum bonus ball = %d\n", maxCostBonusBall);
}
Output from the above C code:
--- entries --- random entries processed = 10 --- time --- elapsed time = 2 seconds --- min --- minimum cost = 0 minimum main balls = 1,2,3,4,5,9 minimum bonus ball = -1 --- max --- maximum cost = 5000050 maximum main balls = 1,4,7,10,21,30 maximum bonus ball = -1
Twice as fast as the Java version for ten entries! Lets up the number of entries to 1000 to get a better idea of performance:
--- entries --- random entries processed = 1000 --- time --- elapsed time = 155 seconds --- min --- minimum cost = 0 minimum main balls = 1,2,7,9,10,11 minimum bonus ball = -1 --- max --- maximum cost = 6101000 maximum main balls = 3,4,5,32,34,36 maximum bonus ball = 1
Processing 20,000,000 total entry lines should take 20,000 times longer than the previous output:
155 seconds * 20,000 = 3,100,000 seconds
3,100,000 seconds / (60 * 60 * 24) ~ 36 days
Even with the code optimisations and porting to C, 36 days is way longer than our 90 minute window.
Rigging the National Lottery is hard.
There will be further optimisations to be had with this code, but who cares, we all know how the Lottery is really rigged...
... MAGNETS!
Source Code
- Java and C code available in GitHub - lotto
