CPTR 124 Fundamentals of Programming

In this lab you will use two-dimensional lists to implement a word search puzzle.
  1. As usual, you are invited to work with a partner.

  2. Background. A word search puzzle consists of words hidden in a rectangular block of random characters. Write a Python program to produce such a puzzle.

  3. Implementation details. Your program should read the list of words from a text file. The name of the file is specified on the command line as the programs we wrote in class. The file should contain ten words, each on its own line. No word will contain more than 15 letters.

    Place the words in a 20 x 20 block filled with random letters. Provide the puzzle, the list of words to find, and an answer key.

    Your program should place the words randomly in different several ways:

    • It should determine the position of each word randomly.
    • It should randomly decide whether to orient a word horizontally, vertically, or diagonally.
    • It should randomly choose whether to order the letters forwards (left-to-right or top-to-bottom) or backwards (right-to-left or bottom-to-top).

    You can simplify this process by computing a random row, column starting location for the first letter in the word and then computing a random row change, column change vector. This vector then can take care of both the orientation and forwards/backwards direction.

    Using randomness in this way means you should not determine ahead of time how many words are printed backwards or diagonally, etc. Since the placement is done entirely at random, some puzzles, although rare, may contain no diagonally-placed words, or no backwards words; however, multiple runs of your program over the same list of words must clearly demonstrate that your program satisfies all the requirements listed in this specification.

    Another use of randomness is in the selection of letters to fill in around the words to hide; they too should be chosen at random and not predetermined.

    Your program should be able to handle correctly words that overlap, such as: 

                       R
                 O
	 S T A T I C
     D       C
       E   E
         V
           I
             C
               E

    Notice how DEVICE and VECTOR overlap at V, and STATIC and VECTOR overlap at T. Such overlap is not common via purely random placement, so you may need to run your programs multiple times to demonstrate this capability.

    The words in the file may may consist of both upper- and lowercase alphabetic letters, but your program should capitalize all the letters in a word before using them in the puzzle.

  4. Output. The program should produce the following output, in the following order:

    1. the puzzle
    2. the list of words to find
    3. The answer key

      Here is the output of a sample run. 

          P M N R B L H R K X R J F T K B P F W C 
    I E X L B U M W E P U V M U Q R N L T B 
    B P M R K L P E C C N T M D O D F Q W G 
    X K T H A F X B O X U T M G H K S E B E 
    C E Z X Y M B R M M G R R L L K M K Y T 
    O R Z Z Q D L E P G H A S R F W R P K E 
    Z D X R T F Y L U V M I G I P E T O W Z 
    O O W E D O B I T J X M N A V J S D W C 
    X U R R Y X T H E L E P H M Z E W B S N 
    A N G R U P C W R R X P L T E V R Y I E 
    Z W L U Y I M P E E R M B E I U A H P X 
    I I M E M O R Y B L L Y T X J R T R T U 
    U E G L D O O E Y I D G C J H G O D J X 
    G C D B U R K J Q P A E Y C P C V G R F 
    Q B X H X E V H U M J G V W E R M R L T 
    Q S R P L X Z L H O L K Y S M D P S Y A 
    E V C O Y B O J M C H K S F E X A S L E 
    Z N E M J O G W F Q N O V U X I L Z D M 
    E V I T A R E T I W R K N H D V X X A I 
    Z G S L S M L A N O I T I D N O C T Z F 
    
    COMPUTER
    ALGORITHM
    WHILE
    PROGRAM
    COMPILER
    PROCESSOR
    MEMORY
    ITERATIVE
    RECURSIVE
    CONDITIONAL
    
                  R                 P       
                    E             R         
                    C C         O           
                    O   U     G             
                    M     R R               
                  E P     A S               
                  L U   M     I             
                  I T     M     V           
                  H E       H     E         
                  W R R       T             
                      E         I       P   
        M E M O R Y   L           R   R     
                      I             O       
                      P           C   G     
                      M         E       L   
                      O       S           A 
                      C     S               
                          O                 
    E V I T A R E T I   R                   
                L A N O I T I D N O C

    Check out

    Your finished program will be evaluated for correctness and compliance. When approved, you should submit your Python source file(s) to http://eclass.e.southern.edu. Be sure your name (and your partner's name, if necessary) are included in comments at the top of each source file.