Skip to content

A Python solution to the Zebra Problem using logic programming

2016 July 15

In 1962, Life International magazine published a logic puzzle that provided a series of clues about 5 houses that contain people and animals among other things, and asked the reader to figure out which house had the zebra in it:

  1. There are five houses.
  2. The Englishman lives in the red house.
  3. The Spaniard owns the dog.
  4. Coffee is drunk in the green house.
  5. The Ukrainian drinks tea.
  6. The green house is immediately to the right of the ivory house.
  7. The Old Gold smoker owns snails.
  8. Kools are smoked in the yellow house.
  9. Milk is drunk in the middle house.
  10. The Norwegian lives in the first house.
  11. The man who smokes Chesterfields lives in the house next to the man with the fox.
  12. Kools are smoked in the house next to the house where the horse is kept.
  13. The Lucky Strike smoker drinks orange juice.
  14. The Japanese smokes Parliaments.
  15. The Norwegian lives next to the blue house.

This problem can be solved programmatically in a number of ways.  If you already know the technique to solving it (make a table), you can brute force it. However, it’s far more interesting and fun to solve the problem declaratively, using a logic solver.

So what? If it’s a big table, can’t you just dump it into a database and query it with SQL? The trouble is with these kinds of statements:

They drink water in a house next to the house where they smoke Blend.

Such a statement declares a relationship between some house and some other house. The word ‘some’ is actually very important here: it is a logic variable, which acts as a placeholder for a value without specifying a single actual value. It allows the solver to ‘try out’ different possible values and eventually (hopefully) land on a final one.

A logical solution

Here is such a solution using the logpy python library, which is an implementation of the miniKanren logic programming language:

This solution is adapted from / inspired by David Nolen’s solution using Clojure’s core.logic.

(See the full repo of my logpy examples, including an explanatory readme.)

What’s going on here?

If you’ve never done declarative programming, this can be kind of confusing. Think of each clue as a rule or constraint that specifies the way something must be. The solver’s job is to take all those constraints and tell you what (if any) values will satisfy all of them.

Two examples:

(eq, (var(), var(), var(), var(), var()), houses)

Sets up houses as a list of logic variables (each house), each of which will itself contain a list of logic variables (each property of that house), by saying “houses equals a list of 5 logic variables.” Note that this is actually declaring equality, not assignment.

(membero, ('Englishman', var(), var(), var(), 'red'), houses)

Stipulates that one of the houses has both the ‘Englishman’ and ‘red’ properties. The other properties are left ‘blank’ as logic variables, which get ‘filled in’ by the solver.

Once we’ve inputted all the rules, we run the solver by querying for

houses

:

solutions = run(0, houses, zebraRules)

In other words, “What houses meet the requirements in zebraRules?” The answer may surprise you! 😉

Remote desktop control of a Raspberry Pi

2016 June 8
by Tedb0t

Say you want to configure a nifty dashboard powered by a Raspberry Pi. You can attach a keyboard and mouse to it, but that’s for suckers—we want to control it over the network.  Should be simple, right? We’ll just use X11 or VNC!

Wrong.  It turns out that BOTH X11-forwarding and the Raspbian-included tightvnc start new displays instead of controlling the existing one, and as far as I can tell, cannot be used for that purpose. Super lame.  However, there does turn out to be an easy solution: x11vnc.

  1. First you’ll need to get into your Pi, either locally (kb & mouse) or via SSH.
  2. Once you’re in, install x11vnc:
    sudo apt-get install x11vnc
  3. Setup x11vnc for the first time:
    x11vnc -storepasswd

    It will prompt for a password to use for future connection attempts.

  4. To make x11vnc start at login (since we’re assuming this is a dashboard starting up with an x-window session):
    mkdir /home/pi/.config/autostart
    touch /home/pi/.config/autostart/x11vnc.desktop
    nano /home/pi/.config/autostart/x11vnc.desktop
  5. Paste this in:
    [Desktop Entry]
    Name=X11VNC Server
    Comment=Share this desktop by VNC
    Exec=x11vnc -forever -usepw -httpport 5900 -auth guess
    Icon=computer
    Terminal=false
    Type=Application
    StartupNotify=false
    #StartupWMClass=x11vnc_port_prompt
    Categories=Network;RemoteAccess;
  6. Hit Ctrl-O to save and Ctrl-X to exit
  7. Then reboot:
    sudo reboot
  8. Once the Pi’s back up and you’re logged back in, make sure x11vnc is running:
    ps -ef | grep vnc

    In the results you should see:

    ... x11vnc -forever -usepw -httpport 5900 -auth guess
  9. Great! Now you can connect to and control your Pi from the VNC client of your choice. Remember that OSX actually has one already, called “Screen Sharing.” Just hit command-space to search and start typing that name and it’ll pop right up.  Then put this in as the host:
    <ip of Pi>:5900

