2
\$\begingroup\$

(See the next iteration.)

Introduction

Suppose Evil Lottery Inc is interested in not paying millions of dollars back to players. They gather the drawn lottery rows first, after which they mine rows that does not appear in the dataset.

The Evil Lottery Inc's approach is this: it first builds a radix tree of the drawn lottery rows:

Radix tree for representing lottery rows data

After the tree is ready, the Evil Algorithm mines for all the lottery rows that do not appear in the data set, and chooses it as the next show result.

Output

The output for 40M randomly generated lottery rows in Finnish Veikkaus lottery (40 balls, 7 drawn, 40 choose 7 = 18643560) is:

1,2,3
1,2,5
1,3,4
1,4,5
2,3,4
2,3,5
Seed = 1588051533998
Data generated in 49625 milliseconds.
Duration: 115987 milliseconds.
Missing lottery rows: 2181642

Memory note Please specify in invocation of java ... -XmsNm -XmxNm with large enough N.

Code

net.coderodde.datamining.lottery.LotteryConfiguration.java

package net.coderodde.datamining.lottery;

/**
 * This class specifies the lottery game configuration.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 18, 2020)
 * @since 1.6 (Jan 18, 2020)
 */
public final class LotteryConfiguration {

    /**
     * The maximum ball integer value.
     */
    private final int maximumNumberValue;

    /**
     * The length of each lottery row.
     */
    private final int lotteryRowLength;

    /**
     * Construct a new lottery configuration.
     * 
     * @param maximumNumberValue the maximum ball integer value.
     * @param lotteryRowLength   the lottery row length.
     */
    public LotteryConfiguration(final int maximumNumberValue,
                                final int lotteryRowLength) {
        checkArgs(maximumNumberValue, lotteryRowLength);
        this.maximumNumberValue = maximumNumberValue;
        this.lotteryRowLength   = lotteryRowLength;
    }

    /**
     * Returns the maximum ball value/number.
     * 
     * @return the maximum bill value/number.
     */
    public int getMaximumNumberValue() {
        return this.maximumNumberValue;
    }

    /**
     * Returns the number of drawn balls.
     * 
     * @return the number of drawn balls.
     */
    public int getLotteryRowLength() {
        return this.lotteryRowLength;
    }

    private static void checkArgs(int maximumNumber, int numberCount) {
        if (maximumNumber < 1) {
            throw new IllegalArgumentException(
                    "maximumNumber(" + maximumNumber + ") < 1");
        }

        if (numberCount < 1) {
            throw new IllegalArgumentException(
                    "numberCount(" + numberCount + ") < 1");
        }

        if (numberCount > maximumNumber) {
            throw new IllegalArgumentException(
                    "numberCount(" + numberCount + ") > " + 
                    "maximumNumber(" + maximumNumber + ")");
        }
    }
}

net.coderodde.datamining.lottery.LotteryRow.java

package net.coderodde.datamining.lottery;

import java.util.Arrays;
import java.util.Objects;

/**
 * This class implements a single lottery row.
 * 
 * @author Rodion "rodde" Efremove
 * @version 1.61 (Apr 27, 2020) ~ removed manual sorting.
 * @version 1.6 (Apr 18, 2020) ~ initial version.
 * @since 1.6 (Apr 18, 2020)
 */
public final class LotteryRow {

    /**
     * The configuration object.
     */
    private final LotteryConfiguration lotteryConfiguration;

    /**
     * The actual lottery numbers.
     */
    private final int[] lotteryNumbers;

    /**
     * Stores the index of the internal storage array at which the next lottery
     * number will be inserted.
     */
    private int size = 0;

    /**
     * Constructs an empty lottery row with given configuration.
     * 
     * @param lotteryConfiguration the lottery row configuration.
     */
    public LotteryRow(LotteryConfiguration lotteryConfiguration) {
        this.lotteryConfiguration = 
                Objects.requireNonNull(lotteryConfiguration);

        this.lotteryNumbers =
                new int[lotteryConfiguration.getLotteryRowLength()];
    }

