Milking Cows

This is the problem specification of the Milking Cows Programming Problem From USACO.

Milking Cows

Three farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time 1000. The second farmer begins at time 700 and ends at time 1200. The third farmer begins at time 1500 and ends at time 2100. The longest continuous time during which at least one farmer was milking a cow was 900 seconds (from 300 to 1200). The longest time no milking was done, between the beginning and the ending of all milking, was 300 seconds (1500 minus 1200).

Your job is to write a program that will examine a list of beginning and ending times for N (1 <= N <= 5000) farmers milking N cows and compute (in seconds):

• The longest time interval at least one cow was milked.
• The longest time interval (after milking starts) during which no cows were being milked.

PROGRAM NAME: milk2

INPUT FORMAT

Line 1:	The single integer
Lines 2..N+1:	Two non-negative integers less than 1000000, the starting and ending time in seconds after 0500

SAMPLE INPUT (file milk2.in)

3
300 1000
700 1200
1500 2100

OUTPUT FORMAT

A single line with two integers that represent the longest continuous time of milking and the longest idle time.

SAMPLE OUTPUT (file milk2.out)

900 300

You can view my solution (source code) to this problem at PlanetSourceCode.com

When the Siants Go Marching In By Greg Howlett and Andi Leftwich

Greg Howlett - Piano
Andi Leftwich - Fiddle

This is an excerpt from Greg Howlett's "Live in Charleston" DVD.

Click here for Greg Howlett's Explanation of "When the Saints".


Enjoy!

Recursion

This is Assignment #3 of Stanford's CS106B class last Spring Quarter 2011.

It consists of four problems and 2 warm-up problems.
(I only did 3 of the 4 problems because the last one was fairly difficult). Click here here to download the assignment handout.

The link for downloads below might not work. Please use this link to download all solutions to the problems.

Warm-up problem 0a. Binary encoding

Write a recursive function GenerateBinaryCode(nBits) that generates the bit patterns
for the standard binary representation of all integers that can be represented using the
specified number of bits. For example, calling GenerateBinaryCode(3) should produce
the following output:

000
001
010
011
100
101
110
111

Download my solution for Warm-up problem 0a here.
Warm-up problem 0b. Subset sum

The subset sum problem is an important and classic problem in computer theory. Given  a set of integers and a target number, your goal is to find a subset of those numbers that sum to that target number. For example, given the numbers {3, 7, 1, 8, -3} and the target sum 4, the subset {3, 1} sums to 4. On the other hand, if the target value were 2, the result is false since there is no subset that sums to 2.

 Download my solution for Warm-up problem 0b here.
Problem 1. Karel goes home

Your job in this problem is to write a recursive function

int CountPaths(int street, int avenue)

that returns the number of paths Karel could take back to the origin from the specified starting position, subject to the condition that Karel doesn’t want to take any  unnecessary steps and can therefore only move west or south (left or down in the diagram).

 Download my solution for problem 1 here.
 Problem 2. Balancing parentheses

Write a function

bool IsBalanced(string exp);

that takes a string consisting only of parentheses, brackets, and curly braces and returns true or false according to whether that expression has properly balanced operators. (Your function should operate recursively.)

Download my solution for problem 2  here.

Problem 3. Cell phone mind-reading

Write a function

void ListCompletions(string digits, Lexicon & lex);

that prints all words from the lexicon that can be formed by extending the given digit sequence. For example, calling ListCompletions("72547", english) should generate the following sample run:

palisade
palisaded
palisades
palisading
palish
rakis
rakish
rakishly
rakishness
sakis

 Download my solution for problem 3  here.

Problem 4. Stock Cutting

You are charged with buying the plumbing pipes for a construction project. Your
foreman gives you a list of the varying lengths of pipe needed. Home Depot sells stock
pipe in one fixed length. You can divide each stock pipe in any way needed. Your job is
to figure out the minimum number of stock pipes required to satisfy the list of requests,
thereby saving money and minimizing waste.

Your job is to write a recursive function

int CutStock(Vector<int> & requests, int stockLength);


that takes two arguments—a vector of the lengths needed and the length of stock pipe
that Home Depot sells—and returns the minimum number of stock pipes needed to
service all requests in the vector. For example, if the vector contains [ 4, 3, 4, 1, 7, 8 ]
and the stock pipe length is 10, you can purchase three stock pipes and divide them as
follows:

Pipe 1: 4, 4, 1
Pipe 2: 3, 7
Pipe 3: 8

Doing so leaves you with two small remnants left over. There are other possible
arrangements that also fit into three stock pipes, but it cannot be done with fewer.

Download my solution for problem 4 here or  here.
Happy coding!!!