Assignment 4 Question 1

Introduction

In this assignment, you are going to help generate a word search puzzle. If you are not familiar with word search puzzles, you can find out more information

here:

In problem 1, you will write a function, willWordFitH(), which will determine whether or not a given word can fit into a word search puzzle horizontally starting at given row and column indexes.

For this problem, the puzzle grid has been created for you. It is an N×N table (a list of lists), in which N is both the number of rows and the number of columns (the table forms a square). Each cell is a single character, and all empty cells have been initialized to a period (.). For example, initially a 5x5 grid would look like the following:

[[".", ".", ".", ".", "."],
 [".", ".", ".", ".", "."],
 [".", ".", ".", ".", "."],
 [".", ".", ".", ".", "."],
 [".", ".", ".", ".", "."]]

First, the word can fit into the puzzle if it is NOT too long for the row. For example,

• If the row is 5 cells wide and the word is “CAT”, it could fit starting at column index 0, 1, or 2:

["C", "A", "T", ".", "."]
[".", "C", "A", "T", "."]
[".", ".", "C", "A", "T"]

- However, the word would be too long if it starts at column index 3 or 4:

[".", ".", ".", "C", "A"]
[".", ".", ".", ".", "C"]

• If the word is “ZEBRA”, it could fit in the row 5 cells wide starting at column 0 only:

["Z", "E", "B", "R", "A"]

• Starting at any other column would make the word too long to fit.

Second, words can overlap if they share letters:

• For example, in the following row, there is no room left for “CAT” starting at column index 2, because the cell at column index 2 already holds a “G”:

["D", "O", "G", ".", "."]

• However, there is room for “GOT” starting at column index 2, because the cell already contains “G”, which is the last letter of “DOG” and the first letter of “GOT”. That is, the two words can share the letter “G”, so the following is legal:

["D", "O", "G", "O", "T"]

Details for function willWordFitH()

Parameter Variables (Input)

• puzzle (list): The word search puzzle (a table—a list of lists—with the same number of rows as columns). Remember, this is a reference to the list. Changes made in the function are made to the actual table.
• word (string): The word to test for inclusion in the puzzle (all words will be uppercase)
• row (integer): The row index at which to place word in the puzzle table
• col (integers): The column index at which to place word in the puzzle table

Processing

• Test word to see if it can fit into puzzle. -You CANNOT add word to puzzle:
  • If word is too long to fit into the grid horizontally, starting at index [row][column] (see Introduction for examples)
  • If word overlaps with another word already in the puzzle but does NOT share the same letters (see Introduction for examples)
  • Otherwise, add the word to puzzle.

Return Value (Output)

• Return:
  • True if word was added into puzzle at [row][column]
  • False if it was not added

Sample Input/Output

Before

 [[".", ".", ".", "."], 
  [".", ".", ".", "."],
  [".", ".", ".", "."],
  [".", ".", ".", "."]]	

Notes

We want to add “CAT” to myPuzz at [0][1]

Call: willWordFitH(myPuzz, “CAT”, 0, 1)

Return: True. “CAT” has been added to myPuzz because there was room.

After

 [[".", "C", "A", "T"], 
  [".", ".", ".", "."],
  [".", ".", ".", "."],
  [".", ".", ".", "."]]

Before

 [[".", "C", "A", "T"], 
  [".", ".", ".", "."],
  [".", ".", ".", "."],
  [".", ".", ".", "."]]	

Notes

Now we want to add “DOG” at [0][1].

Call: willWordFitH(myPuzz, “DOG”, 0, 1)

Return: False. Grid remains unchanged because “CAT” already exists where we wanted to place “DOG”.

After

 [[".", "C", "A", "T"], 
  [".", ".", ".", "."],
  [".", ".", ".", "."],
  [".", ".", ".", "."]]

Before

 [[".", "C", "A", "T"], 
  [".", ".", ".", "."],
  [".", ".", ".", "."],
  [".", ".", ".", "."]]	

Notes

Now we want to add “SCAT” at [0][0].

Call: willWordFitH(myPuzz, “SCAT”, 0, 0)

Return: True. Grid has been updated since there is room for “SCAT” since it shares letters with “CAT”.

After

 [["S", "C", "A", "T"], 
  [".", ".", ".", "."],
  [".", ".", ".", "."],
  [".", ".", ".", "."]]

Before

 [["S", "C", "A", "T"], 
  [".", ".", ".", "."],
  [".", ".", ".", "."],
  [".", ".", ".", "."]]	

Notes

