MagicYang: 2010

Sunday, November 14, 2010

A python example: Convert CSP problem to prolog format

#!/usr/bin python
"""
Author : Yinfei Yang
Mail : yangyin7 AT gmail DOT com
Date : 2010-11-12 Fri 04:52 PM

python version: 2.6.5

Usage 1: python convert.py inputFileName outputFileName
Usage 2: python convert.py dirName

Notice: Please ensure the file need to be converted with the suffix .prb

example of input file:

20 15
  0 136 1 189 2 121 3 183 4 77 5 133 6 77 7 155 8 68 9 97 10 99 11 37 12 51 13 149 14 132
  0 2 1 7 2 93 3 99 4 42 5 66 6 190 7 174 8 94 9 171 10 7 11 129 12 60 13 56 14 12
  0 167 1 68 2 176 3 30 4 99 5 107 6 152 7 184 8 186 9 15 10 145 11 21 12 199 13 43 14 135
  0 137 1 162 2 98 3 2 4 92 5 123 6 171 7 100 8 191 9 57 10 166 11 168 12 59 13 145 14 73
  0 7 1 197 2 192 3 53 4 146 5 104 6 169 7 182 8 98 9 145 10 80 11 133 12 5 13 16 14 146
  0 166 1 73 2 133 3 35 4 141 5 90 6 136 7 184 8 135 9 3 10 195 11 132 12 178 13 7 14 162
  0 197 1 51 2 137 3 136 4 121 5 15 6 160 7 179 8 20 9 44 10 159 11 38 12 55 13 55 14 170
  0 151 1 153 2 82 3 40 4 97 5 200 6 165 7 69 8 29 9 49 10 30 11 30 12 84 13 78 14 87
  0 171 1 155 2 123 3 131 4 168 5 155 6 145 7 155 8 135 9 66 10 89 11 19 12 4 13 134 14 161
  0 183 1 161 2 165 3 116 4 184 5 157 6 175 7 48 8 85 9 165 10 94 11 149 12 84 13 138 14 137
  0 114 1 40 2 6 3 170 4 163 5 118 6 79 7 154 8 195 9 34 10 197 11 45 12 39 13 125 14 160
  0 65 1 105 2 24 3 31 4 90 5 22 6 59 7 66 8 20 9 150 10 37 11 101 12 139 13 87 14 138
  0 110 1 37 2 73 3 25 4 38 5 46 6 11 7 123 8 195 9 164 10 86 11 191 12 184 13 120 14 43
  0 50 1 181 2 23 3 134 4 198 5 169 6 186 7 75 8 141 9 62 10 173 11 123 12 192 13 29 14 124
  0 67 1 80 2 155 3 166 4 25 5 4 6 11 7 184 8 32 9 64 10 16 11 108 12 31 13 4 14 145
  0 149 1 195 2 125 3 118 4 18 5 186 6 22 7 15 8 118 9 60 10 176 11 82 12 94 13 170 14 27
  0 174 1 126 2 49 3 77 4 92 5 147 6 171 7 18 8 193 9 14 10 171 11 50 12 95 13 24 14 104
  0 156 1 1 2 158 3 192 4 155 5 99 6 62 7 82 8 115 9 41 10 33 11 139 12 77 13 61 14 161
  0 49 1 179 2 183 3 176 4 164 5 165 6 93 7 194 8 46 9 59 10 199 11 197 12 5 13 143 14 23
  0 5 1 185 2 92 3 173 4 116 5 81 6 131 7 85 8 115 9 98 10 135 11 163 12 68 13 179 14 1

"""

import sys, re, os

DATA_START = "data([\n"
DATA_END = "])."

def convert(inputFile, outputFile):
   print ''.join(['Start to convert ',inputFile,' ...'])
   f = open(inputFile,'r')
   f2 = open(outputFile,'w')

   f2.write(DATA_START)

   file_lines = f.readlines()
   num = file_lines[0].replace('\n','').split(' ')
   if len(num) != 2:
   print 'Error 2:'
   print 'prb file format error, please check it, exit.'
   sys.exit(2)
   row = int(num[0])
   column = int(num[1])
   count = row * column
   current_job = 0

   for line in file_lines[1:len(file_lines)]:
   tasks = re.split('[ ]+',line.replace('\n','').strip())
   task_number = len(tasks)/2
   if(len(tasks) != column*2):
   print 'Error 2:'
   print 'prb file format error, please check it exit'
   sys.exit(2)
   for i in range(0,task_number):
   current_job += 1
   f2.write(''.join(['task( ' , str(current_job) , ', ' , tasks[2*i+1] , ', [']))
   if current_job%column==0:
   current_line = current_job/column
   else:
   current_line = current_job/column+1
   for j in range(1, current_job - (current_line-1)*column):
   f2.write(str((current_line-1)*column+j))
   if(j != current_job-(current_line-1)*column-1):
   f2.write(',')
   f2.write(''.join(['], ', tasks[2*i], ')']))
   if current_job < count:
   f2.write(',')
   f2.write('\n')

   f2.write(DATA_END)
   f.close()
   f2.close()
   print ''.join(['Convert succeed. Output file: ', outputFile])

