10 Kasım 2012 Cumartesi

Puzzling Computers - 1 - Easy as ABC




Enter the letters from 'A' to 'C' into the diagram, so that in every row and every column every letter occurs exactly once; in every row and every column one field remains empty. The letters at the borders indicate the letter that comes first in the corresponding row or column.[1]


Easy as ABC is a simple puzzle and a good starting point for our journey. We'll be using Python 2.7 all the time. If you are using a linux distro, it is probably already installed. (On arch linux you need to install and run python2). If you are on Windows, it is available for download here

There are many variations of this puzzle, but we will just be solving the usual one.

Let's begin. We firstly need to create the puzzle and get user input. 
 
class ABCPuzzle(object):
    def __init__(self, size, letterCount):

        self.count = letterCount
        self.size = size

This should be clear. The puzzle is a square, so it has a size and a number of letters will be placed in each row and column. Now we can get the user input. The classical Easy as ABC puzzle begins with an empty matrix and clues on four sides. We will store the clues as integers. (We will implement all letters as numbers) So we can use loops in an easier a more effective way. So, we need to get input as a string (containing letters and spaces) and convert to an array of integers.


    def getInput(self):
        horizontalUpper = raw_input("Horizantal ^ (0 for empty):")
        horizontalBottom = raw_input("Horizantal v (0 for empty):")
        verticalLeft = raw_input("Vertical < (0 for empty):")
        verticalRight = raw_input("Vertical > (0 for empty):")
        self.horizontalUpper = []
        self.horizontalBottom = []
        self.verticalLeft = []
        self.verticalRight = []
        keys = {" ":0,"A":1,"B":2,"C":3,"D":4,"E":5}
        for i in horizontalUpper:
            self.horizontalUpper.append(keys[i])
        for i in horizontalBottom:
            self.horizontalBottom.append(keys[i])
        for i in verticalLeft:
            self.verticalLeft.append(keys[i])
        for i in verticalRight:
            self.verticalRight.append(keys[i])


This just works for puzzles with letter from a to e, but in order to keep it simple, I avoided a few tricks with ascii values and used a simple dictionary instead. If you like to, you can expand the code to support puzzles with more letters.

    self.getInput()


We add this line to end of the __init__() function for obvious reasons.

We will begin with a matrix of all available numbers for each coordinate and eliminate them step by step.


    def createPossibleMatrix(self):
        self.possible = []
        for i in range(self.size):
            self.possible.append([])
            for j in range(self.size):
                self.possible[-1].append([])
                for k in range(self.count+1):
                    self.possible[-1][-1].append(k)  
This function creates a 3-dimensional array. First two dimensions are the coordinates and third is an array of possible numbers (letters) There are many combinations of a row or a column. For any cell, if there is no valid combination with a certain number in it for its row or column, it means that this cell doesn't contain this number. Instead of creating this combinations again and again, it is better to create them at the beginning and iterate through this array when we need to.
    def createCombinations(self):
        combinations = [[]]
        for number in range(self.count):
            newCombs = [] 
            for adress in range(self.size):
                for comb in combinations:
                    if not adress in comb:
                       newCombs.append(comb + [adress])             
            combinations = newCombs
        self.lines = []
        for comb in combinations:
            self.lines.append(self.size * [0])
            for number in range(self.count):
                self.lines[-1][comb[number]] = number + 1
The first loop creates an array of arrays, which hold each numbers (letter) index. The second one converts it into another array of array, which represent either a column or a row. For example [1,2,4] is converted to [0,1,2,0,3]. The first part is a little tricky. It firstly creates and array with all possible indexes for 1 (A). For example, if size is 3, the creates array is [[0],[1],[2]]. Then for the next number, all possible indexes are added to each element. The result is [[0,1],[0,2],[1,0],[1,2],[2,0],[2,1]]. With each new number, they get longer by one element and the number of array is multiplied by count-n, where n represents the new number. Then we call those two functions by adding these lines to __init__()
        self.createCombinations()
        self.createPossibleMatrix()
Now we are ready to start solving the puzzle
    def solve(self, pmap=None):
        if pmap==None:
            pmap = []
            for i in range(self.size):
                pmap.append([])
                for j in range(self.size):
                    pmap[-1].append(self.possible[i][j][:])
