Python Pa help po ako sa ma debug tong assignment ko sa Python

[blindpick]

a1_partc.py

class Stack:
    def __init__(self, cap=10):
        # Initializes the stack with capacity or a default of 10 if not provided
        # The _stack will store elements and size will keep track of the number of elements
        self._stack = [None] * cap
        self.size = 0
        self.cap = cap

    def capacity(self):
        # Returns the capacity of the stack
        return self.cap

    def push(self, data):
        # If the stack is at capacity, resize it (double the cap)
        if self.size == self.cap:
            self._resize(2 * self.cap)
       
        # Adds data to the top of the stack
        self._stack[self.size] = data
        self.size += 1

    def pop(self):
        # If the stack is empty, raise an error
        if self.is_empty():
            raise IndexError('pop() used on empty stack')
       
        # Removes the newest value from the stack and returns value removed
        self.size -= 1
        data = self._stack[self.size]
        self._stack[self.size] = None
        return data

    def get_top(self):
        # Returns the newest value from the stack without removing it
        # Returns None if the stack is empty
        if self.is_empty():
            return None
        return self._stack[self.size - 1]

    def is_empty(self):
        # Returns True if the stack is empty
        return self.size == 0

    def __len__(self):
        # Returns the number of values in the stack
        return self.size

    def _resize(self, newcap):
        # Private method to resize the underlying list
        new_stack = [None] * newcap
        for i in range(self.size):
            new_stack[i] = self._stack[i]
        self._stack = new_stack
        self.cap = newcap

class Queue:
    def __init__(self, cap=10):
        # Initializes the queue with capacity or a default of 10 if not provided
        # The _queue will store elements and front and size will help manage them
        self._queue = [None] * cap
        self.front = 0  # Index of the front element
        self.size = 0  # Number of elements currently in the queue
        self.cap = cap

    def capacity(self):
        # Returns the capacity of the queue
        return self.cap

    def enqueue(self, data):
        # If the queue is at capacity, resize it (double the cap)
        if self.size == self.cap:
            self._resize(2 * self.cap)
       
        # Adds data to the back of the queue
        back_index = (self.front + self.size) % self.cap
        self._queue[back_index] = data
        self.size += 1

    def dequeue(self):
        # If the queue is empty, raise an error
        if self.is_empty():
            raise IndexError('dequeue() used on empty queue')
       
        # Removes the oldest value from the queue and returns value removed
        data = self._queue[self.front]
        self._queue[self.front] = None
        self.front = (self.front + 1) % self.cap
        self.size -= 1
        return data

    def get_front(self):
        # Returns the oldest value from the queue without removing it
        # Returns None if the queue is empty
        if self.is_empty():
            return None
        return self._queue[self.front]

    def is_empty(self):
        # Returns True if the queue is empty
        return self.size == 0

    def __len__(self):
        # Returns the number of values in the queue
        return self.size

    def _resize(self, newcap):
        # Private method to resize the underlying list
        new_queue = [None] * newcap
        for i in range(self.size):
            new_queue[i] = self._queue[(self.front + i) % self.cap]
        self._queue = new_queue
        self.front = 0
        self.cap = newcap




