(archive 'newLISPer)

October 9, 2010

egnellahC nilperG ehT

Filed under: newLISP — newlisper @ 22:19
Tags:

I spent a happy half hour today trying to take the Greplin Challenge.

Unfortunately, I managed to complete only the first level. It wasn’t so much that the problem was hard. It was more that I couldn’t find an elegant solution that satisfied me.

The problem is to find the longest substring of a string that is the same in reverse. In other words, to find the longest palindrome.

Here’s my attempt. If the string is in ‘source-string’:

    (for (character 0 (dec (length source-string)))
            (set 'end-of-word
                    (find (source-string character) source-string nil
                            (+ character 1)))

            (when end-of-word
                    (set 'word (slice source-string character
                                    (+ 1 (- end-of-word character))))
                    (when (= (lower-case word)
                                    (reverse (lower-case word)))
                            (push word palindromes))))

    (first (sort palindromes
                    (fn (a b) (> (length a ) (length b)))))

As you can see, it's not exactly a one-liner. But at least it avoids a completely 'brute-force' technique. It looks for likely palindromes rather than testing every possible substring. Apart from that, it just puts all the palindromes in a list and finds the longest later. I'm sure you can produce a more elegant solution!

It might be a few days before I get round to level 2. But don't wait for me - have a go!

Update

I realised later that this algorithm isn't very good. Yes, it finds the correct answer for the particular test case on the Greplin challenge, but it doesn't always find the longest palindrome. For example, if the string contains the substring "hahah", then the longest palindrome found will be "hah" rather than "hahah". That's because I used find to locate the matching end character for each start character. To obtain more accurate results, I'd need to check for every subsequent matching end character in the rest of the string, not just the next one.

Now a brute force technique starts to look attractive. Instead of being intelligent and looking for a prospective end character for each start character, let's just try every possible substring and test it for palindromicity. Hammer time! Yes, it's painful to write such brutal code, but sometimes it's just easier:

(for (begin-char 0 (- (length source-string) 2))
        (for (end-char begin-char (dec (length source-string)))
                (set 'word (slice source-string begin-char 
                    (+ 2 (- end-char begin-char))))
                (when  (= (lower-case word) (reverse (lower-case word)))    
                        (push word palindromes))))
(first
        (sort palindromes
                (fn (a b) (> (length a ) (length b)))))

Finally, a teaser for you. Notice those two lower-case functions? What would happen if you factored them out and placed a single call to it in the line above?

October 1, 2010

Tree fun

Filed under: newLISP — newlisper @ 17:47
Tags:

I stumbled across a neat little piece of code this week, over at Learning Clojure. It’s a simple program that draws fractal trees. I don’t use Clojure here, so I wanted to make a newLISP version that I could draw some trees with. It looked easy enough to translate the algorithm, and, because I didn’t understand the graphical code, I knocked up a simple, and I hope, equivalent-ish version, using the newLISP-GS Java graphics environment. Here’s a screenshot of the luxuriant growth generated so far:

fractal-tree-1.png

And here’s the code.

    #!/usr/bin/env newlisp

    (load (append (env "NEWLISPDIR") "/guiserver.lsp")) 

    (constant 'PI 3.141592653589793)

    (define (deg->rad d)
     (mul d (div PI 180)))

    (define (draw-tree angle x y len branch-angle depth)
        (if (> depth 0)
            (letn ((new-x (sub x (mul len (sin (deg->rad angle)))))
                         (new-y (sub y (mul len (cos (deg->rad angle)))))
                         (new-length (fn () (mul len (add 0.75 (random 0.01 0.1)))))
                         (new-angle  (fn (op) (op angle (mul branch-angle (add 0.75 (random 0 3)))))))
                (gs:draw-line 'T (int x) (int y) (int new-x) (int new-y) '(0.1 0.9 0.1))
                ; for slow drawing: (sleep 10) (gs:update)
                (gs:update)
                (draw-tree (new-angle add) new-x new-y (new-length) branch-angle (- depth 1))
                (draw-tree (new-angle sub) new-x new-y (new-length) branch-angle (- depth 1)))))

    (define (render w h max-depth branch-angle)
        (letn ((init-length (div (min w h) 2)))
            (gs:delete-tag 'T)
            (draw-tree 0 (/ w 2) h init-length branch-angle max-depth branch-angle)))

    ; handlers

    (define (update)
         (gs:set-text 'depth-label (string {depth: } *depth))
         (gs:set-text 'branch-angle-label (string {branch-angle: } *branch-angle))
         (render *width *height *depth *branch-angle))

    (define (depth-slider-handler id value)
        (set '*depth (int value))
        (update))

    (define (branch-angle-slider-handler id value)
        (set '*branch-angle (int value))
        (update))

    ; global variables 
    (set '*width 150 '*height 150 '*depth 12 '*branch-angle 10)

    (gs:init)
    (gs:frame 'f 50 50 530 670 "tree")
    (gs:set-border-layout 'f)
    (gs:set-resizable 'f true)

    ; canvas
    (gs:canvas 'tree-canvas)
    (gs:set-size 'tree-canvas 530 450)
    (gs:set-background 'tree-canvas 0.2 0.1 0.1)
    (gs:set-stroke 1)

    ; controls
    (gs:panel 'controls )
    (gs:set-grid-layout 'controls 3 1)

    ; labels
    (gs:slider 'depth-slider 'depth-slider-handler "depth" 3 15 *depth) 
    (gs:label 'depth-label (string "depth: " *depth) "left")

    (gs:slider 'branch-angle-slider 'branch-angle-slider-handler "branch-angle" 3 18 *branch-angle) 
    (gs:label 'branch-angle-label (string "branch-angle: " *branch-angle) "left")

    ; go for it
    (gs:add-to 'controls 'depth-slider 'depth-label 'branch-angle-slider 'branch-angle-label) 
    (gs:add-to 'f 'tree-canvas "center" 'controls "south")
    (gs:set-translation 200 300)
    (gs:set-visible 'f true)
    (render *width *height *depth *branch-angle)
    (gs:listen)

I like the way that the declaration section of the draw-tree function defines two anonymous functions, new-length and new-angle, which generate new values for the next recursive call. Notice that I had to switch to floating-point arithmetic...it's easy to forget when looking at other languages.

Fractal trees are cool, and it's easy to add a few controls to the script so that you can design different types of tree by adjusting the parameters.

It would be simple enough to add parameters for changing line width, adjusting the colour of the branches, and so on.

fractal-tree-2.png

John's original post was focused on Clojure performance, but that doesn't interest me here, not being a Clojurer. I've never considered the newLISP graphics system to be a speed demon, but that's probably because it always takes a couple of seconds to start up the Java server, on my machine at least. I wouldn't expect interpreted trees to grow as fast as the compiled ones!

As for Clojure: I'm very pleased to see more members of the Lisp family, and Clojure looks impressive and exciting. However, as a non-programmer and amateur scripter I've tried and failed to make progress in learning it so far. But there's always tomorrow.

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.