Programming Problems

Ruins

André Roberge has started a project to embed programming challenges in his Crunchy project. Crunchy is a way to embed both Python code and an interpreter into a web page, making it great for Python education projects. I like the idea of collecting both sources of programming challenges, and solutions to them in Python, as a way of spurring interest. Discussion around alternative solutions could get pretty interesting. Anyway, rather than try to coordinate this through the comments on André’s blog, or via email, I created a page on the Python wiki to help organize this: Problem Sets. I listed the 99 Prolog Problems that Andé pointed to originally, and a couple more sources of programming challenges I was aware of. Hopefully more people will fill in both the sources, and some solutions. I’ve started to put up a few solutions, but this is definitely something that would benefit from more participation.

If you know of a good source of programming problems (or want to create one), or want to provide some solutions of your own, or even just kibbitz, please dive in!

Simple text adventure

Stairs down

My daughter was working on her XO and said something like, “Dad, you promised to help me with Python.” It turns out she was working on her first python program, using the bare-bones IDE for the XO, Pippy. (Aside: If anyone has a suggestion for a better environment than Pippy, that runs on the XO, I’m all ears.) I helped her with the syntax of an if statement and explained how else works, and how to quote the strings she was testing against. Looking over her shoulder I see that she’s got a minimal version of a text adventure game shaping up. I thought this would be a good opportunity to introduce her to lists and dicts, so I put together an email for her, so she would have it to refer back to later. Here is what I wrote:

In Python there are some powerful data structures for organizing your
code and information. You can also build your own, and I’ll show you
how to do that soon, but it is amazing what you can do just with what
is built in. Three of the key structures are lists, dicts (short for
dictionaries), and tuples. Tuples are similar enough to lists that I
will only talk about lists and dicts for now, and we can talk about
tuples later. Also, it is important to know that when I talk about
“strings” I mean text, which is a string of characters, generally
surrounded by either single quotes ‘like this’ or double quotes “like
this”.

Dictionaries

Dicts are a lot like real dictionaries: there is something you use to
look something else up. With a real dictionary you use the spelling
of a word to look up its definition. With python dictionaries, you
can use a wide variety of objects to look up other objects. The
objects you look up can be anything: strings, functions, even lists or
other dictionaries. The objects you use to look up with are required
to be things that cannot change, but usually they are strings.

For convenience we call the things we use to look up with “keys” and
the things that are looked up “values”. In the case of a real
dictionary, the key is the spelling of a word, and the value is the
definition.

There are two ways to create a dict and assign it to a variable, in
this example the variable is “my_lookup”. There is the dict()
constructor function, and the literal notation.

my_lookup = dict(one=1, two=2, three='xyzzy') # dict constructor
my_lookup = {'one': 1, 'two': 2, 'three': 'xyzzy')

Once we have a dict, we can change the value of the keys, add new key/
value pairs, remove key/value pairs, or loop through all the keys:

print my_lookup['one'] # prints ‘1′

my_lookup['one'] = ‘flugelhorn’ # the key ‘one’ is now associated with the value ‘flugelhorn’

my_lookup['four'] = ‘this is the value of the key “four”‘ # add a new key, my_lookup now has four key/value pairs

del my_lookup['one'] # remove a key/value pair, my_lookup now has keys ‘two’, ‘three’, and ‘four’

for key in my_lookup:
print key, my_lookup[key] # will print each key with its value, in random order

The last point is important: dicts do not keep any specific order for
their keys. If you need to have the keys in order, you need to sort
them first. Usually this is not a problem.

For more information on dicts and things you can do with them: http://docs.python.org/lib/typesmapping.html

If you do need ordering, then you would generally use lists. Lists
keep what you put into them in order. They can grow or shrink as you
put things in or take them out, and you can put pretty much anything
into a list, including dicts or other lists. Getting or putting an
item into a list looks a lot like getting or putting an item into a
dict, except the keys are always integers. By now you probably know,
or can guess, that the first item in a list is 0, followed by 1, then
2, etc. You can also count down in a list: the last item is -1, the
next-to-last is -2, etc.


my_list = list(1,2,3,4)
my_list = [1,2,3,4] # create a literal list

So far my_list may not be what you expect. What is the value of
my_list[1]?

print my_list[1] # prints 2 because the indexes (like keys) of the list start with 0
my_list = [4,8,16,32]
print my_list[1] # prints 8