Finally we want to add “ZEBRA” at [2][0].

Call: willWordFitH(myPuzz, “ZEBRA”, 2, 0)

Return: False. Grid remains unchanged because “ZEBRA” will not fit starting at [1][0].

After

 [["S", "C", "A", "T"], 
  [".", ".", ".", "."],
  [".", ".", ".", "."],
  [".", ".", ".", "."]]

My Solution also hosted here

#########################
# CSCI 1105
# Assignment 4, Problem 1
# @author: Fleming

######################################################################
################# DO NOT CHANGE CODE INSIDE THIS BOX #################
######################################################################
numSize = int(input())                                               #
numRows = int(input())                                               #
                                                                     #
wordList = []                                                        #
for i in range(numRows):                                             #
    wordList.append(input().split(" "))                              #
    wordList[len(wordList)-1][1] = int(wordList[len(wordList)-1][1]) #
    wordList[len(wordList)-1][2] = int(wordList[len(wordList)-1][2]) #
                                                                     #
myPuzz = []                                                          #
for i in range(numSize):                                             #
    myPuzz.append( ['.'] * numSize )                                 # 
######################################################################



################## WRITE YOUR CODE AFTER THIS LINE ###################


# this is the ultimate function
def willWordFitH(puzzle, word, row, col):
    
    # made a variable that holds the number of columns in the puzzle 
    # which was useful rule out that exceeds the tables length
    puzzlecol = len(puzzle[0])
    
    # made a variable for length of the word and converted the row 
    # and col to integer if not already done
    length = len(word)
    row = int(row)
    col = int(col)
    
    # made two availability variable but if elseavailability is 
    # False the word cannot be put in the puzzle
    ifavailability = False
    elseavailability = True
    
    # made a for loop to check if the word has the eligibility to 
    # be inputted into the puzzle
    for i in range(length):
        
        # if the starting column plus the length of the word is larger
        # than the number of columns in the table it fails immediately
        if col + length > puzzlecol:
            elseavailability = False
            
        # check if the space is blank or has the same letter that the word needs
        elif puzzle[row][col+i] == "." or puzzle[row][col+i] == word[i]:
            ifavailability = True
        
        # if neither of the two above matches, it fails the test
        else:
            elseavailability = False
    
    # if the elseavailability test fails the overall availability fails
    if elseavailability == False:
        availability = False
        
    # if the elseavailability passes, overall availability is True 
    # then start inputting the numbers
    else:
        availability = True
        for i in range(length):
            puzzle[row][col+i] = word[i]
            
    return availability



################## WRITE YOUR CODE ABOVE THIS LINE ###################



######################################################################
################# DO NOT CHANGE CODE INSIDE THIS BOX #################
######################################################################
for words in wordList:                                               #
    print(willWordFitH(myPuzz, words[0], words[1], words[2]))        #
                                                                     #
for rowList in myPuzz:                                               #
    for char in rowList:                                             #
        print(char+" ", end="")                                      #
    print()                                                          #
######################################################################

Question 2 Finding Horizontally

Introduction

In problem 2, you will write a function, findHorizontally(), which will determine whether or not a given word exists in a word search puzzle horizontally.

In word search puzzles, words can be written towards the right (left-to-right) or towards the left (right-to-left). For example, “CAT” appears at [0][0] written towards the right, while “ZEBRA” appears at [2][4] written towards the left:

[[**"C", "A", "T"**, "X", "R"],
 ["D", "T", "E", "Z", "L"],
 [**"A", "R", "B", "E", "Z"**],
 ["X", "Q", "E", "A", "U"],
 ["J", "S", "O", "K", "W"]]

Your function must look through each row for the word. If it is found, it must return the row and column at which the word starts and the direction in which the word is written.

Details for function findHorizontally()

Parameter Variables (Input)

• puzzle (list): The word search puzzle (a table—a list of lists—with the same number of rows as columns).
• word (string): The word to find written horizontally in the puzzle (all words will be uppercase).

Processing

• For each row in puzzle:
• If you find word written towards the right (left-to-right, like “CAT” in the example above), stop searching.
• If you find word written towards the left (right-to-left, like “ZEBRA” in the example above), stop searching.
• Otherwise, move to the next row in puzzle.

Return Value (Output)

