Just another Perl shrine PerlMonks

### Simple but thought-provoking programming tasks [OT]

by Cody Pendant (Prior)
 on Apr 16, 2007 at 02:00 UTC Need Help??

Cody Pendant has asked for the wisdom of the Perl Monks concerning the following question:

I teach a general programming class, and I'm looking for interesting tasks to teach programming concepts.

One example is "produce English date suffixes from numbers", i.e.

```for(1 .. 31){
print \$_ . suffix(\$_) . "/n";
}
where "suffix()" is a sub that the students have to come up with.

• it's relatively simple, although
• there's a gotcha because all numbers ending in "1" take "st" except 11, and the same for 2/12 and 3/13
• it kind of involves math but mostly just logical thinking
• TMTOWTDI -- I can think of about ten ways to do it, from the straightforward but clunky:
```    @suffixes = ( undef, 'st','nd','rd' ... etc);
return \$suffixes[\$_[0]];
to the golf-y
```    \$_[0]=~/(\b|[^1])(\d)\$/;qw(0 st nd rd)[\$2]or'th'
• the content is familiar and practical, not abstract -- you might actually want someday to produce output like "last edited: 1st of April".

So, have monks got any examples of similar exercises which would be suitable for learners?

(\$_='kkvvttuu bbooppuuiiffss qqffssmm iibbddllffss')
=~y~b-v~a-z~s; print

Replies are listed 'Best First'.
Re: Simple but thought-provoking programming tasks [OT]
by Old_Gray_Bear (Bishop) on Apr 16, 2007 at 03:21 UTC
You might introduce them to the concepts of data validation by asking them to determine if a particular string of characters represents a telephone number.
• 867-5309
• 555 123-456
• (555) 456 - 1234
• +1 555-234-9874
• 911
• extra credit for:
• +66 44-515-0123
• +47 2291 2345
• 02/xx xx xx xx (inside Czech Republic)
• +420 (0)2/xx xx xx xx (outside Czech Republic)
There is an ISO standard (E.164) the details all the possibilities....

----
I Go Back to Sleep, Now.

OGB

There is a draft version of the standard document here. Note that this is a download link for a Microsoft Word document.

DWIM is Perl's answer to Gödel
• 02/xx xx xx xx (inside Czech Republic)
• +420 (0)2/xx xx xx xx (outside Czech Republic)

Actually not. The 0 has been dropped from the phone numbers some years ago. The original scheme was 4 to 8 numbers not starting with 0 for a local number (different districts had different number of phones and thus different number length) or 0 area_code local_number. 02 used to mean Prague. They increased the number of digits as necessary and made the area code required and thus the 0 unnecessary. So 02 12 34 56 78 became 212 345 678.

Regarding +420 (0)2 ... the original country code was 42 so the numbers were +42 0 area_code local_number. After we split with the slovaks our code was "changed" to 420, they were assigned 421. So the international numbers became +420 area_code local_number. In either case +420 02/xx xx xx xx would have one too many zeroes I believe. (Sorry for this lengthy and largely pointless post.)

In either case I think this is a bit too tricky task. Especially if you wanted them to accept the special numbers. 911 in US, 112,150,155,158 and probably a few others in Czech Rep and quite a few more in other countries. I think it's best not to be too strict while validating phone numbers. At least unless you can restrict them to a single country.

555 123 456 is an interesting one. It's obviously invalid because it's too short. But if you make it long enough by adding a digit on the end it's still invalid, because 1 is illegal in the fourth digit of NANP numbers. To be honest, this sort of thing, which requires esoteric domain-specific knowledge to get right, is not really suitable for a student exercise.

But it does make a good teaching example, by starting with the most basic rules (is it the right length?) then add more and more complex ones - start with why the A and D digits can't be 0 or 1 (getting the students to figure out why this is the case is a useful exercise in itself, even without then encoding the rule in a program); then add the other special cases (eg, the BC digits can't be 11 and again get the students to figure out why) and finally wrap up with "and you don't have to do any of that work if you use perl because there's a CPAN module for it". That module is Number::Phone::NANP.

Re: Simple but thought-provoking programming tasks [OT]
by Zaxo (Archbishop) on Apr 16, 2007 at 02:19 UTC

The problem of listing prime numbers is nice. It is a simply understood problem which has been gradually understood better over 3000 years of effort. It emphasizes that domain knowledge pushes better algorithms. There is a current discussion of this problem here, at ulam's spiral too slow.

After Compline,
Zaxo

Re: Simple but thought-provoking programming tasks [OT]
by bobf (Monsignor) on Apr 16, 2007 at 04:06 UTC

There's always the classic "making change" problem:

What is the least number of coins required to total \$x.xx?
Variations on that problem could include:
• Allow the user to input the value of each coin (instead of relying on the assumed values of a penny, nickel, etc)
• Add restrictions on the maximum (or minimum) number of coins available (e.g., you can use no more than one nickel)
• Find a solution that uses some exact number of coins
• Count how many different ways are possible (using any number of coins)

Re: Simple but thought-provoking programming tasks [OT]
by GrandFather (Saint) on Apr 16, 2007 at 02:44 UTC

The various issues that List::Compare addresses (just don't tell em about the module up front) are interesting challenges, especially if you want a solution that scales well.

DWIM is Perl's answer to Gödel
Re: Simple but thought-provoking programming tasks [OT]
by GrandFather (Saint) on Apr 16, 2007 at 02:49 UTC

or in a similar vein to the OP's suggested problem, generate the English phrase representing a given integer or dollars and cents value (which can allow a nice introduction to recursion).

DWIM is Perl's answer to Gödel
Would this be recursion as much as divide-and-conquer?

My criteria for good software:
1. Does it work?
2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
```use strict;
use warnings;

