Sunday 17 November 2013

Java Collection Literals

The blog post I've had by far the most feedback on is Java Multiline String. It seems to have found a niche with a few programmers for quickly defining formatted SQL and XML for unit testing.

After reading Steve Yegge's post which covered the lack of Java syntax for defining literal data objects, I thought the multiline string code could be extended to provide this kind of syntax for Java Collections.

The code below, like the multiline string code, uses Javadoc comments, annotations and annotation processors to generate code at compile time to initialise and populate a collection.

Collection fields are annotated with an annotation which specifies which annotation processor to use. The annotation processor uses the fields Javadoc comment, which contains a JSON string, to generate additional code to populate the field.

For example, the annotation used to initialise a List field as an ArrayList:

ArrayList.java

package org.adrianwalker.collectionliterals;

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

@Target(ElementType.FIELD)
@Retention(RetentionPolicy.SOURCE)
public @interface ArrayList {
}

The code generation is handled using an annotation processor for each annotation, with common code being inherited from an abstract class:

AbstractCollectionProcessor.java

package org.adrianwalker.collectionliterals;

import com.sun.source.tree.ClassTree;
import com.sun.source.util.Trees;
import com.sun.tools.javac.code.Flags;
import com.sun.tools.javac.code.Symbol;
import com.sun.tools.javac.model.JavacElements;
import com.sun.tools.javac.processing.JavacProcessingEnvironment;
import com.sun.tools.javac.tree.JCTree;
import com.sun.tools.javac.tree.JCTree.JCExpression;
import com.sun.tools.javac.tree.JCTree.JCMethodInvocation;
import com.sun.tools.javac.tree.TreeMaker;
import com.sun.tools.javac.util.Context;
import com.sun.tools.javac.util.List;
import com.sun.tools.javac.util.ListBuffer;
import com.sun.tools.javac.util.Names;
import java.util.Collection;
import java.util.Set;
import javax.annotation.processing.AbstractProcessor;
import javax.annotation.processing.ProcessingEnvironment;
import javax.annotation.processing.RoundEnvironment;
import javax.lang.model.element.Element;
import javax.lang.model.element.TypeElement;
import org.codehaus.jackson.map.ObjectMapper;

public abstract class AbstractCollectionProcessor<C> extends AbstractProcessor {

  private static final String THIS = "this";
  private JavacElements elementUtils;
  private TreeMaker maker;
  private Trees trees;
  private Names names;

  @Override
  public void init(final ProcessingEnvironment procEnv) {
    super.init(procEnv);
    JavacProcessingEnvironment javacProcessingEnv = (JavacProcessingEnvironment) procEnv;
    Context context = javacProcessingEnv.getContext();
    this.elementUtils = javacProcessingEnv.getElementUtils();
    this.maker = TreeMaker.instance(context);
    this.trees = Trees.instance(procEnv);
    this.names = Names.instance(context);
  }

  public JavacElements getElementUtils() {
    return elementUtils;
  }

  public TreeMaker getMaker() {
    return maker;
  }

  public Trees getTrees() {
    return trees;
  }

  public Names getNames() {
    return names;
  }

  @Override
  public boolean process(final Set<? extends TypeElement> annotations, final RoundEnvironment roundEnv) {

    Set<? extends Element> fields = roundEnv.getElementsAnnotatedWith(getAnnotationClass());

    for (Element field : fields) {
      String docComment = elementUtils.getDocComment(field);

      if (null == docComment) {
        continue;
      }

      processField(field, parseJson(docComment));
    }

    return true;
  }

  private C parseJson(final String json) throws ProcessorException {

    ObjectMapper mapper = new ObjectMapper();

    C collection;
    try {
      collection = (C) mapper.readValue(json, getCollectionClass());
    } catch (final Throwable t) {
      throw new ProcessorException(t);
    }

    return collection;
  }