class Deque:
    def __init__(self, cap=10):
        # Initializes the Deque with capacity or a default of 10 if not provided
        # The _deque will store elements and front and size will help manage them
        self._deque = [None] * cap
        self.front = 0  # Index of the front element
        self.size = 0  # Number of elements currently in the deque
        self.cap = cap

    def capacity(self):
        # Returns the capacity of the deque
        return self.cap

    def push_front(self, data):
        # If the deque is at capacity, resize it (double the cap)
        if self.size == self.cap:
            self._resize(2 * self.cap)
       
        # Decrement the front index (and wrap around if necessary)
        self.front = (self.front - 1) % self.cap
        self._deque[self.front] = data
        self.size += 1

    def push_back(self, data):
        # If the deque is at capacity, resize it (double the cap)
        if self.size == self.cap:
            self._resize(2 * self.cap)
       
        # Adds data to the back of the deque
        back_index = (self.front + self.size) % self.cap
        self._deque[back_index] = data
        self.size += 1

    def pop_front(self):
        # If the deque is empty, raise an error
        if self.is_empty():
            raise IndexError('pop_front() used on empty deque')
       
        # Removes the front value from the deque and returns value removed
        data = self._deque[self.front]
        self._deque[self.front] = None
        self.front = (self.front + 1) % self.cap
        self.size -= 1
        return data

    def pop_back(self):
        # If the deque is empty, raise an error
        if self.is_empty():
            raise IndexError('pop_back() used on empty deque')
       
        # Removes the back value from the deque and returns value removed
        back_index = (self.front + self.size - 1) % self.cap
        data = self._deque[back_index]
        self._deque[back_index] = None
        self.size -= 1
        return data

    def get_front(self):
        # Returns the front value from the deque without removing it
        # Returns None if the deque is empty
        if self.is_empty():
            return None
        return self._deque[self.front]

    def get_back(self):
        # Returns the back value from the deque without removing it
        # Returns None if the deque is empty
        if self.is_empty():
            return None
        back_index = (self.front + self.size - 1) % self.cap
        return self._deque[back_index]

    def is_empty(self):
        # Returns True if the deque is empty
        return self.size == 0

    def __len__(self):
        # Returns the number of values in the deque
        return self.size

    def __getitem__(self, k):
        # Returns the k'th value from the front of the deque without removing it
        if k < 0 or k >= self.size:
            raise IndexError('Index out of range')
       
        return self._deque[(self.front + k) % self.cap]

    def _resize(self, newcap):
        # Private method to resize the underlying list
        new_deque = [None] * newcap
        for i in range(self.size):
            new_deque[i] = self._deque[(self.front + i) % self.cap]
        self._deque = new_deque
        self.front = 0
        self.cap = newcap

a1_partd.py

from a1_partc import Queue

def get_overflow_list(grid):
    rows = len(grid)
    cols = len(grid[0])
    overflow_cells = []

    for row in range(rows):
        for col in range(cols):
            cell_value = abs(grid[row][col])
            neighbors = 0

            if row > 0:
                neighbors += 1
            if row < rows - 1:
                neighbors += 1
            if col > 0:
                neighbors += 1
            if col < cols - 1:
                neighbors += 1

            if cell_value >= neighbors:
                overflow_cells.append((row, col))

    if not overflow_cells:
        return None
    else:
        return overflow_cells

def overflow(grid, queue):
    def spread_overflow(row, col, is_negative):
        neighbors = [
            (row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)
        ]

        for r, c in neighbors:
            if 0 <= r < len(grid) and 0 <= c < len(grid[0]):
                if grid[r][c] < 0:
                    grid[r][c] -= 1
                else:
                    grid[r][c] += 1
        for r, c in neighbors:
            if is_negative and 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] > 0:
                grid[r][c] *= -1
            if not is_negative and 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] < 0:
                grid[r][c] *= -1

    steps = 0
    while True:
        overflow_list = get_overflow_list(grid)
        if not overflow_list:
            break

        for r, c in overflow_list:
            is_negative = (grid[r][c] < 0)
            grid[r][c] = 0
            spread_overflow(r, c, is_negative)

        queue.enqueue([row[:] for row in grid])
        steps += 1

    return steps

Tester:

#
#   These are the unit tests for functions and classes of assingment 1 part D
#   To use this, run: python test_a1_partd.py

import unittest
from collections import Counter
from a1_partd import get_overflow_list, overflow
from a1_partc import Queue