while (<DATA>) {
chomp;

next unless length;
print "\$_ is not a number that I can handle\n" unless /^\d+\$/;
print "\$_ = ", toWords("00\$_"), "\n";
}

sub toWords {
my (\$leftBit, \$groups) = @_;

return '' unless \$leftBit;

\$groups ||= 0;

my \$group = substr \$leftBit, -3, 3, '';

if (\$groups > 4) {
print "Argh, I can't deal with numbers that big!\n";
print "The part I can deal with is: ";
return '';
}

my %digits = (
0 => '', 1 => 'one ', 2 => 'two ', 3 => 'three ', 4 => 'four '
+,
5 => 'five ', 6 => 'six ', 7 => 'seven ', 8 => 'eight ', 9 =>
+'nine '
);
my %teens = (
10 => 'ten ', 11 => 'eleven ', 12 => 'twelve ', 13 => 'thirtee
+n ',
14 => 'fourteen ', 15 => 'fifteen ', 16 => 'sixteen ',
17 => 'seventeen ', 18 => 'eighteen ', 19 => 'nineteen '
);
my %tens = (
2 => 'twenty ', 3 => 'thirty ', 4 => 'fourty ',
5 => 'fifty ', 6 => 'sixty ', 7 => 'seventy ',
8 => 'eighty ', 9 => 'ninety '
);
my \$groupStr = '';

# Deal with last two digits
my \$tensStr = \$group % 100;

\$groupStr = \$tens{int (\$tensStr / 10)} if \$tensStr >= 20;

if (int (\$tensStr / 10) == 1) {
\$groupStr .= \$teens{int \$tensStr};
} else {
\$groupStr .= \$digits{\$tensStr % 10}
unless \$tensStr > 10 and \$tensStr % 10 == 0;
}

my \$hundreds = int (\$group / 100);

if (\$hundreds) {
my \$prefix = "\$digits{\$hundreds}hundred ";

\$prefix .= 'and ' if \$groupStr;
\$groupStr = "\$prefix\$groupStr";
}

my \$prefix = toWords (\$leftBit, \$groups + 1);

\$prefix .= qw(thousand million billion trillion)[\$groups] . ' ' if
+ \$prefix;

\$groupStr = "\$prefix\$groupStr";
\$groupStr = 'zero' unless \$groupStr or \$groups;
return \$groupStr;
}

__DATA__
0
1
10
11
20
21
99
100
901
98012785623123

Prints:

