Lisp Quiz #2?

Lisp Quiz challenges and discussion
Post Reply
aaronla
Posts: 7
Joined: Fri Jan 02, 2009 3:42 am
Contact:

Lisp Quiz #2?

Post by aaronla » Thu Apr 30, 2009 12:35 am

Wow, this area is dead. I liked the first post, but to be honest, I'm very much in the beginners category for both Common Lisp and Scheme.

Seeing as the last thread was started a good 3/4 yr previous, thought it couldn't hurt to post another. Either everyone has left the LispForum-Quiz-of-the-delta-T and I'm talking to myself, or people out there are waiting for #2. I read a little up on the Ruby quiz -- comes originally from the Perl-quiz-of-the-week, which had this in its charter:
The 'regular' quiz can be solved using only techniques and functions found in Learning Perl (3rd edition) by Schwartz and Phoenix. The 'expert' quiz may be difficult. The two kinds of quizzes appear on alternate weeks.
Since the last one was a bit tough, this one should be easy. Plot the mandelbrot set. Define a function (mb rmin rmax imin imax) taking 4 real numbers, that will print-print-plot a 30 row, 50 column image of the mandelbrot set

For example,

Code: Select all

#;> (mb -2.0 1.0 -1.5 1.5)
..................................................
..................................................
....................::::::::::....................
..............::::::::::::::::::::::..............
...........::::::::::::::::://$//::::::...........
........:::::::::::::::::::////$%/::::::::........
.......::::::::::::::::::////$$#$///:::::::.......
.....:::::::::::::::::://////####$/////::::::.....
....::::::::::::::::///$%/$$$$##%$$$////::::::....
...:::::::::::::///////$############$##%/::::::...
..:::::::::://///////$%%##############$///::::::..
.::::::::///$///$////%%#################$/:::::::.
.:::::://////$#%%#%$$%##################//:::::::.
.::::://////$#######%##################%//:::::::.
.////////$%#%#########################%///:::::::.
.////////$%#%#########################%///:::::::.
.::::://////$#######%##################%//:::::::.
.:::::://////$#%%#%$$%##################//:::::::.
.::::::::///$///$////%%#################$/:::::::.
..:::::::::://///////$%%##############$///::::::..
...:::::::::::::///////$############$##%/::::::...
....::::::::::::::::///$%/$$$$##%$$$////::::::....
.....:::::::::::::::::://////####$/////::::::.....
.......::::::::::::::::::////$$#$///:::::::.......
........:::::::::::::::::::////$%/::::::::........
...........::::::::::::::::://$//::::::...........
..............::::::::::::::::::::::..............
....................::::::::::....................
..................................................
..................................................
Common Lisp, Scheme, NewLisp, Clojure -- everyone is welcome.

Extra credit / golf ides:
* Navigation features for zooming and panning
* Other fractal favorites - Koch snowlflake, xkcd valentines fractal, etc.
* Better ascii art generation (such as using characters that correspond to the image contours)

Have fun.

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: Lisp Quiz #2?

Post by findinglisp » Thu Apr 30, 2009 8:57 am

Well done. I have been meaning to come up with a new quiz for quite a while but have simply been swamped with other things. Thanks for taking the initiative.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: Lisp Quiz #2?

Post by findinglisp » Thu Apr 30, 2009 9:00 am

Also, be sure to observe the 48-hour no-spoiler period before posting your code.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

aaronla
Posts: 7
Joined: Fri Jan 02, 2009 3:42 am
Contact:

Re: Lisp Quiz #2?

Post by aaronla » Fri May 01, 2009 11:48 pm

And the no-spoiler period is up. (although we should try to get the next no-spoiler period to expire on Monday next time, as is customary).

Don't want to clutter up things much, but I can't resist throwing my chip in: http://codepad.org/rk6S6he9. Style feedback most welcome -- I'd like to know if my code is putting the proverbial foot in the mouth. ^_^

Unne
Posts: 32
Joined: Sat Jun 28, 2008 6:10 pm
Location: Oregon
Contact:

Re: Lisp Quiz #2?

Post by Unne » Tue May 12, 2009 6:38 pm

This is a neat problem, wish I'd seen it sooner. I borrowed from http://bc.tech.coop/blog/040811.html for the idea of how to render it, and came up with this Clojure code:

