Futoshiki Solver Tester

testFutoshiki.py

import sys
import urllib2
import xml.etree.ElementTree as etree
import subprocess


def parseBoard(boardData, size):
    board = []
    rowLength = 2 * size - 1

    for i in range(0, size):
        startChar = 2 * i  * rowLength
        newRow = []
        for j in range(startChar, startChar + rowLength, 2):
            if boardData[j] != '.':
                newRow.append(int(boardData[j]))
            else:
                newRow.append(0)
        board.append(newRow)

    # Parse constraints
    constraints = []    # Stores compared values in ascending order of value
    for i in range(0, size - 1):
        startChar = (2 * i + 1)  * rowLength
        for j in range(startChar, startChar + rowLength, 2):
            currentCol = (j - startChar) / 2
            if boardData[j] == 'v':
                constraints.append(( (i+1, currentCol), (i, currentCol) ))
            elif boardData[j] == '^':
                constraints.append(( (i, currentCol), (i+1, currentCol) ))

    for i in range(0, size):
        startChar = 2 * i  * rowLength
        for j in range(startChar+1, startChar + rowLength, 2):
            currentCol = (j - startChar) / 2
            if boardData[j] == '(':
                constraints.append(( (i, currentCol), (i, currentCol + 1) ))
            elif boardData[j] == ')':
                constraints.append(( (i, currentCol + 1), (i, currentCol) ))

    return (board, constraints)


def getPuzzle(size, difficulty, id):
    response = urllib2.urlopen('http://www.goobix.com/games/futoshiki/get.cgi?size=' + size.__str__() + '&difficulty=' + difficulty.__str__() + '&id=' + id.__str__())
    responseBody = response.read()
    tree = etree.fromstring(responseBody)
    gameData = tree.__dict__['text']

    (initialBoard, constraints) = parseBoard(gameData[ : len(gameData)/2], size)
    (finalBoard, constraints) = parseBoard(gameData[len(gameData)/2 : ], size)
    return (initialBoard, constraints)


def printBoardToFile(board, constraints, inputFilePath):
    f = open(inputFilePath, 'w')
    f.write(len(board).__str__() + '\n')
    for i in range(0, len(board)):
        for j in range(0, len(board[i])):
            if board[i][j] > 0:
                f.write((i+1).__str__() + ' ' + (j+1).__str__() + ' ' + board[i][j].__str__() + '\n')

    for i in range(0, len(constraints)):
        c = constraints[i]
        f.write((c[0][0]+1).__str__() + ' ' + (c[0][1]+1).__str__() + ' < ' +
                (c[1][0]+1).__str__() + ' ' + (c[1][1]+1).__str__() + '\n')


