Friday, February 22, 2008

99 problems: looking for volunteers

Some time ago, Dr. Werner Hett created a list of 99 Prolog problems that could be used to skills in logic programming. More recently, a Ruby learner posted a Ruby version of the first 10 problems, and his solutions. This seemed to be a good idea, especially if one makes use of doctests ... and Crunchy :-). So, I've started my own version of these which you can get as a zip file (containing 6 problems and their solutions) from the Crunchy main page. If you have never done so before, to load a local html file within Crunchy, you simply click on the "Browsing" menu on the left hand side and scroll down until you reach the "Closer to home" section and follow the instructions.

Note that with the next version of Crunchy (the current one is 0.9.8.6) you will be able to start Crunchy with an arbitrary file using something like

python crunchy.py --url=full_local_path_or_url

It would be nice if there could be a complete Python version of the 99 Prolog problems. If anyone is interested in helping, please do not hesitate to contact me.

22 comments:

Alex said...

I'd like to help (as long as I can just code Python: no time to learn what Crunchy is!) but you give no indication on how to get in contact with you, whence this comment -- just make a further followup comment and I'll also get it in my email, thanks.

Alex

André Roberge said...

email is andre dot roberge at gmail dot com

If you get the zip file (from the link in the post, look on the right hand side of that page), you will see it contains simple html files, with some Python code in them. You can use these as templates.

If you have a few minutes, you may want to watch the video
here
; there is a small example of how Crunchy deals with doctests in that video.

Paddy3118 said...

Hi again,
I enjoyed doing P28 length sorts.

- Paddy.

Alex said...

I can't really relate to the py-in-html format, but the problems are fun (mostly well treated in the Python Cookbook already) IF accompanied by discussion and alternative. E.g., flatten as posed (with only lists, not other sequences, needing expansion) is easy to do in a recursive generator (you can call list(thegen(L)) to get a list out of flatten as required), the fun trick is a version with recursion elimination (maintain an explicit stack of what iterators you're expanding next -- not posting code here because well-formatted Python appears to be hard to post;-). P08 to P13 are rather easy with itertools.groupby (they're exactly the kinds of jobs it does well!), but it's also instructive to consider how you'd do it directly; similarly P06, as well as being solvable by direct comparison of the list and its reverse as you did, can be solved in other ways (compare each element appropriately, compare first half with reversed second half, etc) which are fun to explore.

Alex

Anonymous said...

Andre, do you want to set up a wiki, or a page on the Python wiki, for these problems/solutions/commentary? I think the real community value is in the alternate solutions and comments, but it is also valuable to be able to tackle a problem that you see no-one has done yet.

Anonymous said...

OK, I took the volunteer bit, and my own advice, to heart and started a set of pages for this on the Python wiki: http://wiki.python.org/moin/ProblemSets . I hope that's OK with you.

André Roberge said...

Alex: The py-in-html format, as you call it, is such that it can be used effectively by Crunchy. Crunchy is an application that allows you to load up an html page in your browser (Firefox or Safari but not IE) and allows you to embed a Python interpreter (and other objects) that you can use on that page.

I agree with your comments that the problems (or rather solutions) should be accompanied by commentaries, alternative solutions, etc. Eventually I'd like to do this.

Dethe: Yes, what you did is OK with me - it's great actually.

What I would like is to build a collection of these (including the other ones you linked to) set up as doctest-based exercises that could be used with Crunchy. With a "complete set", I could see Python being even more widely adopted as a first programming language.

André Roberge said...

I just started a separate project located at http://code.google.com/p/doctests to collect problem sets. When I have a few more than I have now (and with commentaries as suggested by Alex), I will most likely write a separate blog post about it.

Anand said...

I have written a python tutorial with lot of problems. You may like them.

http://pythonprogramming.jottit.com

André Roberge said...

Anand:

Do I have your permission to make a copy of your problems in separate pages (like I started to do for the Prolog problems) to be used as doctest-based problems with Crunchy?

Anand said...

Yes. Feel free to copy any of those problems.

I haven't seen your prolog problems. Where are they?

Anand said...

Have to seen Eloquent Javascript[1]?

[1]: http://eloquentjavascript.net/

I liked its interface very much. It will be very useful to have a some utility like that to make python tutorials.

Btw, is there any reason for writing use your own web handling code. I would recommend using web.py.

André Roberge said...

Anand:

First, thanks for your permission.

The Prolog problems I refer to are the ones I mentioned on the blog post. I've started adapting them for Python - as I mentioned.

Regarding the javascript site you mentioned, I referred to it in a
previous post
. Crunchy can do the same ... and more.

Regarding "web.py", we've tried to design Crunchy so that it has as little external dependency as possible. When we started working on Crunchy, I do not believe that web.py had been created yet. Furthermore, web.py appears to be more for creating static web sites. Crunchy does not create web sites; it fetches pre-existing pages (even from external sites like python.org, either in html or reStructuredText format), process them and displays them in the browser. From the little I have read, web.py appears to be designed to use a database.

Anand said...

No, web.py can be used without any database.
web.py doesn't have any external dependencies, so you can package it
along with your application.

I am the lead developer and maintainer of web.py, you can trust me.

André Roberge said...

Anand: Thanks for the info; I trust you :-)

What would be the advantage of replacing the current Crunchy modules used as simple web server with web.py?

(If it ain't broke ...)

Alex said...

Somebody created an appropriate wikipage and I've been adding some solutions there (and discussion, but only for problem seven) -- so, solutions up to 25 can be found at http://wiki.python.org/moin/ProblemSets/99_Prolog_Problems_Solutions (and freely reused, of course, so feel free to use them as basis of a Crunchy or whatever, with attribution please). Would be nice to add discussion, expand 1-6 (which are now just a pointer to that .zip, not optimally easy to read for somebody reading the web on their phone say;-), etc, but I think that the first priority is having all solutions up there;)

Alex

André Roberge said...

Thanks Alex.

Attribution, in general, is going to be a bit tricky since it anyone can use the wiki (and I don't know of a way to retrieve the history of changes with authors). However, I have made a note of what you wrote.

Anonymous said...

I've already done the first 60 though I think some of the solutions on the wiki defeat the mission statement of the prolog problems: Clarity, Efficiency, and not using built ins, I translated this into not using any import statements and in general just using basic types (tuples, lists, dictionaries) along with recursion, generators, decisions sequences and loops.

André Roberge said...

anonymous:

I would be very interested in getting your solutions - I like the idea of not using any imports as well.

Anonymous said...

I'll give you (or post) my solutions when I am done, I am currently on #67

David Tchepak said...

I had a go at the first 10. I'm a newbie Python coder though :)

Anonymous said...

Once you're done with these easy problems, maybe it's challenging to tackle the (Prolog) problems from The First 10 Prolog Programming Contests.