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)

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 )

Google photo

You are commenting using your Google 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 )

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

    Sahana’s Respo… on A brief history of Sahana by S…
    Sahana’s Respo… on A brief history of Sahana by S…
    James Murray on On being the maintainer, sole…
    James Murray 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: