# Assignment 2

Type: Group Assignment

## Prologue

This is a group assignment. Remember that you should always be working with your partner. You may NOT divide up the work and complete the parts independently. All work you submit must be fully authored by both you and your partner.

## Part 1: Word Search Puzzles

### Introduction

A word search puzzle is a game that consists of a list of words and a large table of characters, and the objective is to find every given word in the table. The challenge is that the words may appear horizontally, vertically, or diagonally; similarly, they may appear backwards or forwards. Thus, there are eight possible orientations of a word in the table. To make them especially hard to find, any unused space in the table is filled with random characters.

Below is an example of a word search puzzle.

List of Words:

 COMPUTER SCIENCE TITUS KLINGE

Table of Letters

 G M H X B Y F C T C O M P U T E R P U O M N E Z R P J F J X U A M F Z M X S T T U V Z Z V K Z F A Y Z P X Q J Y T K O T W H M Z G V K B A E O Y S M O K L M Y F N Z K R D I G F S V H B B Q V I A Y B N U V Q N L U F A Y R H R N G N U H M M P Z D S F D U E I S N R X C G F T I T U S G F E V T A Q C F P O Y E P W M M R I J Z U N R Y R N D D X V Z Y T Q I Y U D N C L H L L R Z N U N Z Q S Z L B X B T B F V U K B I V S C I E N C E B Z

### Word Search Algorithm

Your task for this part is to describe an algorithm that, when given an arbitrary word search puzzle, will help me successfully find the locations of all the words. Since you do not know much Python yet, your algorithm will be written in English prose and I will execute your algorithm with pencil and paper. The challenge of the problem is that you must assume that I have very limited memory, but I have access to a lot of paper and a pencil.

You may assume that I can do the following things reliably:

1. Understand the English alphabet,
2. Draw symbols such as alphabetic characters or place special markings on characters (e.g. circling, drawing a line through, or placing a dot above a character or word),
3. Use an eraser extremely precisely (e.g. remove a marking from a character),
4. Remember a few words or characters in my head, but not more than three,
5. Recognize a word or character I am thinking about, and
6. Use my fingers to keep track of where I am on the paper and understand concepts such as left, right, up, down, etc.

You may also assume that I know how to copy the list of words and the entire table of characters onto paper so that I can mark on it in future instructions.

Given your algorithm, I should be able to solve any word search puzzle (with any number of words and a board of any size). After executing your algorithm, I should be holding a piece of paper that includes the original table of characters with each of the hidden words circled.

### Hints

1. Start by solving the above word search puzzle yourself and take note of what you are doing to solve it. Now try to formalize that strategy so that it can be used to solve any search problem.
2. Since your algorithm will likely need to repeatedly do similar operations, consider decomposing the problem into subroutines to save work. (e.g. a find_single_word that searches for a specific word I am currently thinking of)
3. You can name certain parts of the puzzle or marks on the paper using a variable. For example, naming something cur_letter or cur_word might be helpful.
4. You can make use of repetition and repeatedly do operations for each element in a set. (e.g. using a pencil mark to keep track of your place in the row, execute [subroutine] on each character in the row)

### Template File

Start by downloading the word_search.txt template file. Put the names of all of your partners at the top of the file, and write your algorithm at the bottom of the file.

## Part 2: Temperature Converter

Write a Python program named convert.py that converts temperatures from Fahrenheit to Celsius. When you run the program in Thonny, it should prompt the user for a number, and then print the result. Below is an example of what the interaction might look like:

Enter a temperature in Fahrenheit: 70.0
The temperature in Celsius is: 21.11111111111111


Hint: Use the chaos.py code from the Getting Started with Python lab as a template to get started. There are also several examples from the readings that could be helpful.

## How to Turn in Your Code

1. Once you are finished with the assignment, you should go to https://codepost.io and log into your account.
2. Go to the CS 65 course.
4. After you submit the assignment, you should be able to reopen it and see a Partners tab at the top of the submission page. Send the link to your partner and have them open it while logged in with their account.
5. That’s it! You’ve just submitted your assignment.