• Return:
• If word is found, return a dictionary containing the row and column indexes at which the word starts and the direction in which it is written.
• If the following examples, DIR_R and DIR_L are integer constants the starter code defines for you. They represent directions: DIR_R means the word is written towards the right (left-to-right), while DIR_L means the word is written towards the left (right-to-left).
• For example:
• If “CAT” is found as in the example above, the dictionary returned would be:
• {“row”: 0, “column”: 0, “direction”: DIR_R}
• If “ZEBRA” is found as in the example above, the dictionary returned would be:
• {“row”: 2, “column”: 4, “direction”: DIR_L}
• If word is NOT found, return None, the special Python type used to represent the absence of a value.

Sample Input/Output

Puzzle List

 [["Q", "W", "E", "R"], 
  ["W", "O", "R", "D"],
  ["Z", "X", "C", "V"],
  ["V", "B", "N", "M"]]	

Notes

Call: findHorizontally(myPuzz, “WORD”)

Return: {“row”: 1, “column”: 0, “direction”: DIR_R}

Puzzle List

 [["Q", "W", "E", "R", "T"], 
  ["W", "O", "R", "D", "K"],
  ["S", "C", "N", "D", "A"],
  ["E", "L", "O", "V", "R"],
  ["V", "B", "N", "M", "S"]]	

Notes

Call: findHorizontally(myPuzz, “VOLE”)

Return: {“row”: 3, “column”: 3, “direction”: DIR_L}

Puzzle List

 [["Q", "W", "E",], 
  ["W", "O", "R"],
  ["V", "B", "N"]]	

Notes

Call: findHorizontally(myPuzz, “DOG”)

Return: None

My Solution also hosted here

#########################
# CSCI 1105
# Assignment 4, Problem 2
# @author: Fleming

############################################
#### DO NOT CHANGE CODE INSIDE THIS BOX ####
############################################
# Direction constants                      #
DIR_U = 0                                  #
DIR_UR = 1                                 #
DIR_R = 2                                  #
DIR_DR = 3                                 #
DIR_D = 4                                  #
DIR_DL = 5                                 #
DIR_L = 6                                  #
DIR_UL = 7                                 #
                                           #
# Create the puzzle table                  #
myPuzz = [input()]                         #
myPuzz[0] = myPuzz[0].split(" ")           #
for i in range(1,len(myPuzz[0])):          #
    myPuzz.append(input())                 #
    myPuzz[-1] = myPuzz[-1].split(" ")     #
                                           #
# Get the words to test                    #
wordList = []                              #
wordRead = input()                         #
while wordRead != "STOP!":                 #
    wordList.append(wordRead)              #
    wordRead = input()                     #
############################################



################## WRITE YOUR CODE AFTER THIS LINE ###################

"""
It seems that for the direction for which if the word is found, the 
number 2 and 6 is used as opposed to DIR_L and DIR_R

FYI

"""

# the function that took forever to finish lies below
def findHorizontally(puzzle, word):
    
   # just a placeholder for if statement (doesn't matter in the end)
   availability = False
    
   # made a variable for number of rows and columns along with length of the word 
   row = len(puzzle)
   col = len(puzzle[0])
   length = len(word)
    
   # created an empty dictionary for the word to be added if found
   dictionary = {}
    
   # made a for loop that searches for the word horizontally to the right
   # first for loop goes through every row to find the word
   for i in range(row):
        
        # second for loop goes through zeroth column to the column where beginning 
        # of the word can appear which is col-length and the increment is one
        for j in range(0, col-length, 1):
            
            # created a test variable that tests if all letter of the word is 
            # found which is used in the if statement below
            test = []
            
            # used an if statement to find the word
            # if the first letter of the word is found somewhere in the puzzle
            if puzzle[i][j] == word[0]:
                
                # used for loop to see if the letters to the right of that spot 
                # also matches with the word 
                for k in range(length):
                    
                    # it tests each one and if it matches, it puts yeah into 
                    # the list called "test" or "nah"
                    if puzzle[i][j+k] == word[k]:
                        test.append("yeah")
                    else:
                        test.append("nah")
                
                # if a single "nah" is found in the list called test, 
                # availability becomes false but otherwise it adds the location
                # and the direction into the dictionary
                if "nah" in test:
                    availability = False
                else: 
                    dictionary["row"] = i
                    dictionary["column"] = j
                    
                    # I do not know why the mimir takes 2 as opposed to "DIR_R" but
                    # I guess it happened as the prof made an adjustment
                    dictionary["direction"] = 2
            
            # cleared the list that was used to test all letter for upcoming 
            # other test (just in case)
            test.clear()
    
   # this test does the confirmation if the word can be found horizontally 
   # but in opposite way for loop to test each row
   for i in range(row):
        
       # for loop to test each column (parameter adjusted to weird counting 
       # that python uses 
       with an increment of -1 since going opposite way)
        for j in range(col-1, length-2, -1):
            
            # list to test the letters
            test = []
            
            # same as the previous test to see if the first letter of the word is 
            # found in the puzzle
            if puzzle[i][j] == word[0]:
                
                # if the first letter is found it goes through the opposite way to 
                # test the remaining letter using for loop
                for k in range(length):
                    
                    # the j-k goes backward to test the letters and adds the "yeah"
                    # or "nah" to the list as appropriate
                    if puzzle[i][j-k] == word[k]:
                        test.append("yeah")
                    else:
                        test.append("nah")
                
                # if single "nah" is found in the test, availability is False or 
                # if it finds it, the location and the direction of 6 is added
                if "nah" in test:
                    availability = False
                else: 
                    dictionary["row"] = i
                    dictionary["column"] = j
                    dictionary["direction"] = 6
            
            # clears the list used for testing (just in case again)
            test.clear()    
    
    # if both horizontal test gives no result and the dictionary remains empty,
    # the final result of None is given, otherwise the dictionary containing 
    # the location and the direction is printed
    if dictionary == {}:
        final = "None"
    else:
        final = dictionary
    return(final)


