blocks1.txt

1 1 1 1 1 1 1 3 4 2 2 3

gistfile1.py

"""
Austin Malerba, CS I, pack.py
Creates a "box" with square dimensions box size. A file containing "blocks", square in dimensions, is read and the blocks
are fit into the box in first-fit, descending order. If a block does not fit in the box, it is discarded and the next
block is tried. Unfilled elements of the box are marked by zeroes.

"""

def create_box(boxsize):
    """
    Creates list of lists with dimensions determined by the user where each
    element is 0.
    Returns this list, box.
    """
    box=[[0 for column in range(boxsize)] for row in range(boxsize)]
    return box


def print_box(box,boxsize):
    """
    Prints box in grid formation.

    Parameters:box (list) - list of lists square in dimensions. boxsize
    (int) - represents the dimensions of the box
    
    """
    for row in range(boxsize):
        for column in range(boxsize):
            print(box[row][column],end=" ")
        print()

def get_blocks():
    """
    Prompts user for block file, which it opens and reads. Creates a list, blocks,
    containing the blocks in the file.
    Returns blocks (list).
    
    """
    
    blocks=[]
    block_file=input("Enter name of block file:")
    for line in open(block_file):
        blocks += line.split()
    for index in range(len(blocks)):
        blocks[index]=int(blocks[index])
    return blocks


def sort_blocks(blocks):
    """
    Sorts list in decreasing order.

    Parameters: blocks (list)- unsorted list of blocks

    Preconditions:blocks unsorted
    Postconditions:blocks still unsorted

    Returns sorted_blocks (list)- list of blocks sorted in decreasing order

    """
    sorted_blocks=sorted(blocks,reverse=True)
    return sorted_blocks


def check_fit(box, block, row, column):
    """
    Checks if a block fits for one location in the box.

    Parameters:box (list)- list of lists. block (int)- size of block to be
    checked. row (int)- row to be checked. column (int)- column to be checked.

    Returns False if block does not fit.
    Returns True if block does fit.

    """
    
    if row+block>len(box) or column+block>len(box):
        return False
    for row_index in range(row,row+block):
        for column_index in range(column,column+block):
            if box[row_index][column_index]!=0:
                return False
        return True

def check_all_spots(box,block):
    """
    Calls check_fit for all locations in box, starting in top left and ending
    in bottom right.

    Parameters:box (list)- list of lists. block (int)- size of block being
    checked.

    Returns row,column if block fits.
    Returns False if block does not fit at any location.

    """
    for row in range(len(box)):
        for column in range(len(box)):
            if check_fit(box,block,row,column)==True:
                return row,column
    return False

def update_box(box,block,row,column):
    """
    Swaps block for zeros in box.

    Parameters: box (list)- list of lists. block (int)- size of block being
    checked. row (int) row where block should be entered. column (int)- column
    where block should be entered (starting with top left of block).

    Preconditions:box contains n blocks
    Postconditions:box contains n+1 blocks

    Returns updated box.
    """
    for row_spot in range(row,row+block):
        for column_spot in range(column,column+block):
            box[row_spot][column_spot]=block
    return box


def check_all_blocks(box,blocks,boxsize):
    """
    Checks fit for all blocks in block file. If the blcok does not fit, the
    block is added to the list unpacked_blocks. If the block does fit, the box
    is updated.

    Parameters:box (list)- list of lists square in dimensions.blocks (list)-
    sorted list of blocks available. boxsize (int)- represents the dimensions
    of the box.

    Preconditions:box all zeros
    Postconditions:box has been updated to final state

    Returns box (the updated box), and unpacked_blocks (list of unpacked blocks)
    """
    unpacked_blocks=[]
    for block in blocks:
        if check_all_spots(box,block)==False:
            unpacked_blocks.append(block)
        else:
            row,column=check_all_spots(box,block)
            box=update_box(box,block,row,column)
    return box,unpacked_blocks

def count_zeros(box):
    """
    Checks each element in the box and, if it equals zero, adds one to
    total_zeros.

    Parameters: box (list):list of lists square in dimensions.

    Returns total_zeros

    """  
    total_zeros=0
    for row in box:
        for column in row:
            if column==0:
                total_zeros+=1
    return total_zeros
    
def main():
    """
    Prompts user for box size, calls create_box(), calls get_blocks, calls
    sort_blocks(),calls check_all_blocks,prints box, free spaces, and list of
    unpacked blocks.
    
    """
    boxsize=int(input("Enter size of box:"))
    box=create_box(boxsize)
    blocks=get_blocks()
    blocks=sort_blocks(blocks)
    box,unpacked_blocks=check_all_blocks(box,blocks,boxsize)
    print_box(box,boxsize)
    print("Free Spaces:",count_zeros(box))
    print("Unpacked blocks:",unpacked_blocks)


main()