Never Get Out of the Boat

Being a brief look at
Logical Programming in Python

As motivated by
The Family Tree
&
Eight Queens Problem

Never Get Out of the Boat

Logical Programming

answer = solution.provider("CONTROL text GOES <here> mode=UNSAFE")

data_blob1 = "(son1 mother1 father1)
              (son2 mother1 father2)
               ...
              (dauther57 mother21 father43)"

data_blob2 = "(name1 son name2)
              (name2 daughter name3)
              ...
              (name78 son name3)"

SQL Sucks

Parsing a Family Tree in Python

family_tree = [('Brett Paufler', 'Boy', 'Mommy', 'Daddy'),
               ('Mommy', 'Girl', 'Mat Grandma', 'Mat Grandpa'),
               ('Daddy', 'Boy', 'Pat Grandma', 'Pat Grandpa')
               ]

def are_brothers((a,b,c,d),(w,x,y,z)):
    '''returns True if two boys have the same parents
    '''
    return all([b=='Boy',x=='Boy',c==y,d==z])


def are_sisters((a,b,c,d),(w,x,y,z)):
    '''returns True if two girls have the same parents
    '''
    return all([b=='Girl',x=='Girl',c==y,d==z])


def are_siblings((a,b,c,d),(w,x,y,z)):
    '''returns True if two whatever share the same parents
    '''
    return all([c==y,d==z])


def list_all_brothers(family_tree):
    '''returns a list of all brothers in given family_tree
    '''
    return [(a,w) for (a,b,c,d) in family_tree
                      for (w,x,y,z) in family_tree
                      if are_brothers((a,b,c,d),(w,x,y,z))
                      and a < w] #this '<' here is a thing of beauty


def list_all_ancestors((a,b,c,d),family_tree):
    '''returns a list of ancestors
    for subject person
    '''
    ancestors = set([])
    parents = [c,d]

    while parents:
        p =  parents.pop()
        p = [(a,b,c,d) for (a,b,c,d) in family_tree if a==p]
        if p:
            a,b,c,d = p[0]
            ancestors.add((a,b,c,d))
            parents += [c,d]
    return ancestors


def are_related(a,b,family_tree):
    '''returns true if a and b share a common ancestor
    from list_all_ancestors
    '''
    aF = set(list_all_ancestors(a,family_tree))
    aF.add(a)
    bF = set(list_all_ancestors(b,family_tree))
    bF.add(b)
    if aF.intersection(bF):
        return True
    else:
        return False

The Eight Queens Problem in Python

from itertools import permutations

#range(1,9) spits out [1,2,3,4,5,6,7,8]
#permutations spits out every permutation of same
#zipping together gives every possible chessboard combination
#  with no two pieces in same rank or file
boards = [zip(range(1,9),p) for p in permutations(range(1,9))]

print len(boards)
#40320
print boards[0]
#print first possible solution set
#Note, rank and file different for each tuple
#[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8)]


def no_diagonals(board):
    '''given a list of tuples representing a possible solution
    returns False if any are diagonally aligned, True otherwise
    '''
    for x,y in board:
        for r in (range(-7,0,1) + range(1,8,1)):
            if (x+r,y+r) in board:
                return False
            elif (x-r,y+r) in board:
                return False
    return True

#And this is the solution
#Take the first list with no overlapping rank and files
#And filter with no_diagonals()         
boards = [b for b in boards if no_diagonals(b)]


print len(boards)
#92, which is the correct number of answers
print boards[0]
#A sample solution set
#[(1, 1), (2, 5), (3, 8), (4, 6), (5, 3), (6, 7), (7, 2), (8, 4)]

boards = [zip(range(1,9),p) for p in permutations(range(1,9))]
boards = [b for b in boards if no_diagonals(b)]

Picture Perfect

def board_image(board):
    '''standard board graphic
    '''
    #holding array, 1 being white in grayscale
    #np being the result of import numpy as np
    bI = np.ones((100,100), dtype=float)
    
    #these are the board grid lines
    for x in range(10,100,10):
        bI[x,10:90] = 0.0
        bI[10:90,x] = 0.0
        
    #these are the squares, which represent the queens
    for (x,y)in board:
        bI[x*10:x*10+10,y*10:y*10+10] = 0.0

    print bI #debug
    skimage.io.imsave("eight_queens.png", bI) #save png
    return bI #return array for next funtion

	
def all_boards_image(boards):
    '''standard boards, full array
    '''
    #make array with full 92 solution set
    #precomposed into image arrays
    images = []
    for b in boards:
        images.append(board_image(b))

    #arrange the img solution sets
    #into a 23x4 grid 
    img = np.vstack((np.hstack(images[0:23]),
                     np.hstack(images[23:46]),
                     np.hstack(images[46:69]),
                     np.hstack(images[69:92])))
    
    #save the solution set as an image
    skimage.io.imsave("eight_queens.png",img)