Collaborator8.2-Blog-CTA-Demo

7 Silly Programming Challenges to Do for Fun

challenges

Practice makes perfect. Unfortunately, the more we do something, the more set in our ways we risk becoming. The more we solve the same sort of problem using the same tools, the better we get at it – but at the expense of more flexible thinking.

With these silly exercises, you get to try things that are, I hope, completely outside of your comfort zone, and since it’s for fun, there’s no pressure. They require original thinking and flexibility that you can then draw on when solving the real programming problems that matter. And perhaps it’s an opportunity to teach yourself a new set of programming skills that you never got around to trying.

Initially, I intended to provide sample solutions, but then I realized it would deprive you of the pleasure to work on these yourself. These challenges are all feasible. Some may take longer than others, depending on your background; you might have encountered some of them in your programming classes.

I tried to include something for all tastes. Some challenges are language specific, but others are not. Dig in!

1) Sums

Once upon a time, processing was expensive, but random access memory – the memory used while executing a program – was not only expensive, but also limited to an amount that we’d find totally ridiculous by today’s standards. Some programing environments today still carry RAM limitations, but most of us do not have to deal with that on a regular basis. I’m glad I don’t.

For this first challenge, you therefore have to use a technique that has been used by programmers for decades. You start with a data file that lists the number of red-haired students in each grade, in each school, in each city, and in each state.  Your mission, should you choose to accept it, is to generate summaries of red-haired students per school, city, and state. The data is sorted per state first, city second, school third, and finally by grade (K to 6).

You must write out a summary as soon as it is available. You must not read in the whole file before processing it, but you must process it as you read it in, line by line.  If it helps, pretend we’re in the early 1970s, you’re wearing your best bell-bottoms and wide lapels, and that you’re programming in COBOL. If you feel daring, and want to try your hand at COBOL for real, here’s a shell of a program to get started. You don’t even have to install open-cobol; you can use it interactively online (no really, I’m not making this up, it exists for real). But any language will do.

IDENTIFICATION DIVISION.

PROGRAM-ID. SUMS.

ENVIRONMENT DIVISION.

INPUT-OUTPUT SECTION.

FILE-CONTROL.

SELECT StudentFile ASSIGN TO 'input.txt'

    ORGANIZATION IS LINE SEQUENTIAL.

DATA DIVISION.

FILE SECTION.

FD StudentFile.

01 StudentCount.

   02  State       PIC X(12).

   02  City        PIC X(18).

   02  School      PIC X(20).

   02  Grade      PIC X.

   02  RedHaired   PIC 9999.

WORKING-STORAGE SECTION.

[…]

PROCEDURE DIVISION.

Begin.

    OPEN INPUT StudentFile.

    READ StudentFile

      AT END MOVE HIGH-VALUES TO StudentCount

    END-READ.

    […]

STOP RUN.

And here is a sample input file, and the corresponding expected output:

NY        NYC             PS 122            K1000

NY        NYC             PS 122            12000

NY        NYC             PS 122            43000

NY        NYC             St-Judes          40043

NY        NYC             St-Judes          50057

NY        Albany          Green Acres       K0003

NY        Albany          Green Acres       20005

NY        Albany          Green Acres       30010

NY        Albany          Blue Hills        30123

NY        Albany          Blue Hills        40302

NY        Albany          Blue Hills        50067

NY        Rochester       Happy Trails      50076

Gives:

      PS 122                 6000

      St-Judes                100

      NYC                  6100

      Green Acres              18

      Blue Hills              492

      Albany                510

      Happy Trails             76

      Rochester              76

      NY             6686

Note that since I used COBOL in this example, I used fixed length fields, and my numeric values are padded with zeros. You may assume tab- or comma-separated input, and of course the values do not have to be zero-padded. The goal of the exercise is to add up the right values and display them at the right time – not to prove you can parse the input into local variables. Still, there are a few ways your code could get it wrong and the sample data I showed you might trigger some of it. Note that all data is totally fictitious.

2) Fibonacci Sequence

The Fibonacci sequence is constructed by adding the last two numbers of the sequence so far to get the next number in the sequence. The first and second numbers of the sequence are defined as 0 and 1. We get:

0, 1, 1, 2, 3, 5, 8, 13, 21…

Write a function that returns the nth number of the sequence. This should be pretty easy. Your solution here may well be suitable for one of the next mini-challenges.

Note that for this, I mention a single function, but you may choose to have a “setup function” and a “processing function,” as you see fit.

Write the same function, but you may not use a loop; and if you use variables, treat them as constants (within the scope of the function). You may not reassign them.

Write the same function, but you may not use local variables at all.

Write the same function, but the last statement must be a recursive function call. The result of the recursion is returned as-is; it is not transformed in any way, or added to anything. This is a concept called tail recursion, and can be used to optimize processing in languages and compilers that support it.

Write the same function, but this time, you’re not allowed to use recursion.

3) Drawing with a Turtle

If you came to programming as a serious grown-up doing serious programming, you may not have had the chance to play with program builders often suggested to younger programmers. While these tools are suitable to help kids learn the basics of programming, it doesn’t mean that serious grown-ups can’t have some fun too.

Unlike “real” programming, you create your programs by assembling various blocks. There are blocks representing numbers, operations, comparators; there are blocks representing tests and loops; and there are blocks to set variables and blocks to retrieve them. You can even create your own blocks by putting together existing blocks.