  private void processField(final Element field, final C collection) {

    JCTree fieldTree = elementUtils.getTree(field);
    JCTree.JCVariableDecl fieldVariable = (JCTree.JCVariableDecl) fieldTree;
    Symbol.VarSymbol fieldSym = fieldVariable.sym;
    boolean isStatic = fieldSym.isStatic();
    JCTree.JCExpression fieldEx;

    if (!isStatic) {
      fieldEx = maker.Ident(names.fromString(THIS));
      fieldEx = maker.Select(fieldEx, fieldSym.name);
    } else {
      fieldEx = maker.QualIdent(fieldSym);
    }

    Symbol.ClassSymbol collectionClass = elementUtils.getTypeElement(getCollectionClassName());
    JCTree.JCExpression collectionEx = maker.QualIdent(collectionClass);

    JCTree.JCNewClass newCollection = maker.NewClass(
            null,
            List.<JCTree.JCExpression>nil(),
            collectionEx,
            List.<JCTree.JCExpression>nil(), null);

    JCTree.JCAssign assign = maker.Assign(fieldEx, newCollection);
    JCTree.JCStatement assignStatement = maker.Exec(assign);

    JCExpression collectionMethodEx = maker.Select(fieldEx, names.fromString(getCollectionMethodName()));

    ListBuffer blockBuffer = new ListBuffer();
    blockBuffer.add(assignStatement);
    blockBuffer.appendList(processCollection(collection, collectionMethodEx));

    long flags = Flags.BLOCK;
    if (isStatic) {
      flags |= Flags.STATIC;
    }

    JCTree.JCBlock block = maker.Block(flags, blockBuffer.toList());

    TypeElement type = (TypeElement) field.getEnclosingElement();
    ClassTree cls = trees.getTree(type);

    JCTree.JCClassDecl cd = (JCTree.JCClassDecl) cls;

    cd.defs = cd.defs.append(block);
  }

  public List processCollection(final C collection, final JCTree.JCExpression collectionMethodEx) {
    ListBuffer collectionMethodBuffer = new ListBuffer();

    for (Object element : (Collection) collection) {

      ListBuffer addBuffer = new ListBuffer();
      addBuffer.add(getMaker().Literal(element));

      JCMethodInvocation addInv = getMaker().Apply(
              List.<JCTree.JCExpression>nil(),
              collectionMethodEx,
              addBuffer.toList());
      JCTree.JCStatement addStatement = getMaker().Exec(addInv);

      collectionMethodBuffer.add(addStatement);
    }

    return collectionMethodBuffer.toList();
  }

  public abstract Class getAnnotationClass();

  public abstract String getCollectionClassName();

  public abstract Class getCollectionClass();

  public abstract String getCollectionMethodName();
}

This class can be extended to create a concrete implementation, for an ArrayList field:

ArrayListProcessor.java

package org.adrianwalker.collectionliterals;

import java.util.ArrayList;
import javax.annotation.processing.SupportedAnnotationTypes;
import javax.annotation.processing.SupportedSourceVersion;
import javax.lang.model.SourceVersion;

@SupportedAnnotationTypes({"org.adrianwalker.collectionliterals.ArrayList"})
@SupportedSourceVersion(SourceVersion.RELEASE_6)
public final class ArrayListProcessor extends AbstractCollectionProcessor<ArrayList<Object>> {

  @Override
  public Class getAnnotationClass() {
    return org.adrianwalker.collectionliterals.ArrayList.class;
  }

  @Override
  public Class getCollectionClass() {
    return java.util.ArrayList.class;
  }

  @Override
  public String getCollectionClassName() {
    return getCollectionClass().getName();
  }

  @Override
  public String getCollectionMethodName() {
    return "add";
  }
}

Because Java Maps don't implement the Collection interface, the processor for a HashMap field is a bit more complicated:

HashMapProcessor.java

package org.adrianwalker.collectionliterals;

import com.sun.tools.javac.tree.JCTree;
import com.sun.tools.javac.tree.JCTree.JCMethodInvocation;
import com.sun.tools.javac.util.List;
import com.sun.tools.javac.util.ListBuffer;
import java.util.HashMap;
import java.util.Map.Entry;
import javax.annotation.processing.SupportedAnnotationTypes;
import javax.annotation.processing.SupportedSourceVersion;
import javax.lang.model.SourceVersion;

@SupportedAnnotationTypes({"org.adrianwalker.collectionliterals.HashMap"})
@SupportedSourceVersion(SourceVersion.RELEASE_6)
public final class HashMapProcessor extends AbstractCollectionProcessor<HashMap<String, Object>> {

