Planet Scheme

March 27, 2015

Programming Praxis

String Re-ordering

Today’s exercise is a fun little interview question:

You are given a string O that specifies the desired ordering of letters in a target string T. For example, given string O = “eloh” the target string T = “hello” would be re-ordered “elloh” and the target string T = “help” would be re-ordered “pelh” (letters not in the order string are moved to the beginning of the output in some unspecified order).

Your task is to write a program that produces the requested string re-ordering. 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 27, 2015 09:00 AM

March 24, 2015

Programming Praxis

Excellent Numbers

Today’s exercise channels our inner Project Euler:

An excellent number n has an even number of digits and, if you split the number into the front half a and the back half b, then b2a2 = n. For example, 3468 = 682 − 342 = 4624 − 1156 = 3468, so 3468 is an excellent number. The only two-digit excellent number is 48 and the only four-digit excellent number is 3468. There are eight six-digit excellent numbers, 140400, 190476, 216513, 300625, 334668, 416768, 484848, and 530901, and their sum is 2615199. What is the sum of the 10-digit excellent numbers?

Your task is to compute the sum of the 10-digit excellent numbers; in the spirit of Project Euler, your solution should take no more than one minute of computation time. 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 24, 2015 09:00 AM

March 20, 2015

Programming Praxis

Matrix Transpose

Transposing a matrix turns rows into columns and columns into rows; for instance the transpose of the matrix below left is the matrix below right:

11 12 13 14 11 21 31
21 22 23 24 12 22 32
31 32 33 34 13 23 33
14 24 34

That’s easy enough to do when everything fits in memory, but when the matrix is stored in a file and is too big to fit in memory, things get rather harder.

Your task is to write a program that transposes a matrix to large to fit in memory. 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 20, 2015 09:00 AM

March 19, 2015

Ben Simon

The "Funny, It Doesn't Look Like a Linux Server", Server

Check out the cutest edition to our Linux family:

What you're looking at is a TP-Link TL-WA850RE WiFi range extender. A while back, I was having WiFi woes, so I picked up this $30 WiFi extender from Amazon. Turns out, the extender didn't help matters much, so I decided to put it to use in another way.

I installed OpenWRT on the device. OpenWRT is a Linux distribution designed for routers and the like, and it caught my eye because it had confirmed support for this particular device. Installing OpenWRT was almost too easy. I grabbed the .bin file (it was in the ar71xx » generic subdirectory) and used the upload firmware option that was available in the built in web based UI.

In just a few minutes I turned this hunk of white plastic into a Linux box, which, well did nothing. Through some small miracle, I was able to hook it up to a cable and telnet to it.

The first order of business was to configure this device as a WiFi client (or station) rather than the default configuration of being an access point. My hope that was once the device was in client mode, I could plug it into the wall in a random spot in our house, it would then boot up and I'd be able to telnet/ssh to it.

I found this and this article handy is setting up client mode on the device. However, it was ultimately this bit of advice that made all the difference:

If the target network uses the 192.168.1.0/24 subnet, you must change the default LAN IP address to a different subnet, e.g. 192.168.2.1 . You can determine the assigned WAN address with the following command: ...

I had wanted to setup the lan (wired side) of the device to have a static IP and the wan (WiFi side) to have a DHCP picked up IP. It wasn't obvious, but attempting to have both the static IP and dynamic IP be on the same network caused it to fail. The static IP would be set, but the WiFi side wouldn't ever be properly configured. Here's the configuration that ended up working for me:

# /etc/config/wireless
config wifi-device 'radio0'
        option type 'mac80211'
        option channel 'auto'
        option hwmode '11g'
        option path 'platform/ar934x_wmac'
        option htmode 'HT20'
        option disable '0'

config wifi-iface
        option device 'radio0'
        option network 'wan'
        option mode 'sta'
        option ssid 'SSID_TO_CONNECT_TO_GOES_HERE'  # [1]
        option encryption 'wep'
        option key 'PASSWORD_GOES_HERE_SEE_BELOW'   # [2]


# /etc/config/network
config interface 'loopback'
        option ifname 'lo'
        option proto 'static'
        option ipaddr '127.0.0.1'
        option netmask '255.0.0.0'

config interface 'lan'
        option ifname 'eth0'
        option force_link '1'
        option proto 'static'
        option ipaddr '192.168.2.75'     # [3]
        option netmask '255.255.255.0'

# /etc/config/firewall

# ... trimmed ...
config zone
        option name             wan
        list   network          'wan'
        list   network          'wan6'
        option input            ACCEPT  # [4]
        option output           ACCEPT
        option forward          REJECT
# ... trimmed ...

Some notes from above:

[1] - This is where you specify your router's SSID to connect up with
[2] - For WEP encryption I entered a hex value here, versus text. I used this site to do the conversion.
[3] - This was key: my router will give a 192.168.1.x IP, so this needs to be off that network.
[4] - Once I got everything set up, I was getting a connection refused message when trying to telnet to the server. The wan firewall needed to be changed to allow access

Once this all got hashed out, I was able plug the device into a random spot on the wall and telnet to it. Success! And yet, where do I go from here?

Obviously this is useful for educational purposes. I've already had to brush up on my basic networking skills to get this far, and there's plenty more to learn. Heck, you could use this $30.00 router to learn about life on the command line and generally how to be a Unix geek.

OpenWRT, however, is more than just a learning platform. There's a large number of software packages available, and they can be installed using opkg with ease. Turning this bad boy into a web server or the like should be easy enough. I was even able to install a version of scheme, by grabbing an older sigscheme package:

root@pipsqueak:/# opkg install http://downloads.openwrt.org/attitude_adjustment/12.09/ar71xx/generic/packages/sigscheme_0.8.3-2_ar71xx.ipk
Downloading http://downloads.openwrt.org/attitude_adjustment/12.09/ar71xx/generic/packages/sigscheme_0.8.3-2_ar71xx.ipk.
Installing sigscheme (0.8.3-2) to root...
Configuring sigscheme.
root@pipsqueak:/# sscm 
sscm> (map (lambda (x) (* x 9)) '( 1 2 3 4 5 6))
(9 18 27 36 45 54)
sscm> (exit)

Ultimately, what will make this useful is if I can find an application for the device that leverages its near invisible profile and dirt cheap price. If I was in the security business, or a nerd-action-novel writer, then the uses would be pretty obvious. Walk in, plug in device, walk out. And bam! you've got a server that can try to worm it's way onto the network. But for myself, I'm going to have to think a little more on this. Perhaps the device should live in my car? Or maybe it'll be useful in a hotel room? Not sure, but the technology is just too cool to ignore.

by Ben Simon (noreply@blogger.com) at March 19, 2015 03:09 PM

March 17, 2015

Programming Praxis

Common Elements Of Three Arrays

We have another interview question today. There are several different ways to approach this task, so it makes for an interesting exercise:

Given three arrays of integers in non-decreasing order, find all integers common to all three arrays. For instance, given arrays [1,5,10,20,40,80], [6,7,10,20,80,100] and [3,4,15,20,30,70,80,120] the two common integers are 20 and 80. If an integer appears multiple times in each of the arrays, it should appear multiple times in the output, so with input arrays [1,5,5,5], [3,4,5,5,10] and [5,5,10,20] the correct output is [5,5].

Your task is to write a program to solve the interview question. 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 17, 2015 09:00 AM

March 13, 2015

GNU Guix

GNU Guix recruits for GSoC

This year again Guix participates in the Google Summer of Code under the umbrella of the GNU Project.

If you are an eligible student, your contributions to GNU's package manager and to the Guix System Distribution are welcome!

We have collected project ideas (see also related ideas for GNU dmd) touching a variety of topics. If you are a free software hacker passionate about GNU/Linux packaging, Scheme, functional programming, operating system development, or peer-to-peer networking, check out the proposed projects. The list is far from exhaustive, so feel free to bring your own!

Get in touch with us on the mailing list and on the #guix IRC channel.

Make sure to send your application to Google by March 27th.

About GNU Guix

GNU Guix is a functional package manager for the GNU system. The Guix System Distribution (GuixSD) is an advanced distribution of the GNU system that relies on GNU Guix.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. It also offers a declarative approach to operating system configuration management. Guix uses low-level mechanisms from the Nix package manager, except that packages are defined as native Guile modules, using extensions to the Scheme language.

At this stage the Guix System Distribution can be used on an i686 or x86_64 machine. It is also possible to use Guix on top of an already installed GNU/Linux system, including on mips64el and armv7.

by Ludovic Courtès at March 13, 2015 12:25 PM

Programming Praxis

Prime Power Predicate

In today’s exercise we write a function that determines if a number n can be written as pk with p prime and k > 0 an integer. We looked at this function in a previous exercise where we tested each prime exponent up to the base-2 logarithm of n.

Henri Cohen describes a better way to make that determination in Algorithm 1.7.5 of his book A Course in Computational Algebraic Number Theory. He exploits Fermat’s Little Theorem and the witness to the compositeness of n that is found by the Miller-Rabin primality tester. Cohen proves that if a is a witness to the compositeness of n, in the sense of the Miller-Rabin test, then gcd(ana, n) is a non-trivial divisor of n (that is, it is between 1 and n).

Your task is to write a program that determines if a number can be written as a prime power and, if so, returns both the prime and 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 13, 2015 09:00 AM

March 10, 2015

Programming Praxis

Count All Matches

Count All Matches

Today’s exercise is an interview question from Google, as reported at Career Cup:

Given two strings, find the number of times the first string occurs in the second, whether continuous or discontinuous. For instance, the string CAT appears in the string CATAPULT three times, as CATapult, CAtapulT, and CatApulT.

Your task is to write the indicated program. 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 10, 2015 09:00 AM

March 06, 2015

Programming Praxis

357 Numbers

This question arose at a job-interview site:

Find all numbers divisible only by 3, 5 and 7. For instance, 35 = 5 × 7 is included in the set, but 30 = 2 × 3 × 5 is not because of the factor of 2.

Your task is to write the requested program and determine how many numbers in the set are less than a million. When you are finished, you are welcome to read or run a suggest solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at March 06, 2015 09:00 AM

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