* Quiz 1 sent 20021016
Write a subroutine, 'subst', which gets a string argument, $s. It
should search $s and replace any occurrences of "$1" with the current
value of $1, any occurrences of "$2" with the current value of $2, and
so on.
For example, if $1, $2, and $3 happen to be "dogs", "fish" and
"carrots", then
subst("$2, $1 and $3")
should return
"fish, dogs, and carrots"
----------------------------------------------------------------
Write a function, 'expand_escapes', which expands escape sequences in
text. Escape sequences have the form
X<.....>
where 'X' is any letter or digit and '.....' is any string that
contains balanced <...> sequences. A backslash before a < or >
removes its special meaning, so, for example,
Ahij> k l m>
is a valid single escape sequence. The arguments to 'expand_escapes'
are the string to be expanded, and a reference to a hash which maps
the escape codes to expansion functions. When 'expand_escapes'
recognizes an escape sequence, say
W
it should first expand escape sequences in 'some text', if there are
any, removing backslashes where appropriate; then look in the hash to
find the associated function for 'W'; invoke the function with the
expanded 'some text', and finally, replace the entire sequence
'W<...>' with the return value of the function. It should do this for
every escape sequence in its string argument.
For example, given these arguments:
expand_escapes("Result: R<12\>34>, S, Rxyz>",
{ R => sub { scalar reverse $_[0] },
S => sub { join " ", split //, $_[0] },
}
);
'expand_escapes' should return the string
"Result: 43>21, G i v e m e p i e !, zyxt x < e tcba"
----------------------------------------------------------------
Write a program whose input is a Perl program and whose output
includes counts of the number of statements and the number of control
expressions in the program. (A control expression is the expression
that controls the execution of a 'while' or 'if' block.)
----------------------------------------------------------------
The unix 'fmt' command accepts arguments in the following format:
fmt -### -cstu files...
Here '###' can be any numeral. 'fmt' reads the specified files (or
the standard input, if no files) and reformats paragraphs to the width
specified by the -### option.
Neither of the Perl standard option-parsing modules, Getopt::Std and
Getopt::Long, can handle an option in this format. Subclass
Getopt::Long and extend it so that it can.
Similarly: 'comm'.
----------------------------------------------------------------
Write a function 'show_split' which accepts two arguments: A regex and
a target string; it should return a display that shows where the
target string would be split, if it were given to the 'split' function
with the specified pattern. For example,
show_split('\s+', 'Example target string.');
should return the string:
" "
and
show_split('a.', 'Example target string.');
should return the string:
"amar"
and
show_split('', 'Example target string.');
should return the string:
"< >< >*<.>"
(Too easy?)
----------------------------------------------------------------
* Quiz 2 sent 20021023
The local high school baseball team, the West Philadelphia High School
Fightin' Quakers, will be playing a series of games against their
rivals, the Levittown Richard M. Nixon Memorial High School Sewer
Fungus. The series lasts at most five games, and ends when one team
has won three games. You want to bet $80 on the Fightin' Quakers to
win, but your bookie will only take bets on individual games. (The
bookie pays even money on all bets.) A mathematically-inclined friend
solves the problem for you, giving you the following instructions:
Bet $30 on each of the first two games.
Bet $20 on the third game if either team has won both of the first two
games, $40 otherwise.
Bet $40 on the fourth game, if there is one.
Bet $80 on the fifth game, if there is one.
At the end of the series, you will be ahead by exactly $80 if the
Fightin' Quakers have won the series, and behind by exactly $80 if
the Sewer Fungus have won.
We could summarize the instructions in a table like this:
If the game score is:
0 to 0, bet $30
1 to 0, bet 30
1 to 1, bet 40
2 to 0, bet 20
2 to 1, bet 40
2 to 2, bet 80
Write a function which calculates the appropriate bet for any such
contest, given the total amount you want to risk on the series, the
length of the series, and the current game score. For example,
bet 80 5 2 1
should return '40', because if you want to risk $80 on a 5-game
series, and one team is presently ahead 2 games to 1, you should bet
$40.
----------------------------------------------------------------
Given a string, find the longest substring that appears more than once.
The function should be efficient even for very long strings.
----------------------------------------------------------------
Given a string and a number k, find all the repeated subsequences of
length at least k.
* Quiz 14, sent 2003061 was to locate the longest repeated substring
in a string.
----------------------------------------------------------------
* Quiz 8 sent 20021211
Given n, compute the Graham number G_n.
----------------------------------------------------------------
Newton-Raphson approximation; compute derivative numerically.
----------------------------------------------------------------
Suppose you're given a set of vectors of integers, each with the same
length L an associated unique name:
Ruth 10923 4503 714 ...
Aaron ...
Morandini ...
...
You're also given a list of the names of the vectors that are
distinguished in some way; we'll call these the 'famous' vectors.
Vectors not in this list are not famous.
Your job: Compute a list of W integers such that, for any name N,
sub is_famous {
my $total = 0;
my $name = shift;
for my $v (0 .. $L-1) {
$total += $Vector{$name}[$v] * $W[$v];
}
die if $total == 0;
return $total > 0;
}
is correct for all the names.
Idea: The vectors list number of at-bats, hits, home runs, etc., for
baseball players; you are figuring out a weighting that correctly
divides the players into those who are in the Hall of Fame and those
who aren't.
Explain up front what you're doing. Don't pose it as an abstract
mathematical problem.
Pose this one right before the summer break.
----------------------------------------------------------------
Suite to replace 'locate'.
----------------------------------------------------------------
* Quiz 5 sent 20021113
Tree-drawing library
----------------------------------------------------------------
Given a web log, extract user paths and display graphically
----------------------------------------------------------------
TK application for editing generic hierarchies
----------------------------------------------------------------
* Quiz 4 sent 20021106
anagram dictionary ranked by score
----------------------------------------------------------------
* Quiz 3 sent 20021030
asynchronous DNS lookup server
----------------------------------------------------------------
program to play tetris: calls function that returns type and position
of next piece. Places piece.
program to sabotage tetris player. Given board position, decide which
piece to send in.
Problem: It's easy to sabotage tetris players. Jujst give them
nothing but
XX
XX
and they will lose quickly. Some restriction must be placed on the
distribution of shapes. Maybe some sort of ergodicity requirement?
Perhaps the referee can generate shapes at random and give player A a
choice of three to give to player B. A gets the two unchosen ones
back with the next menu.
----------------------------------------------------------------
Solve polyomino puzzles
----------------------------------------------------------------
* Quiz 6 sent 20021120
CGI program that generates a survey from a simple config file:
How old are you? 0-12; 13-19; 20-24; 25-34; 35-44; 45 or older
What is your favorite color? red; blue; black; other
and poses the quiz and accumulates the results.
----------------------------------------------------------------
Metronome program a la Dominic Pain
----------------------------------------------------------------
use strict;
my $z = DerivedClass->new(...);
...
package BaseClass;
sub new { ... }
...
package DerivedClass;
BEGIN {
@ISA = ('BaseClass');
}
...
This raises a 'strict vars' failure for @ISA. So the programmer adds
our(@ISA);
just below the 'use strict'.
Now the programmer gets 'can't locate method via DerivedClass'. Why?
----------------------------------------------------------------
* Quiz 9 sent 20021212
Spelling checker: Load dictionary; read input; find mismatched words,
**suggest alternatives**. Base this on the regular quiz, which will
just find mismatched words.
----------------------------------------------------------------
Double-acrostic generator. Given a string of between 243 and 250
characters, an author's name and a title which total between 20 and 30
characters, and a dictionary, find a set of dictionary words suitable
for use as double-acrostic clue answers.
Quality-of-implementation: Letters close together in the clue answers
should be far apart in the grid.
----------------------------------------------------------------
Yahtzee player. (Goes with intro quiz Yahtzee referee.)
Optimal yahtzee player
Duplicate Yahtzee
Tic-tac-toe player. (Goes with intro quiz Tic-Tac-Toe referee.)
Then have a tournament between the submitted programs.
----------------------------------------------------------------
Query engine for family relationships:
Read input of the form
Joe is Mary's brother
Joe is Bill's father
Bill is married to Rachel
and then answer questions like
How is Rachel related to Mary?
(Andy Bach)
----------------------------------------------------------------
Lambda calculus evaluator
----------------------------------------------------------------
Unlambda interpreter
----------------------------------------------------------------
Traffic flow simulation? Cars have routes in mind; the move at a
speed proportional to the distance to the next obstacle (whether that
be another car or a stop sign or whatever) etc.
----------------------------------------------------------------
Monty Hall envelope problem: N envelopes, each containing a random
number. You open an envelope and may continue or stop. If you stop
on the nth-smallest random number, you get a prize of $N.
Beginners can write a harness for it.
----------------------------------------------------------------
Dissociated press.
Markov generator.
----------------------------------------------------------------
LZW.
----------------------------------------------------------------
Minesweeper. Beginners write harness?
----------------------------------------------------------------
* Quiz 7 sent 20021127
Frost simulation w/ Margolus neighborhoods.
----------------------------------------------------------------
* Quiz 11
Guess-the-animal regex manufacturer.
----------------------------------------------------------------
Computer matchmaking.
----------------------------------------------------------------
* Quiz 15
patch
----------------------------------------------------------------
compute fractal dimension of something or other
----------------------------------------------------------------
Tivo program scheduling
----------------------------------------------------------------
* Quiz 10 sent 20030128
Guess-the-animal with corrections
----------------------------------------------------------------
Email three-way-handshake library
----------------------------------------------------------------
Simplify iterator 'or' and 'and' operators.
----------------------------------------------------------------
Fourier transform. Given a list of mass extinction dates, can it
detect the 26MY periodicity?
----------------------------------------------------------------
Satisfiability of Boolean expressions
----------------------------------------------------------------
* Quiz 13 sent 20030528
Implement 'sortby': A directory contains a collection of email
messages. The filenames are numerals. Rename the files so that (a)
the names are the same, and (b) when the subjects of the files are
listed in increasing numerical order by filename, the subjects are
also in alphabetical order.
Do this with 'scan' exercise in intro quiz.
----------------------------------------------------------------
Calculate pi using monte carlo method: Generate random x and y in [0,
1]. Calculate hit++ if sqrt(x*x+y*y) < 1. Then pi = 4 * tries/hits.
----------------------------------------------------------------
* Quiz 16 sent 20040519
Class scheduling suggested by Shlomi Fish
Given numbers N and M, there are N classes and M slots in which
classes are held. You are giving a boolean matrix which says which
classes meet during which slots. Several classes might meet in the
same slot.
Your job is to assign instructors to classes subject to the
constraints:
Each class has only one instructor.
Each instructor has at most one class per slot.
with as few instructors as possible.
----------------------------------------------------------------
Manufacture stupid riddles. Locate a dictionary. Select a noun A at
random such that A contains a shorter noun B. Then generate
Q: What sort of pet is a thick, heavy covering for a floor,
usually made of wool or synthetic fibers?
A: A carpet! HA HA HA HA HA HA
Q: What kind of tor is a male theatrical performer?
A: An actor! YUK YUK YUK
----------------------------------------------------------------
Replacement for MLDBM. Usage:
tie %h => 'MyMLDBM', \%underlying;
and then accesses on $h{blah}{blah}{blah} turn into
$underlying{something-or-other} in a faithful way.
----------------------------------------------------------------
Figure out a way to use locking to allow N processes, but no more, to
hold the lock at the same time.
For example, this doesn't work:
for (1..$N) {
#try to lock $lockfile # $n
# if fail, try next lock file
}
----------------------------------------------------------------
* Quiz 17 sent 20040602
NOB sphinx puzzle
----------------------------------------------------------------
A curry_n function. It gets two arguments: $N and $f.
$N is a number; $f is a coderef.
It returns a curried version of $f. If the curied version is supplied
with $N or more arguments, $f is called on the arguments and $f->(...)
is returned. Otherwise, another coderef is returned which remembers
the arguments for later.
----------------------------------------------------------------
Given a monotonically increasing function V of six parameters,
and a threshhold B, find all the 6-tuples of arguments such that
f(a,b,c,d,e,f) >= B
but f(a',b',c',d',e',f') <= B for all a' <= a, b' <= b, etc.
Specifically, find all ways of getting the upper bonus in Yahtzee that
aren't subsumed by some easier way. For example, throwing
A23456
333334
is subsumed by
A23456
333333
----------------------------------------------------------------
Given
n1 s1 s2
n2 s3 s4
...
where n_i are real numbers that indicate a degree of relatedness, and
s_i are strings, organize the strings into groups of most-nearly
related strings.
----------------------------------------------------------------
Test number to see if it is the sum of two squares.
----------------------------------------------------------------
TiVo scheduling. Support scheduling of a program at a certain time
with a certain duration and life, altering the lifetime, etc. The
interesting part is the interaction with wishlists. Deleting a
program, or shortening the retention life of a program that will be
recorded in the future, increase the amount of free space at present
and also in the expected future, so that more future wish-list
programs can be scheduled for recording.
----------------------------------------------------------------
Alter frost simulator to demonstrate countercurrent exchange.
----------------------------------------------------------------
Boggle player that plays like a human.
Each word in its dictionary should have a weight. The weight is the
likelihood of the computer remembering that that word exists in any
particular game. If the computer forgets about a word in a game, it
will not find that word in the Boggle grid.
When a human finds a word while playing against the computer, the
computer adjusts the weight of that word upwards so that it is more
likely to notice that word in the future.
Big question: how to initialize the weights? Idea: use the polysemy
count from WordNet.
----------------------------------------------------------------
Script to unsubscribe someone from a mailman mailing list.
It should visit the web page, get a mailed copy of the password, then
forge the unsubscription request with the password.
----------------------------------------------------------------
Street parking simulation. Cars come according to a Poisson
distribution, with their sizes distributed normally. Each one parks
as close as possible to its desired spot, with some random variation
in the distance from the car immediately in front of it. Of course,
it can't park in a space if the space is too small. Cars also leave
according to a Poisson distribution.
On *my* street, there are always some spaces that are half a car
long. Do these appear in the simulation?
What happens if someone parks a big dumpster on the street for a
couple of weeks and then removes it?
----------------------------------------------------------------
Given a chunk of text and a part-of-speech dictionary, turn the text
into a Mad Lib.
----------------------------------------------------------------
Compute the convex hull of a pixel array.
----------------------------------------------------------------
Calculate de bruijn sequences.
----------------------------------------------------------------
Sent
University of Chicago word problem.
----------------------------------------------------------------
Inverse ascii-art banner problem:
Transform
XXXXX
X
XXX
X
X
into 'F'.
----------------------------------------------------------------
Oskar cube. (Can this be done as a regular quiz?)
----------------------------------------------------------------
Gosper continued fraction arithmetic calculations
----------------------------------------------------------------
Monte Carlo simulation of Poisson distribution. Was Poisson correct?
----------------------------------------------------------------
Make 'qsummary' command generate output faster.
(Maybe regular quiz?)
----------------------------------------------------------------
The came of 'Set' is played with a deck of 81 cards. Each card has
some blobs. Each card has between one and three identical blobs.
The blobs can be ovals, rectangles, or waves; they can be red, blue, or
green; and they can be hollow, filled, or striped. There is exactly
one card with each combination of attributes. For example, there is
one card with a single red hollow oval; one card with two red hollow
ovals, one card with two red striped ovals, one card with two red
striped waves, and one card with two blue striped waves.
Three cards form a "set" if, for each of the four properties (number,
shape, fill, color) either all three cards have the property in
common, or no two of the three cards have the property in common.
For example, these cards form a set:
three red filled ovals
three red hollow ovals
three red striped ovals
So do these three:
three red filled ovals
one blue hollow oval
two green striped ovals
So do these three:
three red filled ovals
one blue filled wave
two green filled rectangles
So do these three:
one blue filled oval
one blue filled wave
one blue filled rectangle
These do not:
one blue filled oval
one blue filled oval
one blue filled rectangle
because a set must have either three of the same shape, or else one of
each shape.
We will represent a "Set" card as an array of four integers, each
between 1 and 3, such as:
# Three green striped rectangles
[3, 2, 2, 1]
1. Write a function, "set", which takes a list of these arrays, and
which decides whether or not they contain a set. If there is a
set, the function should return three of these array objects which
form a set. If not, it should return an empty list.
2. What is the largest possible input to the function that will cause
it to return false?
----------------------------------------------------------------
Given a pair of numbers (i,j) that are relatively prime, find a
sequence
(i0,j0) = (i, j)
(i1,j1)
...
(iN,jN) = (1, 1)
such that (i{k+1}, j{k+1}) = (ik+1, jk) or
(ik-1, jk) or
(ik , jk+1) or
(ik , jk-1)
or prove that no such exists.
----------------------------------------------------------------
Write a program that figures out and prints a correct operator
precedence table.
----------------------------------------------------------------
Computer dating
----------------------------------------------------------------
Consider the following game: There is a 12x12 board. On each turn,
the computer selects a color and an empty square at random and tells
the player the color and the square. The player then selects any
piece already on the board and makes a rooklike move with it. If
there is now an orthogonally-connected set of at least four pieces of
all the same color, they are removed, and the player gets a free move;
if the player completes another set, they get another free move, and
so on. When the player makes a move that does not complete a set, the
computer places a new piece on the board as chosen earlier, if the
chosen space is still unoccupied.
----------------------------------------------------------------
Given something like
AAAAB
CCBBB
CDDDB
CCDDD
produce
+-------+-+
| | |
+---+---+ |
| | |
| +-+---+ |
| | | |
| +-+ +-+
| | |
+---+-----+
-------------------------------------------------------------------
Graph 3-coloring
----------------------------------------------------------------
Interconvert expressions from Principia Mathematica-style dot notation and
standard parenthesis notation. There is an explanation of the dot notation
in J. Barkley Rosser's book "Logic for Mathematicians", and probably
also in Principia Mathematica itself.
Use . : .: :: for dots. Don't forget that .: may also apear as :. .
*