```0 = zero
1 = one
10 = ten
11 = eleven
20 = twenty
21 = twenty one
99 = ninety nine
100 = one hundred
901 = nine hundred and one
98012785623123 = ninety eight trillion twelve billion seven hundred an
+d eighty five million six hundred and twenty three thousand one hundr
+ed and twenty three

looks recursive to me, but it would be easy to make it iterative instead (left as an exercise for the reader).

DWIM is Perl's answer to Gödel
Re: Simple but thought-provoking programming tasks [OT]
by Krambambuli (Curate) on Apr 16, 2007 at 08:33 UTC
Just take care not to be tempted to come up with something _you_ like/admire, but that could just pass by the intended audience... Beauty is in the mind of the viewers - so take your time to try to guess what sort of problems would impress your audience.

It very much depends on the general skills they already have, and even if they are more or less at the same level, there are so many different possible approaches. Programming problems that are like little jewels for people with a strong taste for mathematics might be entirely 'oh noooo, not again!' problems for others.

You'll see if you took the 'right' approach very soon - in the eyes of your audience.

One particular problem I remember made me love programming was the one known (if I'm right) as "Joseph's problem".

Given n entities (childs sitting in a circle, Martin, Peter, John, ...) which is the order they step out of the circle if you count them and every 'm-th' has to step out ?

It seemed so obviously simple - and still, it didn't and didn't work out correctly!! Just to be again as simple as thought in the beginning once you had the right idea about how to tackle it. Wow! :)

As a side question: do you use Perl to start teach your audience programming in general or do you start teach them Perl and they know some programming ?

Thanks.
Definitely a possible and nice solution! :)
Re: Simple but thought-provoking programming tasks [OT]
by johngg (Canon) on Apr 16, 2007 at 08:54 UTC
Similar to bobf's suggestion, many, many moons ago I did the weekly wage packets where I worked. These were paid in cash and one of things you had to work out was what denomination notes and coins would you need from the bank. Given that Fred needed £305.27, Mary needed £387.43 and Bill was to recieve £287.94, how do you break up the total of £980.64 so that you could make up each pay packet exactly, always using the highest denomination possible, i.e 8p would be 5p + 2p + 1p, not 4 x 2p or 8 x 1p.

I hope this is of interest.

Cheers,

JohnGG

Re: Simple but thought-provoking programming tasks [OT]
by robot_tourist (Hermit) on Apr 16, 2007 at 08:11 UTC

hehe, now we'll know for sure if someone wants the monks to do their homework for them :) Go the whole hog and give them the Knight's Tour.

I did my own plaintext Minesweeper once, which is a nice project because is has input, output, objects, arrays and recursion in one package. Teach a principle and get them to implement it themselves as you go along. You could also introduce modules with something like Curses or even TK for extra credit.

Or go really hardcore and introduce them to threads with the dining philosophers (which I must confess to not to comletely mastering at uni).

How can you feel when you're made of steel? I am made of steel. I am the Robot Tourist.
Robot Tourist, by Ten Benson

Actually I did too. One that could solve most of the stuff automatically actually ... it even went as far as "due to this number here, there must be two mines in these three fields so the 2 over here will have both its mines there and therefore this field is safe, click" and then to one more level. All in Prolog. It was an interesting exercise. Shame I lost the code :-(

Re: Simple but thought-provoking programming tasks [OT]
by hangon (Deacon) on Apr 16, 2007 at 09:26 UTC

Along the lines of robot_tourist's suggestion, games are probably a good choice. They should generate a lot of interest, particularly from a younger group. A simple basic game such as tic-tac-toe could work for beginners. The beauty is that there are an endless variety of games to choose from. Another possibility is to ask them to choose or make up their own game and use it to demonstrate specific programming concepts.

Re: Simple but thought-provoking programming tasks [OT]
by dokkeldepper (Friar) on Apr 16, 2007 at 08:54 UTC

Fibonacci series for recursion versus looping. Where goes the quotient of two consecutive Fibonacci numbers?

Mortgage calculation, interest, compound interest (looping verus direct calculation, an interesting and underused introductory example for oo-Programming with mathematical twists from elementary to numerics even fractals (internal rate of return computation)).

Sudoku solution and puzzle generation (bit counting, recursion).

Pick the technique first
by Anonymous Monk on Apr 16, 2007 at 15:35 UTC
Cody,

May humbly suggest that you pick the techniques you are trying to teach and then select problems that rely and utilize those techniques?

By techniques I mean things like subroutines, references, iteration, simple data structures (stacks, queues, etc.), sorting, recursion.

Then create problems that focus on each specific technique and tell the students that's what the problem is meant to illustrate. For example: sorting -- sort an array of dates of the form "12 Jan 2007".

Random mathematical curiosities is a sure way of turning off most young minds. Remember, most people really hate pointless mathematical exercises.

Good luck,
Rob

Re: Simple but thought-provoking programming tasks [OT]
by Moron (Curate) on Apr 16, 2007 at 15:08 UTC
A few ideas, some from my own early education and some thought up

- find the LCD of two natural numbers

- test whether an array of reals is pointwise convergent. Spoiler:

- given a five-letter English word, find all two- or more-letter permutations that are present in the dictionary (dictionary file is /usr/share/lib/dict/words).

- write a program for a robot to explore and map an orthogonal maze 40m x 40m. The robot can see one metre in each of four directions North, South, East or West and perceives the presence or absence of a wall. A wall is a one metre cube. The robot receives only the instructions N, S, E and W (to move one metre in that direction). It then returns four binary digits to your program indicating the presence or absence of walls in these directions and awaits further instructions. If the robot is told to hit a wall, it will, but will emergency shut down after that, so the program must not instruct this. The maze has an entrance and an exit which are interchangeable for these purposes. The goal of the program should be to produce a map of any such maze as efficiently as possible. Include an iteration counter and fail at a million iterations to prevent accidental looping of the program. Communication with the robot takes place via STDIN/STDOUT. (advanced version: extend this to N robots exploring the same maze. Robots cannot discern between walls and other robots. In this case messages to and from robots begin with a numeric robot id followed by a space.)

__________________________________________________________________________________

Re: Simple but thought-provoking programming tasks [OT]
by mattr (Curate) on Apr 17, 2007 at 05:12 UTC
You could look at the American Computer Science League. It was a lot of fun when I was in it umpteen years ago and they have some sample problems online. They have different levels, including the all-stars which I believe is the one used for the national finals. They include problem solving, geometric, financial, graph etc. various problems to be solved by writing a program in a limited amount of time.
Re: Simple but thought-provoking programming tasks [OT]
by swampyankee (Parson) on Apr 17, 2007 at 03:46 UTC

There are numerous exercises in D E Knuth's Art of Computer Programming. Ones I found especially intriguing were calculation of Easter, Least Common Multiple, Greatest Common Divisor, and converting names into their Soundex representation. Other possibilities are converting a date into its Julian Day Number, and vice-versa, and an automated generator of knock-knock jokes.

emc

Insisting on perfect safety is for people who don't have the balls to live in the real world.

—Mary Shafer, NASA Dryden Flight Research Center
Re: Simple but thought-provoking programming tasks [OT]
by bibliophile (Parson) on Apr 16, 2007 at 13:38 UTC
Re: Simple but thought-provoking programming tasks [OT]
by Limbic~Region (Chancellor) on Apr 17, 2007 at 10:55 UTC
Re: Simple but thought-provoking programming tasks [OT]
by tlm (Prior) on Apr 19, 2007 at 04:26 UTC

In the lab where I did my graduate work, there was a post doc who used to give the following problem to those prospective graduate students who were uncertain about their programming chops (and wanted some reassurance on whether they'd be able to handle the work).

Consider a 3-dimensional graph consisting of 27 vertices with coordinates (x, y, z), where each of x, y, and z belongs to the set {0, 1, 2}, and whose edges are the segments of length 1 between any two nodes along the coordinate axes (i.e. the coordinates of the endpoints of each edge differ by 1 at exactly one position). A "path" on this graph is defined as an ordered sequence of vertices such that adjacent vertices in the sequence are neighbors in the graph (i.e. the coordinates of two adjacent vertices in a path differ at exactly one position). A Hamltonian path (HP) on this graph is one that visits each of the 27 vertices exactly once.

The problem is to count exactly all the HPs on this graph.

One further detail had to do with the geometric symmetries of such cubic lattice. In the way the problem was usually posed, all the HPs that could be obtained from a given HP by a 3-D symmetry operation (e.g. flipping the lattice around one of its axes of symmetry, or reflecting through a plane of symmetry, etc.) counted as only one HP. (BTW, accounting for these symmetries is the trickiest aspect of the problem.) However, two HPs that could be obtained from each other by reversing the order of the nodes were to be counted as two different HPs.

the lowliest monk

Re: Simple but thought-provoking programming tasks [OT]
by sfink (Deacon) on Apr 16, 2007 at 23:48 UTC
Insult generation.
```sub insult {
my \$r = rand();
if (\$r < 0.3) {
return "You are " . bad() . ".";
} elsif (\$r < 0.60) {
return others() . " cannot believe how " . bad() . " you are.";
} elsif (\$r < 0.90) {
return "If I had " . money() . " for every time you " . didsomethi
+ngstupid() . ", I would be rich.";
} else {
return insult() . " " . insult();
}
}
etc. There are a ton of ways of doing it, some more flexible than others, so you could probably explore a whole series of successive "improvements". The language you use doesn't matter all that much either. (Especially if you print everything out immediately instead of returning it.)
The missing subroutines all seem to want to pick random words from a dictionary file, as per Ode to a random number. The improvement I haven't yet figured out (without a lot of manual typing in) is to have a modified dictionary file with a part of speech field alongside the word. i.e. in your example you want your insult to call somone an adjective noun or an adverb adjective noun and the filtering should be data-driven rather than by using different subroutines.
__________________________________________________________________________________

Re: Simple but thought-provoking programming tasks [OT]
by chexmix (Hermit) on May 09, 2007 at 18:13 UTC
I just want to say I'm really glad you posted this. One of the hurdles I'm finding difficult to maneuver around (in learning Perl well) is my lack of a programming background. This has made it more of a problem than I'd like being "creative" in this realm ... and by "creative" I don't really mean coming up with Perl poems -- it's more basic than that, e.g. knowing what questions are worth posing, or knowing /how to ask/ the questions. I think it has to do with a familiarity or comfort (or lack thereof in my case) with the real foundation stones/basics.

So tasks like these really appeal. Thanks!

Create A New User
Node Status?
node history
Node Type: perlquestion [id://610245]
Approved by BrowserUk
Front-paged by GrandFather
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (2)
As of 2021-01-21 04:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The STEM quote I most wish I'd made is:

Results (229 votes). Check out past polls.

Notices?