วิชาโครงสร้างข้อมูลและอัลกอริทึม 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[0]
    else:
        return num_List[0] + 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
	return total
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[3] =", data_list[3], "\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[4] =", data_car[4], "\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[3] =", real_number[3], "\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[2])
print(arr[3])

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))

  def add(self, entry):
    """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[0], e[1])
    board.add(ge)
    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)
    answer = cipher.decrypt(coded)
    print('Message: ',answer)

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:
            raise ValueError('Game is already complete')
        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[0][0] == board[0][1] == board[0][2] or #row 0
               mark == board[1][0] == board[1][1] == board[1][2] or #row 1
               mark == board[2][0] == board[2][1] == board[2][2] or #row 2
               mark == board[0][0] == board[1][0] == board[2][0] or #column 0
               mark == board[0][1] == board[1][1] == board[2][1] or #column 1
               mark == board[0][2] == board[1][2] == board[2][2] or #column 2
               mark == board[0][0] == board[1][1] == board[2][2] or #diagonal
               mark == board[0][2] == board[1][1] == board[2][0])  #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: [5]
S.push(3)                   #contents: [5, 3]
print(len(S))               #contents: [5, 3];      outputs 2
print(S.pop())              #contents: [5];         outputs 3
print(S.is_empty())         #contents: [5];         outputs False
print(S.pop())              #contents: [];          outputs 5
print(S.is_empty())          #contents: [];          outputs True
S.push(7)                   #contents: [7]
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')
        answer = self._data[self._front]
        self._data[self._front] = None      #help garbage collection
        self._front = (self._front + 1)%len(self._data)
        self._size -= 1
        return answer
    
    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)          #[5]
Q.enqueue(3)          #[5, 3]
print(len(Q))         #[5, 3]
print(Q.dequeue())    #[3]
print(Q.is_empty())   #[3]
print(Q.dequeue())    #[] 
print(Q.is_empty())   #[] 
#print(Q.dequeue())   #Error
Q.enqueue(7)          #[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]

Aj. NesT The Series on sabemailAj. NesT The Series on sabfacebookAj. NesT The Series on sabinstagramAj. NesT The Series on sabtwitterAj. NesT The Series on sabyoutube
Aj. NesT The Series
at GlurGeek.Com
Lecturer, Blogger, Traveler, and Software Developer ที่ชอบอ่านบทความใหม่ๆ ตลอดเวลา ชอบหาวิธีสร้าง Inspiration เป็นชีวิตจิตใจ มีความฝันอยากทำ CREATIVE PRODUCT ที่สามารถเปลี่ยนแปลงโลกให้ดีขึ้น และอยากถ่ายรูปสถานที่ท่องเที่ยวรอบโลก สอนหนังสือ ชอบแลกเปลี่ยนความรู้ และเขียน WEBSITE, MOBILE APP, GAME, ETC ที่เป็นประโยชน์กับโลกใบนี้

Leave a Reply

Copyright © 2021 GlurGeek.Com. All Rights Reserved.