    @Override
    public String toString() {
        final StringBuilder stringBuilder = new StringBuilder();
        boolean isFirst = true;

        for (final int number : this.lotteryNumbers) {
            if (isFirst) {
                isFirst = false;
                stringBuilder.append(number);
            } else {
                stringBuilder.append(",").append(number);
            }
        }

        return stringBuilder.toString();
    }

    /**
     * Appends a number to the tail of this lottery row.
     * 
     * @param number the number to append.
     */
    public void appendNumber(int number) {
        checkNumber(number);
        checkHasSpaceForNewNumber();
        this.lotteryNumbers[this.size++] = number;
        Arrays.sort(this.lotteryNumbers, 0, size);
    }

    /**
     * Returns the <code>index</code>th number.
     * 
     * @param index the index of the desired number.
     * @return the <code>index</code>th number.
     */
    public int getNumber(int index) {
        checkIndex(index);
        return this.lotteryNumbers[index];
    }

    /**
     * Returns the length of the lottery row in numbers.
     * 
     * @return the length of the lottery row.
     */
    public int size() {
        return this.lotteryConfiguration.getLotteryRowLength();
    }

    /**
     * Returns the configuration object of this row.
     * 
     * @return the configuration object.
     */
    public LotteryConfiguration getLotteryConfiguration() {
        return this.lotteryConfiguration;
    }

    /**
     * Checks that there is more space for lottery numbers in this row.
     */
    private void checkHasSpaceForNewNumber() {
        if (size == lotteryNumbers.length) {
            throw new IllegalStateException(
                    "The lottery row cannot accommodate more numbers.");
        }
    }

    /**
     * Checks that the input number is within the lottery number range.
     * 
     * @param number the number to check.
     */
    private void checkNumber(int number) {
        if (number < 1) {
            throw new IllegalArgumentException("number(" + number + ") < 1");
        }

        if (number > this.lotteryConfiguration.getMaximumNumberValue()) {
            throw new IllegalArgumentException(
                "number (" + number + ") > " +
                "this.lotteryConfiguration.getMaximumNumberValue()[" +
                this.lotteryConfiguration.getMaximumNumberValue() + "]");
        }
    }

    /**
     * Checks that the index is withing the range <code>[0, n)</code>.
     * 
     * @param index the index to check.
     */
    private void checkIndex(int index) {
        if (index < 0) {
            throw new IllegalArgumentException("index(" + index + ") < 0");
        }

        if (index >= this.size) {
            throw new IllegalArgumentException(
                    "index(" + index + ") >= this.index(" + this.size + ")");
        }
    }
}

net.coderodde.datamining.lottery.LotteryRowGenerator.java

package net.coderodde.datamining.lottery;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Random;

/**
 * This class implements a facility for creating random lottery rows.
 * 
 * @author Rodion "rodde" Efremov 
 * @version 1.6 (Apr 18, 2020) 
 * @since 1.6 (Apr 18, 2020)
 */
public final class LotteryRowGenerator {

    /**
     * The lottery configuration object.
     */
    private final LotteryConfiguration lotteryConfiguration;

    /**
     * The random number generator.
     */
    private final Random random;

    /**
     * The storage array for.
     */
    private final int[] numbers;

    /**
     * Constructs a {@code LotteryRowGenerator} with a given configuration.
     * 
     * @param lotteryConfiguration the lottery configuration object.
     */
    public LotteryRowGenerator(LotteryConfiguration lotteryConfiguration) {
        this(lotteryConfiguration, new Random());
    }

    /**
     * Constructs a {@code LotteryRowGenerator} with a given configuration and
     * a seed value.
     * 
     * @param lotteryConfiguration the lottery configuration object.
     * @param seed the seed value.
     */
    public LotteryRowGenerator(LotteryConfiguration lotteryConfiguration,
                               long seed) {
        this(lotteryConfiguration, new Random(seed));
    }

