The earliest memory I have of ‘programming’ is in the early/mid 90s when my father brought home a computer from work. We could play games on it … so of course I took the spreadsheet program he used (LOTUS 123, did I date myself with that?) and tried to modify it to print out a helpful message for him. It … halfway worked? At least I could undo it so he could get back to work…

After that, I picked up programming for real in QBASIC (I still have a few of those programs lying around), got my own (junky) Linux desktop from my cousin, tried to learn VBasic (without a Windows machine), and eventually made it to high school… In college, I studied computer science and mathematics, mostly programming in Java/.NET, although with a bit of everything in the mix. A few of my oldest programming posts on this blog are from that time.

After that, on to grad school! Originally, I was going to study computational linguistics, but that fell through. Then programming languages (the school’s specialty). And finally I ended up studying censorship and computer security. That’s about where I am today!

But really, I still have a habit of doing a little bit of everything. Whatever seems interesting at the time!

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.

Two More Random Exercises

2012-08-23

Programming Praxis put out the previous had us composing already existing PRNGs).

Two Random Exercises

2012-08-22

here. First, let’s make a function that can turn any die into an unfair coin. Basically, return #t / true if and only if you roll the die twice and get the same result: ; given any random die and a possible outcome ; turn it into an unfair coin (define (die->coin possible die) (lambda () (eq? possible (die)))) From here, use the same idea that I posted about earlier to turn that unfair coin into a fair 50/50 coin:

SEND + MORE = MONEY

2012-08-21

There was here.

There are a few ways that you could brute force the problem (discussed in here.

Life isn't fair...

2012-08-20

…but if you have an unfair coin, you can fix it!

Based on this post over at Lauren Ipsum, you can use statistics to make any unfair coin (defined as something that can return either heads or tails with some arbitrary but constant percent chance) into a fair one with a 50/50 chance of heads or tails.

The loneliest number...

2012-08-17

I was reading the io9 article Why four is the nemesis of happy numbers and it got me thinking. Are there actually any cycles other than the one stated in the article? Why or why not?

OpenID - Part 2

2012-07-20

I wrote yesterday about getting OpenID up and running, but when I played with the code a bit more today, I realized that something funny was going on. Yahoo worked exactly as I expected, when I clicked on the link for the first time, it would take me to the Yahoo login page and then to a page to grant the proper permissions. All well and good. The same with Google.