Simple but thought-provoking programming tasks [OT]

[Cody Pendant]

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.

I like this task because

• 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?

[Old_Gray_Bear]

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
• [phone]
• 911
• extra credit for:
  • [phone]
  • [phone]
  • 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....

[GrandFather]

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

[Jenda]

• 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.

[DrHyde]

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.

[Zaxo]

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.

[bobf]

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)

[GrandFather]

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.

[GrandFather]

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).

[dragonchild]

Would this be recursion as much as divide-and-conquer?

[GrandFather]

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, '';
    
    return toWords ($leftBit, $groups + 1) unless $group;

    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).

[Krambambuli]

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.

[Jenda]

Like this?
<Reveal this spoiler or all in this thread>

[Krambambuli]

Definitely a possible and nice solution! :)

[robot_tourist]

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).

[Jenda]

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 :-(

[johngg]

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

[hangon]

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.

[dokkeldepper]

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).

[Anonymous Monk]

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

[Moron]

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:

Read more... (357 Bytes)
- 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.)

[mattr]

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.

[swampyankee]

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.

[bibliophile]

How about the bin-packing problem?

[Limbic~Region]

Cody Pendant,
Might I recommended Recommended Reading.

[tlm]

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.

[sfink]

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.)

[Moron]

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.

[chexmix]

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!