Enjoy! Let me know if this works for you.

Better account validation in Meteor: t3db0t:accounts-invite

2016 March 10
by Tedb0t

While working on a Meteor project, I needed a way to allow or deny user account creation only at certain places (such as an ‘accept invitation’ route/template).  This turns out to be difficult, because the core accounts package doesn’t provide a way to do a server-side validation of the attempted login.

So after a whole lot of research and hacking, I’ve published t3db0t:accounts-invite.  See a live demo/explanation.

Using it is easy: register a validation callback, and then call inviteWithLogin in the route/template (or wherever) of your choice.

Comments and Pull Requests are welcome at the Github repo.

Complete mobile/large Meteor starter project with Meteoric

2015 July 13
by Tedb0t

meteoricMobileI put together a handy starter project for Meteor that combines a Meteoric (Meteor-Ionic) tab-bar mobile layout with an easily customizable ‘large’ screen layout, giving you a full-featured mobile app and desktop app in one Meteor project.

To use, clone the repo, start meteor, and navigate to localhost:3000.  To check it out as an iPhone or Android app, just do meteor add-platform ios (or android), then meteor run ios-device -p <local port>.

Enjoy, and let me know what you think!  Pull requests welcome.

Importing GitHub issues into JIRA OnDemand

2014 October 23
tags: ,
by Tedb0t

JIRA has a GitHub issues importer, but it isn’t available on the Atlassian Marketplace for JIRA OnDemand, the hosted version of JIRA.  I thought I was going to have to fsck around with a CSV import script but thankfully it’s not necessary: buried in the Atlassian OnDemand docs is a section on “Importing Data from GitHub,” which allows you to import one or more GitHub repos as projects, whether new or existing. I just did it, and it worked almost perfectly, retaining issue comments and everything, with the following caveats:

  • The GitHub repo I was interested in importing was under a GitHub organization.  The importer doesn’t recognize this, so at first the repo didn’t show up in the list.  All I had to do was star the repos I wanted to import, back up and it showed up.
  • The importer will create JIRA users for every user referenced in the issue tracker!!  It didn’t tell me this or give me any options, so you’re going to have to live with it.  In my case it wasn’t a big deal, since several of the users were ones I would have to create anyway.  The problem is that if the user had comments or tickets, you won’t be able to delete them from JIRA.  O_O
  • Only one out of ~160 issues didn’t import, and I suspect it was because of a unicode emoticon in a comment. (?)

Enjoy!

Two Nifty Mechanical Engineering Resources

2013 August 2
by Tedb0t

Today I stumbled across these nifty mechanical engineering resources:

  1. 507 Mechanical Movements,” a wonderful cross between a 19th-century encyclopedia and interactive web resource for all manner of clever mechanisms.
  2. GearSketch, a demo web app and source code for very rapidly modeling gear-based mechanisms.  I’m really impressed with this, and it’s just the beginning—I could see people continuing to extend the code and taking it really far.


On Secrecy & Authority

2013 June 29
by Tedb0t

One week ago, my wife, Lindsey, and I returned home from a fabulous week in Ireland for our honeymoon.  By the time we had landed, Lindsey was suffering from some painful gastritis (she has a very sensitive stomach/GI system) and walking was exacerbating it, so we took advantage of the free wheelchairs being offered right inside the jet bridge.  A very helpful young guy henceforth wheeled Lindsey around the airport. We joked that Lindsey’s red merino wool sweater that we bought in Kenmare adorably exaggerated the “little old lady” look of her in the wheelchair.  We got to the customs booth and presented our passports.  The officer was taking a while with Lindsey’s, so I fiddled around on Instagram on my phone until the officer sternly and sharply instructed me that there is “NO TEXTING” while in the immediate area of the booth (I guess).  Lindsey told me she was still feeling the gastritis pain.  After another couple of minutes I got the impression something was wrong.  They were asking Lindsey if she’d ever notified them of a lost passport. read more…

