Two Word Games

2012-10-10

Another day, another post from Programming Praxis. Today they posted a word game that seems simple enough: first find all words in a given dictionary that contain all five vowels (a, e, i, o, u) in ascending order and then find any words (at least six letters long) where the letters are all in ascending alphabetical order.

read more...

A piece of the abc conjecture

2012-09-19

There’s been a bit of hubbub in the in the math world the last few weeks with Shinichi Mochizuki's 500 page proof that of the ABC conjecture. Basically, the conjecture states that given three positive coprime integers a, b, and c such that a + b = c, the product of the distinct prime factors of a, b, and c is rarely much smaller than c. While this may sound strange, there are a number of interesting consequences that you can read about here.

To make a long story shorter, there was a challenge on Programming Praxis that intrigued me, which was to write code that given a upper bound on c would generate a list of all of the triples (a, b, c) such that the product is larger.

read more...

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.

read more...

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.

read more...

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))))

read more...

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:

read more...