    /**
     * Constructs a {@code LotteryRowGenerator} with a given configuration and
     * a random number generator.
     * 
     * @param lotteryConfiguration the lottery configuration object.
     * @param random the random number generator.
     */
    public LotteryRowGenerator(LotteryConfiguration lotteryConfiguration,
                               Random random) {
        this.random = Objects.requireNonNull(random, 
                                             "The input Random is null.");
        this.lotteryConfiguration =
                Objects.requireNonNull(
                        lotteryConfiguration,
                        "The input LotteryConfiguration is null.");

        this.numbers = new int[lotteryConfiguration.getMaximumNumberValue()];

        for (int i = 0; i < this.numbers.length; i++) {
            this.numbers[i] = i + 1;
        }
    }

    /**
     * Generates and returns a list of random lottery rows.
     * 
     * @param numberOfLotteryRows the requested number of lottery rows.
     * @return a list of random rows.
     */
    public List<LotteryRow> 
        generateLotteryRows(int numberOfLotteryRows) {
        List<LotteryRow> rows = new ArrayList<>(numberOfLotteryRows);

        for (int i = 0; i < numberOfLotteryRows; i++) {
            rows.add(generateRow());
        }

        return rows;
    }

    private LotteryRow generateRow() {
        LotteryRow lotteryRow = new LotteryRow(this.lotteryConfiguration);
        shuffleInternalNumbers();
        loadLotteryRow(lotteryRow);
        return lotteryRow;
    }

    private void shuffleInternalNumbers() {
        for (int i = 0, n = this.lotteryConfiguration.getMaximumNumberValue();
                i < n; 
                i++) {
            final int i2 = getRandomIndex();
            swap(i, i2);
        }
    }

    public void loadLotteryRow(LotteryRow lotteryRow) {
        for (int i = 0, n = this.lotteryConfiguration.getLotteryRowLength();
                i < n;
                i++) {
            lotteryRow.appendNumber(this.numbers[i]);
        }
    }

    private int getRandomIndex() {
        return this.random.nextInt(
                this.lotteryConfiguration.getMaximumNumberValue());
    }

    private void swap(final int index1, final int index2) {
        int tmp = this.numbers[index1];
        this.numbers[index1] = this.numbers[index2];
        this.numbers[index2] = tmp;
    }
}

net.coderodde.datamining.lottery.MissingLotteryRowsGenerator

package net.coderodde.datamining.lottery;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * This class implements a tree data structure for infering missing lottery 
 * rows.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.61 (Apr 27, 2020) ~ renamed the class.
 * @version 1.6 (Apr 20, 2020) ~ initial version.
 * @since 1.6 (Apr 20, 2020)
 */
public final class MissingLotteryRowsGenerator {

    /**
     * This inner class implements an integer tree node type.
     */
    private static final class IntegerTreeNode {

        /**
         * Children map.
         */
        private SortedMap<Integer, IntegerTreeNode> children;

        /**
         * Returns the textual representation of this 
         * {@linkplain net.coderodde.datamining.lottery.LotteryRowsIntegerTree.IntegerTreeNode}.
         * 
         * @return the textual representation of this tree node.
         */
        @Override
        public String toString() {
            return "{children: " + children.toString() + "}";
        }
    }

    /**
     * The root node of this integer tree.
     */
    private IntegerTreeNode root = new IntegerTreeNode();

    /**
     * The lottery configuration.
     */
    private final LotteryConfiguration lotteryConfiguration;

    /**
     * Caches the length of the lottery rows.
     */
    private final int length;

    /**
     * Implements the main constructor.
     * 
     * @param lotteryConfiguration the lottery configuration object.
     * @param root the root node of the radix tree.
     */
    private MissingLotteryRowsGenerator(
            final LotteryConfiguration lotteryConfiguration,
            final IntegerTreeNode root) {

        this.lotteryConfiguration =
                Objects.requireNonNull(
                        lotteryConfiguration, 
                        "lotteryConfiguration == null");

        this.root = Objects.requireNonNull(root, "The root node is null.");
        this.length = this.lotteryConfiguration.getLotteryRowLength();
    }

