CIS 199

Project 3: Writing Methods

Due: Feb 11, 5:00 P.M.

This project is designed to give you some experience implementing your own methods in Ruby.

There are three projects. For each one, you need to download a Ruby program that I have written. Each program has "stubs" for methods that need to be implemented to get the program to generate the correct output. Your job is to fill in the body of each method according to the specifications below.

Each program is written so that you can either run it interactively with irb or as a stand-alone command line program. For example, the first project is to implement methods named read_polygon and segment_length in a program named perimeter.rb. If you want to test the segment_length method with irb:

% irb
>> load "perimeter.rb"
>> segment_length([0,0],[3,4])
=> 5.0

and If you run it from the command line:

% perimeter.rb polygon.txt

Computing the Perimeter of a Polygon

Download the program named perimeter.rb and the data file named polygon.txt.

The data file has a set of lines, each with two numbers on it. The numbers are the x and y coordinates of the vertices of a polygon. Your first job is to fill in the body of the method that reads the data file. Return an array of points, where each point is represented by an array of two numbers, corresponding to the x and y coordinates of the point.

Your second job is to implement the method that computes the length of a line segment. The two parameters to this method are points p1 and p2. Use Pythagoras' equation to compute the length of the segment between p1 and p2:

When both methods are implemented use the program to compute the perimeter of the figure with coordinates in the file polygon.txt:

% perimeter.rb polygon.txt
15.0, 30.0 to 18.0, 20.0
18.0, 20.0 to 29.0, 20.0
29.0, 20.0 to 21.0, 13.0
21.0, 13.0 to 24.0, 3.0
24.0, 3.0 to 15.0, 9.0
15.0, 9.0 to 6.0, 3.0
6.0, 3.0 to 9.0, 13.0
9.0, 13.0 to 1.0, 20.0
1.0, 20.0 to 12.0, 20.0
perimeter: 106.654825313895

Simulated Evolution

Download the program named evolve.rb. When this program is run from the command line, it applies a series of mutations to a string representing a strand of DNA and prints the final string. Your job is to fill in the code for two methods in the program.

The first method is named mutate. The parameters to the method are the string of DNA, and a location to change. You just need to pick a random DNA letter and store it in the specified location. You can use the code you wrote for the last project if you wish.

The second method implements a type of mutation called a "transposition", where a random chunk of DNA is cut out of the strand and moved to a new location. For example, if the strand is

AAACCCTTTAAA

a transposition might move the 4-letter string starting at position 2 ("ACCC" -- remember that in programs the first position is 0, not 1) so the new strand is

AATTTACCCAAA

Before you dig in to write this method explore the String class some more using irb, and also play around with objects called Ranges. A Range is written as a pair of integers separated by two dots, e.g. 1..3. You can use a Range to select items from a string. For example:

>> s= "Hello, World"
=> "Hello, World"
>> s[1..3]
=> "ell"
>> s[4..7]
=> "o, W"

You can also use a Range on the left side of an assignment to replace a substring:

>> s[0..4]
=> "Hello"
>> s[0..4] = "Goodbye"
=> "Goodbye"
>> s
=> "Goodbye, World"

This gives us a way to splice out a substring for a transposition, e.g. to remove characters 4..6 from a string replace them by the empty string:

>> s[4..6] = ""
=> ""
>> s
=> "Good, World"

To insert a string into s, use the insert method:

>> s.insert(4," grief")
=> "Good grief, World"

The first parameter of the insert method is the location of the insertion, and the second is the string to insert.

When you get both methods working you can run the program from the command line to simulate the evolution of a simple gene:

% evolve.rb 50
AAAAAAAAAAAAAAAACAAGCCAACAACAAAAAATGCAGTAAAAAAGAAAAAAAAGACAAGTAGAAAATGTGAAAAAAAAAAACAAAAATAACAAAAGA

Since this program produces a random output your program won't print this exact same output. Part of your writeup for this project should be a description of how you verified the mutate and transpose methods are working as you expect they should.

Password Cracker

Unix systems have a file named /etc/password to store user names and passwords. Each line in the password file looks like this:

fredf:shLJLlCugycmg:2:2:Fred Flintstone:/home/Users/fredf:/bin/tcsh

There are seven fields, separated by a colon (:). The fields that are important for this project are the username in the first field (fredf in this example), the user's encrypted password in the second field (shLJLlCugycmg in this example), and the user's full name in the fifth field (Fred Flintstone).

Ruby's String class has a method named crypt that will encrypt a string: call s.crypt(k) to create an encrypted copy of s using key k. For Unix password files the key is defined by the system administrator and kept secret.

The program for this project is named cracker.rb. When run from the command line, it takes the name of a password file as a parameter. It then checks each password to make sure it is secure. For this simple program, a secure password is defined to be one that is six letters or longer and is not a plain English word. Our hypothetical system adminstrator wants to make sure Fred hasn't chosen "bedrock" as his password because it's too easy to crack.

When the program starts, it reads a wordlist, a file containing over 58,000 words of six or more letters commonly found in crossword puzzles and other word games. It then saves the encrypted form of each word in a Hash object so they are easy to look up. As the program reads the password file, it extracts the encrypted password field from the line, and then it checks the hash table to see if that string is a key in the hash: if it is, that means the user has used a word from the wordlist as their password, and the program should print a message.

Here are the details:

• Download the program cracker.rb, a sample password file, and the wordlist.
• Implement the encrypt method, which takes a name of the word list file as a parameter. Encrypt each word by calling the crypt method, using the key "sh" (which is the same key used to make the password file). Don't forget to strip the end of line character from the line, i.e. if x is a line from the file, call x.chomp.crypt("sh") to make the encrypted string. Save all the encrypted words in a Hash object, and return the hash as the value of the method.
• Implement a method name make_entry. The parameter to this method is a line from the password file. The method should create a hash object with the important fields for this application. For example, if the example line for Fred Flintstone is passed to this method, it should return

  { :username => "fredf", :passwd => "shLJLlCugycmg", :name => "Fred Flintstone" }

• The main routine, which I've written, will read lines from the input file, call your make_entry method, and then look up the encrypted password in the hash of encrypted words from the wordlist.

To run the program from the command line:

% cracker.rb password

One of the users in this file has an insecure password.

What to Turn In

Write a short description of each of your programs. All you need is a paragrpah or two about what you did. If you think there is anything interesting or unusual, or something you want me to comment on, describe it in this document. Please use one of the following formats:

• plain text -- put ".txt" at the end of the file name
• rich text -- put ".rtf" at the end of the file name
• Microsoft Word -- put ".doc" at the end of the file name
• Adobe PDF -- put ".pdf" end of the file name

Send e-mail to conery@cs.uoregon.edu with separate attachments for the three programs and the documentation.