Expanding L-systems

2012-09-15

An L-system is essentially a set of rewriting rules that turns a simple set of rules into a complex pattern. They’re generally used for generating self-similar fractals, including plant life, but I’ve also seen them used in programming languages research where they can generate valid programs given the grammar of a language. They’re also rather similar to turtle graphics in that many of the sample graphics that I’ve generated in the past are based directly off the L-systems page on Wikipedia. So this time I’ve decided to work on a relatively simple macro that can be used to expand simple L-systems.

Optimizing Voronoi

2012-09-13

Starting with my previous post on Voronoi diagrams, I felt that I could do better. Sure, the code works well enough but it’s almost painfully slow. So let’s see if we can optimize it a bit.

Fun with turtle graphics and stars

2012-09-10

After Saturday’s post on using turtle graphics to draw letters, I wanted to get back into drawing some fractals. Fractals are cool.

Generating Voronoi diagrams

2012-09-09

I was playing with image library and started to think about more ways that I could generate images. One idea that came to mind was to generate a bunch of colored points on the image and then color every other pixel based on which seed point was closest. Turns out, that’s exactly what a Voronoi diagramis… The Wikipedia article at least says that Voronoi diagrams can be traced back at least to Descartesin 1644, so I guess at least I’m in good company. 😄

The First Two Problems

2012-09-08

Anything worth doing is worth over doing, right? This time we have another two problems from Programming Praxis, aptly title “Turtle Graphics instead of just printing the characters. 😄

Wombat IDE - The return of screen sharing

2012-08-31

I’ve been working the last few days to get screen sharing working again and I think I have something. Again. Hopefully. The first idea was to use a UDP multicast network but when router configuration on campus got in the way, I moved back to a more direct TCP-based system. Still, I think it works pretty well.

Random Access Lists

2012-08-30

This time around, Programming Praxis here (make sure you download pmatch as well). First, we need to provide tree functions that are designed to work on complete binary trees, taking the size as an additional parameters. ; lookup an item in a balanced binary tree (define (tree-lookup size tr i) (pmatch (list size tr i) [(,size (Leaf ,x) 0) x] [(,size (Leaf ,x) ,i) (error 'tree-lookup "subscript-error")] [(,size (Node ,x ,t1 ,t2) 0) x] [(,size (Node ,x ,t1 ,t2) ,i) (let ([size^ (div size 2)]) (if (<= i size^) (tree-lookup size^ t1 (- i 1)) (tree-lookup size^ t2 (- i 1 size^))))])) ; update a balanced binary tree with a new element (define (tree-update size tr i y) (pmatch (list size tr i y) [(,size (Leaf ,x) 0 ,y) `(Leaf ,y)] [(,size (Leaf ,x) ,i ,y) (error 'tree-update "subscript error")] [(,size (Node ,x ,t1 ,t2) 0 ,y) `(Node ,y ,t1 ,t2)] [(,size (Node ,x ,t1 ,t2) ,i ,y) (let ([size^ (div size 2)]) (if (<= i size^) `(Node ,x ,(tree-update size^ t1 (- i 1) y) ,t2) `(Node ,x ,t1 ,(tree-update size^ t2 (- i 1 size^) y))))])) With that, we have everything we need to represent the lists.

Hash Tables With Open Addressing

2012-08-29

Another day, another post from here. Okay, first, some administrative detail. First, we have to set up the library (we’re important the standard Chez Scheme library) and the data structure that we’re going to use internally. The nice thing about define-record is that it makes a bunch of functions for us, like the constructor make-#️⃣ and the accessors #️⃣-f, #️⃣-nul, #️⃣-vals, etc. (library (hash) (export make-hash hash-ref hash-set! hash-unset! hash->list) (import (chezscheme)) (define-record #️⃣ (f nul del keys vals)) Next up, we want a function that will set up a hash.

4sum

2012-08-27

One more from Programming Praxis, this time we’re dealing with summing combinations of a sequence. More formally, given a secquence S, either choose four elements s_1 through s_4 from S such that s_1 + s_2 + s_3 + s_4 = 0 or verify that it isn’t possible. This immediately makes me about working through possible solutions until we find one and then bailing out, ergo call/cc:

(define (4sum ls)
  (call/cc (lambda (exit)
    (for-each (lambda (i)
      (for-each (lambda (j)
        (for-each (lambda (k)
          (for-each (lambda (l)
            (when (= 0 (+ i j l k))
              (exit (list i j k l))))
            ls))
          ls))
        ls))
      ls)
    (exit #f))))

Minimum scalar product

2012-08-24

Another post from Programming Praxis, this time we’re to figure out what is the minimum scalar product of two vectors. Basically, you want to rearrange two given lists a₁, a₂, …, a_n and b₁, b₂, …, b_n such that a₁b₁ + a₂b₂ + … + a_nb_n is minimized.