You can change any value in a list

my_list[2] = "new value of two"

You can add new values to the end of a list

my_list.append(64)

And you can go through all the values of a list:

for value in my_list:
    print value

OK, so what does all of this have to do with games?

Here is a simple example game. See if you can extend it to do some
more things, like dropping an item (or all items), or the ‘look’
command to show the long description and the room’s contents. What
else would be good to add?

'''
Simple dungeon game
'''

character = {'inventory': [], 'location': 'west room'}

dungeon = {
    'west room': {
        'short description': 'west room',
        'long description': 'a sloping north-south passage of barren rock',
        'contents': ['pail of water', 'dragon tooth'],
        'exits': {'east': 'centre room'}
    },
    'east room': {
        'short description': 'east room',
        'long description': 'a room of finished stone with high arched ceiling and soaring columns',
        'contents': [],
        'exits': {'west': 'centre room'}
    },
    'centre room': {
        'short description': 'centre room',
        'long description': 'the very heart of the dungeon, a windowless chamber lit only by the eerie light of glowing fungi high above',
        'contents': ['golden key', 'spiral hourglass'],
        'exits': {'east': 'east room', 'west': 'west room'}
    }
}

while True:
    room = dungeon[character['location']]
    command = raw_input(room['short description'] + ' > ')
    command_parts = command.split(None, 1)
    verb = command_parts[0]
    obj = command_parts[-1] # if the user only types one word, both verb and obj will be the same
    if verb in ['east', 'west', 'north', 'south', 'up', 'down', 'in', 'out']:
        if verb in room['exits']:
            character['location'] = room['exits'][verb]
            room = dungeon[character['location']]
            print 'You are in', room['long description']
            for item in room['contents']:
                print 'There is a', item, 'here'
        else:
            print 'You cannot go that way'
    if verb == 'inventory':
        print 'You are carrying:'
        for item in character['inventory']:
            print '   ', item
    if verb == 'quit':
        print 'Goodbye'
        break
    if verb == 'take':
        if obj == 'all':
            if room['contents']:
                for item in room['contents'][:]: # this part: [:] makes a copy of the list so removing items works
                    print 'You pick up the', item
                    character['inventory'].append(item)
                    room['contents'].remove(item)
            else:
                print 'There is nothing to take!'
        else:
            for item in room['contents']:
                if obj in item: # does the word in obj match any part of the text of item?
                    print 'You pick up the', item
                    character['inventory'].append(item)
                    room['contents'].remove(item)

That’s it for now. I hope this was clear. Feel free to ask me
question.

Love,

–Dad

Apologies

Mandala

I wanted to apologize for spamming Planet Python (and anyone else that happens to subscribe) with old posts recently. After spending many of my free hours for the past year noodling around with my weblog software (and the myriad of problems getting anything to run persistently on Dreamhost), I finally gave up and switched to WordPress. I’ve imported my old blogs for the sake of continuity (from Blogger and my own custom weblog, but not going back to Manila yet), and mapped the old URLs with redirects, so things should be fairly transparent to the casual observer.

A couple of good things came from my time wrestling with my own software. I learned a lot more about WSGI. I got to evaluate TurboGears, Django, web.py, Pylons, and raw WSGI. I learned more about Atom syndication and AtomPub. And while I was doing all that, WordPress got semi-decent Atom 1.0 support and also began to support tagging: two of the reasons I was rolling my own. It’s still dog-slow, but I think that may have more to do with how DreamHost is running it (as a CGI) than WordPress itself. And since I’m running several other WordPress blogs for family members and friends, at least I only have one system to fight with rather than two.

Another good thing that came out of switching to WordPress, and one of the main reasons I had ripped my old blogging system apart to rebuild it it as a server-side tool, is that my blog supports comments now. I have spent the past year doing a bit more than just twiddling with blogging software, and I hope to have some of my more interesting experiments and some tutorials to post soon. Let me know what you think of it.

The importance of visual programming

Kudzu flower manipulated with NodeBox

Python has a well-earned reputation for being easy to use and to learn, at least for people who have learned programming in other languages first. Lately my kids have been very interested in programming, and I’ve found that Python doesn’t come as easily to 6-11 year olds as it does to adult programmers.

So I see two approaches to this problem, if it is a problem. One, let them use other languages than Python. Two, find (or make) ways for Python to be more approachable. Let’s look at both of these.

Scratch Screenshot

