# วิชาโครงสร้างข้อมูลและอัลกอริทึม Data Structures and Algorithms with Python Programming by Aj.NesT the Series

วิชาโครงสร้างข้อมูลและอัลกอริทึม
Data Structures and Algorithms with Python Programming by Aj.NesT the Series

# Lab 1 Recursion in Python

“Of all ideas I have introduced to children, recursion stands out as the one idea that is particularly able to evoke an excited response.”
“จากความคิดทั้งหมดที่ฉันจะแนะนำให้เด็ก ๆ รู้จัก การเรียกซ้ำมีความโดดเด่นคือเป็นแนวคิดเดียวที่สามารถทำให้เกิดการตอบสนองที่น่าตื่นเต้น”
— Seymour Papert, Mindstorms

Lab 1.1 The Factorial Function

```#Recursion
#Lab1.1 The Factorial Function

def factorial(n):
if n == 0:
return 1
else:
return n*factorial(n-1)

#int(input("...")) รับค่าข้อมูลแบบตัวเลข integer
number = int(input("Enter factorial number: "))
print(factorial(number))
```

Lab 1.2 Drawing an English Ruler

```#Lab1.2 Drawing an English Ruler
def draw_line(tick_length, tick_label=''):
"""Draw one line with given tick length (followed by optional label)."""
line = '-' * tick_length
if tick_label:
line += ' ' + tick_label
print(line)

def draw_interval(center_length):
"""Draw tick interval based upon a central tick length."""
if center_length > 0:  # stop when length drops to 0
draw_interval(center_length - 1)  # recursively draw top ticks
draw_line(center_length)  # draw center tick
draw_interval(center_length - 1)  # recursively draw bottom ticks

def draw_ruler(num_inches, major_length):
"""Draw English ruler with given number of inches and major tick length."""
draw_line(major_length, '0')  # draw inch 0 line
for j in range(1, 1 + num_inches):
draw_interval(major_length - 1)  # draw interior ticks for inch
draw_line(major_length, str(j))  # draw inch j line and label

if __name__ == '__main__':
draw_ruler(3, 6)
print('=' * 30)
```

Lab 1.3 The Sum of a List of Numbers

```#Lab1.3 The sum of a list of numbers
def list_sum(num_List):
if len(num_List) == 1:
return num_List
else:
return num_List + list_sum(num_List[1:])

print(list_sum([3, 6, 9, 12, 16]))
```

Lab 1.4 Recursion List Sum

```#Lab1.4 Recursion List Sum
def recursive_list_sum(data_list):
total = 0
for element in data_list:
if type(element) == type([]):
total = total + recursive_list_sum(element)
else:
total = total + element
print( recursive_list_sum([2, 4, [6,8],[10,12]]))
```

Lab 1.5 Sum of a Non-Negative Integer Digit

```#Lab1.5 Sum of a Non-Negative Integer
def sumDigits(n):
if n == 0:
return 0
else:
return n % 10 + sumDigits(int(n / 10))
print(sumDigits(678))
print(sumDigits(79))
```

# Lab 2 Array in Python

Lab 2.1 Dynamic Arrays

```#Array
#Lab2.1 Dynamic Arrays
#Array Set 1
data_list = [2, 4, [6, 8], [10, 12]]
for element in data_list:
print("index[", data_list.index(element),"] is", element)
a = len(data_list)
print("data_list's Length =", a)
print("data_list =", data_list, "\n")

#Array Set 2
data_car = ["Toyota", "Honda", "Ford"]
for element in data_car:
print("index[", data_car.index(element),"] is", element)
print("data_car's Length = ", len(data_car))
data_car.append("Benz")
data_car.append("BMW")
for element in data_car:
print("index[", data_car.index(element),"] is", element)
print("Last data_car's Length = ", len(data_car))
print("data_car =", data_car, "\n")

#Array Set 3
real_number = [1, 2.8, 3.149]
real_number.append(89)
real_number.append(368.659)
real_number.remove(3.149)
for element in real_number:
print("index[", real_number.index(element),"] is", element)
print("Last real_number's Length = ", len(real_number))
print("real_number =", real_number, "\n")
```

Lab 2.2 Implementing a Dynamic Array

