On Programming. A Program Written Because of a Tweet: Calcu-Doku.py

I noticed a few days back that Twitter @Puzzlewright had started following me on Twitter. I sent a note saying, “Thanks for the vote of confidence. I am returning the favor.”

Soon thereafter I saw a twit from P. Wright about “calcu-doku,” yet another variant of sudoko and kenken. Calcu-doku has several variants, perhaps the simplest being kenken with just one arithmetic operator.

This inspired me to write the following variant of my KenKen Solver in Python. I expect this is one of the first, if not the first, program to be written because of a tweet.

I see by Puzzlewright’s home page that next week is Calcu-Doku week, and so offer this code as a contribution to that effort.

# Copyright (C) 2009, David Shields
# Licensed under "License Dave Shields for Software" available at https://daveshields.wordpress.com/about/#license
#
# A puzzle is represented by a list [title-string, puzzle-size, cage-list]
# where
#   title-string is a string identifying the puzzle
#   puzzle-size is an integer giving the number of rows (and also columns)
#   operator is a string, one of '+', '-', '*', '/' and '='
#   cage-list is a list of cages

# A cage is a list (result-value,  cell-list)
# where
#   result-value is the value of the operator applied to the values in the cells in the cell-list
#   cell-list is a list of cells

# A cell is a list (row, column)
#   By convention, the first cell in the cell-list is the topmost, leftmost cell, but this is not required.
#
# An assignment is a list of cages and assignments of values for the cells in each cage: [cage, values]
#

# A solution is a list of assignments to cages that satisfies the non-duplication requirement

import copy
import pprint
import string
import sys

def add(size, cage):
    # ways to get result res with puzzle size size and length length
    # if length is two and since must add at least one, then just
    # look at values less than result
    result, cells = cage
    length = len(cells)
    r = []
    if result == 0:
        return r
    if length < 2:
        return r
    if length == 2:
        for i in range(size):
            n = i+1
            if result - n  0 and (result - n) > 0:
                    r.append([n, result - n])
                    #                if result -n != n: # append complentary choice if it is different
                        #                    r.append([result - n, n])
    else:
        # try all the possibilities for first cell, and then look for alternatives in the remaining cells
        for i in range(size-1):
            n = i+1
            tail = [result - n, cells[1:]]
            others = add(size, tail)
            t = [n]
            for o in others:
                 r.append([n] + o)
    if length == 3: # remove obvious incorrect possibilities
        trim3(cage, r)
    return r

def adjacent(cell0, cell1):
    r0, c0 = cell0
    r1, c1 = cell1
    if r0 == r1 or c0 == c1: return True
    return False
    
def choices(puzzle):
    title,size,operator, cages = puzzle
    res = []
    for cage in cages:
        result, cells = cage
        length = len(cells)
        if length == 1:
            possible = [[result]]
        elif operator == '+':
            possible = add(size, cage)
        elif operator == '-':
            possible = subtract(size, cage)
        elif operator == '*':
            possible = multiply(size, cage)
        elif operator == '/':
            possible = divide(size, cage)
        else:
            print "error, unknown operator",operator
        if possible == None or len(possible) == 0:
            print "no solution for cage ", result, operator, cells
            print " ", 1 / 0
        res.append(possible)
    return res


def classify(cells): #classify triple, returning center
    if len(cells) != 3: return None
    cell0, cell1, cell2 = cells
    if adjacent(cell0, cell1) and adjacent(cell0, cell2): return 0
    if adjacent(cell1, cell0) and adjacent(cell1, cell2): return 1
    if adjacent(cell2, cell0) and adjacent(cell2, cell1): return 2
    return []
    
