Saturday, December 3, 2011

Where's Waldo - Text style



Ok, it's a word search.

We're always looking for interesting applications to build lessons around. Over the years, I've tried different things when teaching 2 dimensional arrays. Simple game boards, representing a crossword puzzle, tables of various sorts, etc.

This year, JonAlf, one of my amazingly talented colleagues, decided to go with building a word search. I decided to steal the idea. It's a great one.

I thought I'd use this post to go through the project and why I like it.

Ultimately, the students end up with a program that will generate an n by m word search filled with random words from a dictionary. We gave the kids a skeleton of the base class. The only actual code we had to supply was the method that loaded a dictionary file into memory. You can check out the assignment here and the finished code here (we updated the repository as the project developed).


The first part of the project are pretty mundane. The kids write a couple of constructors and toString. Basically just practice traversing a 2D array. The project starts to get interesting at part 2, when they write the methods that add words into the grid. First horizontally:



After they write the method to add words vertically, we can start to refine things. We notice that the routines are essentially the same. The only difference between adding a word horizontally and vertically is  what we add  to the row and column each time. For one, there is a delta column of + 1, for the other it's a delta row. Further, they realize that adding diagonal words just needs both deltas. This leads us to factoring out the common aspects of the code and writing something like:



All of a sudden, they've written one piece of code that can add words in 8 orientations.

After filling the rest of the grid with random letters, we turn our attention to building a random puzzle.

This part of the project involves using an ArrayList of words. Our students frequently mix up array and ArrayList notation early on so by having a project that uses both but in clearly delineated areas, the students can be more comfortable with each.

For this piece, the code is again straight forward. Students run a loop that gets a random word from our dictionary and tries to place it in our grid at a random location choosing one of our possible orientations randomly. We get to see another nice little refinement again when we move from the typical first take at building a random puzzle which uses a three (or more) way if statement to select how to add words:



to using our more general addWords method described above:




When we're all done, we had some time to project the word search on the board and fun was had by all.

Peter, another one of our CS teachers had a great suggestion that I think I'll try. Start a competition to have the students modify the program so that it generates as densely packed  a wordsearch  as possible (giving higher scores first for longer words, then number of words).

Between the way the project broke down, the topics covered and the little refinements, I really enjoyed working with my classes on this project -- I'm hoping they enjoyed it as well.



4 comments:

  1. Neat project! I like how you approach writing the general method later, as a consequence of writing the specific methods. I feel like that iterative development is a process students rarely get to see and do themselves.

    Do you teach the use of try/catch as a normal part of control flow? I would always write explicit bounds checks.

    ReplyDelete
  2. Actually, I've always preferred using explicit checks with if statments. Probably because I cut my teeth as a C programmer. As I say to my students, it's more of a "look before you leap" approach and it's what I encourage.

    On the other hand, we do have to teach them about exceptions.

    I've never found a natural place to deal with exceptions in our curriculum, but since this project had file input and thus an exception anyway, it seemed as good a place as any.

    ReplyDelete
  3. Hmm. I guess I tend to gloss over exception handling and emphasize that exceptions are only thrown when something goes wrong. I also subscribe to this philosophy for Java: http://c2.com/cgi/wiki?DontUseExceptionsForFlowControl

    ReplyDelete
  4. Ben - Nice link -- I pretty much agree with you. The most important thing is that programmers don't assume everything's going to work perfectly and to write code that actively ensures success.

    I can't tell you how many times I've seen code fail due to someone not checking a return value from an open or malloc or something similar.

    ReplyDelete