Python Code Examples: Data Structures, Algorithms, and More
Python Code Examples
Game2048
This code implements the game 2048, including functions for moving cells, checking for blocked states, and managing the game board.
def __can_move_cell__(self, row, col):
value = self.cells[row][col]
if value == 0:
found_mov = True
else:
found_mov = False
i = 0
pos_lst = [(-1,0),(1,0),(0,-1),(0,1)]
while i < len(pos_lst) and not found_mov:
row_i = row + pos_lst[i][0]
col_i = col + pos_lst[i][1]
found_mov = self.get_value(row_i, col_i) == value
i += 1
return found_mov
def is_blocked(self):
row = 0
found_mov = False
while row < self.get_size() and not found_mov:
col = 0
while col < self.get_size() and not found_mov:
found_mov = self.__can_move_cell__(row, col)
col += 1
row += 1
return not found_mov
def get_size(self):
return len(self.cells)
def get_value(self, row, col, trasposed=False):
if row<0 or row>=self.get_size() or \
col<0 or col>=self.get_size():
return Board.OUT
if not trasposed:
return self.cells[row][col]
else:
return self.cells[col][row]
def put_value(self, row, col, value, trasposed=False):
if not trasposed:
self.cells[row][col] = value
else:
self.cells[col][row] = value
def get_free_cells(self):
free_cells = []
for row in range(len(self.cells)):
for col in range(len(self.cells)):
if self.cells[row][col] == Board.EMPTY:
free_cells.append((row, col))
return free_cells
def __move_cell__(self, row_col, move_to, current, inc, trasposed):
score = 0
moved = False
move_to_value = self.get_value(row_col, move_to, trasposed)
cur_value = self.get_value(row_col, current, trasposed)
if cur_value != 0:
if move_to_value == 0:
self.put_value(row_col, move_to, cur_value, trasposed)
self.put_value(row_col, current, 0, trasposed)
moved = True
elif move_to_value == cur_value:
value = 2*cur_value
self.put_value(row_col, move_to, value, trasposed)
self.put_value(row_col, current, 0, trasposed)
moved = True
score += value
move_to += inc
else: # move_to_value!=0 and move_to_value != cur_value
#print('1-{0}:{1}:{2}:{3}'.format(self,move_to, current,inc))
move_to += inc
moved = current != move_to
if moved:
# the order of these two instruction cannot be changed
self.put_value(row_col, current, 0, trasposed)
self.put_value(row_col, move_to, cur_value, trasposed)
#print('2-{0}:{1}:{2}'.format(self,move_to, current))
return moved, score, move_to
def __move_row_col__(self, row_col, ini, end, move_rows):
trasposed = not move_rows
score = 0
moved = False
inc = 1
if ini > end:
inc = -1
current = ini + inc
move_to = ini
while current != end:
tmp_moved, tmp_score, move_to = self.__move_cell__(row_col, move_to, current, inc, trasposed)
score += tmp_score
moved = moved or tmp_moved
current += inc
return moved, score
def move(self, start_end, move_rows):
ini = 0
end = len(self.cells)
if start_end:
ini = len(self.cells) -1
end = -1
score = 0
moved = False
for i in range(len(self.cells)):
tmp_mv, tmp_sc = self.__move_row_col__(i, ini, end, move_rows)
score += tmp_sc
moved = moved or tmp_mv
return moved, score
def get_max_value(self):
max_value = 0
for row in self.cells:
for cell in row:
if cell>max_value:
max_value = cell
return max_value
def __str__(self):
res = ''
size = self.get_size()
for row in range(size):
for col in range(size):
res += '{0:5}'.format(self.get_value(row, col))
res += '\n'
return res
def __init__(self, dim, num_initial_cells, seed):
random.seed(seed)
self.game = Game2048(self.build_cells(dim))
for i in range(num_initial_cells):
self.game.add_new_cell()
def build_cells(dim):
cells = []
for i in range(dim):
cells.append([Board.EMPTY] * dim)
return cells
def play(self):
print(self.game)
move = 'X'
while move != 'q' and not self.game.is_blocked():
move = input('use the keys adwx:')
if move == 'a':
self.game.left()
elif move == 'd':
self.game.right()
elif move == 'w':
self.game.up()
elif move == 'x':
self.game.down()
self.game.add_new_cell()
print(self.game)
Linear Regression
This code calculates the linear regression of a dataset read from a file.
def linear_regression(filename: str) -> tuple[float, float]:
xsum = .0
ysum = .0
xysum = .0
x2sum = .0
total = .0
with open(filename) as fl:
for line in fl:
data = line.strip().split()
x = float(data[0])
y = float(data[1])
xsum += x
ysum += y
xysum += x * y
x2sum += x ** 2
total += 1
sxy = xysum - (xsum * ysum) / total
sxx = x2sum - (xsum ** 2) / total
a = sxy / sxx
b = ysum / total - a * xsum/total
return a, b
Merging Sorted Files
This code merges two sorted files into a new sorted file.
def merge(fln1: str, fln2: str, res:str) -> None:
with open(fln1) as f1, open(fln2) as f2, \
open(res, 'w') as fres:
l1 = f1.readline()
l2 = f2.readline()
while l1!='' and l2!='':
n1 = int(l1)
n2 = int(l2)
if n1 < n2:
fres.write(f'{n1}
')
l1 = f1.readline()
else:
fres.write(f'{n2}
')
l2 = f2.readline()
while l1!='':
n1 = int(l1)
fres.write(f'{n1}
')
l1 = f1.readline()
while l2!='':
n2 = int(l2)
fres.write(f'{n2}
')
l2 = f2.readline()
Prime Numbers
This code defines functions for checking primality, finding the next prime number, and managing a list of prime numbers stored in a file.
def is_prime(num: int, primelst: list[int]) -> bool:
i = 0
while i<len(primelst) and primelst[i]**2 < num and num % primelst[i] != 0:
i += 1
return i == len(primelst) or primelst[i]**2 > num
def next_prime(primelst: list[int]) -> None:
if len(primelst) == 0:
primelst.append(2)
else:
num = primelst[-1] + 1
while not is_prime(num, primelst):
num += 1
primelst.append(num)
def add_primes(filename: str, nprimes: int) -> None:
primelst = read_primes(filename)
with open(filename, "a") as flp:
for _ in range(nprimes):
next_prime(primelst)
prime = primelst[-1]
flp.write(f"{prime}
")
def read_primes(filename: str) -> list[int]:
"""
Read the primes form the list
Parameters
----------
filename contains a list of the first primes
"""
primelst: list[int] = []
with open(filename) as fl:
for line in fl:
primelst.append(int(line))
return primelst
Hangman Game
This code implements a hangman game, including functions for drawing the hangman, choosing a word, managing game state, and handling user input.
def game2str(game: dict) -> str:
pict = picture2str(game['drawing'], game['fails'])
right_letters = 0
for letter in game['word']:
if letter in game['given_letters']:
pict += letter
right_letters += 1
else:
pict += "_"
pict += " "
pict += "\n"
if game['fails'] == game['drawing']['max_attemps']:
pict += f"You have lost, the word is: {game['word']}\n"
elif right_letters == len(game['word']):
pict += "You have won\n"
return pict
def drawing(filename: str) -> dict:
drw = dict()
with open(filename) as pict_file:
rows = int(pict_file.readline())
line = pict_file.readline().rstrip()
drw['picture'] = []
i = 0
while i < rows:
drw['picture'].append(line)
i += 1
line = pict_file.readline().rstrip()
drw['order'] = []
i = 0
max_fails = -1
while i < rows:
row = []
for x in line.split():
val = int(x)
if val > max_fails:
max_fails = val
row.append(val)
drw['order'].append(row)
i += 1
line = pict_file.readline().rstrip()
drw['max_attemps'] = max_fails
return drw
def choose_word(filename: str) -> str:
words = []
with open(filename) as word_file:
for line in word_file:
words.append(line.strip())
return random.choice(words)
def init(words_filename: str, picture_filename: str) -> dict:
game = {
'drawing': drawing(picture_filename),
'word': choose_word(words_filename),
'given_letters': set(),
'fails': 0
}
return game
def is_ended(game: dict) -> bool:
count = 0
for l in game['word']:
if l in game['given_letters']:
count += 1
return count == len(game['word']) or \
game['fails'] == game['drawing']['max_attemps']
def update(game: dict, letter: str) -> str:
if letter in game['given_letters']:
msg = f"You have already said '{letter}'"
elif letter in game['word']:
msg = f"Good, {letter} is in the word"
game['given_letters'].add(letter)
else:
msg = f"Sorry, {letter} is NOT in the word"
game['given_letters'].add(letter)
game['fails'] += 1
return msg
def main(words_filename: str, picture_filename: str) -> None:
game = init(words_filename, picture_filename)
while not is_ended(game):
print(game2str(game))
letter = input("Give a letter: ")
msg = update(game, letter)
print(msg)
print(game2str(game))
Text Processing
This code defines functions for splitting text into words, converting to lowercase, finding unique words, and calculating word frequency.
PUNCTUATION = ' ¡!"#$%&\'()*+,-./:;<=>¿?@[\]^_`{|}~«»\n\t\r'
def is_in(s: str, ltr:str) -> bool:
i = 0
while i<len(s) and s[i]!=ltr:
i = i + 1
return i<len(s)
def get_word(txt:str, pos:int) -> str:
i = pos
while i<len(txt) and is_in(PUNCTUATION, txt[i]):
i += 1
word = ''
while i<len(txt) and not is_in(PUNCTUATION, txt[i]):
word += txt[i]
i += 1
return word, i
def split(txt: str) -> list[str]:
i = 0
word_lst = []
while i < len(txt):
word, i = get_word(txt, i)
if word!='':
word_lst.append(word)
return word_lst
def lower(word: str) -> str:
new = ''
for ltr in word:
if 'A' <= ltr <= 'Z':
ltr = chr(ord('a') + ord(ltr) - ord('A'))
elif ltr == 'Á':
ltr = 'á'
elif ltr == 'É':
ltr = 'é'
elif ltr == 'Í':
ltr = 'í'
elif ltr == 'Ó':
ltr = 'ó'
elif ltr == 'Ú':
ltr = 'ú'
elif ltr == 'Ü':
ltr = 'ü
new = new + ltr
return new
def index(lst: list, elem) -> int:
i = 0
while i<len(lst) and lst[i]!=elem:
i = i + 1
if i<len(lst):
pos = i
else:
pos = -1
return pos
def different_words(words: list[str]) -> list[str]:
different = []
for w in words:
lw = lower(w)
if index(different, lw) == -1:
different.append(lw)
return different
def mean_variance(serie: list[float]) -> (float, float):
s = 0
s_sq = 0
for n in serie:
s += n
s_sq += n*n
mean = s/len(serie)
variance = s_sq/len(serie) - mean*mean
return mean, variance
def get_lengths(words: list[str]) -> list[int]:
lengths = []
for w in words:
lengths.append(len(w))
return lengths
def frequency(text: str) -> dict[str, int]:
words = split(text)
freq = {}
for w in words:
lw = lower(w)
if lw in freq:
freq[lw] += 1
else:
freq[lw] = 1
return freq
def frequency_rel(freq: dict):
s = 0
for v in freq.values():
s += v
for w in freq:
freq[w] = freq[w] / s
Merge Sort
This code implements the merge sort algorithm for sorting a list.
def merge(lst: list, low: int, mid: int, high:int, aux: list) -> None:
i = low #index to make the run to the first sublist
j = mid+1 #index to make the run to the second sublist
k = 0 #index pointing to the position to the next element of aux
while i<=mid and j<=high:
if lst[i]<=lst[j]:
aux[k]=lst[i]
i+=1
k+=1
else:
aux[k]=lst[j]
j+=1
k+=1
while i<=mid: #copy what is left in the first sublist
aux[k]=lst[i]
i+=1
k+=1
while j<=high: #copy what is left in the second sublist
aux[k]=lst[j]
j+=1
k+=1
i = low #copy the elements from aux to lst
k = 0
while i<=high:
lst[i] = aux[k]
i+=1
k+=1
def merge_sort(lst: list, low: int, high: int, aux: list) -> None:
if lowMastermind Game
This code implements a mastermind game, including functions for generating combinations, calculating clues, checking compatibility with game history, and managing game state.
NCOLORS = 6
SIZE = 4
def next_combination(comb: str) -> str:
newcomb = ''
end = False
carry = 1
i = len(comb)-1
while i>=0:
n = ord(comb[i]) - ord('a') + carry
if n >= NCOLORS:
n = 0
carry = 1
else:
carry = 0
newcomb = chr(n + ord('a')) + newcomb
i = i-1
return newcomb
def gen_combination() -> str:
comb = ''
for _ in range(SIZE):
n = random.randint(0, NCOLORS - 1)
comb = comb + (chr(n + ord('a')))
return comb
def ocurrences(color: str, comb: str) -> int:
hits = 0
for i in comb:
if color == i:
hits += 1
return hits
def get_clues(secret: str, guess: str) -> (int, int):
deads = 0
for i in range(SIZE):
if secret[i]==guess[i]:
deads += 1
wounds = 0
for i in range(NCOLORS):
n = chr(i + ord('a'))
wounds += min(ocurrences(n, secret), ocurrences(n, guess))
return wounds - deads, deads
def is_compatible_history(comb: str, history: dict) -> bool:
i = 0
while i < len(history['guesses']) and \
get_clues(comb, history['guesses'][i]) == history['clues'][i]:
i += 1
return i == len(history['guesses'])
def next_compatible_comb(current: str, history: dict) -> str:
current = next_combination(current)
while not is_compatible_history(current, history):
current = next_combination(current)
return current
def found_sol(history: dict) -> bool:
return history['clues'][-1] == (0, SIZE)
def game(secret):
current = 'a' * SIZE
history = {'guesses': [ current ],
'clues': [ get_clues(secret, current) ] }
while not found_sol(history):
#print(history['guesses'][-1], history['clues'][-1])
# print(history)
current = next_compatible_comb(current, history)
match = get_clues(secret, current)
history['guesses'].append(current)
history['clues'].append(match)
#print(f'The secret number is "{secret}"')
#print(f'The current combination is "{current}"')
return history
Matrix Operations
This code defines functions for creating, filling, representing, and performing operations on matrices, including addition, multiplication, transposition, and determinant calculation.
def create_matrix(nrows: int, ncols: int) -> list[list[float]]:
"""
This function creates a nrows x ncols matrix of zeroes
"""
assert nrows > 0 and ncols > 0, \
f'The number of rows and cols must be positive {nrows} {ncols}'
mat = []
for _ in range(nrows):
mat.append([0.0] * ncols)
return mat
def fill_matrix(m: list[list[float]]):
elem = 0.0
for i in range(len(m)):
for j in range(len(m[i])):
m[i][j] = elem
elem += 1
def repr_matrix(matrix: list[list[float]]) -> str:
"""
Procedure to transform a real number matrix into a str.
We do not requiere that is a well form matrix.
"""
if len(matrix) == 0 or len(matrix[0]) == 0:
s = f'Incorrect list: {matrix}'
else:
s = f'matrix {len(matrix)}x{len(matrix[0])}\n'
for row in matrix:
s += '|'
for cell in row:
s += "{0:.2f} ".format(cell)
s += '|\n'
return s
def is_correct_matrix(mat: list[list[float]]) -> bool:
res = len(mat)>0 and len(mat[0])>0
i = 1
while res and i bool:
assert is_correct_matrix(mat1) and is_correct_matrix(mat2) and \
len(mat1)==len(mat2) and \
len(mat1[0])==len(mat2[0]), \
f'incorrect arguments:\n {repr_matrix(mat1)}\n--------\n{repr_matrix(mat2)} '
nrows = len(mat1)
ncols = len(mat1[0])
eq = True
i = 0
while eq and i < len(mat1):
j =0
while eq and j < len(mat1[0]):
eq = math.isclose(mat1[i][j], mat2[i][j])
j += 1
i += 1
return eq
def is_square(mat: list[list[float]]) -> bool:
assert is_correct_matrix(mat), \
f'incorrect arguments:\n {repr_matrix(mat)}'
nrows = len(mat)
ncols = len(mat[0])
return ncols == nrows
def is_symmetric(mat: list[list[float]]) -> bool:
assert is_correct_matrix(mat), \
f'incorrect arguments:\n {repr_matrix(mat)}'
nrows = len(mat)
if is_square(mat):
i = 0
res = True
while i < nrows and res:
j = i+1
while res and j < nrows:
res = math.isclose(mat[i][j], mat[j][i])
#print(f'c1, {i} {j} {mat[i][j]} {mat[i][j]}, {res}')
j = j+1
i = i+1
else:
res = False
return res
def copy_matrix(mat: list[list[float]]) -> list[list[float]]:
assert is_correct_matrix(mat), f'Cannot copy an incorrect matrix'
new_mat = create_matrix(len(mat), len(mat[0]))
for i in range(len(mat)):
for j in range(len(mat[0])):
new_mat[i][j] = mat[i][j]
return new_mat
def transpose(matrix: list[list[float]]) -> list[list[float]]:
assert is_correct_matrix(matrix), f'inctorrect matrix {repr_matrix(matrix)}'
rows = len(matrix)
cols = len(matrix[0])
new = create_matrix(cols, rows)
i = 0
while i list[list[float]]:
assert is_correct_matrix(mat2), f'inctorrect matrix {repr_matrix(mat1)}'
assert is_correct_matrix(mat1), f'inctorrect matrix {repr_matrix(mat2)}'
assert len(mat1)==len(mat2) and len(mat1[0])==len(mat2[0]), \
'The sizes of the matrixes does not match {len(mat1)}x{len(mat1[0])} and {len(mat1)}x{len(mat1[0])} '
nrows = len(mat1)
ncols = len(mat1[0])
new = create_matrix(nrows, ncols)
for i in range(nrows):
for j in range(ncols):
new[i][j] = mat1[i][j] + mat2[i][j]
return new
def mult(mat1: list[list[float]], mat2: list[list[float]]) -> list[list[float]]:
assert is_correct_matrix(mat2), f'inctorrect matrix {repr_matrix(mat1)}'
assert is_correct_matrix(mat1), f'inctorrect matrix {repr_matrix(mat2)}'
assert len(mat1[0])==len(mat2), \
'The sizes of the matrixes does not match {len(mat1)}x{len(mat1[0])} and {len(mat1)}x{len(mat1[0])} '
rows = len(mat1)
cols = len(mat2[0])
common = len(mat2)
new = create_matrix(rows, cols)
i = 0
while i < rows:
j = 0
while j < cols:
k = 0
elem = 0.0
while k < common:
elem += mat1[i][k]*mat2[k][j]
k = k+1
new[i][j] = elem
j = j+1
i = i+1
return new
def find_non_null(matrix, col):
i = col
while i < len(matrix) and math.isclose(matrix[i][col], 0.0):
i += 1
return i
def change_row(matrix, row1, row2):
len_row = len(matrix)
for i in range(len_row):
aux = matrix[row1][i]
matrix[row1][i] = matrix[row2][i]
matrix[row2][i] = aux
def divive_row(matrix, row, value):
for i in range(len(matrix)):
matrix[row][i] = matrix[row][i] / value
def combine_rows(matrix, row, col, val):
i = 0
while i