At this point, I should explain why the function is called with a pmap paramater. For some puzzles, we may need to use brute-force (yeah, not elegant, but it work pretty well) on some imaginary maps, so it is nice when the function is callable with maps other than self.possible. For the first call, this is not the case so we copy self.possible to pmap. We need to iterate over self.possible again and again until we are done. Question is, when are we done? Answer is simple, when there is only one possible number for each cell. So, let's write an "is Done" function.
    def isDone(self, pmap):
        for i in range(self.size):
            for j in range(self.size):        
                if len(pmap[i][j])>1:
                    return False
        return True
Then, we will do the eliminations as long as we aren't done. We also need to check, whether a change has been made on self.possible. If not, we will need to think of something else (brute force :) ) as nothing would change the next time we go over the same array.
        change = True
        while not self.isDone(pmap): 
            if self.isBroken(pmap):
                return False
            if change:
So, this one is a good beginning for the solve function. That isBroken function returns True, if an impossible map is created, like a map with cells with no possible entry.
    def isBroken(self, pmap):
        for i in range(self.size):
            for j in range(self.size):        
                if len(pmap[i][j])==0:
                    return True
        return False 
isBroken can return True, only when a cell is given a wrong value when using brute force. Otherwise the right value for the cell wouldn't be eliminated as long as the puzzle is a valid one. When a wrong guess is inserted in a cell, we create an invalid puzzle, which leads in long term to a broken one. If a guess is right, whole puzzle will be solved without getting broken, so if solve function returns False, it means we have been trying a wrong number for a cell. Let's think of how to eliminate numbers without using brute force. Easy as ABC is Sudoku-like and the easiest method of eliminating numbers is checking the rows and columns and seeing whether it is repeated.
            if change:
                change = False
                for i in range(self.size):
                    for j in range(self.size):
                        for k in pmap[i][j]:
                            if k:
                                if not self.simpleCheckCell(i,j,k, pmap):
                                    change = True
                                    pmap[i][j].remove(k)
For all cells (pmap[i][j]), all numbers excluding 0 checked, and the impossible ones are removed. If at least one candidate is eliminated, change is set to True and all cells will be check one more time. Else, we will have to use some other methods, as this one can't solve the whole puzzle. (For example, at the beginning, no candidate can be eliminated this way). But this one is much much lighter than checking all combinations of a line, so it speed up the solving process a bit.
    def simpleCheckCell(self, x,y,guess, pmap):
        for iy in range(self.size):
            if pmap[x][iy] == [guess] and iy!=y:
                return False
        for ix in range(self.size):
            if pmap[ix][y] == [guess] and ix!=x:
                return False
        return True
Now, for each cell, we will check whether there is at least one valid combination of the column and the row. If we can eliminate a candidate this way, we will go back to simple scan. Otherwise, we will have to use brute force.
            if not change:
                change = False
                for i in range(self.size):
                    for j in range(self.size):
                        for k in range(self.count+1):
                            if k in pmap[i][j]:
                                if not self.checkCell(i,j,k, pmap):
                                    change = True
                                    pmap[i][j].remove(k)   
The checkCell function checks is there a valid combination
    def checkCell(self, x, y, guess, pmap = None):
        return self.checkVertical(x,y, guess, pmap) and self.checkHorizontal(x,y,guess, pmap)
    def checkHorizontal(self, x, y, guess, pmap = None):
        if pmap == None:
            pmap = []
            for i in range(self.size):
                pmap.append([])
                for j in range(self.size):
                    pmap[-1].append(self.possible[i][j][:])    
        validCombExists = False

        for comb in self.lines:
            if comb[y] == guess:  
                combIsValid = True
                for i in range (self.size):
                    number = comb[i]
                    if not (number in pmap[x][i]):    
                        combIsValid = False
                if combIsValid:
                    #check sides
                    upValid = False
                    bottomValid = False
                    if self.horizontalUpper[x]:
                        checkingSide = True
                        if getFirst(comb) == self.horizontalUpper[x]:
                            upValid = True
                        else:
                            continue
                    else:
                        upValid = True
                    if self.horizontalBottom[x]:
                        checkingSide = True
                        if getLast(comb) == self.horizontalBottom[x]:
                            bottomValid = True
                        else:
                            continue
                    else:
                        bottomValid = True    
                    validCombExists = upValid and bottomValid
                    if validCombExists:
                        return True
                else:
                    continue                  
        return validCombExists      
        
        
    def checkVertical(self, x, y, guess, pmap = None):
        if pmap == None:
            pmap = []
            for i in range(self.size):
                pmap.append([])
                for j in range(self.size):
                    pmap[-1].append(self.possible[i][j][:])
        validCombExists = False
        
        for comb in self.lines:
            if comb[x] == guess:  
                combIsValid = True              
                for i in range (self.size):
                    if not (comb[i] in pmap[i][y]):    
                        combIsValid = False
                if combIsValid:
                    #check sides
                    leftValid = False
                    rightValid = False
                    if self.verticalLeft[y]:
                        checkingSide = True
                        if getFirst(comb) == self.verticalLeft[y]:
                            leftValid = True
                        else:
                            continue
                    else:
                        leftValid = True
                    if self.verticalRight[y]:
                        checkingSide = True
                        if getLast(comb) == self.verticalRight[y]:
                            rightValid = True
                        else:
                            continue
                    else:
                        rightValid = True    
                    validCombExists = leftValid and rightValid
                    if validCombExists:
                        return True
                else:
                    continue                    
        return validCombExists      