    /**
     * Constructs a missing rows generator with given lottery configuration.
     * 
     * @param lotteryConfiguration the lottery configuration.
     */
    public MissingLotteryRowsGenerator(
            final LotteryConfiguration lotteryConfiguration) {
        this(lotteryConfiguration, new IntegerTreeNode());
    }

    /**
     * Adds a list of lottery rows to this generator.
     * 
     * @param lotteryRows the lottery rows to add one by one.
     * @return this generator for chaining.
     */
    public MissingLotteryRowsGenerator 
        addLotteryRows(final List<LotteryRow> lotteryRows) {

        for (final LotteryRow lotteryRow : lotteryRows) {
            addLotteryRow(lotteryRow);
        }

        return this;
    }

    /**
     * Adds a single lottery row to this generator.
     * 
     * @param lotteryRow the lottery row to add.
     * @return this generator for chaining.
     */
    public MissingLotteryRowsGenerator 
        addLotteryRow(final LotteryRow lotteryRow) {

        Objects.requireNonNull(lotteryRow, "lotteryRow == null");
        checkLotteryRow(lotteryRow);
        IntegerTreeNode node = root;

        for (int i = 0, sz = this.length; i < sz; i++) {
            final IntegerTreeNode nextNode;
            final int number = lotteryRow.getNumber(i);

            if (node.children == null) {
                node.children = new TreeMap<>();
            }

            if (!node.children.containsKey(number)) {
                node.children.put(number, nextNode = new IntegerTreeNode());

                if (i < sz - 1) {
                    nextNode.children = new TreeMap<>();
                }
            } else {
                nextNode = node.children.get(number);
            }

            node = nextNode;
        }

        return this;
    }

    /**
     * Computes and returns all the <i>missing</i> lottery rows. A lottery row 
     * is <i>missing</i> if and only if it was not drawn in the population of
     * players.
     * 
     * @return the list of missing lottery rows.
     */
    public List<LotteryRow> computeMissingLotteryRows() {
        List<LotteryRow> lotteryRows = new ArrayList<>();
        final int[] numbers = getInitialNumbers();

        do {
            LotteryRow lotteryRow = convertNumbersToLotteryRow(numbers);

            if (!treeContains(lotteryRow)) {
                lotteryRows.add(lotteryRow);
            }

        } while (increment(numbers));

        return lotteryRows;
    }

    private boolean treeContains(final LotteryRow lotteryRow) {
        IntegerTreeNode node = root;

        for (int i = 0; i < this.length; i++) {
            final int number = lotteryRow.getNumber(i);
            final IntegerTreeNode nextNode = node.children.get(number);

            if (nextNode == null) {
                return false;
            }

            node = nextNode;
        }

        return true;
    }

    private boolean increment(final int[] numbers) {
        final int maximumNumber =
                this.lotteryConfiguration.getMaximumNumberValue();

        for (int i = this.length - 1, j = 0; i >= 0; i--, j++) {
            if (numbers[i] < maximumNumber - j) {
                numbers[i]++;

                for (int k = i + 1; k < this.length; k++) {
                    numbers[k] = numbers[k - 1] + 1;
                }

                return true;
            }
        }

        return false;
    }

    /**
     * Converts a number integer array into a 
     * {@link net.coderodde.datamining.lottery.LotteryRow}.
     * @param numbers the raw number array in ascending order.
     * @return the lottery row with exactly the same numbers as in 
     * {@code numbers}.
     */
    private LotteryRow convertNumbersToLotteryRow(final int[] numbers) {
        LotteryRow lotteryRow = new LotteryRow(this.lotteryConfiguration);

        for (final int number : numbers) {
            lotteryRow.appendNumber(number);
        }

        return lotteryRow;
    }