```#Lab2.2 Implemenring a Dynamic Array p.195
import ctypes
class DynamicArray(object):
"""DYNAMIC ARRAY CLASS (Similar to Python List)"""
#initilize ir
def __init__(self):
#We will have 3 atributes
self.n = 0 # Count actual elements (Default is 0)
self.capacity = 1 # Default Capacity
self.A = self.make_array(self.capacity) #make_array will be defined later
#special len method
def __len__(self):
"""Return number of elements sorted in array"""
return self.n
def __getitem__(self, k):
"""Return element at index k"""
if not 0 <= k <self.n:
# Check it k index is in bounds of array
return IndexError('K is out of bounds !')
return self.A[k] # Retrieve from the array at index k
def append(self, ele):
"""Add element to end of the array"""
#Checking the capacity
if self.n == self.capacity:
# Double capacity if not enough room
self._resize(2 * self.capacity)     #_resize is the method that is defined later
#Set the n indexs of array A to element
self.A[self.n] = ele
self.n += 1
def _resize(self, new_cap): #new_cap is for new capacity
"""Resize internal array to capacity new_cap"""
#Decalare array B
B = self.make_array(new_cap)
for k in range(self.n): # Reference all existing values
B[k] = self.A[k]
self.A = B # Call A the new bigger array
self.capacity = new_cap # Reset the capacity
#making the make-array method using ctypes
def make_array(self, new_cap):
"""Returns a new array with new_cap capacity"""
return (new_cap * ctypes.py_object)()

arr = DynamicArray()
arr.append(1)
print(len(arr))
arr.append(2)
arr.append(6)
arr.append(89)
print(len(arr))
print(arr)
print(arr)
```

Lab 2.3 Storing High Scores for a Game

```#Lab 2.3 Storing High Scores for a Game
class GameEntry:
"""Represents one entry of a list of high scores."""

def __init__(self, name, score):
"""Create an entry with given name and score."""
self._name = name
self._score = score

def get_name(self):
"""Return the name of the person for this entry."""
return self._name

def get_score(self):
"""Return the score of this entry."""
return self._score

def __str__(self):
"""Return string representation of the entry."""
return '({0}, {1})'.format(self._name, self._score) # e.g., '(Bob, 98)'

class Scoreboard:
"""Fixed-length sequence of high scores in nondecreasing order."""

def __init__(self, capacity=10):
"""Initialize scoreboard with given maximum capacity.

All entries are initially None.
"""
self._board = [None] * capacity        # reserve space for future scores
self._n = 0                            # number of actual entries

def __getitem__(self, k):
"""Return entry at index k."""
return self._board[k]

def __str__(self):
"""Return string representation of the high score list."""
return '\n'.join(str(self._board[j]) for j in range(self._n))

"""Consider adding entry to high scores."""
score = entry.get_score()

# Does new entry qualify as a high score?
# answer is yes if board not full or score is higher than last entry
good = self._n < len(self._board) or score > self._board[-1].get_score()

if good:
if self._n < len(self._board):        # no score drops from list
self._n += 1                        # so overall number increases

# shift lower scores rightward to make room for new entry
j = self._n - 1
while j > 0 and self._board[j-1].get_score() < score:
self._board[j] = self._board[j-1]   # shift entry from j-1 to j
j -= 1                              # and decrement j
self._board[j] = entry                # when done, add new entry

if __name__ == '__main__':
board = Scoreboard(5)
for e in (
('Somchai', 750), ('Somsri',1105), ('Somying', 590), ('Sompong', 740),
('Somrak', 510), ('Somhwang', 660), ('Somporn', 720), ('Sompon', 400),
):
ge = GameEntry(e, e)
print('After considering {0}, scoreboard is:'.format(ge))
print(board)
print()
```

Lab 2.4 Caesar Cipher – Using Array-Based Sequences
Caesar Cipher เป็นการเข้ารหัสแบบซีเคร็ทคีย์ (Secret Key) หรือ Symmetric Key Cryptography คิดค้นโดยกษัตริย์ Julius Caesar เพื่อสื่อสารกับทหารในกองทัพ และป้องกันไม่ให้ข่าวสารรั่วไหลไปถึงศัตรู

```#Lab 2.4 Caesar Cipher - Using Array-Based Sequences
class CaesarCipher:
"""Class for doing encryption and decryption using a Caesar Cipher."""
def __init__(self, shift):
"""Construct Caesar Cipher using given intefer shift for rotation."""
encoder = [None]*26         #temp array for encryption
decoder = [None]*26         #temp array for decryption
for k in range(26):
encoder[k] = chr((k + shift)%26 + ord('A'))
decoder[k] = chr((k - shift)%26 + ord('A'))
self._forward = ''.join(encoder)        #will store as string
self._backward = ''.join(decoder)       #since fixed
def encrypt(self, message):
"""Return string representing encripted message."""
return self._transform(message,self._forward)
def decrypt(self, secret):
"""Return decrypted message given encrypted secret."""
return self._transform(secret, self._backward)
def _transform(self, original, code):
"""Utility to perform transformation based on given code string."""
msg = list(original)
for k in range(len(msg)):
if msg[k].isupper():
j = ord(msg[k])-ord('A')    #index from 0 to 25
msg[k] = code[j]            #replace this character
return ''.join(msg)

if __name__ == '__main__':
cipher = CaesarCipher(3)
message = "HELLO PYTHON PROGRAMMING; I LOVE YOU."
coded = cipher.encrypt(message)
print('Secret: ', coded)
```