Code: Select all

(ns mandelbrot
  (:refer-clojure :exclude [+ * <])
  (:use (clojure.contrib complex-numbers)
        (clojure.contrib.generic [arithmetic :only [+ *]]
                                 [comparison :only [<]]
                                 [math-functions :only [abs]])))

(defn- mandelbrot-seq [x y]
  (let [z (complex x y)]
    (iterate #(+ z (* % %)) z)))

(defn- mandelbrot-char [x y]
  (loop [c 126
         m (mandelbrot-seq x y)]
    (if (and (< (abs (first m)) 2)
             (> c 32))
      (recur (dec c) (rest m))
      (char c))))

(defn- mandelbrot-line [xs y]
  (apply str (map #(mandelbrot-char % y) xs)))

(defn- m-range [min max num-steps]
  (range min
         max
         (/ (+ (abs min)
               (abs max))
            num-steps)))

(defn mandelbrot [rmin rmax imin imax]
  (let [rows 30
        cols 50
        xs (m-range rmin rmax cols)
        ys (m-range imin imax rows)]
    (dorun (map #(println (mandelbrot-line xs %)) ys))))
(download at http://briancarper.net/clojure/mandelbrot.clj)

Some things Clojure does well here:

1. A lazy infinite list works well to generate the Mandelbrot numbers.
2. Functional style doesn't make this much uglier than an imperative style.
3. I like working with ranges of numbers as standalone, concrete sequences. It feels more decoupled than traditional loops, for some reason.

Some things Clojure does not so well:

1. No "built-in" support for complex numbers, so I have to import a bunch of contrib libraries for it.
2. Clojure's package/lib import syntax never ceases to be ugly and verbose in my eyes.
3. I couldn't figure out how to avoid an explicit loop/recur. I tried reduce but didn't have any success.

aaronla your code looks good to me, but my eyes were starting to cross at all those nested loops and lets. ;)

simon
Posts: 16
Joined: Wed May 13, 2009 9:12 am

Re: Lisp Quiz #2?

Post by simon » Wed May 13, 2009 9:20 am

Because of the support for complex numbers, this is pretty simply expressed in common lisp. I've made it a little more flexible with optional height/width arguments but otherwise left along. A clear improvement would be add a look up table into a list of characters ordered by "brightness"....

Code: Select all

(defun mb (r-min r-max i-min i-max &optional (height 31) (width 50))
  (dotimes (i height)
    (dotimes (j width)
      (loop 
         with z0 = (complex (+ r-min (* j (/ (- r-max r-min) (1- width))))
                            (+ i-min (* i (/ (- i-max i-min) (1- height)))))
         for z = z0 then (+ z0 (expt z 2))
         for n from (char-code #\z) above (char-code #\ )
         while (< (abs z) 2)
         finally (princ (code-char n))))
    (princ #\newline)))
It is better to have an odd height, so the "spike" along the axis shows up. Output:

Code: Select all

CL-USER> (mb -2.0 1.0 -1.5 1.5)
zzzzzzzzzzzzyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
zzzzzzzzzzyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
zzzzzzzzyyyyyyyyyyyyxxxxxxxxxxyyyyyyyyyyyyyyyyyyyy
zzzzzzzyyyyyyyyxxxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyy
zzzzzzyyyyyxxxxxxxxxxxxxxwwwvtnvvwwxxxxyyyyyyyyyyy
zzzzzyyyyxxxxxxxxxxxxxwwwwwvvuqrpuwwwwxxxyyyyyyyyy
zzzzyyyxxxxxxxxxxxxxwwwwwwvvtrjartvvwwwxxxxyyyyyyy
zzzyyxxxxxxxxxxxxxwwwwwwvuutrH  Lotvvvwwxxxxxyyyyy
zzzyxxxxxxxxxxxxwwwwwvutnssrp$   prsuutuwxxxxxyyyy
zzyxxxxxxxxxxxwwwvvvvuto QN        @phlivwxxxxxyyy
zzxxxxxxxxxwwvvvvvvuutkn              dtuvwxxxxxyy
zyxxxxxwwwvuptttttttsqh                qnvwxxxxxyy
zxxwwwwwvvvurljphnprq+                 jsvwwxxxxxy
zxwwwwvvvvttp       l                  2svwwxxxxxy
zwwwwuuutskhk                          euvwwxxxxxy
za^Y [ VH#                           cqtuvwwxxxxxy
zwwwwuuutskhk                          euvwwxxxxxy
zxwwwwvvvvttp,      l                  2svwwxxxxxy
zxxwwwwwvvvurljphnprq+                 jsvwwxxxxxy
zyxxxxxwwwvuptttttttsqh                qnvwxxxxxyy
zzxxxxxxxxxwwvvvvvvuutkn              dtuvwxxxxxyy
zzyxxxxxxxxxxxwwwvvvvuto QN        @phlivwxxxxxyyy
zzzyxxxxxxxxxxxxwwwwwvutnssrp$   prsuutuwxxxxxyyyy
zzzyyxxxxxxxxxxxxxwwwwwwvuutrH  Lotvvvwwxxxxxyyyyy
zzzzyyyxxxxxxxxxxxxxwwwwwwvvtrjartvvwwwxxxxyyyyyyy
zzzzzyyyyxxxxxxxxxxxxxwwwwwvvuqrpuwwwwxxxyyyyyyyyy
zzzzzzyyyyyxxxxxxxxxxxxxxwwwvtnvvwwxxxxyyyyyyyyyyy
zzzzzzzyyyyyyyyxxxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyy
zzzzzzzzyyyyyyyyyyyyxxxxxxxxxxyyyyyyyyyyyyyyyyyyyy
zzzzzzzzzzyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
zzzzzzzzzzzzyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

aaronla
Posts: 7
Joined: Fri Jan 02, 2009 3:42 am
Contact:

Re: Lisp Quiz #2?

Post by aaronla » Sat May 16, 2009 8:24 pm

@unne - i wasn't able to run your code because it appears I don't have the contrib libraries. Is that something you have to download separately? I haven't really done much with clojure yet, other than install it and run thru the first tutorial page.

Heh, yeah, the 'do's and 'let's can be a bit dizzying at first. This is what happens initially when a C++ developer learns scheme -- 'do's replace 'for's, and 'let*'s replace sequences of assignments. Hopefully my scheme coding will improve with time.

@simon - wow, that is some serious LOOP-fu. I'd heard that CL's LOOP was its own embedded language, but i think this is perfect demonstration of that fact. Do you find LOOPs to be practical in general, or was this more a good opportunity to take LOOP to extreme?

Wodin
Posts: 56
Joined: Sun Jun 29, 2008 8:16 am

Re: Lisp Quiz #2?

Post by Wodin » Sun May 17, 2009 9:50 am

aaronla wrote:@unne - i wasn't able to run your code because it appears I don't have the contrib libraries. Is that something you have to download separately? I haven't really done much with clojure yet, other than install it and run thru the first tutorial page.
Get clojure-contrib from here (via SVN):

http://code.google.com/p/clojure-contrib/

Run "ant" to package it up as a jar file. If you want the code precompiled to Java bytecode (which is required for some of the contribs like the pretty printer) you need to do this:

Code: Select all

ant -Dclojure.jar=/path/to/clojure.jar
Then start clojure something like this:

Code: Select all

java -cp /path/to/clojure.jar:/path/to/clojure-contrib.jar clojure.main
(or clojure.lang.Repl instead of clojure.main)

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: Lisp Quiz #2?

Post by findinglisp » Mon May 18, 2009 9:23 am

aaronla wrote:@simon - wow, that is some serious LOOP-fu. I'd heard that CL's LOOP was its own embedded language, but i think this is perfect demonstration of that fact. Do you find LOOPs to be practical in general, or was this more a good opportunity to take LOOP to extreme?
Actually, that's only about 6 out of 10 on the LOOP-fu scale. I've seen far worse. 8-)

LOOP looks scary when you first approach it, but you'll quickly find that it's very useful. That said, I'm trending toward using ITERATE now.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

aaronla
Posts: 7
Joined: Fri Jan 02, 2009 3:42 am
Contact:

Re: Lisp Quiz #2?

Post by aaronla » Wed May 27, 2009 10:24 pm

Unne, i really liked the use of iterate, I think it's a great example of lazy infinite sequences. Can you post a quiz next?

(simon, yours was really cool too, but I had to pick one)

Post Reply