class A1DTestCase(unittest.TestCase):
    """These are the test cases for functions and classes of a1"""
   
    def test_get_overflow_list(self):

        def gen_id(row,col):
            return row * 100 + col

        grid =[[0, 0, 0, 0, 0, 0 ,0],
               [0, 0, 0, 0, 0, 0 ,0],
               [0, 0, 0, 0, 0, 0 ,0],
               [0, 0, 0, 0, 0, 0 ,0],
               [0, 0, 0, 0, 0, 0 ,0],
               [0, 0, 0, 0, 0, 0 ,0]
               ]
        result = get_overflow_list(grid)
        self.assertEqual(result, None)


        grid =[[1, 2, 2, 2, 2, 2 , 2, 1],
               [2, 3, 3, 3, 3, 3 , 3, 2],
               [2, 3, 3, 3, 3, 3 , 3, 2],
               [2, 3, 3, 3, 3, 3 , 3, 2],
               [2, 3, 3, 3, 3, 3 , 3, 2],
               [2, 3, 3, 3, 3, 3 , 3, 2],
               [1, 2, 2, 2, 2, 2 , 2, 1]
               ]

        result = get_overflow_list(grid)
        self.assertEqual(result, None)



        grid =[[-1, -2, -2, -2, -2, -2 , -2, -1],
               [-2, -3, -3, -3, -3, -3 , -3, -2],
               [-2, -3, -3, -3, -3, -3 , -3, -2],
               [-2, -3, -3, -3, -3, -3 , -3, -2],
               [-2, -3, -3, -3, -3, -3 , -3, -2],
               [-2, -3, -3, -3, -3, -3 , -3, -2],
               [-1, -2, -2, -2, -2, -2 , -2, -1]
               ]

        result = get_overflow_list(grid)
        self.assertEqual(result, None)


        grid =[[2,  0,  0, 0, 0],
                [0, -3,  0, 0, 0],
                [0,  0, -2, 0, 0],
                [-1, 0,  0, 0, 3]
                ]
        correct = [(0,0),(3,4)]
        overflow_hash = Counter()
        for coord in correct:
            overflow_hash[gen_id(coord[0],coord[1])] += 1

        result = get_overflow_list(grid)

        self.assertEqual(len(correct), len(result))

        for coord in result:
            self.assertEqual(overflow_hash[gen_id(coord[0],coord[1])], 1)
            overflow_hash[gen_id(coord[0],coord[1])] += 1

        grid =[[-2,  0,  0, 0, 0],
                [0, 3,  0, 0, 0],
                [0,  0, 2, 0, 0],
                [1, 0,  0, 0, -3]
                ]

        correct = [(0,0),(3,4)]
        overflow_hash = Counter()
        for coord in correct:
            overflow_hash[gen_id(coord[0],coord[1])] += 1

        result = get_overflow_list(grid)

        self.assertEqual(len(correct), len(result))

        for coord in result:
            self.assertEqual(overflow_hash[gen_id(coord[0],coord[1])], 1)
            overflow_hash[gen_id(coord[0],coord[1])] += 1



        grid =[
                [2, 3, 3, 3, 3, 2],
                [3, 4, 4, 4, 4, 3],
                [3, 4, 4, 4, 4, 3],
                [3, 4, 4, 4, 4, 3],
                [2, 3, 3, 3, 3, 2]

            ]

                                                       
        correct = [(0,0), (0,1), (0,2), (0,3),(0,4),(0,5),
                   (1,0), (1,1), (1,2), (1,3),(1,4),(1,5),
                   (2,0), (2,1), (2,2), (2,3),(2,4),(2,5),
                   (3,0), (3,1), (3,2), (3,3),(3,4),(3,5),
                   (4,0), (4,1), (4,2), (4,3),(4,4),(4,5)
                 ]
        overflow_hash = Counter()
        for coord in correct:
            overflow_hash[gen_id(coord[0],coord[1])] += 1

        result = get_overflow_list(grid)
        self.assertEqual(len(correct), len(result))

        for coord in result:
            self.assertEqual(overflow_hash[gen_id(coord[0],coord[1])], 1)
            overflow_hash[gen_id(coord[0],coord[1])] += 1



    def test_overflow(self):
        original = [
            [
                [-2,  2, -3,  0,  0],
                [ 0, -4,  0,  0,  0],
                [ 0,  0,  3,  0,  1],
                [-1,  0,  0,  0,  1]
            ],
            [
                [-1,  3,   3,  0,  0],
                [ 0, -3,   0,  0,  0],
                [ 0,  0,  -3,  0,  2],
                [-1,  0,  -2, -2,  2]
            ],

            [
                [ 1,  2,   2,  0,  0],
                [ 0, -3,   0,  0,  0],
                [ 0,  0,  -3,  0,  2],
                [-1,  0,  -2, -2,  1]
            ],
            [
                [ 1,  3,   3,  0,  0],
                [ 0,  3,   0,  0,  0],
                [ 0,  0,   3,  0,  2],
                [ 1,  0,   2,  2,  2]
            ],
            [
                [ -1, -3,   -3,  0,   0],
                [  0, -3,    0,  0,   0],
                [  0,  0,   -3,  0,  -2],
                [ -1,  0,   -2, -2,  -2]
            ],
        ]
        steps = [
                    [
                     [  0,  -5,  0,  -1,  0 ],
                     [ -2,   0, -2,   0,  0 ],
                     [  0,  -1,  3,   0,  1 ],
                     [ -1,   0,  0,   0,  1 ]
                    ],
                    [
                     [ -1,   0,  -1,  -1,  0 ],
                     [ -2,  -1, -2,   0,  0 ],
                     [  0,  -1,  3,   0,  1 ],
                     [ -1,   0,  0,   0,  1 ]
                    ],
                    [
                     [  2,   1,  1,  1,  0 ],
                     [  0,   4,  1,  0,  0 ],
                     [  0,   0, -3,  0,  3 ],
                     [ -1,   0, -2,  3,  0 ]
                    ],
                    [
                     [  0,   3,  1,  1,  0 ],
                     [  2,   0,  2,  0,  1 ],
                     [  0,   1, -3,  2,  0 ],
                     [ -1,   0,  3,  0,  2 ]
                    ],
                    [
                     [  1,   0,  2,  1,  0 ],
                     [  2,   1,  2,  0,  1 ],
                     [  0,   1,  4,  2,  1 ],
                     [ -1,   1,  0,  2,  0 ]
                    ],

                    [
                     [  1,   0,  2,  1,  0 ],
                     [  2,   1,  3,  0,  1 ],
                     [  0,   2,  0,  3,  1 ],
                     [ -1,   1,  1,  2,  0 ]
                    ]


                ]



        the_queue = Queue()
        grid = []
        for i in range(len(original[0])):
            grid.append(original[0][i].copy())

        rc = overflow(grid,the_queue)
        self.assertEqual(rc, 2)
        self.assertEqual(len(the_queue), 2)
        for i in range(len(the_queue)):
            tmp = the_queue.dequeue()
            self.assertEqual(tmp,steps[i])
        self.assertEqual(grid,tmp)



        grid = []
        for i in range(len(original[1])):
            grid.append(original[1][i].copy())
        rc = overflow(grid,the_queue)
        self.assertEqual(rc, 4)
        self.assertEqual(len(the_queue), 4)
        for i in range(len(the_queue)):
            tmp = the_queue.dequeue()
            self.assertEqual(tmp,steps[i + 2])
        self.assertEqual(grid,tmp)

        grid = []
        for i in range(len(original[2])):
            grid.append(original[2][i].copy())
        rc = overflow(grid,the_queue)
        self.assertEqual(rc, 0)
        self.assertEqual(len(the_queue), 0)
        self.assertEqual(grid,original[2])


        grid = []
        for i in range(len(original[3])):
            grid.append(original[3][i].copy())
        rc = overflow(grid,the_queue)
        self.assertEqual(rc, 0)
        self.assertEqual(len(the_queue), 0)
        self.assertEqual(grid,original[3])


        grid = []
        for i in range(len(original[4])):
            grid.append(original[4][i].copy())
        rc = overflow(grid,the_queue)
        self.assertEqual(rc, 0)
        self.assertEqual(len(the_queue), 0)
        self.assertEqual(grid,original[4])

        grid = []
        for i in range(len(original[0])):
            grid.append(original[0][i].copy())
        rc = overflow(grid,the_queue)
        self.assertEqual(rc, 2)
        self.assertEqual(len(the_queue), 2)

        grid = []
        for i in range(len(original[1])):
            grid.append(original[1][i].copy())
        rc = overflow(grid,the_queue)
        self.assertEqual(rc, 4)
        self.assertEqual(len(the_queue), 6)

        grid = []
        for i in range(len(original[2])):
            grid.append(original[2][i].copy())
        rc = overflow(grid,the_queue)
        self.assertEqual(rc, 0)
        self.assertEqual(len(the_queue), 6)

        grid = []
        for i in range(len(original[3])):
            grid.append(original[3][i].copy())
        rc = overflow(grid,the_queue)
        self.assertEqual(rc, 0)
        self.assertEqual(len(the_queue), 6)


        grid = []
        for i in range(len(original[4])):
            grid.append(original[4][i].copy())
        rc = overflow(grid,the_queue)
        self.assertEqual(rc, 0)
        self.assertEqual(len(the_queue), 6)


        for i in range(len(steps)):
            tmp = the_queue.dequeue()
            self.assertEqual(tmp,steps[i])



    def test_overflow2(self):


        grid =[
                [ 2 , -2,   -1, 0, 0,  0],
                [ 2,  0 , 0,  0,  0,  0],
                [ 1,  0,  0,  0,  0, 0],
                [ 0,  0,  0,  0,  0, 0],
                [ 0,  0,  0,  0,  0, -1]
              ]


        steps = [
                    [
                    [ 0 , 3,  -1, 0, 0,  0],
                    [ 3,  0 , 0,  0,  0,  0],
                    [ 1,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, -1]
                     ],
                    [
                    [ 2 , 0,  2,  0, 0,  0],
                    [ 0,  2 , 0,  0,  0,  0],
                    [ 2,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, -1]
                    ],
                    [
                    [ 0 , 1,  2,  0, 0,  0],
                    [ 1,  2 , 0,  0,  0,  0],
                    [ 2,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, -1]
                    ]
                ]
       




        the_queue = Queue()

        rc = overflow(grid,the_queue)


        self.assertEqual(rc, 3)

        for i in range(len(steps)):
            tmp = the_queue.dequeue()
            self.assertEqual(tmp,steps[i])

        self.assertEqual(tmp,grid)
 

    def test_overflow3(self):


        grid =[
                [ 2 , -2,   -2, 0, 0,  0],
                [ 2,  0 , 3,  0,  0,  0],
                [ 1,  0,  0,  0,  0, 0],
                [ 0,  0,  0,  0,  0, 0],
                [ 0,  0,  0,  0,  0, 0]
              ]


        steps = [
                    [
                    [ 0 , 3,  -2, 0, 0,  0],
                    [ 3,  0 , 3,  0,  0,  0],
                    [ 1,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, 0]
                     ],
                    [
                    [ 2 , 0,  3,  0, 0,  0],
                    [ 0,  2 , 3,  0,  0,  0],
                    [ 2,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, 0]
                    ],
                ]

        the_queue = Queue()

        rc = overflow(grid,the_queue)


        self.assertEqual(rc, 2)

        for i in range(len(steps)):
            tmp = the_queue.dequeue()
            self.assertEqual(tmp,steps[i])

        self.assertEqual(tmp,grid)


    def test_overflow4(self):

        grid =[
                [ 2 , -2,   -1, 0, 0,  0],
                [ 2,  0 , 0,  0,  0,  0],
                [ 1,  0,  0,  0,  0, 0],
                [ 0,  0,  0,  0,  0, 0],
                [ 0,  0,  0,  0,  0, 1]
              ]


        steps = [
                    [
                    [ 0 , 3,  -1, 0, 0,  0],
                    [ 3,  0 , 0,  0,  0,  0],
                    [ 1,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, 1]
                     ],
                    [
                    [ 2 , 0,  2,  0, 0,  0],
                    [ 0,  2 , 0,  0,  0,  0],
                    [ 2,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, 0],
                    [ 0,  0,  0,  0,  0, 1]
                    ]
                ]
       




        the_queue = Queue()

        rc = overflow(grid,the_queue)


        self.assertEqual(rc, 2)

        for i in range(len(steps)):
            tmp = the_queue.dequeue()
            self.assertEqual(tmp,steps[i])

        self.assertEqual(tmp,grid)




if __name__ == '__main__':
    unittest.main()