Lab 2.5 Tic Tac Toe 1

```#Lab 2.5 Tic Tac Toe 1
class TicTacToe:
"""Management of a Tic-Tac-Toe Game (does not do strategy)."""
def __init__(self):
"""Start a new game."""
self._board = [[' ']*3 for j in range(3)]
self._player = 'X'
def mark(self, i, j):
"""Put an X or O mark at position(i,j) for next player's trun."""
if not(0 <= i <= 2 and 0 <= i <= 2):
raise ValueError('Invalid board position')
if self._board[i][j] != ' ':
raise ValueError('Board position occupied')
if self.winner() is not None:
self._board[i][j] = self._player
if self._player == 'X':
self._player = 'O'
else:
self._player = 'X'
def _is_win(self, mark):
"""Check whether the board configuration is a win for the given player."""
board = self._board
return(mark == board == board == board or #row 0
mark == board == board == board or #row 1
mark == board == board == board or #row 2
mark == board == board == board or #column 0
mark == board == board == board or #column 1
mark == board == board == board or #column 2
mark == board == board == board or #diagonal
mark == board == board == board)  #rev diag

def winner(self):
"""Return mark of winning player, or None to indicate a tie."""
for mark in 'XO':
if self._is_win(mark):
return mark
return None
def __str__(self):
"""Return string representation of current game board."""
rows = ['|'.join(self._board[r]) for r in range(3)]
return '\n-----\n'.join(rows)

game = TicTacToe()
#X moves:               #O moves:
game.mark(1,1);         game.mark(0,2)
game.mark(2,2);         game.mark(0,0)
game.mark(0,1);         game.mark(2,1)
game.mark(1,2);         game.mark(1,0)
game.mark(2,0)

print(game)
winner = game.winner()
if winner is None:
print('Tie')
else:
print(winner, 'wins')
```

Assignment Lab 2 จงเขียนเกม O-X หรือเกมที่ใช้ Array ประยุกต์จากตัวอย่าง โดยมีการรับค่าจากผู้เล่น

# Lab 3 Stack, Queue, and Deque in Python

### Stack

Lab 3.1 The following table shows a series of stack operations and their effects on an initially empty stack S of integers

```#Stack
class ArrayStack:
"""LIFO Stack implementation using a Python list as underlying storage."""
def __init__(self):
"""Create an empty stack."""
self._data = []                         #nonpublic list instance
def __len__(self):
"""Return the number of elements in the stack."""
return len(self._data)
def is_empty(self):
"""Return True if the stack is empty."""
return len(self._data) == 0
def push(self, e):
"""Add element e to the top of the stack."""
self._data.append(e)                    #new item stored at end of list
def top(self):
"""Return (but do not remove) the element at the top of the stack.
Raise Empty excpetion if the stack is empty."""
if self.is_empty():
raise Empty('Stack is empty')
return self._data[-1]                   #the last item in the list
def pop(self):
"""Remove and return the element from the top of the stack (i.e., LIFO).
Raise Empty exception if the stack is empty."""
if self.is_empty():
raise Empty('Stack is empy')
return self._data.pop()                 #remove last item from list

S = ArrayStack()            #contents: []
S.push(5)                   #contents: 
S.push(3)                   #contents: [5, 3]
print(len(S))               #contents: [5, 3];      outputs 2
print(S.pop())              #contents: ;         outputs 3
print(S.is_empty())         #contents: ;         outputs False
print(S.pop())              #contents: [];          outputs 5
print(S.is_empty())          #contents: [];          outputs True
S.push(7)                   #contents: 
S.push(9)                   #contents: [7, 9]
print(S.top())              #contents: [7, 9];      outputs 9
S.push(4)                   #contents: [7, 9, 4]
print(len(S))               #contents: [7, 9, 4];   outputs 3
print(S.pop())              #contents: [7, 9];      outputs 4
S.push(6)                   #contents: [7, 9, 6]
```