    private int[] getInitialNumbers() {
        final int[] numbers = new int[this.length];

        for (int i = 0, number = 1; i < this.length; i++, number++) {
            numbers[i] = number;
        }

        return numbers;
    }

    private void checkLotteryRow(final LotteryRow lotteryRow) {
        if (lotteryRow.size() != this.length) {
            throw new IllegalArgumentException(
                    "Wrong length of a row (" + lotteryRow.size() + ", " +
                            "must be exactly " + 
                            this.lotteryConfiguration.getLotteryRowLength() + 
                            ".");
        }
    }
}

net.coderodde.datamining.lottery.Demo.java

package net.coderodde.datamining.lottery;

import java.io.IOException;
import java.util.Arrays;
import java.util.List;

/**
 * This class demonstrates the functionality of the missing lottery row data
 * mining algorithm.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 25, 2020)
 * @since 1.6 (Apr 25, 2020)
 */
public class Demo {

    // 40 choose 7 = 18_643_560 combinations:
    private static final int LOTTERY_ROW_LENGTH = 7;
    private static final int LOTTERY_MAXIMUM_NUMBER = 40;
    private static final int LOTTERY_ROWS = 40_000_000;

    public static void main(String[] args) throws IOException {
        smallDemo();

        final long seed = System.currentTimeMillis();
        final LotteryConfiguration lotteryConfiguration = 
                new LotteryConfiguration(LOTTERY_MAXIMUM_NUMBER,
                                         LOTTERY_ROW_LENGTH);

        System.out.println("Seed = " + seed);

        final List<LotteryRow> data = benchmarkAndObtainData(seed);
        benchmark(lotteryConfiguration, data);
    }

    private static List<LotteryRow> benchmarkAndObtainData(final long seed) {
        final LotteryConfiguration lotteryConfiguration = 
                new LotteryConfiguration(LOTTERY_MAXIMUM_NUMBER,    
                                         LOTTERY_ROW_LENGTH);

        // Warmup run:
        new LotteryRowGenerator(lotteryConfiguration, seed)
                .generateLotteryRows(LOTTERY_ROWS);

        long startTime = System.nanoTime();

        // Data generation: 
        final List<LotteryRow> data =
                new LotteryRowGenerator(lotteryConfiguration)
                        .generateLotteryRows(LOTTERY_ROWS);

        long endTime = System.nanoTime();

        System.out.println(
                "Data generated in " + 
                        ((endTime - startTime) / 1_000_000L) + 
                        " milliseconds.");

        return data;
    }

    // Warms up and benchmarks the 
    private static void benchmark(
            final LotteryConfiguration lotteryConfiguration,
            final List<LotteryRow> data) throws IOException {

        final long startTime = System.nanoTime();

        final List<LotteryRow> missingLotteryRows = 
            new MissingLotteryRowsGenerator(lotteryConfiguration)
                .addLotteryRows(data)
                .computeMissingLotteryRows();

        final long endTime = System.nanoTime();

        System.out.println(
                "Duration: " 
                        + ((endTime - startTime) / 1_000_000L) 
                        + " milliseconds.");

        System.out.println(
                "Missing lottery rows: " + missingLotteryRows.size());

//        boolean isFirst = true;
//        
//        for (final LotteryRow lotteryRow : missingLotteryRows) {
//            if (isFirst) {
//                isFirst = false;
//            } else {
//                System.out.println();
//            }
//            
//            System.out.print(lotteryRow);
//        }
    }