Scratch

For languages other than Python, there are some really good choices. The best language for getting kids interested and up to speed quickly that I’ve found is Scratch, which is a visual, drag-and-drop programming language for games and animations based on Squeak Smalltalk. Scratch allows kids to program without worrying about the syntax, so they can drag blocks together, use the built-in drawing program to create sprites or import images from the library that comes with the environment. They can also share their creations on the web, projects get automatically converted to Java applets when shared on the Scratch website, and the kids can vote for and comment on each others projects.


Learn more about this project

Scratch is great for learning and for sharing. My seven-year-old can download someone else’s project and generally is able to read it to see what is going on, so it is good for building basic programming literacy. It also has some pretty severe limitations: no user-defined blocks, no return values, no file interaction (so no high scores), no network interaction, no dynamic object creation, the program cannot draw on sprites (only on the background), no string variables or any real string handling. It is a great environment for learning to think creatively within its constraints, but my kids also bump up against its limits pretty quickly.

One option that is often suggested as a step up from Scratch is GameMaker, which apparently is a very nice commercial system that lets kids build games. Besides being commercial, it is also Windows-only, which makes it a non-starter in my household. Scratch runs on both Windows and OS X, with a port to Linux being worked on, but as a Windows-free household, GameMaker is right out.

Quartz Composer Screenshot

Quartz Composer

Another interesting system we’ve been playing around with lately is Quartz Composer. This is a program that comes with Apple’s free Developer Tools. Rather than snap-together blocks, as in Scratch, it is a patch-based environment (there are many of these for working with audio): You drag patches onto a workspace, then wire them up by dragging from the output of one patch to the input of another. Different patches have different numbers of connectors and there are a wide variety of patches to choose from, along with template starter projects for screen savers, audio visualizers, and more. This is a popular tool with VJs, and there is a community around it for sharing custom patches and compositions. A composition can be saved and used in various Cocoa programs that take *.qtz files as plugins, such as the Screen Saver or iChat.

While my seven-year-old can create some effects by playing around with the patches and randomly wiring them up, the system as a whole has been too abstract for him and he doesn’t get it the way he gets Scratch. There is a steeper learning curve to literacy with Quartz Composer.

eToys Screenshot

eToys

One more tool we’ve begun to explore is Squeak/eToys. I have tried in the past to understand the Squeak environment, and to grasp eToys. I was amazed how impenetrable this system, ostensibly designed for children, was to me. A while back I read on Ted and Julie Leung’s respective blogs I read about Squeak: Learn Programming with Robots. This book finally gave me a good starting point for learning Squeak, and an introduction to eToys I could understand. Familiarity with Scratch helps too, since I think Scratch came about in part as a way to make eToys more accessible. So far, while I like the ideas behind Smalltalk, I haven’t been able to muster much enthusiasm for Squeak. It’s always been slow on the Mac (the Macs I have now are finally fast enough to make it bearable), and the UI for it is downright ugly.

I realize there are lots of other visual environments out there we could try. Alice and StarLogo are on our radar, for instance. But that is enough to give a sample of both what is available and the journey my kids and I have taken so far.

Turtles

Turning now to Python. Python has some visual tools built in: Tkinter for building a GUI and the turtle library that is built on top of Tkinter. I actually built a turtle library on top of Tkinter once, not knowing that Python came with one. I added a few things: Turtles could follow mouse clicks, and they looked like turtles, not like triangles. There is also the rather more advanced xturtle library, which is quite cool (also built on top of Tkinter). Besides adding more direct manipulation to turtle drawing (point to move, drag to reposition, etc.) I wanted to have the turtles able to write out the resulting scripts, so kids could learn by modifying those starter scripts. Other projects came along though, and I still haven’t finished either my turtle program or my port of xturtle to run on top of PyObjC on the Mac.

Programming for Artists

