Need "awesome" programming problems

Discussion in 'Mac Programming' started by jctj, Jun 18, 2013.

  1. jctj macrumors newbie

    Feb 24, 2010
    I am going to be teaching an Intro to Computer Programming class next year in High School. I am looking for examples of motivating problems to give the kids. It is easy to come up with something everyone hates, but there seems to be certain problems whose solutions are interesting enough to gain and keep attention, and whose solutions are hard enough (but not impossible) that there is real pride when the solution is found. I am looking for problems that require for their solution learning how to use various programming tools or ideas, from complete beginner (loops, if-then controls, variables, arrays) to beginning OOP.

    Can you please tell me of computer problems you had to solve (lol - not bugs, not OS updates....) when learning to program that you really remember as being motivational? Please include which language (BASIC, Pascal, C, C++) or simply what type of language (Spaghetti, Procedural, Object-Oriented).

    For example: my "become a geek" moment was in 7th grade when my math teacher challenged the class to figure out 2^64 - EXACTLY. Yes, we all grabbed our calculators (as he knew we would) and got an answer, but we then had a discussion on rounding errors, digits of accuracy, etc. This was back in 1980, so clearly what he was expecting was for us to do the multiplying by hand. Being stubborn and having just learned BASIC on an Apple I or Apple IIe (can't remember which one we had at that time), I was determined to figure it out with a program. It took over 4 hours - multiples of what it would have taken to do it by hand... - but I finally got it perfect so that it showed commas and leading zero's where it needed to. The very first thing I did when I downloaded Chipmunk Basic (Old-style BASIC compiler for Mac - in preparation for my class) was to replicate this program (this time in just 30 minutes, lol). It was amazing to me that, some 33 years later, I could still remember the approach, the problems encountered, and the solutions to those problems. As a teacher, I would call that problem a "significant learning moment" but just because it was significant for me doesn't mean it would be significant for anyone else. So.... I need to know what sort of problems created significant learning moments for all of you, so I can present multiple problems to my class.

    Thank you in advance for your help!

  2. chown33, Jun 18, 2013
    Last edited: Jun 18, 2013

    chown33 macrumors 604

    Aug 9, 2009
    Sailing beyond the sunset
    What programming language will you be teaching?

    I ask because there are some important fundamentals that are frequent hurdles, and they vary somewhat by language. In C, it's pointers, the array/pointer relationship, and structs. I'd also include unions, but that's more advanced than an intro. In any OO language, it's the class/instance dichotomy, inheritance, and overriding.

    In any language, there are fundamental structural patterns, such as linked lists. A singly-linked list is a good choice for C, as an exercise in ptrs and structs. Simple example: read an arbitrary number of lines, then put them in sorted order by length. A book worth looking at is "Algorithms" by Sedgwick (there are language-specific versions). It's clearly written and has good diagrams.
  3. kubaw macrumors newbie

    Apr 18, 2012
    No awesome issue here, but a little tip: instead of jumping onto OOP focus on pointers and recursion first. For me understanding pointers was a milestone in learning programming as an amateur. Years later I was able to win a micro-contest in my class for a fastest solution to count distinct words in a file. My choice of pure C with binary tree was twice as fast as second program, that was using C++' STL. :cool:
  4. 960design macrumors 68030

    Apr 17, 2012
    Destin, FL
    Deitel and Deitel How to Program comes to mind. It had pretty awesome end of chapter question / quizes and some AMAZING programming exercises.

    Elevator, Tower of Hanoi, ect.
  5. ArtOfWarfare macrumors G3


    Nov 26, 2007
    I personally hated the tower of Hanoi and I'm pretty sure most students just look up the answer rather than figure it out.

    Writing a sodoku solver is pretty challenging but rewarding.

    I'd suggest looking through TopCoder's algorithm match archives. They often have interesting problems for a variety of skill levels.
  6. estorstenson macrumors member

    Jan 30, 2013
    Honestly, I fell in love with computers because I wanted to write games. I was probably 13 or 14 when I got my little Texas Instruments computer and it's extended basic cartridge. I would say within a year, I was animating sprites and had written a little star wars rip-off (remember the old atari star wars game?). They were simple and totally amateur, but I loved it and spent hours reading the reference guide to learn how to use new functions.

    You could very easily find a language where the kids build a simple game step by step over the course of the year or semester. Maybe start off learning to position characters on a screen for one assignment (you could have them use for loops to repeat the character, use a 2 dimensioned array to determine positions, etc). Then load in information from a file which is used to position stuff on the screen, etc. All the way until you have a simple pursuer type game with obstacles and goodies to be collected. AI can be super simple, such as a pre-determined path for the "bad guys". You could even provide them the input files for these, leaving it strictly up to them to write the logic for both parts. Key stroke input is pretty easy to learn in any language.

    Python and probably lots of other languages have some open source graphical interfaces which you might be able to use to allow them to manipulate simple graphics instead of ascii characters. There are lots of decent looking trees, dragons and stuff available online that you can freely use.

    They'll probably make fun of the game they created, but I bet they'll have a lot of fun watching it take shape.
  7. ChristianVirtual macrumors 601


    May 10, 2010
    Agree on that one; did it once in JS. Was really fun and something I always wanted to do.

    Another one: Game of Life;with an interesting start screen like moving across the screen or some "violent battle"
  8. jctj thread starter macrumors newbie

    Feb 24, 2010
    It is an Intro class designed to prep kids for AP Programming the following year. Some teachers simply go straight to Java even for the Intro class, figuring there is no need to use out-dated languages. As someone who grew up with all those changes, I would like to have kids have a (granted - small) understanding of how we got where we are now. I don't teach how to use a slide rule, so at some point there really needs to be a cut-off, but here is my very basic outline:

    Option 1:
    BASIC: input-output, program control (If-Then, switch (case), etc.); loops (For-While-Do), variables (types, representation), and arrays. I will introduce subroutines (goto and then gosub) as a segway into a procedural language.

    Procedural: using functions/procedures to clear up the confusion of spaghetti code from BASIC. Not sure which language to use. C is the obvious choice, but I fear for an intro class this would be too involved - all I really want to get at are procedures and pointers. Linked lists are fundamental, but I am nervous about how long that will take kids to work through - the concept is easy, but getting kids to really develop the ability to work with linked lists (and the dreaded sorting routines...) seems to be a major hurdle and may eat up all my time. This could literally be a 1 or 2 class lecture where I just tell them about it, but we do not actually use any procedural language.

    Java: Since the AP Programming is all Java, the sooner I introduce this, the better. Here is where I would address the notion of why we ended up with OOP and its pro's/con's. This is the language/syntax/formatting I want them to really remember moving on. They will be well informed that if they choose Computer Science in college, they MUST learn C, C+, and then C++ as the basis for all other modern languages.

    Option 2: Start with BASIC (as above), then ignore Java, and just go C => C+ => C++. That way once they are done with BASIC (with its, what, 20 commands?!?) all they need to memorize for a language, syntax, formatting, etc., is just C. If they learned C, C+, and C++ picking up Java the next year should be a snap.

  9. ghellquist macrumors regular

    Aug 21, 2011
    Stockholm Sweden
    Things that move

    Things that move...

    We did an elevator in Lego with three stops and buttons to summon th cage at each level.

    What really got me hooked was programming a xy-plotter to write text.

  10. jctj, Jun 18, 2013
    Last edited: Jun 18, 2013

    jctj thread starter macrumors newbie

    Feb 24, 2010
    Compiled ideas so far

    So far, plans are:
    (1) 2^64 question as in OP
    (2) Towers of Hanoi ("just look up the answer" concern noted...)
    (3) Soduku
    (4) Bubble Sort (not going into all the sorting options, but great for linked lists)
    (5) Game of Life

    Areas to Research:
    (1) Deitel and Deitel How to Program
    (2) TopCoder's algorithm match archives

    The "Main Event" I am planning is BattleShip. To the extent practical, I would like to introduce this as early as possible (in BASIC) and then continue to re-visit the game with procedural (if done) and OO versions. The general concept is that I write the interface and each student or team of students writes their own AI for both placing the pieces and making shots on the opponent. Then we can play AI vs. AI - best of 1001 games. Done properly, we could even have the final battle of the top two AI's done in front of the school at Assembly on a projector screen (school of only 300, so yeah, we can do things like that here...) - with the winner(s) getting guarantee A's for the semester.

    I haven't written all of these programs myself yet because I am still working on which programs to teach, etc. Some of this may be a bit over-ambitious, but Battleship is a game that can be programmed very simply (hard-wire placement of ships, shoot every-other square until you win or lose, shooting every adjacent square when you hit something until it is sunk) or very complexly (shooting pattern based on finding largest ship first, then smaller ships, analyzing previous ship locations, analyzing opponent's shooting patterns to influence ship placement, etc.). This one game allows students of all levels of ability or motivation to at least have something to show at the end of the class.

    I love all the comments, folks. Even the "hated Towers" comment because it hadn't occurred to me that this had become *such* a standby that kids would simply find the solution on line instead of figuring it out. I loved the Towers problem because I could play the game with a real (physical) set, and *see* how the recursion worked and then translate that understanding to what the recursive procedure was doing.



    Ooohhhh. I haven't played with it yet (yet....) but the school just got a Maker Bot, and I wonder if there is a way to incorporate that into the course. These days you just upload 3-d files to the maker bot rather than control it directly, but I will have to think about that....

    Also, on "Things that move" I remember - can't remember what it was called - a program in 1978 that had you placed in a room with a number of killer robots and some obstacles. You took a move (using the numeric keypad) and then each robot took one step directly towards you. You won by moving in such a way as to cause the robots to run into obstacles and then die/explode/vaporize/whatever. The computer had *no* screen - it just re-printed the entire room after each move on paper - back when we had continuous reams of paper with the holes on the side.... Man, am I old?!?
  11. gnasher729 macrumors P6


    Nov 25, 2005
    Remove "Bubble Sort" and let the kids figure out how to sort an array by themselves. Bubble Sort is quite confusing and unintuitive. I'd think they would divide up 50% using direct insertion, and 50% using direct selection.

    Then you can let them measure how long it takes to sort 10, 100, 1000, 10000, 100,000 and a million random numbers. That should be _very_ educational.

    And then you can figure out together how you can sort a million random numbers thousand times quicker.
  12. balamw Moderator


    Staff Member

    Aug 16, 2005
    New England

    Sort, and shuffle operations are both really interesting problems that have real world tangibility.

    Shuffle can be applied to a simple blackjack or poker game.

  13. dukebound85 macrumors P6


    Jul 17, 2005
    5045 feet above sea level
    I think it would be alot of fun coding up something and then interfacing it with say a raspberry pi, or a basic pic and circuit board and seeing how your code can actually mechanically interface with things!

    Perhaps programming a chip to interface with an LCD screen outputting ambient air temp? or a sensor that detects if a cup is there where a pump will activate and fill?
  14. jctj thread starter macrumors newbie

    Feb 24, 2010
    I like this idea - this could easily be turned into a competition between student groups. One of the tasks I am trying to teach them is how to look up information themselves and they will learn more by using Wikipedia (or this forum...) and figuring out what is the best sorting method, etc., than the could ever learn from listening to me lecturing.


    My school also has a robotic's team/class. I know the instructor well so we should be able to figure out some coordination there and have my students work on the software part of their robots. I agree that what you program makes more sense or "comes alive" when you can see the results of your logic (or lack thereof) in terms of things moving around.
  15. ArtOfWarfare, Jun 18, 2013
    Last edited: Jun 18, 2013

    ArtOfWarfare macrumors G3


    Nov 26, 2007
    Were I to teach OOP, I would make them work on something that is trivial in OOP BEFORE teaching OOP - let them fail at it completely before you come to the rescue with OOP.

    Too many students don't understand why OOP is great until they've experienced first hand the pain of doing it wrong.

    Also, don't touch #define, teach const.

    You might use the same "do it wrong first" with goto when functions are what is needed. Goto has a single proper use that I know of in C: breaking out two loops in a row (IE, breaking all the way to the outside when control is in a loop in another loop.)
  16. subsonix macrumors 68040

    Feb 2, 2008
    Personally I think problems connected to real world applications are the most motivating. Perhaps a search problem, binary search is pretty simple in concept and also reveals the importance of algorithms when compared to linear search. Parallels could be drawn to something everyone is familiar with, like web search engines, although Google use map reduce which is a big ass hash table. :)

    For languages I think Python or Ruby are better than basic, because both of them is actually used and they are simple. Eventhough both of them are larger than basic (especially including their libraries) you could restrict your use to a small subset to introduce concepts like, conditionals, loops and so on.

    Another interesting language is Processing, which gives instant gratification by creating graphics, and at the same time still have the same basic constructs, loops, conditionals etc. When you get the Processing IDE everything is set up so that you can see the results immediately in the environment. There are lots of examples available at and since there is also a JS library available you can see it in the browser here.
  17. ArtOfWarfare macrumors G3


    Nov 26, 2007
    Oh yes, binary search is excellent.

    It's also great to compare exhaustive on NP-Hard problems vs. greedy and various other things you can try to do to approximate an answer (although perhaps branch and bound would just go over their heads...)

    At the same time though, it's important to teach the dangers of premature optimization. Always write the most legible code possible, first. Only reduce legibility in the event that you can definitively say that the particular spot is utilizing unacceptably large amounts of resources and that another method will do better, and in that case, comment it heavily.
  18. PatrickCocoa macrumors 6502a

    Dec 2, 2008
    Run Away! Run Away!

    Stay far, far away from object oriented programming.

    Stay far, far away from pointers.

    Both of those require a level of abstraction that can kill dead any interest in programming before they experience the joy of creating new worlds. Both of my daughters took Java in high school and ran away screaming. One of them later graduated college with a math degree and the other is currently majoring in chemistry, so they're not science/math/complexity adverse.

    Stay far, far away from anything that gets in the way of immediate gratification.

    What they need to learn is variables, program flow, and simple input/output. This will give them a taste of creating new worlds and the excitement of programming.


    My suggestions:
    - a guess the random number between 1 and 10 game. The user inputs a guess, the program returns High, Low, or Match! That will take a couple of days. Then have someone else write a program to do the guessing (have them run the programs on separate computers and manually type the guesses in). Someone will stumble on binary search!

    - a program that computes the average speed in MPH given the time it takes Usain Bolt to run 100 meters (9.58 seconds) and 200 meters (19.19 seconds). This is a simple input a number, crunch it though a formula, and output it, but that's a building block skill that will be much needed later in their programming career.

    - a program that adds up the integers between 1 and an input less than 1000. Then if you want you can casually mention Gauss's solution 250 years ago.

    - a space attack game where you shoot either phasers or photon torpedoes, the enemy randomly picks shields or evasive manuvers (each of which have a different effectiveness against the two types of attacks). Or any game where there are two attacks and two defenses.
  19. pianojoe macrumors 6502


    Jul 5, 2001
    N 49.50121 E008.54558
    Another thumbs up for Robert Sedgewicks "Algorithms in C" book. I'd focus on

    1. sorting, because its thrilling to hunt down even better algorithms, and you can explain by creating simple yet instructive animations
    2. trees, because they're elegant and magic
  20. Duncan C macrumors 6502a

    Duncan C

    Jan 21, 2008
    Northern Virginia
    I agree with some of the others that getting to hairy too soon would be a mistake.

    My first "Real" program was a simple game for the Apple 2 called Blockade, written in Integer Basic. It was like snake for 2 people, where you tried to box in the other person with your snake, who's tail got ever longer. That would be too much first first program however.

    Games are good though.

    How about a hangman game, developed as a team?

    Simon (memory game, remembering increasing sequences of random notes/colored lights flashing)

    A recursive routine for calculating factorials? Easy to write, fairly simple to understand once you get the idea of recursion.

    I've also written a prime number generator that used a fixed-sized C array of integers to save the primes it found. It tested each candidate number against all previous primes. It seeded the array with 2 and then only looked at odd numbers.

    I then fine-tuned it to try dividing each candidate against all previous primes up to an arbitrary value, and then beyond that value, calculate the square root of the prime and stop checking for prime divisors once I reached the square root.

    You can calculate a million primes pretty fast with this algorithm. You could then talk about faster algorithms, and how large primes are useful in cryptography.

    You could walk the class through the steps of creating a very naive generator, then talk about possible enhancements (first dividing by all numbers less than the candidate, then only checking against the previous primes, stopping at the square root, only calculating the square root once/candidate, etc.) Measure performance all along the way to illustrate optimizing code.

    I've also used a large word list to pick 2 random words as a password generator. With a word list of 100,000 words you get very random passwords that are easy to remember. This has the advantage of being dirt-simple to do and real-world useful. The passwords are often funny.

    I also wrote a polar equation graphing program in my trig class in high school and demonstrated it to the class. You had to modify the code to add a new equation, which was fine for teaching (an equation parser is way beyond an intro class.) Requires an understanding of trig.
  21. ianray macrumors 6502

    Jun 22, 2010
  22. 960design macrumors 68030

    Apr 17, 2012
    Destin, FL
    I just picked up a Romo from I have no idea how practical it will be for the app programming club, but I thought it was cute and would look into the API and see what it could do.

    I highly recommend as a way to teach programming to students. It helps students visualize OOP and they will be publishing 'scenarios' within days.

    I imagine it could be used as a step off to bluejay and then eclipse their senior year.
  23. hhas, Jun 19, 2013
    Last edited: Jun 19, 2013

    hhas macrumors regular

    Oct 15, 2007
    the problem with today's programming pedagogy... is today's programming pedagogy

    Motivation is easy: every kid wants to make their own games. Those games might be shooters, they might be world builders, they might be social; that'll vary according to individual tastes. Lots of interesting CS-y problems there, like graphics, physics, path finding/AI, network comms, etc. that are considered 'hard' in themselves but these days have extensive library support.

    The real challenge isn't teaching students mechanistic details like loops, conditionals, values and variables, nor even how to assemble larger programs using prebuilt libraries, it's teaching them structured thinking, independent learning and analytical problem-solving skills. The most important concept in all of computer science is abstraction (to quote Guy Steele), so anything else you have to introduce before abstraction that is just diverting them from that, filling their minds with distractions and trivia instead of instituting a clear framework for thinking.

    Unfortunately, popular languages today (C, Java, Python, Ruby, JavaScript, etc) with their love of special forms draw far too much attention to mechanistic trivia like variables and flow control, encouraging novices to believe that these hardcoded, low-level features are central and unique concepts in programming. That in turn draws their attention away from what's really important, which is the tools and techniques for extending the basic language by adding your own more specific features on top of the general ones already there. (Or, to put it another way: sorry Algolers, but the Lispers were right after all.)

    Basically, if you really want to understand the problems with CS pedagogy today, you need to go right back to Papert's work on LOGO and look at how he approached it. Bear in mind that Papert was successfully teaching abstraction to 8 year olds. Of course, he wasn't teaching programming specifically; he was teaching structured thinking and problem solving, and the LOGO language and environment was just a good platform for that.

    The original turtle system gets a lot of snark now for being so 'primitive' and 'limited' in features, but that was the point. When the only predefined drawing operations are 'forward', 'left turn', 'pen down' and 'pen up', they are quick and easy to learn and are a direct representation of atomic physical operations so contain no abstract mysteries of their own. Naturally, once users master these commands they want to perform more sophisticated operations, like drawing complex shapes such as a 'house', a 'person' and so on. The obvious way to construct complex shapes, of course, is to arrange the existing forward/turn/up/down words into longer and longer sequences until they produce the required shapes - and in a language like BASIC this is all you would learn to do; thus BASIC creates the impression of empowering users, but really all it does is create unthinking menial drones, like Charlie Bucket's dad screwing the caps on toothpaste tubes eight hours a day.

    With LOGO, a student will easily fall into this behavior too as part of their independent learning process, but this is where the educator would step in, introducing the student to the mind-blowing concept that they can in fact expand the existing, limited vocabulary with much more powerful and expressive words of their own. Thus the student is introduced to LOGO's 'procedure' feature, and shown how they can define new words like 'rectangle', 'triangle', and 'circle' as compositions of existing words, so that instead of writing 'fd 100 lt 120 fd 100 lt 120 fd 100' every time they want to draw a triangle they can just say 'triangle' and a triangle is drawn for them. And then they can be shown how to parameterize their own words, so that they can write 'triangle 50', 'triangle 100', etc. to create any size of triangle using the same word. And once they've got the basic principles of word composition then they can create even more powerful task-specific words that do exactly what they want. For example, a 'house' word is simply a composite of 'rectangle' (the front wall) and 'triangle' (the roof above it), and since that's a bit more complicated to get right they can be shown how how to learn by making mistakes, then troubleshooting and correcting them (i.e. debugging).

    Along the way, of course, students can be introduced to other useful words like 'if' and 'repeat' which they might find useful. While they are certainly useful, they are not initially essential so can be completely ignored while teaching the far more important concept of word composition, And because the are just ordinary words, not special forms with their own unique and important-looking syntax and behavior rules, once they are introduced to them the user is not deceived into thinking that these built-in words are more important than, or any different to, their own words. Which is exactly as their mental priorities should be: after all, what's of most importance to the student themselves: 'if' and 'repeat', or 'house' and 'tree'?

    By the time these learners are drawing elaborate landscapes full of highly detailed buildings of various shapes and sizes, their thinking is much more sophisticated than that of the modern BASIC/JavaScript/Processing/whatever student, who is simply handed a much more powerful 'helpful' language pre-packed with special keywords and syntaxes and libraries full of complex black-box abstractions like 'rectangle(x0, y0, x1, y1)' and taught to plug in numbers.

    Basically, it's the difference between teaching a student how to use an existing tool, and teaching them how to make their own tools; and it's a priceless educational insight that's unfortunately been swamped by great waves of cheap but shiny trinkets that offer superficial rewards and the illusion of control while mostly just taking it away.

    I posted some comments to similar discussions on a couple months back if you want to read more:

    You should also get yourself a copy of Papert's Mindstorms and read it cover to cover until these concepts 'click' in your own head:

    As to how you fuse those lofty principles with the ugly realities of today's popular toolsets, I wish I could offer some solid advice. But having previously educated myself and others on a 'mainstream' end-user language my eventual conclusion was to go away and design my own end-user language from scratch - which is a project I'm still working on.
  24. mslide macrumors 6502a

    Sep 17, 2007
    Games. Having students do things like bubble sort and all the typical boring programming problems is a great way to bore them.

    My high school programming class was BASIC and we did all sorts of graphical and gaming related things. It was a lot of fun.

Share This Page