    // Runs a small demo:
    private static void smallDemo() {
        LotteryConfiguration lotteryConfiguration = 
                new LotteryConfiguration(5, 3);

        LotteryRow lotteryRow1 = new LotteryRow(lotteryConfiguration); // 1, 2, 4
        LotteryRow lotteryRow2 = new LotteryRow(lotteryConfiguration); // 2, 4, 5
        LotteryRow lotteryRow3 = new LotteryRow(lotteryConfiguration); // 1, 3, 5
        LotteryRow lotteryRow4 = new LotteryRow(lotteryConfiguration); // 3, 4, 5

        lotteryRow1.appendNumber(1);
        lotteryRow1.appendNumber(4);
        lotteryRow1.appendNumber(2);

        lotteryRow2.appendNumber(4);
        lotteryRow2.appendNumber(5);
        lotteryRow2.appendNumber(2);

        lotteryRow3.appendNumber(1);
        lotteryRow3.appendNumber(3);
        lotteryRow3.appendNumber(5);

        lotteryRow4.appendNumber(3);
        lotteryRow4.appendNumber(4);
        lotteryRow4.appendNumber(5);

        List<LotteryRow> drawnLotteryRows = Arrays.asList(lotteryRow1,
                                                          lotteryRow2,
                                                          lotteryRow3,
                                                          lotteryRow4);

        MissingLotteryRowsGenerator generator = 
                new MissingLotteryRowsGenerator(lotteryConfiguration);

        List<LotteryRow> missingLotteryRows = generator
                        .addLotteryRows(drawnLotteryRows)
                        .computeMissingLotteryRows();

        missingLotteryRows.forEach((row) -> { System.out.println(row);});
    }
}

(You can find the repository here.)

Critique request

I am most interested in comments regarding how idiomatic code I produced. For example, is it O.K. to use final and this here and there?

\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

You are bound to get different opinions on this one, but I personally do not like the use of final and this in various places:

public final class LotteryConfiguration

Here, final means "you cannot subclass this". Why? Is there a specific reason to forbid subclassing for once and for all? (In real-life projects, 95% of all times it was a bad idea to make a class final, though it always "seemed a good idea at that time".)

final in local variables:

public LotteryConfiguration(final int maximumNumberValue,
                            final int lotteryRowLength) {
    ...
}

final int maximumNumber = this.lotteryConfiguration.getMaximumNumberValue();

for (final int number : numbers) {
     ...
}

Here, final is just noise. OK, you explicitly declare that you will no assign a new value to a local variable, but who cares? Nobody needs this information, and - as your code in general is very readable and understandable - every reader sees this in a single glance without you explicitly telling them.

There are some situations, where the compiler needs an explicit final variable (even though "effectively final" has been introduced in java 8 to reduce this), but apart from that, I'd never use final on a local.

And while we are at compilers: no, todays compilers do not need this information for "optimizing" anymore.

final in class fields:

YES

Used correctly, this can make the class immutable (i.e. suitable for use as a hash-key), makes the intention clear, and is great information for the reader.

this: I normally use it only where it is needed (i.e. mostly when assigning a value in a constructor.)

Here:

public void appendNumber(int number) {
    checkNumber(number);
    checkHasSpaceForNewNumber();
    this.lotteryNumbers[this.size++] = number;
    Arrays.sort(this.lotteryNumbers, 0, size);
}

I would leave out the this. Again, it does not convey any additional information (there is no local lotteryNumbers which I could mistake it for) and adds noise. Apart from that, I use an IDE (this is not the 80s anymore) and see fields and local variables in different colors.

\$\endgroup\$
3
\$\begingroup\$

@mtj already provided a great answer; but I will add mine as I couldn't resist this.

Needless comments

The whole point of comments in code (IMHO) is to add information that is not there yet. Most often to describe WHY something is done in a way. The HOW, we can read from code if it is clean enough :).

Take a look a this comment for example. What does it add?

/**
 * The lottery configuration.
 */
private final LotteryConfiguration lotteryConfiguration;

Nothing valuable. It just repeats the code. It also makes refactoring harder, because you need to keep the comments in sync with the code.

Missing comments

This piece of code goes without comments, but would be an excellent candidate for clarification; WHY is the array initialized with 1 to numbers.length ? Can't tell from this code. (I can tell from the shuffle later on)

   for (int i = 0; i < this.numbers.length; i++) {
        this.numbers[i] = i + 1;
    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.