  @Override
  public List processCollection(final HashMap<String, Object> collection, final JCTree.JCExpression collectionMethodEx) {
    ListBuffer collectionMethodBuffer = new ListBuffer();

    for (Entry<String, Object> entry : collection.entrySet()) {

      ListBuffer putBuffer = new ListBuffer();
      putBuffer.add(getMaker().Literal(entry.getKey()));
      putBuffer.add(getMaker().Literal(entry.getValue()));

      JCMethodInvocation putInv = getMaker().Apply(
              List.<JCTree.JCExpression>nil(),
              collectionMethodEx,
              putBuffer.toList());
      JCTree.JCStatement putStatement = getMaker().Exec(putInv);

      collectionMethodBuffer.add(putStatement);
    }

    return collectionMethodBuffer.toList();
  }

  @Override
  public Class getAnnotationClass() {
    return org.adrianwalker.collectionliterals.HashMap.class;
  }

  @Override
  public Class getCollectionClass() {
    return java.util.HashMap.class;
  }

  @Override
  public String getCollectionClassName() {
    return getCollectionClass().getName();
  }

  @Override
  public String getCollectionMethodName() {
    return "put";
  }
}

The code to use the annotations would look something like this for a class with static fields:

CollectionLiteralUsageStatic.java

package org.adrianwalker.collectionliterals;

import java.util.List;
import java.util.Map;
import java.util.Set;

public final class CollectionLiteralUsageStatic {

  /**
   [1,2,3,4,5,6,7,8,9,10]
   */
  @ArrayList
  private static List<Integer> list;
  /**
   ["0","1","2","3","4","5","6","7",
   "8","9","A","B","C","D","E","F"]
   */
  @HashSet
  private static Set<String> set;  
  /**
   {
     "name":"Adrian Walker", 
     "age":31 
   }
   */
  @HashMap
  private static Map<String, Object> map;

  public static void main(final String[] args) {
    System.out.println(list);
    System.out.println(set);
    System.out.println(map);
  }
}

And example code for classes with instance fields:

package org.adrianwalker.collectionliterals;

import java.util.List;
import java.util.Map;
import java.util.Set;

public final class CollectionLiteralUsage {

  /**
   [1,2,3,4,5,6,7,8,9,10]
   */
  @LinkedList
  private List<Integer> list;
  /**
   ["0","1","2","3","4","5","6","7", 
   "8","9","A","B","C","D","E","F"]
   */
  @HashSet
  private Set<String> set;
  /**
   {
     "name":"Adrian Walker", 
     "age":31 
   }
   */
  @HashMap
  private Map<String, Object> map;

  public List getList() {
    return list;
  }

  public Set<String> getSet() {
    return set;
  }

  public Map getMap() {
    return map;
  }

  public static void main(final String[] args) {
    CollectionLiteralUsage collectionUsage = new CollectionLiteralUsage();
    System.out.println(collectionUsage.getList());
    System.out.println(collectionUsage.getSet());
    System.out.println(collectionUsage.getMap());
  }
}

As before with the multiline code, remember to include an <annotationProcessor> element when compiling classes which use the annotations when using Maven.

pom.xml

...
<plugin>
  <groupId>org.apache.maven.plugins</groupId>
  <artifactId>maven-compiler-plugin</artifactId>
  <version>2.3.2</version>
  <configuration>
    <source>1.6</source>
    <target>1.6</target>
    <annotationProcessors>
      <annotationProcessor>
        org.adrianwalker.collectionliterals.ArrayListProcessor
      </annotationProcessor>
      <annotationProcessor>
        org.adrianwalker.collectionliterals.LinkedListProcessor
      </annotationProcessor>
      <annotationProcessor>
        org.adrianwalker.collectionliterals.HashSetProcessor
      </annotationProcessor>
      <annotationProcessor>
        org.adrianwalker.collectionliterals.HashMapProcessor
      </annotationProcessor>
    </annotationProcessors>
  </configuration>
</plugin>
...

A commenter on Stack Overflow had expressed an issue with this approach having 'a hard dependency on Maven', which is not right. The javac command has direct support for specifying annotation processors: http://docs.oracle.com/javase/6/docs/technotes/tools/solaris/javac.html#processing

Limitations

Currently the code does not support nested data structures, for example this JSON string cannot be used to generate code:

{
  "name":"Adrian Walker",
  "age":31,
  "address":[
    "line1",
    "line2",
    "line3"
  ]
}

Source Code

  • Annotations, annotation processors and example usage code available in GitHub - collection-literals

Rigging the National Lottery (Is Hard)

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:

  1. We only care about the bonus ball if we have 5 matching main balls - this loop can be executed only when we need it.
  2. An intersection of arrays can be used to count the main ball array/entry array matches.
  3. 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