If there still isn't any change, we will choose any cell with more than one candidates, guess any of them, and check if this leads to a broken puzzle. If it doesn't, it will get True from isDone() at the end. If it does, it will return False and we will eliminate the guess.
            if not change:
                x,y = self.getDoubtCell(pmap)               
                newmap = []
                for x0 in range(self.size):
                    newmap.append([])
                    for y0 in range(self.size):
                        newmap[-1].append(pmap[x0][y0][:])
                newmap[x][y] = [pmap[x][y][0]]
                if self.solve(newmap):
                    return True
                else:
                    pmap[x][y].remove(pmap[x][y][0])
                    change = True 
So we copy the map, insert our guess and call the function again. The getDoubtCell function follows:
    def getDoubtCell(self, pmap):    
        for i in range(self.size):
            for j in range(self.size):        
                if len(pmap[i][j])>1:
                    return i,j
        return False
So, only one little step left, displaying our victory!
    def showSolution(self, pmap):
        keys = {0:" ",1:"A",2:"B",3:"C",4:"D",5:"E"}
        for y in range(self.size):
            l = ""
            for x in range(self.size):
                l += keys[pmap[x][y][0]] 
            print l
Call this at the end of self.solve:
self.showSolution(pmap)
return True
And finally, a few more lines to run it:
size = input("size:")
rang = input("range:")
start = time()
a = ABCPuzzle(size,rang)
end = time()
print "Solved in %s seconds" %(end-start)
Lets test the example:
CBA  
CBA
 CBA 
A  CB
BA  C
Solved in 0.0127110481262 seconds
Feels good. In almost 1% of a second. Try easier and harder ones to see the results. You will need to make the program get input from a file instead of the keyboard to keep track of time. On arch-linux I simply run:
python2 main.py < inputfile
After typing everything in inputfile. So this was it. But there are still many things to be done. You can modify the input and output parts to show and get more letters than A to E. You can try to make it run faster. You can clean the code (for example check horizontal and check vertical could be the same function). I have left some little modifications that would speed it up to keep it simple, so you should be able to do soma changes. (For example you can add a few tricks like eliminating others if a number is only one cells candidate in a row). Please feel free to mail me your code (modifications, totally new algorithms), suggestions and please report any mistake you've noticed. As next, I will be solving Skyscrapers with some small changes on this one, so if you like to do it yourself, have fun! By the way, you can download the code is available for download here.

10 Eylül 2012 Pazartesi

Poem - Java, Why I hate you?

Cause you have public static void main
Even hello world is such a pain
Multiple Inheritance had to remain
Interfaces are for litte girls

What was wrong with the pointers
They were the best friends of programmers
Handling SegFaults is easy for real coders
 References are for little girls

Write once, run everywhere was a nice dream
How can you expect that I have JVM?
Was simply compiling that mainstream?
Bytecode is for little girls.

15 Temmuz 2012 Pazar

Python kütle çekim simülasyonu - Bölüm 2

Yazımızın ilk kısmında arayüz ve cisimle ilgili sınıfları tanımlamıştık. Şimdi iki cisim arasındaki kütle çekim kuvvetini hesaplayacak fonksiyonu yazmaya başlayabiliriz. Bu esnada ikisi arasındaki mesafeyi hesaplamaya ihtiyacımız olacak. Her ikisinin de x ve y kordinatlarını bildiğimizden pisagor teoremini kullanarak bunu hesaplayabiliriz:

 
 def distance(ball1, ball2):
    return math.sqrt((ball1.x-ball2.x)**2+(ball1.y-ball2.y)**2) 
--To be continued--

Python kütle çekim simülasyonu - Bölüm 1

Merhabalar. Bu yazımızda her evde bulabileceğiniz malzemelerle (python, tkinter ve canvas) ufak bir simülasyon yazacağız.