################## WRITE YOUR CODE ABOVE THIS LINE ###################



##################################################
####### DO NOT CHANGE CODE INSIDE THIS BOX #######
##################################################
for word in wordList:                            #
    print(word, findHorizontally(myPuzz, word))  #
                                                 #
for rowList in myPuzz:                           #
    for char in rowList:                         #
        print(char+" ", end="")                  #
    print()                                      #
##################################################

Question 3 Finding Vertically

Introduction

In problem 3, you will write a function, findVertically(), which will determine whether or not a given word exists in a word search puzzle vertically.

In word search puzzles, words can be written upwards or downwards. For example, “BEAK” appears at [1][3] written downwards, while “BET” appears at [2][2] written upwards:

[["C", "A", **"T"**, "X", "R"],
 ["D", "T", **"E"**, **"B"**, "L"],
 ["A", "R", **"B"**, **"E"**, "Z"],
 ["X", "Q", "E", **"A"**, "U"],
 ["J", "S", "O", **"K"**, "W"]]

Your function must look through each column for the word. If it is found, it must return the row and column at which the word starts and the direction in which the word is written.

Details for function findVertically()

Parameter Variables (Input)

• puzzle (list): The word search puzzle (a table—a list of lists—with the same number of rows as columns).
• word (string): The word to find written vertically in the puzzle (all words will be uppercase).

Processing

• For each column in puzzle:
• If you find word written downwards (top-to-bottom, like “BEAK” is in the example above), stop searching.
• If you find word written uowards (bottom-to-top, like “BET” is in the example above), stop searching.
• Otherwise, move to the next column in puzzle.

Return Value (Output)

• Return:
• If word is found, return a dictionary containing the row and column indexes at which the word starts and the direction in which it is written.
• If the following examples, DIR_D and DIR_U are integer constants the starter code defines for you. They represent directions: DIR_D means the word is written downwards (top-to-bottom), while DIR_U means the word is written upwards (bottom-to-top).
• For example:
• If “BEAK” is found as in the example above, the dictionary returned would be:
• {“row”: 1, “column”: 3, “direction”: DIR_D}
• If “BET” is found as in the example above, the dictionary returned would be:
• {“row”: 2, “column”: 2, “direction”: DIR_U}
• If word is NOT found, return None, the special Python type used to represent the absence of a value.

Sample Input/Output

Puzzle List

 [["Q", **"W"**, "E", "R"], 
  ["W", **"O"**, "R", "D"],
  ["Z", **"R"**, "C", "V"],
  ["V", **"N"**, "N", "M"]]	

Notes

Call: findVertically(myPuzz, “WORN”)

Return: {“row”: 0, “column”: 1, “direction”: DIR_D}

Puzzle List

 [["Q", "W", "E", "R", **"E"**], 
  ["W", "O", "R", "D", **"K"**],
  ["S", "C", "N", "D", **"A"**],
  ["E", "L", "O", "V", **"R"**],
  ["V", "B", "N", "M", "S"]]	

Notes

Call: findertically(myPuzz, “RAKE”)

Return: {“row”: 3, “column”: 4, “direction”: DIR_U}

Puzzle List

 [["Q", "W", "E",], 
  ["W", "O", "R"],
  ["V", "B", "N"]]	

Notes