Lab 3.2 Reversing Data Using a Stack

Input File: Data.txt
Upload Data.txt –> Write Source Code –> Directory Path: “/content/Data.txt”

```#Stack
class ArrayStack:
"""LIFO Stack implementation using a Python list as underlying storage."""
def __init__(self):
"""Create an empty stack."""
self._data = []                         #nonpublic list instance
def __len__(self):
"""Return the number of elements in the stack."""
return len(self._data)
def is_empty(self):
"""Return True if the stack is empty."""
return len(self._data) == 0
def push(self, e):
"""Add element e to the top of the stack."""
self._data.append(e)                    #new item stored at end of list
def top(self):
"""Return (but do not remove) the element at the top of the stack.
Raise Empty excpetion if the stack is empty."""
if self.is_empty():
raise Empty('Stack is empty')
return self._data[-1]                   #the last item in the list
def pop(self):
"""Remove and return the element from the top of the stack (i.e., LIFO).
Raise Empty exception if the stack is empty."""
if self.is_empty():
raise Empty('Stack is empy')
return self._data.pop()                 #remove last item from list

def reverse_file(filename):
"""Overwrite given file with its contents line-by-line reversed."""
S = ArrayStack()
original = open(filename)
for line in original:
S.push(line.rstrip('\n'))       #we will re-insert newlines when writing
original.close()

#now we overwrite with contents in LIFO order
output = open(filename, 'w')        #reopening file overwrites original
while not S.is_empty():
output.write(S.pop() + '\n')    #re-insert newline characters
output.close()

Output = reverse_file("/content/Data.txt")
```

### Queue

```#Queues
class ArrayQueue:
"""FIFO queue implementation using a Python list as underlying storage."""
DEFAULT_CAPACITY = 10       #moderate capacity for all new queues

def __init__(self):
"""Create an empty queue."""
self._data = [None]*ArrayQueue.DEFAULT_CAPACITY
self._size = 0
self._front = 0

def __len__(self):
"""Return the number of elements in the queue."""
return self._size

def is_empty(self):
"""Return True if the queue is empty."""
return self._size == 0

def first(self):
"""Return (but do not remove) the element at the front of the queue.

Raise Empty exception if the queue is empty.
"""
if self.is_empty():
raise Empty('Queue is empty')
return self._data[self._front]

def dequeue(self):
"""Remove and return the first element of the queue (i.e.,FIFO).

Raise Empty exception if the queue is empty.
"""
if self.is_empty():
raise Empty('Queue is empty')
self._data[self._front] = None      #help garbage collection
self._front = (self._front + 1)%len(self._data)
self._size -= 1

def enqueue(self, e):
"""Add an element to the back of queue."""
if self._size == len(self._data):
self._resize(2*len(self.data))     #double the array size
avail = (self._front + self._size) % len(self._data)
self._data[avail] = e
self._size += 1

def _resize(self, cap):                 #we assume cap >= len(self)
"""Resize to a new list of capacity >= len(self)."""
old = self._data                    #keep track of existing list
self._data = [None]*cap             #allocate list with new capacity
walk = self._front
for k in range(self._size):         #only consider existing elements
self._data[k] = old[walk]       #intentionally shift indices
walk = (1+walk) % len(old)      #use old size as modulus
self._front = 0                     #front has been realigned

Q = ArrayQueue()
Q.enqueue(5)          #
Q.enqueue(3)          #[5, 3]
print(len(Q))         #[5, 3]
print(Q.dequeue())    #
print(Q.is_empty())   #
print(Q.dequeue())    #[]
print(Q.is_empty())   #[]
#print(Q.dequeue())   #Error
Q.enqueue(7)          #
Q.enqueue(9)          #[7, 9]
print(Q.first())      #[7, 9]
Q.enqueue(4)          #[7, 9, 4]
print(len(Q))         #[7, 9, 4]
print(Q.dequeue())    #[9, 4]
``` at GlurGeek.Com
Lecturer, Blogger, Traveler, and Software Developer ที่ชอบอ่านบทความใหม่ๆ ตลอดเวลา ชอบหาวิธีสร้าง Inspiration เป็นชีวิตจิตใจ มีความฝันอยากทำ CREATIVE PRODUCT ที่สามารถเปลี่ยนแปลงโลกให้ดีขึ้น และอยากถ่ายรูปสถานที่ท่องเที่ยวรอบโลก สอนหนังสือ ชอบแลกเปลี่ยนความรู้ และเขียน WEBSITE, MOBILE APP, GAME, ETC ที่เป็นประโยชน์กับโลกใบนี้