Wednesday, March 10, 2021

Inch by Inch–The Inchworm Problem

I am reading a bunch of papers from the SIGCSE 2021conference. The papers are available for free for a limited time.Get them while you can. I started with Exploring the Inchworm Problem's Ability to Measure Basic CS Skills

The Inchworm problem has been around for a while but was new to me. It’s an interesting problem for beginners for sure. Here is the description from TopCoder:

The inchworm is a creature of regular habits. She inches forward some distance along the branch of a tree, then stops to rest. If she has stopped at a leaf, she makes a meal of it. Then she inches forward the same distance as before, and repeats this routine until she has reached or passed the end of the branch.

Consider an inchworm traveling the length of a branch whose leaves are spaced at uniform intervals. Depending on the distance between her resting points, the inchworm may or may not be able to eat all of the leaves. There is always a leaf at the beginning of the branch, which is where the inchworm rests before setting out on her journey.

You are given three int values that specify, in inches: the length of the branch; the distance traveled by the inchworm between rests; and the distance between each consecutive pair of leaves. Given that the inchworm only eats at rest, calculate the number of leaves she will consume.

There is a bit more to the description but that's a start. There were 5 basic ways the paper’s authors found students use to solve the problem. Four are simulations and one is purely mathematical. I confess that a simulation was my first thought about a solution. The mathematical solution is much faster than the simulations.

The paper included multiple solutions and I found a solution on TopCoder pretty easily. That demonstrates a problem typical of interesting programming problems – cheating is easy. The author of the paper use a couple of things to reduce cheating.

For starters, there are few grade points for a solution. I assume the idea is that students will not work too hard to cheat for small point values. I am skeptical of this idea myself. Secondly, and probably a lot more importantly, students were required to document their design and process in digital journals. I had mixed results asking students to document designs in high school. It may be better at the university level. 

Overall, this was an interesting paper and I like the new (to me) project idea. I was thinking about how it might be set up with hints but my fear is that too much scaffolding would force students into one solution rather than letting students get creative.

No comments: