Planet Scheme

March 03, 2015

Programming Praxis

Three Powering Algorithms

In mathematics, the powering operation multiplies a number by itself a given number of times. For instance, the powering operation pow(2,3) multiplies 2 × 2 × 2 = 8.

Your task is to write three functions that implement the powering operation, with time complexities O(n), O(log n) and O(1) in the exponent. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at March 03, 2015 09:00 AM

February 27, 2015

Programming Praxis

Currency Exchange

There is much data available on the internet, and it is often convenient to query that data in a specific way, repeatedly. In that case, the best thing to do is to write a program to automate the request. Today’s exercise is specifically about currency exchange, but anything is fair game, from weather reports to baseball standings.

Your task is to write a program that takes a “from” currency, a “to” currency, and an amount specified in the “from” currency, and returns the equivalent amount in the “to” currency. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at February 27, 2015 09:00 AM

February 25, 2015

Ben Simon

Adventures in Dithering: Making some gray in a sea of black and white

Yesterday I implemented support for printing images in my DropPrint Android app. One issue with the printer is the range of values it prints: mainly it has none. As they say: you can have any color you want, as long as it's black. So a typical photo, which is filled with all sorts of grays, gets turned in a photo filled only with black and white. Like this one:

In some cases this effect may be desirable, but I was curious if I could leverage the halftone effect to simulate shades of gray. With a halftone you trick the eye into seeing gray by by varying the mixture of white and black dots. One Google search told me that while halftoning may get the job done, there's another important option to consider:

If you are doing this because you like the effect, that's cool. But if you just want to dither down to a black and white image consider using a "Floyd-Steinberg" dither. It provides high quality results and distributes the error across the image. http://en.wikipedia.org/wiki/Floyd-Steinberg_dithering

The Floyd–Steinberg dithering looked exactly like what I wanted, and the Wikipedia page even gave me an algorithm I could translate to scheme code:

(for-each-coord src-w src-h
                (lambda (x y)
                  (let* ((old-pixel (rgb->gray (pixels (idx x y))))
                         (new-pixel (if (> old-pixel 128) 255 0))
                         (quant-error (- old-pixel new-pixel)))
                    (store! x y new-pixel)
                    (update! (inc x) y       (* quant-error (/ 7 16)))
                    (update! (dec x) (inc y) (* quant-error (/ 3 16)))
                    (update! x       (inc y) (* quant-error (/ 5 16)))
                    (update! (inc x) (inc y) (* quant-error (/ 1 16))))))

After fixing update! so it wouldn't try to update pixels outside of the image (I'm looking at you (-1, 1)), I was surprised at the quality of the image generated. Here's the same image as above, but with dithering in place:

Look at that, there's now some "gray" in the image!

I'm not sure what to make of the white vertical bars. They are almost certainly a defect in code as I've printed other images that don't have them.

The main issue I have with this algorithm is that it's terribly slow. Dithering a 384x447 pixel image takes almost 30 seconds, with the vast majority of that time spent looping over every pixel in the image. I'm sure I'm doing something inefficient, though it's possible that I'm running into a performance issue with Kawa Scheme. At some point, I'll probably debug it further and see why it's so slow.

Next up: I've got to see if I can get rid of those annoying white bars and then I need to make the Bluetooth connectivity far more bullet proof. When that's done,I should have a pretty dang functional app.

As usual, the DropPrint source code can be found here.

by Ben Simon (noreply@blogger.com) at February 25, 2015 01:41 PM

February 24, 2015

Ben Simon

DropPrint 2.0: Image and QR Code Support

This morning I finished up the next iteration of DropPrint, a tiny Android app that drives a thermal bluetooth printer. The big improvements: DropPrint now supports images as well as bar codes.

Check it out:

The image printing protocol for the printer I'm using, a DL58, is pretty dang simple. It consists of little more than sending each row of an image with the following format:

 0x1F 0x10 NN 0x00 B1 B2 B3 ...

Where NN is the number of bytes being sent to represent the line of the image. B1, B2, etc. are bytes containing the relevant bits (0 black, 1 white) for each pixel. In other words, if my image was 1 pixel high and 8 pixels wide (I know, not a particularly interesting image):

  Black Black Black White White White Black White

I'd send this as:

 0x1F 0x10 0x01 0x0 [00011101]

It through me off at first, but that binary header (0X1F 0x10 ...) is sent at the start of each row, not just at the start of the image.

This whole mapping of image pixels to individual bits, followed by compressing the bits into bytes, was an interesting exercise to say the least. Not being much of a hardware interface guy, these are usually details I'm not worrying about. An interesting side effect of printer's binary protocol is that the height of the image is effectively irrelevant. All the printer knows about are the individual rows of the image. I'm using this to my advantage in DropPrint by rotating images that are taller than they are wider. The result is that especially narrow or wide images, like a panoramic shot, actually do well on the printer.

One obvious issue with the printer is that it only prints black and white, there's no ability to send any sort of gray pixels. The result is that your typical photograph, filled with not-quite-black-not-quite-white areas, looks awful when printed. Still, there's hope. The notion of the halftone was invented to solve exactly this problem. Invented back in the 1830's, it's hardly new tech. The idea is to simulate gray by interspersing black and white dots. Just like our brains can be fooled into seeing fluid movement using the principles of animation, we can also be fooled into seeing gray when only black and white is present. Anyway, this is an area I'll be coming back to.

With the basic image printing ability out of the way adding QRCode support was quite easy. I grabbed the zxing library and put it it to work. Now when DropPrint discovers a .qrc file, it encodes the text found within as a QR Code and prints that.

Next up: I'll work on improving the image printing quality as well as improving how the app handles being put in the background and losing connection to the printer. Still lots to do, but it's amazing when this guy prints out an image I've sent to it.

Check out the source code here.

by Ben Simon (noreply@blogger.com) at February 24, 2015 01:37 PM

Programming Praxis

Coin Flips

I decided over the weekend to perform a simple test over several random number generators at my disposal; the test counts the number of “heads” that appear in a million flips. Here’s the test:

(do ((n 1000000 (- n 1)))
     (h 0 (if (< (rand 1.0) 0.5) (+ h 1) h)))
    ((zero? n) h))

Applied to the random number generator built-in to Chez Scheme, I get these five results: 500017, 500035, 499968, 499977, and 500009. That’s pretty close to perfect. The random number generator in the Standard Prelude isn’t as good: 499987, 500503, 500422, 499808, and 500264. And the simple linear-congruential random number generator (69069 x + 1234567) % 232 gives these results: 500301, 499445, 500232, 500047, and 498341.

None of those results are unusual (well, maybe the Chez result is too close to perfection), but that’s not what interests us today. What we want to do is assume that the random number generator is biased but still use it to make an unbiased coin flip. Say you have a coin that returns 40% heads and 60% tails. To get an unbiased coin result, flip the coin twice; if you get two heads or two tails, flip twice more, but if you get opposite results, return the first.

Your task is to write a program that delivers unbiased coin flips from a biased coin. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at February 24, 2015 09:00 AM

February 23, 2015

Ben Simon

Just a Little Impossible: Morris Counting

I'll often advise entrepreneurs I talk with that it's ideal if their Software Idea is just a little impossible. ProgrammingPraxis recently published a challenge / solution that fits this description well. It's quirky, but still instructive. Here's my own word-problem based description of the challenge:

Imagine you're given the task at counting entrants to the state fair (yum!). Your boss hands you one of those crowd counter devices and walks away. As you examine the counter you realize that it only counts up to 255. Once the 256th person walks in, your screwed. The counter won't work anymore.

What do you do? Pray that the state fair has 254 attendees? Flee for your life? If you're Robert Morris, you get creative and devise a new way of counting, one that solves this seemingly impossible problem.

Here's what you do: you borrow a coin from your fellow fair employees and you stand by the gate. The first time someone walks in, you click the counter. Now it reads one. The next time someone walks you, you look down at the counter and flip the coin however many times is shown on its face. If your coin comes up heads every time, then you click the button to increment the counter. And repeat.