def traverse(dirName):
   filenames = os.listdir(dirName)
   print ''.join(['traverse ',dirName])
   for filename in filenames:
   if 0 == cmp(filename[-4:len(filename)].lower(),'.prb'):
   convert(filename, ''.join([filename[0:-4],'.pl']))

def usage():
   print 'convert.py usage:'
   print 'Usage 1: python convert.py inputFileName outputFileName'
   print 'Usage 2: python convert.py dirName'
   print ''

if __name__=='__main__':
   if len(sys.argv) != 2 and len(sys.argv) != 3:
   usage()
   sys.exit(0)

   if len(sys.argv) == 2:
   if not os.path.isdir(sys.argv[1]):
   print 'Error:'
   print ''.join([sys.argv[1],'is not a directory, exit.'])
   print ''
   sys.exit(1)
   else:
   traverse(sys.argv[1])

   if len(sys.argv) == 3:
   filename = sys.argv[1]
   if 0 == cmp(filename[-4:len(filename)].lower(),'.prb'):
   convert(sys.argv[1],sys.argv[2])
   else:
   print 'Warning:'
   print 'the input file is not with the suffix .prb'
   print sys.exit(0)

Chapter 2: Finite automata

2.1 Deterministic Finite Accepters

Definition: M=(Q, Σ, δ, q0, F)

internal states
input alphabet
transition function δ: Q x Σ -> Q
initial state
F in Q, final states

Visualize and Represent finite automata: transition graphs
Regular languages: L is called regular if and only if there exists some dfa accepter M such that L = L(M)

2.2 Nondeterministic Finite Accepter

Definition: M=(Q, Σ, δ, q0, F)

as for dfa but ransition function δ: Q x (Σ U {λ}) -> 2^Q

2.3 Equivalence of DFA and NFA

DFA is an special NFA
NFA can convert to DFA
link: http://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/nfa-2-dfa.html
tools: JFLAP http://www.cs.duke.edu/csed/jflap/
My lecture slides:http://www.sju.edu/~tezel/CSC_Courses/TheoryOfComputation/Fall_2010/Lectures/GroupLectures/Group2_2.3.pdf

Chapter 1: Introduction to the theory of computation

1.1 Mathematical Preliminaries and Notations

Sets
Functions and Relations
Graphs and Trees
Proof Techniques

induction
contradiction

1.2 Three Basic Concepts

Languages
Grammers

Definition: G = (V,T,S,P), V and T are nonempty and disjoint

V is a finite set of objects called variables
T is a finite set of objects called terminal symbols
S in T, start variable
P is a finite set of productions

L(G), is the language generated by G.

Automata: dfa and nfa

Thursday, September 9, 2010

又到一年生日时

This article is written by Chinese.

瞅着瞅着，在中国已经到了我的生日了，本来对生日是没啥感觉的，逛校内的时候看到一组学校的照片，突然无限伤怀。

写个回忆录吧，纪念我的大学生活。

Monday, August 30, 2010

The first day in Saint Joseph's Uinversity

This article is written by Chinese.

开学的第一天，总算能进图书馆，能有一个安静的地方自习，看书，做自己的事情。于是第一件事开了我的twitter, 第二件事开了我的blogspot。哈哈，肉身翻墙的感觉真好。

到美国已经是上个礼拜的事情了，一切就和国内一样，和大家一起来到这里，住在同一个公寓，讲着熟悉的中文，一起去超市购物，根本无法意识到我们已经是到了美国。于是便没有了所谓的孤独感。 ZDD曾经说过中国人喜欢扎堆，再美国校园里总能看到一群一群的中国人讲着汉语，我们便是如此。或许是刚来的第一周，或许是文化差异的缘故，但是我并不喜欢如此，曾经有人说过一个中国人是条龙，两个中国人就是两条虫，并不是没有道理的。来这里一个礼拜，什么事情也没做，却把实况10玩了两个赛季，罪过罪过。

英语还是一如既往的烂，我需要寻求改变。

不过话说回来，美国的校园还是很好看的，我们学校算是比较差的学校了，不过排场上倒是一点不差，校园边上的街道都挂着SJU的旗帜，煞是威风，学校教廷式的建筑风格也非常独特和美丽。

今天开始要准备重启MEG的研究任务了，等Forrest回Texas说要把暑期的工作做个report，也得重新回顾下前面两个月的工作了。然后今天晚上开始上课，看名字似乎是个中国人授课，好吧，开始吧。

事实上，一切都是新的，换一个角度， just do it.