Strange Loop Talk Online: “Getting Physical”

2013 May 10

I just found out that my talk from the Strange Loop conference last year, “Getting Physical: Networked Hardware with Node.js” is online.  Check it out here!

Sublime Tunnel of Love: How to Edit Remote Files With Sublime Text via an SSH Tunnel

2013 February 4

Eventually you will need to edit a file in-place on a server, for one reason or another (i.e. working on a Javascript front-end that requires templating from a backend); this is partly what Emacs and Vim are for (and they’re both very good at what they do).

There’s nothing wrong with learning either of those tools, but if you really don’t want to, there are options.  If the server is running FTP, you can use something like Transmit to open the file in a local editor and saves will be automatically uploaded to the server.  Unfortunately, FTP is a very old and VERY insecure protocol that should not be used anymore.  What else can we do?

Using Secure Shell (SSH) Tunneling, we can establish an SSH session that routes arbitrary traffic through it to a specified port for any use we want.  Thanks to a nifty set of scripts called rsub, modified originally from TextMate’s rmate, we can run a little utility server on our local machine that interacts with your remote server for you and lets you open up remote files and save them back, all through an encrypted channel.

What Do I Do?

  1. As of writing, these instructions work only for Sublime Text 2.  If I get a chance I’ll look into forking rsub for the newly released ST3 (which runs Python3).
  2. If you don’t already have Sublime Text’s wonderful package manager, install it.
  3. Hit Ctrl+Shift+P, start typing “install” and select “Install Package”
  4. Start typing “rsub” and select it.
  5. Once it’s installed, get on your terminal and do
    nano ~/.ssh/config
  6. Paste the following lines:
    Host your_remote_server.com
        RemoteForward 52698 127.0.0.1:52698
  7. Save (ctrl+w) and SSH into your server (ssh username@your_remote_server.com).
  8. ‘Install’ the rsub remote script:
    sudo wget -O /usr/local/bin/rsub https://raw.github.com/aurora/rmate/master/rmate
  9. Make that script executable:
    sudo chmod +x /usr/local/bin/rsub
  10. Lastly, run rsub on the remote file you want to edit locally:
    rsub ~/my_project/my_file.html

    and it should magically open in Sublime Text!

Let me know if this works for you! Enjoy!

Updating a Mailchimp mailing list with past EventBrite attendees

2013 January 29
by Tedb0t

At Kitchen Table Coders we use EventBrite to sell tickets and Mailchimp to email fans about new classes.  Every time we do a new class I wanted to update our main mailing list with the new attendee email addresses, so I wrote this simple Python script to do it automatically.  Usage details are in the readme.  Enjoy!

Batch convert files to PDFs in OSX Mountain Lion

2012 December 12
tags: , ,
by Tedb0t

Today I needed to convert a bunch of RTF files (I know, what?) to PDFs.  After stumbling through a bunch of dead ends, I realized this—like most things—could be done incredibly easily in Bash:

#!/bin/bash
for file in *.rtf ; do
filename=$(basename "$file") /usr/sbin/cupsfilter "$file" > "$filename.pdf"
done

Getting Physical: Workshop Notes

2012 September 22

Here are some notes and links for my Strange Loop workshop, “Getting Physical.”

Slides for TimesOpen “Sockets & Streams”

2012 September 13
by Tedb0t

Last night at the New York Times “TimesOpen” event, I gave a presentation on internet-enabled bubble guns, wireless joysticks for browser games, and how the “Internet of Things” is better understood as an Internet Ecology:

Thanks to everyone for coming and to Brad Stenger and everyone at the Times for inviting me!

Arduino: A new & improved Button library with some handy features

2012 August 2
by Tedb0t

By Ted Hayes, from code originally by Alexander Brevig & Tom Igoe

The Arduino Button library (Github Repo) makes it easy to do some very common but rather tedious tasks. Usually when you interact with a button (such as a momentary switch), you mainly want to detect the state change, not just the current state. You have to do something like:

int lastState = 0;
void loop(){
    int currentState = digitalRead(11);
    if(currentState != lastState){
        // do something
    }
    lastState = currentState;
}

It’s not hard, just tedious. This new and improved Button library makes this much simpler but adds so much more. Now you can do it this way:

Button button = Button(12);

void onPress(Button& b){
	Serial.print("onPress: ");
	Serial.println(b.pin);
	// will print out "onPress: 12"
}