So if the counter says 8, then you have to flip the coin 8 times in a row. And if you get heads 8 times (unlikely, but do it enough, and it'll happen), you increment the counter to 9.

When your boss comes by and asks how many people visited the fair you bust out your pocket calculator compute 2x-1, where x is the number shown on the counter.

Of course, this won't be the exact number of people who visited the fair, but it will be in the ballpark. It'll certainly tell you if there were 10's, 100's or 1000's of visitors that day. And that's far better data than having nothing.

Here's some random executions of the this algorithm:

In some cases, the number is pretty accurate (524 was estimated at 511, 242 was estimated at 255). In other cases, it's pretty out there (2956 vs. 4095). But still, considering that you're making use of nothing more than a very limited counter and a single coin, the results are quite impressive.

The bigger lesson though is the recipe at play here: find a problem which others think is impossible, solve it, and you're on your way to changing the world. That's not too much to ask, is it?

Here's the code that implements the above algorithm:

;;
;; http://programmingpraxis.com/2015/02/20/morris-counting/
;;

(define (show . words)
 (for-each display words)
 (newline))

(define (heads? n)
 (let ((flip (= 1 (random-integer 2))))
  (cond ((not flip) #f)
        ((and flip (= n 1)) #t)
        (else (heads? (- n 1))))))
        
(define (int-count n)
 (+ 1 n))
 
(define (morris-count c)
 (cond ((= c 0) 1)
       ((heads? c) (int-count c))
       (else c)))
       
(define (morris-value c)
 (- (expt 2 c) 1))
  
(define (trial upper)
 (let loop ((n (random-integer upper))
            (i 0)
            (c 0))
  (cond ((= n 0)
         (show "actual=" i ", morris=" (morris-value c)))
        (else
         (loop (- n 1)
               (int-count i)
               (morris-count c))))))
               
(define (test)
 (for-each trial '(10 50 100 200 500 800 1000
                   1500 2000 5000 7000 10000)))

by Ben Simon (noreply@blogger.com) at February 23, 2015 01:01 PM

February 20, 2015

Programming Praxis

Morris Counting

We have today an algorithm from the early days of computing that is still relevant today: counting a large number of events using only a small amount of memory. The technique was invented by Robert Morris (early unix researcher and NSA cryptographer, father of the RTM of “internet worm” fame) and described in his 1978 paper
“Counting Large Numbers of Events in Small Registers.”

The basic idea is to count logarithms instead of discrete events. Assuming base-2 logarithms, the algorithm is simple:

Initialize a counter C to 0.

When an event occurs, increment the counter with probability 2C.

When asked for the count, return 2C − 1.

It probably seems like a trivial saving to record a count in a single byte instead of, say, a 4-byte integer. But the savings multiply quickly if you need to count a large number of distinct events; the difference between 1-megabyte and 4-megabytes of counters could be significant in a large program where counting is only a small part of the whole.

Your task is to write a program that does Morris counting. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at February 20, 2015 09:00 AM

February 17, 2015

Programming Praxis

Invoice

Today’s exercise comes from a text for a first-level programming course.

          Praxis Grocery Store
               17 Feb 2015

1  2% Milk               2  3.30    6.60
2  93% Ground Beef       1  5.98    5.98
3  Clam Chowder          2  1.78    3.56
4  Honey                 1  4.42    4.42
5  6 Eggs                1  1.18    1.18
   Subtotal                        21.74
   Tax 5.25%                        1.14
   Total                           22.88

Your task is to write a program that prompts the user to enter item descriptions, quantities and amounts and produces an invoice as shown above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at February 17, 2015 09:00 AM

February 13, 2015

Programming Praxis

Closest Pair, Part 2

In a previous exercise we studied the brute-force method for finding the closest pair of points in a set of points by forming all pairs, computing the distance between each of them, and choosing the smallest. That algorithm has time complexity O(n2). Today we will look at a divide-and-conquer algorithm that has time complexity O(n log n.

The divide-and-conquer algorithm sorts the pairs along their x-coordinates, splits the list of pairs in two, recursively finds the closest pair in the two halves, then compares all points for the closest pair that crosses the dividing line between the two sets of points, taking the minimum of the three possibilities. The third possibility is the tricky one. It won’t do to consider all possible pairs. Instead, we consider only those points less than d distance from the dividing line, where d is the minimum of the distances of the two recursive calls. It can be proved, though we won’t do so here, that the third step takes only linear time, so the entire algorithm is O(n log n).

Your task is to write a program that computes the closest pair of points in an input set using the divide-and-conquer algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at February 13, 2015 09:00 AM

February 12, 2015

Grant Rettke

Ben Simon

Thermal Nuclear Bluetooth Printing on Android (minus the nuclear part)

Inspired by this photography idea, I picked up a thermal Bluetooth printer from eBay. Specifically, a model DL58. I was impressed with the Chinese company that sold it to me; my request for access to the SDK was immediately and fully met. While I've got big plans for the printer, the first order of business was to get it printing basic text.

I don't really have any experiencing developing with Bluetooth devices, so I wasn't quite sure what I was in for. Thankfully, the device was discovered and paired with my phone without a hitch (pairing PIN: 1234). The first version of the SDK the eBay seller provided had the printing code wrapped up behind a shared native library. When I couldn't get this to work, the eBay seller provided an updated version of the code. This time, I could see that all the system was doing was making a Bluetooth socket connection to the device and sending text over the socket. Well that's easy enough. The printer does handle images too, and those are sent using some sort special binary header. That's something I'll be figuring out soon enough.

I then went to work taking my new found lessons in Bluetooth printing and turning them into a super simple app. I give you: DropPrint. DropPrint watches the directory /sdcard/DropPrint and when new files are discovered it prints them. Right now, DropPrint only understands two types of file: txt and scm files. I plan to also have it support image files, as well as bar code files (store "foo" in foo.qrc, and a qrcode with the contents "foo" get printed).

There's not much to DropPrint, but here's the requisite screenshot:

DropPrint's handling of txt files is obvious enough. But surely you're wondering what a scm file are all about. Well, it is what you think it is: Scheme file handling.

See, I implemented DropPrint in Kawa Scheme. That makes it trivial to read, eval and literally print scm files. For example, I can drop the following code in DropPrint/fib.scm:

(begin
 (define (dec x) (- x 1))
 (define (fib x) 
  (cond ((= x 0) 1)
        ((= x 1) 1)
        (else
         (+ (fib (dec x)) (fib (dec x))))))
  (let loop ((i 0))
   (cond ((= i 10) 'done)
         (else
          (display i)
          (display " = ")
          (display (fib i))
          (newline)
          (loop (+ i 1))))))

A few moments later, the printer spits out the following:

(Beware: it intentionally deletes the files after printing them)

In the bits-and-bytes world I live in, to actually have something physical generated is amazingly cool.

As implementation languages go, I'm very much warming up to Kawa. It's certainly far more satisfying to use for this sort of project than say PhoneGap, which has a huge number of layers to get to (HTML, JavaScript, PhoneGap code and core Java Code to name a few) before you can work with core Android APIs. I'm not yet sure I can make the case that Kawa is generally better for app development then Java itself, though, with time I'm sure I'll get there. I'm certainly finding it a heck of a lot of fun to program in.

Now that I've got basic printing working, it's time to turn my attention to images. Stay tuned...

by Ben Simon (noreply@blogger.com) at February 12, 2015 01:56 PM

February 10, 2015

Programming Praxis

Project Euler Problem 1

Project Euler is a collection of math problems intended for computer solution, and is one of the inspirations for Programming Praxis. The first problem on Project Euler, which also regularly appears on lists of phone interview questions, asks you to:

Find the sum of all the multiples of 3 or 5 below 1000.

Your task is to write a program that solves Problem 1 for arbitrary n; since the problem is simple, you must provide at least three fundamentally different solutions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at February 10, 2015 09:00 AM

February 06, 2015

Programming Praxis

Two Stream Selection Questions

Today’s exercise provides two questions involving selection from a stream. Both require a solution that takes O(n) time and O(1) space.

First: Given a stream of unknown length, select a random item from the stream, with all items selected with equal probability. For instance, given the stream {A, D, F, A, G} the selection would return A with probability 40% and D, F or G with probability 20%.

Second: Given a stream of unknown length, each item in the stream paired with a weight, select a random item from the stream with all items selected with probability according to their weights. For instance, given the stream {1 A, 2 D, 5 F, 3 A, 9 G} the selection would return A with probability 20%, D with probability 10%, F with probability 25%, and G with probability 45%.

Your task is to write the two programs that select items from streams. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at February 06, 2015 09:00 AM

Ben Simon

Sounds awful, but it's all mine - Adventures in programmatic music generation

A few years ago I discovered the RTTTL "music format." RTTTL, as a quick refresher, was a language used to exchange ring tones. Essentially it's a text file that lists out which notes to play; couldn't be simpler. The textual nature of it means that it's trivial to generate songs using any programming language.

Yesterday evening I had about 3 hours on the train to kill. I had planned to work on my Laptop but the "free" WiFi was apparently maxed out by passengers who had the same idea. So I put the laptop away, busted out the Bluetooth Keyboard and started to brainstorm as to how I could use Scheme to generate sweet, sweet music.

I can tell you that I fully missed the mark on the "sweet, sweet" part. But I did manage to use Scheme to generate RTTTL files, which in turn played on my mobile device. I ended up implementing a series of functions to generate Morse Code from arbitrary text, as well as a function to generate a random song. Here, give a listen to some samples:

The Morse Code needs tuning to be truly accurate, and the "random songs" my program generates are more like random noise. But this is hardly a loss. I've always been curious what an algorithm might be that would generate at least a passable tune, and now I've got the toolkit to experiment with this.

I've included my source code below, and you can grab it from github here.

One feature of RTTTL is that your phone, for historic reasons, probably plays it without needing a special application. The flip side of this, though, is that finding a way to play the RTTTL files outside of your phone is non-trivial. I looked all over Google Play for an app that would convert my RTTTL file to a .wav or .mp3 file, but had no luck. Your typical music player and music publication site (I'm looking at you, soundcloud) is going to be clueless as to what an RTTTL file is. Luckily, I was able to find a recipe that works for converting from RTTTL to .wav. Here it is:

  • Install the SMS-Ringtone-RTTTL-MIDI perl module
  • Grab this script I prepared to leverages this module to create a MIDI file
  • Install some MIDI related tools, including timidity++ and fluidsynth

Once the above steps are taken care of, you can convert foo.rtttl to foo.wav by using the following sequence:

 rtttltomidi < foo.rttl > foo.midi
 timidity foo.midi   # listen to your creation
 fluidsynth -F foo.wav /usr/share/sounds/sf2/default.sf2 foo.mid

That last step was inspired by this post, which also goes on to explain how to convert the .wav to .mp3.

Getting these libraries together sounds tricky, but on my new Linux box the whole process was surprisingly painless.

OK, so now it's your turn. Go off and write some code which in turn writes some amazing music!


;;
;; RTTTL - let's generate some sounds. Below we generate both
;; Morse Code and a random "song"
;;

(define (&& . any)
 (apply string-append
        (map (lambda (x)
              (cond ((number? x) (number->string x))
                    ((symbol? x) (symbol->string x))
                    (else x)))
             any)))
             
(define (implode sep parts)  
 (let loop ((parts parts) (accum '()))
  (cond ((null? parts) (apply && accum))
        (else
         (loop (cdr parts)
               (if (null? accum)
                   (list (car parts))
                   (append accum (list sep (car parts)))))))))

(define (string-head text)
 (substring text 0 1))
(define (string-tail text)
 (substring text 1 (string-length text)))

(define (explode sep text)
 (let loop ((text text) (current "") (accum '()))
  (cond ((equal? text "")
         (if (equal? current "")
             (reverse accum)
             (reverse (cons current accum))))
        ((equal? (string-head text) sep)
         (loop (string-tail text)
               ""
               (cons current accum)))
        (else
         (loop (string-tail text)
               (string-append current (string-head text))
               accum))))) 


(define (rtttl title notes)
 (string-append title ":d=4,o=5,b=160:" notes "\n"))
   
(define (save filename contents)
 (call-with-output-file (string-append "/sdcard/Documents/" filename)
  (lambda (out)
   (display contents out)))) 

(define morse-map
 '((a ".-") (b "-...") (c "-.-.") (d "-..") (e ".")
   (f "..-.") (g "--.") (h "....") (i "..") (j ".---")
   (k ".-.-")  (l ".-..") (m "--") (n "-.") (o "---")
   (p ".-.-") (q "--*-") (r ".-.") (s "...")
   (t "-") (u "..-") (v "...-") (w ".-") (x "-..-")
   (y "-.--") (z "--..")))
   
(define (morse-char c)
 (let ((needle (string->symbol (string (char-downcase c)))))
  (cond ((eq? c #\space) " ")
        ((assoc needle morse-map) => cadr)
        (else (morse-char #\x)))))

(define (morse-word text)
 (let ((chars (map morse-char (string->list text))))
  (implode "|" chars)))
  
(define (morse-string text)
 (let ((words (explode " " text)))
  (implode "_" (map morse-word words))))

(define (morse-notes encoded)
 (let loop ((chars (string->list encoded)) (accum '()))
  (cond ((null? chars)
         (implode "," (reverse accum)))
        (else
         (loop
          (cdr chars)
          (cons
           (case (car chars)
            ((#\.) "c5")
            ((#\-) "a7")
            ((#\|) "p")
            ((#\_) "p,p,p"))
           accum))))))
 
(define (morse-rtttl message)
 (rtttl message (morse-notes (morse-string message))))          
 
             
(define (string-reverse text)
 (apply string
        (reverse (string->list text))))
        
(define (range low high)
 (if (> low high) '() (cons low (range (+ 1 low) high))))
 
(define (random-elt items)
 (list-ref items (random-integer (length items))))
 
(define (random-between low high)
 (+ low (random-integer (- high low))))
 
(define (random-note)
 (let ((note (random-elt '(c c c c d d e f g a p)))
       (len  (random-elt '(1 2 4 8 16)))
       (oct  (random-elt '(5 6))))
       
  (if (eq? note 'p)
      (&& len note)
      (&& len note oct))))
      
(define (random-name)
 (&& (random-note) (random-note) (random-note) (random-note)))
 
(define (random-notes)
 (implode
  ","
  (map (lambda (i)
        (random-note))
       (range 0 (random-integer 100)))))
               

(define (make-buffer)
 (let ((buffer '()))
  (lambda (x)
   (if (equal? x 'get)
       (implode "," (reverse buffer))
       (set! buffer (cons x buffer))))))
       
(define (random-song)
 (let ((chorus (random-notes))
       (buffer (make-buffer)))
   (for-each (lambda (i)
              (buffer (random-notes))
              (buffer chorus))
             (range 1 (random-between 5 10)))
   (buffer (random-notes))
   (rtttl "Music By Scheme" (buffer 'get))))
          
(save "hw.rtttl" (morse-rtttl "Hello World"))
(save "sos.rtttl" (morse-rtttl "SOS"))
(save "random.rtttl" (random-song))

by Ben Simon (noreply@blogger.com) at February 06, 2015 08:13 AM

February 03, 2015

Programming Praxis

Closest Pair, Part 1

Today’s exercise comes from the field of computational geometry; given a set of points in two-dimensional space, find the pair with the smallest distance between them. The simple solution uses brute force to calculate the distance between all pairs, taking time O(n2).

Your task is to write a program that calculates the closest pair of points. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at February 03, 2015 09:00 AM