Speaking of PyObjC, there have been several tools which take advantage of the powerful graphics capabilities of OS X, using the PyObjC bridge to access Cocoa classes and Quartz graphics from Python. The first of these (that I know of) was DrawBot, by Just van Rossum which is now at version 2.0. The 0.9 version of DrawBot was forked to add additional GUI capabilities, but was not differentiated well from the main DrawBot to avoid confusion. Another fork of DrawBot is NodeBox, which also continues on as a current project today and has gathered an ecosystem to it of artists, designers, and many powerful plugin extensions. All of the DrawBot family of tools are inspired by Processing, which is a similarly stripped-down language for graphics processing. While I use NodeBox extensively, and work with the kids with it (my 11-year-old created the logo for her weblog with it), Processing has its advantages too. NodeBox is focussed on creating art works in PDF or Quicktime movies and focuses on making these easy (including very easy to get started with animation). Processing is built on Java rather than Python, and you can embed the resulting tools as interactive art or games directly in a web page as applets. So while the core languages used by both are nearly identical, they diverge quickly based on their extensions or the desired end result. I recommend looking at the galleries for both NodeBox and Processing to get a feel for what they can do. The key goal of these projects is that they are written for artists, not for programmers.

Another tool which is inspired by DrawBot and Processing, but is a separate, cross-platform project, is Winston Wolff’s MakeBot. Besides being the only tool here which works across Windows and Macintosh, MakeBot has games as the end-goal, and is specifically designed with teaching kids in mind (Winston uses it for his Lunar Repair Yard course in NYC). Winston has also started the Command Blocks project to bring some of the drag-and-drop programming ideas from Scratch into Python (and which I’m hoping to contribute to as well).

Graphics for Physicists

The first tool on our tour which handles 3D is VPython (formerly Visual Python, but changed because there was already a Visual Python project, but it’s good to know the history because it still starts as “import visual”). Like the Processing-inspired tools, VPython is designed for non-programmers, although in this case it is designed for physics students to create simple simulations easily, although the possibilities for games and art projects still exist. I love the simple API of this library, if you want a sphere the code is “ball = sphere()” That gets you a grey unit sphere centered on 0,0,0. If you want it a different size, color, or position you can pass them as arguments to sphere or change the properties afterwards. If there isn’t a window yet, one will be created automatically, but of course you can create a window yourself (or more than one). To give a more concrete example, here is a complete, animated program from the VPython examples:

VPython Screenshot

from visual import *

floor = box(length=4, height=0.5, width=4, color=color.blue)

ball = sphere(pos=(0,4,0), color=color.red)
ball.velocity = vector(0,-1,0)

dt = 0.01
while 1:
    rate(100)
    ball.pos = ball.pos + ball.velocity*dt
    if ball.y < 1:
        ball.velocity.y = -ball.velocity.y
    else:
        ball.velocity.y = ball.velocity.y - 9.8*dt

One of the projects I would like to explore is using Python to generate/work with POV-Ray for more advanced 3D rendering than what I can get with VPython, but a good starting point is that there is an extension to VPython that can export its models to POV-Ray.

Taking the Red PIL

The Python Image Library (PIL) is more or less the standard tool for creating non-interactive graphics, but it has its place in interactive graphics as well. I often rely on it for importing and exporting images from PyGame, and it can be used off-line for creating or manipulation graphics to use in an animation or game. It is perhaps a measure of my geekiness that I often find it easier to write a program to create or manipulate some graphics than I do to figure out how to perform the same task in Photoshop or any of the other half-dozen or so graphics programs I have at hand. Lately NodeBox has been my tool of choice for these scripts, but I still use PIL a lot when I’m working in Linux.

Pygame Screenshot

The Once and Future PyGame

PyGame is a great success story for Python. There are real, polished games created with it, like SolarWolf and Pathological. It is also used for teaching (as in the LiveWires course), and in game creation contests such as Ludum Dare and PyWeek. My own experience with PyGame has been something of a love/hate relationship. On the love side, it is easy to set up, works virtually anywhere (on my tiny Nokia N800, for instance) and is quite good at moving pixels around. On the hate side, it is very low-level, and I either have to learn one (of several possible) libraries that add necessary abstractions for events, input, collisions, etc., or I have to roll my own. It feels like programming the Mac, back in the ’80s. Lately I have been trying to do some work with PyGame targetting the OLPC XO and the aforementioned N800, and have been hampered by the fact that many of the really cool extensions to PyGame rely on OpenGL, which neither of those devices have.

There are other cool Python libraries for graphics: Pyglet, PyOpenGL, PyGame. I’ve written stuff for the kids with PyGame, but I think it is still too much for them to manage themselves. And I’m not cruel enough to have thrown OpenGL (which includes Pyglet) at them yet. Let them think the world is kinder than that for awhile yet.

Overall there is a lot of promise in the world of graphics for Python. There is still plenty of work to be done, too. I guess I’d better get coding.

google

google

asus