void setup(){
  Serial.begin(9600);
  // Assign callback function
  button.pressHandler(onPress);
}

void loop(){
  // update the buttons' internals
  button.process();
}

Features

  • Object-oriented design
    Button myButton(11);
  • Automatic pull-up setting
    Button myButton(11, BUTTON_PULLUP_INTERNAL);
  • Simplified state-change detection:
    if(button.isPressed()) ...
  • Callback model
    button.pressHandler(onPress)
  • Built-in debouncing
    // Sets 50ms debounce duration
    Button button = Button(12, BUTTON_PULLUP_INTERNAL, true, 50);

Installing

To install, download the library, extract it to ~/Documents/Arduino/libraries and rename the folder “Button.” (Github generates a different name for the zip link.) Restart Arduino if it was already open.

I hope you find this useful! Please report any bugs using the Github issue tracker.

Arduino: How to Read and Write EEPROM values

2012 August 1
by Tedb0t

When you reset an Arduino, the state of any variables you might have will be lost. So what if you want to keep a value even after it’s been powered off? Luckily, ATmega chips have an area of memory called EEPROM, or “Electrically Erasable Programmable Read-Only Memory.”  This allows you to store persistent values, and Arduino ships with an EEPROM library that makes it easy to use.

Here’s an example Arduino sketch that demonstrates how to read from and write to this part of memory:

Tutorial: How to use your Raspberry Pi like an Arduino

2012 June 15
by Tedb0t

Finally got to experiment with the Raspberry Pi’s GPIO (General Purpose Input/Output) pins.  I tried three methods: Python, Bash and C, and will describe each.  But first, here’s some setup information. read more…

How to build Pd-extended on the Raspberry Pi

2012 June 14
by Tedb0t

It was quite an ordeal, but I managed to build Pd-extended (Puredata with a bunch of externals) on my Raspberry Pi running Debian Squeeze.  I also uploaded my finished package (.deb) to puredata.info, see below for details.  Here’s what you need to do: read more…

Running Puredata on the Raspberry Pi

2012 June 1
by Tedb0t

I’m thrilled to say that today I succeeded in getting Puredata running on my Raspberry Pi. Here’s how!

First, follow this guide to get your Pi set up for the first time.  Make sure your Pi is connected to the internet, and now we can install Puredata.  We’ll start with Vanilla, since pd-extended is not maintained for ARM (as far as I can tell).  I’ll explore getting pd-extended working in a future post (hopefully very soon).

sudo apt-get update
sudo apt-get install puredata

Easy. What’s not easy is getting sound working. This took me about half the day but here’s what worked:

sudo apt-get install alsa-utils
sudo modprobe snd_bcm2835

Note that the modprobe line needs to be run every time the Pi is booted, so you can add it to an .rc file if you want.  Now connect some speakers, turn them down for safety, and run this to make sure sound works:

sudo aplay /usr/share/sounds/alsa/Front_Center.wav

If it works, good! You can now run a Pd patch like so:

pd -nogui -noadc -alsa testPatch.pd

For convenience, here’s my test patch (testPatch.pd) that outputs an LFO’d sine wave. *Important!* Notice in the patch that the loadbang is delayed by 100ms! This is deliberate to avoid a bug in Pd regarding ALSA.

Please let me know if this worked for you.  Happy hacking!  Next up, I’ll be trying to build Pd-extended and then tackling the Raspberry Pi’s General Purpose I/O.

UPDATE:

You’ll notice that the sound quality out of the 1/8″ jack is messed up in some cases (most in my experience).  I’ve heard from various sources that the R-Pi does not use a “real” DAC (Digital-to-Analog-Converter) and that you should get better sound from a USB adapter or from the HDMI output.  Still following up on this.

Getting Started with the Raspberry Pi

2012 June 1
by Tedb0t

The Raspberry Pi is a very low-cost, very small computer capable of running Linux that also provides GPIO (General Purpose Input/Output).  As such, it’s something of a hacker’s dream and there’s been a ton of buzz around it.  I ordered two a couple of months ago and just got them in.  Here’s what you need to get started. read more…

How to get the signal strength of 2 XBees in Processing

2012 May 24
by Tedb0t

I put together a little sketch here on Github that tells you the RSSI (Received Signal Strength Indicator) of a remote XBee in Processing.  All the instructions are there (and here); check it out and let me know what you think.  Post a comment with what you make! read more…