Call: findVertically(myPuzz, “DOG”)

Return: None

My Solution also hosted here

#########################
# CSCI 1105
# Assignment 4, Problem 3
# @author: ???

############################################
#### DO NOT CHANGE CODE INSIDE THIS BOX ####
############################################
# Direction constants                      #
DIR_U = 0                                  #
DIR_UR = 1                                 #
DIR_R = 2                                  #
DIR_DR = 3                                 #
DIR_D = 4                                  #
DIR_DL = 5                                 #
DIR_L = 6                                  #
DIR_UL = 7                                 #
                                           #
# Create the puzzle table                  #
myPuzz = [input()]                         #
myPuzz[0] = myPuzz[0].split(" ")           #
for i in range(1,len(myPuzz[0])):          #
    myPuzz.append(input())                 #
    myPuzz[-1] = myPuzz[-1].split(" ")     #
                                           #
# Get the words to test                    #
wordList = []                              #
wordRead = input()                         #
while wordRead != "STOP!":                 #
    wordList.append(wordRead)              #
    wordRead = input()                     #
############################################



################## WRITE YOUR CODE AFTER THIS LINE ###################

"""
It seems that for the direction for which if the word is found, the number
4 and 0 is used as opposed to DIR_D and DIR_U

FYI

"""


# code copied from question 2 to save my fingers
# function that searches for the word vertically
def findVertically(puzzle, word):
    
   # placeholder variable for testing
   availability = False
    
   # created a variable for number of rows and columns along with the 
   # length of the word
   row = len(puzzle)
   col = len(puzzle[0])
   length = len(word)
    
   # created an empty dictionary for to be used when the word is found
   # in the puzzle
   dictionary = {}
    
   # created a for loop to find the word vertically going down with proper
   # parameter with the increment of 1 for going down for each row
    for i in range(0, row-length, 1):
        
        # created a for loop to find the word for each column
        for j in range(col):
            
            # created a list for testing purposes
            test = []
            
            # if the first letter of the word is found in the puzzle 
            # it goes through this if statement
            if puzzle[i][j] == word[0]:
                
                # since it found the matching first letter of the word, 
                # it goes through for loop to see if the remaining letters match
                for k in range(length):
                    
                    # and it puts the result of "yeah" or "nah" in the 
                    # list called test
                    if puzzle[i+k][j] == word[k]:
                        test.append("yeah")
                    else:
                        test.append("nah")
                
                # if a single "nah" is found in the test, availability is 
                # False but if it doesn't the location and the direction of 4
                # is added to the dictionary
                if "nah" in test:
                    availability = False
                else: 
                    dictionary["row"] = i
                    dictionary["column"] = j
                    dictionary["direction"] = 4
            
            # clears the list that was used for testing (just in case)
            test.clear()
    
    # second test to find the word vertically but going up this time with the 
    # right parameter (due to weird counting that python uses with an increment
    # of -1 for going up)        
    for i in range(row-1, length-2, -1):
        
        # second for loop to test each column
        for j in range(col):
            
            # created a list for testing purposes
            test = []
            
            # if the first letter of the word is found in the puzzle, it 
            # goes through this if statement
            if puzzle[i][j] == word[0]:
                
                # since the first letter of the word is found, it goes 
                # through a for loop to test the remaining letter
                for k in range(length):
                    
                    # if the letter matches, it gives "yeah" or "nah" and 
                    # puts it in the list
                    if puzzle[i-k][j] == word[k]:
                        test.append("yeah")
                    else:
                        test.append("nah")
                
                # if single "nah" is found in the test, the availability 
                # is False but if it doesn't the location and the direction
                # is added to the dictionary
                if "nah" in test:
                    availability = False
                else: 
                    dictionary["row"] = i
                    dictionary["column"] = j
                    dictionary["direction"] = 0
            
            # clears the list that used to test (just in case again for 
            # the last time)
            test.clear()    
    
    # if the dictionary remains empty due to availability being False 
    # for both test, the final is none or otherwise it gives the dictionary 
    # containing the location and the direcion      
    if dictionary == {}:
        final = "None"
    else:
        final = dictionary
    return(final)


################## WRITE YOUR CODE ABOVE THIS LINE ###################



##################################################
####### DO NOT CHANGE CODE INSIDE THIS BOX #######
##################################################
for word in wordList:                            #
    print(word, findVertically(myPuzz, word))    #
                                                 #
for rowList in myPuzz:                           #
    for char in rowList:                         #
        print(char+" ", end="")                  #
    print()                                      #
##################################################