1. NAME THAT NUMBER Among the large Wisconsin cattle ranchers, it is customary to brand cows with serial numbers to please the Accounting Department. The cow hands don't appreciate the advantage of this filing system, though, and wish to call the members of their herd by a sonorous name rather than saying, "C'mon, #4734, get along." Help them out by writing a program that will translate the brand serial number of a cow into possible names uniquely associated with that serial number. Since the cow hands all have cellular saddle phones these days, use the standard Touch-Tone(R) telephone keypad mapping to get from numbers to letters (except for "Q" and "Z"): 2: A,B,C 5: J,K,L 8: T,U,V 3: D,E,F 6: M,N,O 9: W,X,Y 4: G,H,I 7: P,R,S Acceptable names for cattle are provided to you in a file named "PROB1.DAT", which contains a list of fewer than 5,000 acceptable cattle names (first letter capitalized, of course). Take a cow's brand number and report which of all the possible words to which that number maps are in the given dictionary. For instance, the brand number 4734 produces all the following names: Gpdg Gpei Gpdh . Gpdi . Gpeg . Gpeh Isfi As it happens, the only one of these 81 names that is in the list of valid names is "Greg". PART A ******************************************************************* Write a program that repeatedly asks for the brand number of a cow and prints all the valid names that can be generated from that brand number; print "No matching names found" if no valid words match. Serial numbers can be as many as a dozen digits long. End the program when the serial number `0' is entered. *** EXAMPLE RUN *** Enter number to be translated: 4267 Possible names are: Hans Enter number to be translated: 0 PART B ******************************************************************* They're moving towards standardizing the number of digits in the brand and need to choose an appropriate number of digits. The sadistic folks in the Branding Department have their fun by making life hard for the cow hands. They want to choose a brand length with only a few brand numbers from which the cow hands could make names. They will give you a brand length; your program should report the number of brands with that number of digits which do generate a valid name and the total number of brands. Repeatedly ask for the number of digits and report the result until the number 0 is entered; then exit. Enter # digits: 2 There are 14 usable numbers out of 100 Enter # digits: 0 Problem 2a) SUPERPRIME RIB Butchering Farmer John's cows always yields the best prime rib. You can tell prime ribs by looking at the digits lovingly stamped across them, one by one, by FJ and the USDA. Farmer John ensures that a purchaser of his prime ribs gets really prime ribs because when sliced from the right, the numbers on the ribs continue to stay prime right down to the last rib, e.g.: 7 3 3 1 The set of ribs 7331 is prime; the three ribs 733 are prime; the two ribs 73 are prime, and, of course, the last rib, 7, is prime. The number 7331 is called a superprime of length 4. For the purposes of prime ribs, the number 1 (by itself) is not prime. Write a program that accepts a number of ribs (1..8) and then prints all the superprimes of that length. Exit if the number of ribs entered is 0. Example: Number of digits: 4 2333 2339 2393 2399 2579 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393 ---------------------------------------------------------------------- Problem 2b) MOTHER'S MILK Farmer John has three milking buckets of capacity A, B, and C quarts. Each of the numbers A, B, and C is an integer from 1 through 15, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out. Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty. Sample Runs: Enter A B C: 8 9 10 Answer: 1 2 8 9 10 Enter A B C: 2 5 10 Answer: 5 6 7 8 9 10 3a. HOME ON THE RANGE Farmer John grazes his cows on a large, square field N miles on a side (because, for some reason, his cows will only graze on precisely square land segments). Regrettably, the cows have ravaged some of the land (always in 1 mile square increments). FJ needs to map the remaining squares on which his cows can graze (in these larger squares, no 1x1 mile segments are ravaged). Your first job is to find any 4 x 4 mile grazing area in the supplied data. Your program must execute in less than 30 seconds. Your second job is to count up all the various remaining square grazing areas within the supplied dataset and report the number of square grazing areas (of all existing sizes) remaining. Of course, grazing areas may overlap for purposes of this report. Your program must run in under one minute for datasets up to 20 miles on a side. Be sure to read and understand the example below. Your third job is to create the same report as the second job -- but for datasets up to 250 miles on a side. Your program must run in under two minutes. The input data is found in files PROB3A.DAT, PROB3B.dat, ..., etc. Repeatedly ask for name of the input dataset so your program is easily tested. The first line is the number of miles on one side of the square. Subsequent lines give the map of the fields (0 means 'ravaged'; 1 means 'ready to eat'), one row at a time (no extra blanks in the input, just 1's and 0's and line separators). See 6x6 example below. Name your programs PROB3A.xxx, PROB3B.xxx, and PROB3C.xxx (where xxx is the appropriate filename extensioin). Input Dataset PROB3A.DAT: 6 101111 001111 111111 001111 101101 111001 Program Executions: Part 1: Input Dataset: PROB3A.DAT 4x4 is located at row 1 column 3 Part 2: Input Dataset: PROB3A.DAT Squares: 2:10 3:4 4:1 Part 3: Input Dataset: PROB3A.DAT Squares: 2:10 3:4 4:1 [executes very quickly] 3b. AMERICAN HERITAGE Farmer John takes the heritage of his cows very seriously. He is not, however, a truly fine bookkeeper. He keeps his cow geneaologies as binary trees and, instead of writing them in graphic form, he records them in the more linear 'tree in-order' and 'tree pre-order' notations. Your job is to create the 'tree post-order' notation of a cow's heritage after being given the in-order and pre-order notations. Each cow name is encoded as a unique letter. (You may already know that you can reconstruct a tree from any two of the ordered traversals.) Name your program PROB3B.xxx (where xxx is the appropriate filename extension). Given this tree for testing, C / \ / \ B G / \ / A D H / \ E F here is the example program run: In-order: ABEDFCHG <-- you type in this Pre-order: CBADEFGH <-- you type in this Post-order: AEFDBHGC 4. CALF FLAC It is said that if you give an infinite number of cows an infinite number of heavy-duty laptops (with very large keys), that they will ultimately produce all the world's great palindromes. Your job will be to detect these bovine beauties. Ignore punctuation, whitespace, and case when testing for palindromes, but keep these extra characters around so that you can print them out as the answer. Part 1: Find any largest palindrome in a string of maximum length 255 characters. Your program should loop repeatedly asking for a filename which contains the input sequence. Print both the palindrome and its length. Part 2: Find any largest palindrome in a string of unlimited length (by unlimited length, we mean more than 1 million characters). The largest palindrome is guaranteed to be at most 10,000 characters long before whitespace and punctuation are removed. Name your solutions PROB4A.xxx and PROB4B.xxx. Of course, working solutions to Part 2 count as working solutions to Part 1. Sample Run: File: PROB4A.DAT Longest palindrome is of length 11: Madam, I'm Adam File PROB4A.DAT: Confucius say: Madam, I'm Adam. 5.WISCONSIN SQUARES It's spring in Wisconsin and time to move the yearling calves to the yearling pasture and last year's yearlings to the greener pastures of the north 40. Farmer John has five kinds of cows on his farm (abbreviations are shown in parentheses): Guernseys (A), Jerseys (B), Herefords (C), Black Angus (D), and Longhorns (E). These herds are arranged on the 16 acre pasture, acre for each small herd, on a 4 x 4 grid (labeled with rows and columns) like this: 1 2 3 4 +------- 1|A B A C 2|D C D E 3|B E B C 4|C A D E In the initial pasture layout, the herds total 3 A's, 3 B's, 4 C's, 3 D's, and 3 E's. This year's calves have one more D herd and one fewer C herd, for a total of 3 A's, 3 B's, 3 C's, 4 D's, and 3 E's. FJ is extremely careful in his placement of herds onto his pasture grid. This is because when herds of the same types of cows are too close together,they misbehave: they gather near the fence and smoke cigarettes and drink milk. Herds are too close together when they are on the same square or in any of the eight adjacent squares. Farmer John must move his old herd out of the field and his new herd into the field using his old brown Ford pickup truck, which holds one small herd at a time. He picks up a new herd, drives to a square in the yearling pasture, unloads the new herd, loads up the old herd, and drives the old herd to the north 40 where he unloads it. He repeats this operation 16 times and then drives to Zack's for low-fat yogurt treats and familiar wall decor. Help Farmer John. He must choose just exactly the correct order to replace the herds so that he never puts a new herd in a square currently occupied by the same type of herd or adjacent to a square occupied by the same type of herd. Of course, once the old cows are gone and the new cows are in place, he must be careful in the future to separate herds based on the new arrangement. Part 1: Find a way for Farmer John to move the yearlings to their new pasture. Print the 16 sequential herd-type/row/column movements that lead to a safe moving experience for the cows. Part 2: Calculate the total number of possible final arrangements for the 4x4 pasture and calculate the total number of ways those arrangements can be created. Your programs should never run for more than two minutes. If you solve either part, please notify the judges so they can verify the answers and reduce the total time to score this round. Very important hint for both parts: Farmer John knows from past experience that he must move a herd of D cows first.