Simülasyon belirli sayıda dairesel cisim oluşturmamıza izin verecek ve bunların iki boyutlu uzaydaki harekatlerini inceleyecek.

Programlamaya başlamadan önce newton mekaniğini biraz hatırlayalım. Birbirinin kütle çekimi etkisindeki iki cisim arasındaki çekim kuvveti eşittir ve şu formülle hesaplanır:



Daha ayrıntılı incelemek isterseniz ilgili vikipedi makalesi gayet bilgilendirici. Simülasyonumuzda sadece görüntü ile ilgileneceğiz dolayısıyla birimler arasındaki tutarlılığı sağlayan G sabiti bizi pek de ilgilendirmiyor şimdilik.

Bu kuvvetin cisimler üzerindeki etkisni hesaplamak için de


  formülünü kullanacağız. Simülasyonu basit tutmak ve birim adımdaki işlem yükünü azaltmak için her adımdaki ivmenin sabit olduğunu varsayacağız.

Cismimizin kütlesini simülasyonu oluştururken gireceğimizden ve kuvveti her adımda hesaplayacağımızdan ivmeyi de bulmak zor olmayacak. İvme ve cismin önceki hızını kullanarak da konumu x = x0 + v*dt+a*dt^2/2 formülüyle hesaplayacağız.

Şimdiye kadar incelediğimiz üzere, bu hesaplamalar esnasında cismin kütlesini, konumunu (ekranda göstermek ve mesafeyi hesaplamak için) ve hızını hafızada saklamamız gerecek. İvme ve kuvveti ise anlık olarak hesaplayabileceğiz.

Öyleyse artık programlamaya başlayabiliriz. İlk olarak cisim için bir sınıf oluşturalım. Tüm cisimleri dairesel şekillerle göstereceğimizden Ball adını sınıf için uygun gördüm:

 
 
class Ball:
    def __init__(self, x,y,speed_x=0,speed_y=0,m=1):
        self.x = x
        self.y = y
        self.speed_x = speed_x
        self.speed_y = speed_y
        self.force_x = 0
        self.force_y = 0
        self.m = m  

Az önce bahsettiklerimiz haricinde force_x ve force_y adlı iki değişken daha tanımladık. Bunları bir bütün cisimlerin kütle çekimlerini toplayıp tek bir kuvvetmiş gibi hesaplamak için kullanacağız.Cisimlerin görüntülenmesi için de Tkinter kütüphanesinin Canvas sınıfından bir simülasyon sınıfı türeteceğiz.
 
class Simulation(Canvas):
    def __init__(self):
        Canvas.__init__(self, width=1000, height=700)
        self.balls = []
        self.circles = [] 

Burada balls dizisi cisimlerimizi, circles dizisi ise bunların çizimlerini saklayacak.

Her şeyi bir araya getirirsek:

 
from Tkinter import *
import math
import time

# siniflari buraya yapistirin

mainWindow = Tk()
sim = Simulation()
sim.pack()

while True:
    mainWindow.update()
    sim.update()
 

Programı bu haliyle çalıştırdığınızda sim sınıfının update adlı bir methodu olmadığına dair bir hata raporu alırsınız. Simulation sınıfının görüntüyü güncellemesini sağlayacak methodu yazmadan önce cisimleri ekleyebilmemizi sağlayacak olan methodu yazalım:

 
    def addBall(self, x,y,speed_x=0,speed_y=0,m=1):
        self.balls.append(Ball(x,y,speed_x,speed_y,m))
 
Hemen bu şekilde bir cisim tanımlayalım:
 
sim.addBall(100,100)

while True:
    mainWindow.update()
    sim.update()
 
Artık bir cismimiz de olduğuna göre update() methodunu yazmaya başlayabiliriz:
 
    def update()
        for i in self.circles:
            self.delete(i)
        for i in range(len(self.balls)):    
            ball = self.balls[i]
            self.circles.append(self.create_oval(ball.x-5, ball.y-5, ball.x+5, ball.y+5, width=2, fill='blue'))
 
Burada her daireyi tek tek silmek yerine self.delete("all") methodunu kullanabilirdik ancak ileride cisimlerin izlediği yolları da çizdirebilmek için tek tek silmek daha mantıklı olacaktır.

Şimdiye kadar simülasyonumuz çalışacağı alt yapıyı kurduk. Yazımızın ikinci kısmında kütle çekimi hesaplamaya ve cisimleri hareket ettirmeye başlayacağız.

12 Temmuz 2012 Perşembe

Hello, World!

12.07.12 - 20:29 Yalova