One of these program builders is TurtleArt. It is suitable for drawing all sorts of pictures by telling a turtle how to move around. You can lift the “pen” to move to a new location, change the pen color, travel forward and back, and change heading. You can also fill a path you’re drawing so the whole square or circle gets colored. This challenge is to use TurtleArt to draw a flower:

turtle-flower

You can model your flower after mine, but feel free to use your own creative license and come up with a different shape and different colors. If you found this easy, try a tree like the one Michelle Deschênes drew:

arbre 4) 16-Puzzle

Sometimes called a 15-puzzle, this is a small toy often made of plastic, with a 4×4 grid occupied by 15 pieces, each with a part of a picture or drawing on it. The game’s goal is to re-order the pieces by sliding them into the missing “hole” and complete the image. When the image is complete, the missing piece is usually in the lower right corner.

Here is an example of a 9-puzzle from Wikipedia:

Batgirl

We can use Scratch to write our 16-puzzle game. It is very similar to TurtleArt, but it does not require you to install the software. You use Scratch online and you can share your projects with others.

Start with a small puzzle. A 2×2 puzzle does nicely to get used to the algorithms needed. You can create your pieces as sprites, and just put the piece number on it. You can get fancy later and upload cropped images. At first, I don’t recommend trying to scramble the pieces automatically, but do try to detect when the user enters the “winning configuration.” You can then grow your puzzle to 3×3, and eventually get to a complete 16-puzzle.

5) Pascal Triangle

For this challenge, you will use some SQL to compute each row of a Pascal triangle. This is most certainly the wrong tool for the job, no doubt, but that’s not going to stop us.

You may remember the Pascal triangle from your childhood math classes. It starts with a single 1 at the top, then each row after that is built from the previous one, where the first and last number on the row are the first and last number of the previous row, and each number in-between is the sum of the two numbers a little to the right of it, and a little to the left of it, on the previous row. The nth row has n numbers on it. It looks like this:

pascal-triangle

We start with a table definition. Here I’m using MySQL syntax, but this can be done with any SQL database engine:

create table pascal (

  row int not null,

  entry int not null,

  val int not null,

  primary key (row, entry)

);

And we initialize the first two rows. Technically, you only really need the first one, but I find it easier to start at the third row, where you actually have to compute values from the previous row:

insert into pascal values (1, 1, 1);

insert into pascal values (2, 1, 1);

insert into pascal values (2, 2, 1);

You can use a stored procedure to fill in the nth row, or you can use a host language (such as PHP or Java) to call the database.  The only “programming” you’re allowed to do is to pass the row number to your SQL statements. Do not use any flow control (ifs, loops, etc.). Do not use recursive function calls. All you need is insert statements.  Yes, it’s possible.

mysql> select * from pascal where row = 10;

mysql-pascal-row

If you feel more confortable using a NoSQL database, I’m sure you can use that instead. Or, why not try both ways?

6)Sierpiński Triangle

This beautiful fractal is named after Wacław Franciszek Sierpiński, the Polish mathematician who described it in 1915. While its mathematical properties are interesting, it also stands on it own simply on esthetic grounds.

To draw it, you start with an equilateral triangle (one where all the sides are the same length) filled with color. Then hollow out a triangle in the middle, such that each vertex of that triangle is exactly in the middle of each edge of the big triangle. This creates three triangles above, to the left, and to the right of the triangle you hollowed out. You then execute the same procedure in each of these three triangles, and repeat in each of the 9 triangles you now have, then in the 27, and so on. In proper fractal fashion, this can go on forever.

sierpinski-triangle

This challenge consists for you to draw a Sierpiński triangle in an HTML5 canvas. You first have to decide on the shape and size of your canvas, and the coordinates for the triangle:

If each edge has length x, the length h is obtained by drawing a line from the top vertex so that it intersects the bottom edge at right angle. Apply the Pythagorean theorem and find the ratio of h to x.

If you don’t want to work through the math, you can use a canvas of width 220 and height 195, with triangle vertices at (10, 185), (210, 185), (110, 10). Once you have a basic triangle working, add a little animation. Make it render one step per second, so you can see how it progresses.

Once you’ve done the triangle, you can also do the Sierpiński carpet. It is very similar: you start with a square, and break it up into 9 sub-squares. You hollow out the middle, and treat each of the other 8 squares as a Sierpiński carpet. The result is something like this:

sierpinski-square

7) Project Euler

Project Euler is a repository of programming challenges that explore mathematical concepts, from prime numbers to geometry. There are over 400 problems ranked more or less by difficulty. You choose a problem, implement a solution, and once you have an answer to the question, you submit it for verification. If you’re correct, you can then look at other people’s solutions and participate in the forum on that problem.

There is no requirement on the programming language used, since all they want is a numerical answer, so Project Euler is a good excuse to try new programming languages. I find the problems particularly well suited to functional programming such as Scala, Haskell, or Lisp/Scheme. It is a good idea to try various programming paradigms (procedural, functional, object-oriented) to vary how you approach problems and keep your brain nimble. On the other hand, if you’re a regular functional programmer, try something else for your Project Euler attempts. The problems also usually give an answer for a simpler or smaller version of the problem, giving you a good test case for your code; use it!

I hope I have tempted you with these challenges and that you will expand your horizons through them. This should help you think creatively, and no matter what the “Muggles” say, software development is a creative endeavor.

See also:

Comments

  1. This is very good & useful blog i am regular follower thanks for posting wonderful article.Thanks for providing such information.

  2. Michael Murphy says:

    Re-implementing software in the GNU coreutils project is a great way to get programming practice in, especially for newcomers to programming who are looking to program something practical rather than boring math problems.

Speak Your Mind

*