def divide(size, cage):
    result = cage[0]
    r = []
    if result > size:
        print "error, impossible division", result,size
    else:

        for i in range(size):
            n = i + 1
            if n * result <= size:
                r.append(&#91;n, n*result&#93;)
                r.append(&#91;n*result, n&#93;)
    return r
    
def multiply(size, cage):
#   ways to get -result- by multiplying -length- numbers for puzzle of given -size-
    r = &#91;&#93;
    result, cells = cage
    length = len(cells)
    if result == 1:
        # here if want result of 1, so add appropriate number of 1's
        t = &#91;&#93;
        for i in range(length):
            t.append(1)
        r.append(t)
        return r
    if length == 2:
        for i in range(size):
            n = i + 1 # trial divisor
            (quot, rem) =  divmod(result, n)
            if rem == 0:
                if quot  size: break # if too big
        (quot,rem) = divmod(result, n)
        if rem: continue # not a divisor
        # have possible choice for first
        now = &#91;quot, size, cage&#91;1:&#93;&#93;
        others = multiply(size, now)
        for o in others:
            t = &#91;n&#93;
            t.extend(o)
            r.append(t)
    if len == 3: # remove obvious incorrect possibilities
        trim3(cage, r)
    return r

def printsolution(puzzle, solution): #choices, guess):
# solution is list of form &#91;row,col, value&#93;
    title, size, operator, cages = puzzle
    cells = &#91;0&#93; * (size * size)

    for s in range(len(solution)):
        row, col, value  = solution&#91;s&#93;
        cells&#91;col*size + row&#93; = value
    for row in range(size):
        for col in range(size):
            print " ", cells&#91;col*size + row&#93;, " ",
        print ""
        
def readpuzzle():
# read puzzle from standard input
    text  = ""
    lines =  sys.stdin.readlines()
    cages = &#91;&#93;
    nlines = 0
    for line in lines:
        words = line.split() # break line into words separated by whitespace
        if len(words) == 0:
            continue # ignore blank line
        nlines += 1
        cage =  &#91;&#93;
#        print "nlines, line", nlines, line
        if nlines==1:
            title =  line
        elif nlines == 2:
            size = string.atoi(line)
        elif nlines == 3:
            operator = line&#91;0&#93;
        else:
            # new cage
            result = string.atoi(words&#91;0&#93;)
            row = string.atoi(words&#91;1&#93;)
            col =  string.atoi(words&#91;2&#93;)
            cells = &#91;&#91;row,col&#93;&#93;
            if len(words) > 3: # if have more than one cell
                moves = words[3]
                for m in moves:
                    if m == 'r':
                        col += 1
                    elif m == 'l':
                        col -= 1
                    elif m == 'd':
                        row += 1
                    elif m == 'u':
                        row -= 1
                    if [row,col] not in cells: # if new cell
                        cells = cells + [[row,col]]
            cages.append([result, cells])
    return [title, size, operator, cages]

def subtract(size, cage):
    result, cells = cage
    r = []
    if result > size:
        pass
        # no, just look at multiples that match ...
    else:
        for i in range(size):
            v = i + 1
            if (v + result) = trials:
            break
        trial += 1
        t = trial
        if t % 10000 == 0:
            print t
        if t // 100000000:
            print "too many tries", t,
            break;
        solution = []
        guess = []
        nfound = 0
        for i in range(ncages):
            (t,g) = divmod(t, len(c[i]))
            guess.append(g)
        # now fill out solution for this guess
        solution = []
        # This is exhaustive search,
        # it would be better to check for duplicates on the fly
        for i in range(ncages):
            gi = guess[i]
            choicelist = c[i]
            choice = choicelist[gi]
            cage = cages[i]
            cells = cage[1]
            for ci in range(len(cells)):
                row,col = cells[ci]
                if ci= len(choice):
                    print "choice index error", ci, trial
                try:
                    solution.append([row,col, choice[ci]])
                    nfound += 1
                except IndexError:
                    print "error ", row, col, ci, choice
                    raise ValueError
        if nfound != (size * size):
                    print "sizezzzz", nfound, size
        if verify(puzzle, solution):
            print "success:", guess
            print "took ", trial, " trials"
            printsolution(puzzle, solution)
            return guess
    print "no solution"

def trim3(cage, possibles):
    result, cells = cage
    pivot = classify(cells)
    pi = 0
    for pin in possibles:
        p = copy.copy(pin)
        pvalue = p[pivot]
        del p[pivot]
        other1,other2 = p
        if pivot == other1 or pivot == other2: # if cannot be solution
            del possibles[pi]
        pi += 1
    
        
def verify(puzzle, solution): #choices, guess):
# solution is list of form [row,col, value]
    title, size, operator, cages = puzzle
    if len(solution) != (size * size):
        print "solution,len error", len(solution), size
    cells = [0] * (size * size)

    rows = [[]] * size
    cols = [[]] * size
    for s in range(len(solution)):
        row, col, v  = solution[s]
        if row in rows[v-1]:
            return 0; # value already used, so cannot verify
        if col in cols[v-1]:
            return 0; # value already used, so cannot verify
        rows[v-1] = rows[v-1] + [row]
        cols[v-1] = cols[v-1] + [col]

    return 1 # found match!
                # set up possible assignments


puzzle = readpuzzle()
pprint.pprint(puzzle)
c =  choices(puzzle)
print "choices"
pprint.pprint(c)
solve(puzzle, c)
Advertisements

One Comment

  1. Posted April 21, 2009 at 17:33 | Permalink | Reply

    Well I wrote my KenKen solver in response to your tweet, but I was just copying your idea 🙂

One Trackback

  1. […] The Wayward Word Press WordPress gave me a blog to see how I was going to handle it « On Programming. A Program Written Because of a Tweet: Calcu-Doku.py […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

  • Pages

  • April 2009
    M T W T F S S
    « Mar   May »
     12345
    6789101112
    13141516171819
    20212223242526
    27282930  
  • RSS The Wayward Word Press

  • Recent Comments

    russurquhart1 on SPITBOL for OSX is now av…
    dave porter on On being the maintainer, sole…
    daveshields on On being the maintainer, sole…
    Paul Tallett on On being the maintainer, sole…
    mrrdev on On being the maintainer, sole…
  • Archives

  • Blog Stats

  • Top Posts

  • Top Rated

  • Recent Posts

  • Archives

  • Top Rated

  • %d bloggers like this: