generate_tables.py

#!/usr/bin/python

"""Generates a csv file with random numbers following a set of rules.

Usage:
python generate_tables.py -h

Examples:
python generate_tables.py -t 1 -c 11 -m 14 -r 4
python generate_tables.py -t 1 -c 14 -m 14 -r 4
python generate_tables.py -t 1 -c 28 -m 14 -r 4
python generate_tables.py -t 1 -c 30 -m 14 -r 4
python generate_tables.py -t 100 -c 28 -m 14 -r 4 -o o100.csv

Warning:
Every execution will overwrite the output file if exists with the new data.
This is an intentional behavior by design.

Requirements:
1) The output should be readable by Excel.
    .csv was chosen, which can be imported into an Excel document.
2) The output should be an n-by-m table with numbers between 1 and X.
3) Each column (m) should contain numbers from 1..X at most once.
4) Any number's neighbor in all 8 directions including diagonal shall not be the same.
5) If the number of columns (m) is less than or equal to the maximum number (X),
    then each number shall be used at most once.
6) If the number of columns (m) is greater than the maximum number (X),
    then each number shall not be used more frequently than m/X assuming m/X is
    an integer.
7) In 6) if m/X is not an integer, than use the closest greater integer.
8) Using 1..X should prefill the first few cells starting from 0,0 and going downwards first:
    E.g. 1 5  9 13  .  .
         2 6 10 14  .  .
         3 7 11  .  .  .
         4 8 12  .  .  .
Bugs:
1) For certain input parameters it cannot find a soltion. In such cases a
 StopIteration exception is raised after 10000 tries to avoid infinite loop.
 Such an input vector: --tables 1 --columns 4 --maximumNumber 4 -rows 3
"""

import argparse
import csv
import math
import random
from collections import defaultdict

__author__ = "Zsolt Lattmann"
__license__ = "MIT"
__version__ = "1.0.0"
__maintainer__ = "Zsolt Lattmann"
__status__ = "Prototype"


parser = argparse.ArgumentParser(description='Generates tables using the input arguments.')
parser.add_argument('-m', '--maximumNumber', default=14, type=int,
                   help='Maximum number that can appear in the table.')
parser.add_argument('-c', '--columns', default=28, type=int,
                   help='Number of columns')
parser.add_argument('-r', '--rows', default=4, type=int,
                   help='Number of rows')
parser.add_argument('-t', '--tables', default=4, type=int,
                    help='Number of tables')
parser.add_argument('-o', '--out',
                    default='output.csv',
                    help='Output filename')

args = parser.parse_args()

maximumNumber = args.maximumNumber
numColumns = args.columns
numRows = args.rows
numTables = args.tables

print 'Parameters: ', args

def generate(maxNumber, numCol, numRow):
    # check preconditions and basic assumptions
    if maxNumber < 1:
        raise ValueError('Max number has to be equal or greater 1.')
    if numCol < 1:
        raise ValueError('Number of columns has to be equal or greater 1.')
    if numRow < 1:
        raise ValueError('Number of rows has to be equal or greater 1.')
    if maxNumber <= numRow:
        raise ValueError('Max number has to be greater than number of rows.')

    maxOccurancePerRow = int(math.ceil(numCol / maxNumber))
    maxOccurance = maxOccurancePerRow * numRow

    # initialize data structures
    numbers = defaultdict(int)
    numbersPerRow = []

    toPickFrom = range(0, maxNumber)

    solution = []

    for j in range(0, numRow):
        solution.append([])
        for i in range(0, numCol):
            # fill up with -1, if -1 shows up in the solution we potentially have a bug
            solution[j].append(-1)

    for j in range(0, numRow):
        numbersPerRow.append(defaultdict(int))
        for i in range(0, numCol):
            possibleChoices = list(toPickFrom)

            # filtering numbers that we should not choose
            if j > 0:
                for k in range(0, j):
                    # cannot be any number above in this column
                    toRemove = solution[j - 1 - k][i]
                    if toRemove in possibleChoices:
                        possibleChoices.remove(toRemove)
            if i > 0:
                if maxNumber < numCol:
                    maxRangeToCheck = 1 # check only before
                else:
                    maxRangeToCheck = i # check entire row cannot be the number to the left

                for k in range(0, maxRangeToCheck):
                    toRemove = solution[j][i - 1 - k]
                    if toRemove in possibleChoices:
                        possibleChoices.remove(toRemove)

            if i > 0 and j > 0:
                # cannot be the number to the left and above (diagonal)
                toRemove = solution[j - 1][i - 1]
                if toRemove in possibleChoices:
                    possibleChoices.remove(toRemove)
            if i < numCol - 1 and j > 0:
                # cannot be the number to the right and above (diagonal)
                toRemove = solution[j - 1][i + 1]
                if toRemove in possibleChoices:
                    possibleChoices.remove(toRemove)

            for num in numbersPerRow[j]:
                #print maxOccurancePerRow, num, possibleChoices
                if numbersPerRow[j][num] >= maxOccurancePerRow:
                    toRemove = num
                    if toRemove in possibleChoices:
                        possibleChoices.remove(toRemove)

            if len(possibleChoices) == 0:
                # consider to reinitialize and retry for a few numbers or swap numbers
                raise StopIteration('Cannot pick the next number please rerun the program')

            # prefill starting with columns, we need to add 1 since indexing is from 0
            possibleNumber = (i * numRow) + j + 1

            if possibleNumber > maxNumber:
                # pick a random one
                randomNumber = random.choice(possibleChoices)
            else:
                # indexing is from 0 we need to substruct 1 here
                randomNumber = possibleNumber - 1
                if not randomNumber in possibleChoices:
                    raise StopIteration('Cannot pick the next number please rerun the program')

            # keep track of what we picked
            numbers[randomNumber] += 1
            if numbers[randomNumber] == maxOccurance:
                toPickFrom.remove(randomNumber)

            # keep track of what we picked for this row
            numbersPerRow[j][randomNumber] += 1

            # save the picked number into the solution
            solution[j][i] = randomNumber

        # at the end of the row compute sum of the row, sanity check
        solution[j].append(sum(solution[j]))

    # adjust all numbers by 1
    for j in range(0, numRow):
        for i in range(0, numCol):
            solution[j][i] = solution[j][i] + 1

    return solution

def tryGenerateMultipleTimes(maxNumber, numCol, numRow, threshold = 1000):
    maxIterations = threshold
    while True:
        try:
            return generate(maxNumber, numCol, numRow)
        except StopIteration:
            # ignore and retry
            #print 'retry'
            maxIterations -= 1
            if maxIterations < 0:
                raise StopIteration('Cannot find a solution within the max iterations.')
            pass

# initializing solutions
solutions = []

print 'Generating tables ...'
for i in range(0, numTables):
    solutions.append([])
    print 'Generating #', i + 1, ' of ', numTables
    solution = tryGenerateMultipleTimes(maximumNumber, numColumns, numRows)
    solutions = solutions + solution


print 'Saving file to: ', args.out
with open(args.out, "wb") as f:
    writer = csv.writer(f)
    writer.writerows(solutions)

print 'Output was saved.'