# Only overlooks a single whitespace after the last column of every row,
# and a newline character after the last row. Any other whitespace is considered
# as invalid format.
def checkExecutableOutputForPuzzle(board, constraints, outputText):
    rowLength = len(board)
    colLength = len(board[0])

    correctFormat = True
    if len(outputText) == (2 * colLength + 1) * rowLength:
        newLineAfterLastRow = True
        whitespaceAfterLastCol = True
    elif len(outputText) == (2 * colLength + 1) * rowLength - 1:
        newLineAfterLastRow = False
        whitespaceAfterLastCol = True
    elif len(outputText) == 2 * colLength * rowLength:
        newLineAfterLastRow = True
        whitespaceAfterLastCol = False
    elif len(outputText) == 2 * colLength * rowLength - 1:
        newLineAfterLastRow = False
        whitespaceAfterLastCol = False
    else:
        correctFormat = False

    lineLength = 2 * colLength
    if whitespaceAfterLastCol:
        print "b"
        lineLength += 1

    # Check for newline characters
    for i in range(lineLength - 1, lineLength * rowLength, lineLength):
        if outputText[i] != '\n':
            print "outputText[" + i.__str__() + "] = '" + outputText[i] + "' != '\\n'"
            correctFormat = False

    # Check for trailing whitespace at the end of each line
    if whitespaceAfterLastCol:
        for i in range(lineLength, lineLength * rowLength, lineLength):
            if outputText[i] != ' ':
                print "outputText[" + i.__str__() + "] = '" + outputText[i] + "' != ' '"
                correctFormat = False

    if correctFormat != True:
        print "FAILURE! Incorrect format."
        return False


    outputBoard = []
    for i in range(0, rowLength):
        newRow = []
        for j in range(0, lineLength, 2):
            cellValue = int(outputText[lineLength * i + j])
            if cellValue >= 1 and cellValue <= rowLength:
                newRow.append(cellValue)
            else:
                print "FAILURE! Cell value  (" + i.__str__() + ", " + j.__str__() + ") out of range."
                return False
        outputBoard.append(newRow)

    # Look for same or out-of-range elements in a row
    for i in range(0, rowLength):
        aList = [0] + outputBoard[i]
        aList.sort()
        for j in range(0, len(aList)):
            if j != aList[j]:
                print "FAILURE! Duplicate value on row " + i.__str__() + "."
                return False

    # Look for same or out-of-range elements in a column
    for i in range(0, colLength):
        aList = [0]
        for j in range(0, rowLength):
            aList.append(outputBoard[j][i])
        aList.sort()
        for j in range(0, len(aList)):
            if j != aList[j]:
                print "FAILURE! Duplicate value on column " + j.__str__() + "."
                return False

    # Check if initial values on board are the same
    for i in range(0, rowLength):
        for j in range(0, colLength):
            if board[i][j] > 0 and outputBoard[i][j] != board[i][j]:
                print "FAILURE! Initial value given on board changed. (" + i.__str__() + ", " + j.__str__() + ")"
                return False

    # Check if constraints still hold
    for i in range(0, len(constraints)):
        (lHand, rHand) = constraints[i]
        if outputBoard[lHand[0]][lHand[1]] > outputBoard[rHand[0]][rHand[1]]:
            print "FAILURE! Constraint " + i.__str__() + " not satisfied."
            return False

    print "SUCCESS!"
    return True


def testExecutableWithPuzzle(board, constraints, executableFilePath, inputFilePath):
    printBoardToFile(board, constraints, inputFilePath)
    outputString = subprocess.check_output([executableFilePath, inputFilePath])
    return checkExecutableOutputForPuzzle(board, constraints, outputString)


def runTests(executableFilePath, inputFilePath):
    for s in range(4, 10):
        for d in range(1, 4):
            for i in range(0, 10000):
                (initialBoard, constraints) = getPuzzle(s, d, i)
                print "Testing for size=" + s.__str__() + ", difficulty=" + d.__str__() + ", id=" + i.__str__() + ": "
                result = testExecutableWithPuzzle(initialBoard, constraints, executableFilePath, inputFilePath)
                if result != True:
                    return


if __name__ == '__main__':
    executableFilePath = ''
    inputFilePath = ''
    print "len(sys.argv)="+len(sys.argv).__str__()

    if len(sys.argv) == 1:
        print "This script takes 2 command line arguments: file path of the executable, and a file path suggestion for the sample input file.\n"
    elif len(sys.argv) == 2:
        executableFilePath = sys.argv[1]
        inputFilePath = './CENG561HW2SAMPLEINPUT.txt'
        print 'No input file name suggested. Automatically assigned:' + inputFilePath + "\n"
    elif len(sys.argv) == 3:
        executableFilePath = sys.argv[1]
        inputFilePath = sys.argv[2]
    else:
        print "Invalid number of command line arguments. Exiting...\n"

    try:
        if len(executableFilePath) > 0:
            f = open(inputFilePath, 'w')
            f.close()
            runTests(executableFilePath, inputFilePath)
    except:
        print''
#        print "Can not open file for writing. Exiting.\n"

Here's a quick and not-so-elegant bit of Python script to fetch all the Futoshiki puzzles available on www.futoshiki.org sequentially and test if a Futoshiki solver executable works properly. The specifications of the solver executable can be found at http://www.ceng.metu.edu.tr/~e1746460/Homework02.pdf

This script is created for testing purposes and is a non-compulsory part of a homework assignment given in Artificial Intelligence course at Middle East Technical University. I am afraid the code is not so platform-independent. Still, it seems to work on my personal machine running Ubuntu 14.04 and JRE 1.8.0.

After putting it to your FutoshikiSolver directory(see the specs at the link above) you can run it from the command line simply by entering the command "python testFutoshiki.py ./<your_executable_filename>.jar".

Let me know if you run into any bugs in the script which you think is not caused by running it on a different platform than inek machines or by a difference in your output format.