I've been kicking around an idea in my head for some programming challenges for introductory programming, and I think I need to hear input from other voices. From my past experiences, students at that level are simply quite sloppy in their thinking, and they just don't have a lot of mental organization. I'm trying to figure out how to fix that.
As I was thinking about this, I remembered a type of puzzle that was introduced to me a long time ago. It's basically a simplified model of a Turing machine. You have a finite strip of paper with special markings at the beginning and end to let you know that you've reached the ends. And you have a read/write head that just moves back and forth across that strip.
We're going to sweep the state table (the formal language/construct) under the rug and just proceed with a simple flowchart/pseudocode to explain what we're going to do. You can write any code you want, but you only have the following commands:
* Read/Write: Reads the value or writes a specific value in the position of the head. My memory was that you could only have the symbols 0 or 1, but that's not absolutely necessary.
* Left/Right: Moves the head left or right. If you attempt to move left when you're at the first position there's a feedback that lets you know you're at the beginning. And similarly on the end of the right side.
I don't remember being given any memory to work with, but that can be flexible.
And my recollection about this starts to run dry pretty quickly after that. I remember there being little puzzles. They all started with a random collection of 0s and 1s. For example:
* Move all the 1s to the left or right.
* Create alternating 0s and 1s (or determine this is not possible).
And... that's it.
The basic idea is that anyone can look at that and say "That's easy" but when you actually get them to explain how they would do it step-by-step (ie, using the four commands), they reach that level of cognitive dissonance where they *know* they can do it, but have a hard time explaining exactly what they're doing. And that's what forces them to really slow down and pick things apart more carefully.
So here are my questions:
1) Does anyone have any recollection of something like this? Maybe it was in a magazine or something? I don't think it was from a book or a textbook. There may even be lots of implementations of this idea floating around, and I just haven't looked in the right places.
2) Do you think that these puzzles could be beneficial to students? Or do you think it's "too much" or "too difficult" or "not in the right direction" to try to do this early on?
3) Can you think of any other programming puzzles that would make use this structure?
As far as implementing their plan, I have a pretty basic Python module that I think should do it.
Code:
class Turing:
def __init__(self, length):
self.tape = [0] * length
self.position = 0
def randomize(self):
from random import randrange
for position in range(len(self.tape)):
self.tape[position] = randrange(2)
self.display()
return True
def display(self):
for symbol in self.tape:
print(symbol, ' ', end='')
print()
for _ in range(self.position):
print(' ', end='')
print('^')
def move_right(self):
self.position += 1
if(self.position) == len(self.tape):
self.position -= 1
print('End of Tape')
self.display()
return False
self.display()
return True
def move_left(self):
self.position -= 1
if(self.position) == -1:
self.position = 0
print('End of Tape')
self.display()
return False
self.display()
return True
def read(self):
return self.tape[self.position]
def write(self, value):
if type(value) != type(0):
print('You can only write integers')
return False
self.tape[self.position] = value
return True
