Sunday, October 14, 2012

Solving Jumble with Python and Bash

In order to solve jumble, we first write a Python script that outputs all character permutations of a given string. The script demonstrates a cool little recursive algorithm. To compute all permutations of a string of length n, we pick off the character at each index in the string, and compute the permutations of the remaining n-1 characters. The function substring constructs this n-1 character string. When we have a list of the permutations of these n-1 characters, we use the list comprehension
[first + i for i in perms(others)]
to prepend the character that we initially picked off onto each string in the list.

permutations.py


#!/usr/bin/env python

import sys 

def substring(s, i): 
    if i == (len(s) - 1): 
        return s[:i]
    elif i == 0:
        return s[1:]
    else:
        return s[0:i] + s[i+1:]

def perm(s):
    p = []
    length = len(s)
    if length <= 1:
        p.append(s)
    else:
        for i in range(length):
            first = s[i]
            others = substring(s, i)
            p.extend([first + i for i in perm(others)])
    return p

if __name__ == '__main__':
    if len(sys.argv) != 2:
        print('usage: %s word' % sys.argv[0])
        sys.exit(1)
    perms = perm(sys.argv[1])
    for i in perms:
        print(i)
    sys.exit(0)

Let's try out the script by having it display all permutations of the string 'one'.

$ ./permutations.py one
one
oen
noe
neo
eon
eno

Now all we have to do to solve jumble is loop over each string in the output and see if that string appears in a dictionary. To do this, we'll write a short Bash script that greps for each word against a dictionary file. On my computer a flat text dictionary is located at /usr/share/dict/words. Feel free to change the assignment of the variable DICT to some other dictionary file that is found on your machine.

jumble.sh


#!/bin/bash

DICT=/usr/share/dict/words

if [ $# -ne 1 ]; then
    echo "usage: $0 jumble-word"
    exit 1
fi

cnt=1
for i in `./permutations.py $1`; do
    grep -q "^$i$" $DICT 
    if [ $? -eq 0 ]; then
        printf "%6d: %s ... [YES]\n" "$cnt" "$i"
        exit 0
    fi  
    printf "%6d: %s ... [NO]\n" "$cnt" "$i"
    let cnt=cnt+1
done

exit 1

Let's try out our program on an example taken from jumble.com.

$ ./jumble.sh tecot
     1: tecot ... [NO]
     2: tecto ... [NO]
     3: teoct ... [NO]
     4: teotc ... [NO]
     5: tetco ... [NO]
     6: tetoc ... [NO]
     7: tceot ... [NO]
     8: tceto ... [NO]
     9: tcoet ... [NO]
    10: tcote ... [NO]
    11: tcteo ... [NO]
    12: tctoe ... [NO]
    13: toect ... [NO]
    14: toetc ... [NO]
    15: tocet ... [NO]
    16: tocte ... [NO]
    17: totec ... [NO]
    18: totce ... [NO]
    19: tteco ... [NO]
    20: tteoc ... [NO]
    21: ttceo ... [NO]
    22: ttcoe ... [NO]
    23: ttoec ... [NO]
    24: ttoce ... [NO]
    25: etcot ... [NO]
    26: etcto ... [NO]
    27: etoct ... [NO]
    28: etotc ... [NO]
    29: ettco ... [NO]
    30: ettoc ... [NO]
    31: ectot ... [NO]
    32: ectto ... [NO]
    33: ecott ... [NO]
    34: ecott ... [NO]
    35: ectto ... [NO]
    36: ectot ... [NO]
    37: eotct ... [NO]
    38: eottc ... [NO]
    39: eoctt ... [NO]
    40: eoctt ... [NO]
    41: eottc ... [NO]
    42: eotct ... [NO]
    43: ettco ... [NO]
    44: ettoc ... [NO]
    45: etcto ... [NO]
    46: etcot ... [NO]
    47: etotc ... [NO]
    48: etoct ... [NO]
    49: cteot ... [NO]
    50: cteto ... [NO]
    51: ctoet ... [NO]
    52: ctote ... [NO]
    53: ctteo ... [NO]
    54: cttoe ... [NO]
    55: cetot ... [NO]
    56: cetto ... [NO]
    57: ceott ... [NO]
    58: ceott ... [NO]
    59: cetto ... [NO]
    60: cetot ... [NO]
    61: cotet ... [NO]
    62: cotte ... [YES]

Friday, October 5, 2012

JavaScript Celsius-Fahrenheit Converter

Your first JavaScript script pops up an alert box. Your second script converts between Celsius and Fahrenheit. So without further ado ... the infamous Celsius-Fahrenheit Converter.

Fahrenheit
Celsius

Source code:

<html>
  <head>
    <title>Temperature Converter</title>
  </head>
  <body>
    <h2>Temperature Converter</h2>
    <hr/>
    <form name="temperature">
      <table>
        <tr>
          <td>Fahrenheit</td>
          <td><input type="text" name="fahrenheit" onchange="ftoc();"></td>
        </tr>
        <tr>
          <td>Celsius</td>
          <td><input type="text" name="celsius" onchange="ctof();"></td>
        </tr>
      </table>
    </form>
    <script language="JavaScript">
      function ftoc() {
        var f = document.temperature.fahrenheit.value;
        if (isNaN(f)) {
            document.temperature.celsius.value = '';
        } else {
            var c = (5.0 / 9.0) * (f - 32);
            document.temperature.celsius.value = c.toFixed(2);
        }
      }

      function ctof() {
        var c = document.temperature.celsius.value;
        if (isNaN(c)) {
            document.temperature.fahrenheit.value = '';
        } else {
            var f = ((9.0 / 5.0) * c) + 32;
            document.temperature.fahrenheit.value = f.toFixed(2);
        }
      }
    </script>
  </body>
</html>

Monday, October 1, 2012

Lazy Initialization, Memoization, and Fun with Python Magic Methods

In this blog, we have some fun creating a class that implements the mapping protocol. The class also provides a simple example of the techniques of lazy initialization and memoization.

Let's say we have a configuration file, planets.conf that lists standard attributes for each planet in the solar system.

planets.conf


[Mercury]
orbit = 57910000
diameter = 4880
mass = 3.30e23

[Venus]
orbit = 108200000
diameter = 12103.6
mass = 4.869e24

[Earth]
orbit = 149600000
diameter = 12756.3
mass = 5.972e24
satellites = Moon

[Mars]
orbit = 227940000
diameter = 6794
mass = 6.4219e23
satellites = Phobos Deimos
.
.
.

Let's now create a structure-like class, called Planet, that encapsulates the attributes of planet name, orbit, diameter, mass, and satellites.

class Planet:
    def __init__(self, name, orbit, diameter, mass, satellites = []):
        self._name = name
        self._orbit = orbit
        self._diameter = diameter
        self._mass = mass
        self._satellites = satellites

    def __str__(self):
        return '%s%s\torbit: %.2f%s\tdiameter: %.2f%s\tmass: %g%s' +
            '\tsatellites: %s%s' \
            % (self._name, os.linesep,  \
            self._orbit, os.linesep, \
            self._diameter, os.linesep, \
            self._mass, os.linesep, \
            ', '.join(self._satellites), os.linesep)
    @property
    def name(self): return self._name
    @property
    def orbit(self): return self._orbit
    @property
    def diameter(self): return self._diameter
    @property
    def mass(self): return self._mass
    @property
    def satellites(self): return self._satellites

Next, we create a dictionary-like class, called Planets, that manages the creation of each Planet object.

class Planets:
    _NUM_PLANETS = 9
    _PLANET_NAMES = ['Mercury', 'Venus', 'Earth', 'Mars', 'Jupiter', 'Saturn',
    'Uranus', 'Neptune', 'Pluto']

    def __init__(self):
        self._planets = {}
        self._parser = SafeConfigParser()
        self._parser.read('planets.conf')

    def __len__(self):
        return self._NUM_PLANETS

    def __getitem__(self, key):
        if key in self._planets:
            return self._planets[key]
        if not self._parser.has_section(key):
            raise KeyError(key)
        orbit = self._parser.getfloat(key, 'orbit')
        diameter = self._parser.getfloat(key, 'diameter')
        mass = self._parser.getfloat(key, 'mass')
        satellites = []
        if self._parser.has_option(key, 'satellites'):
            satellites = self._parser.get(key, 'satellites').split()
        self._planets[key] = Planet(key, orbit, diameter, mass, satellites)
        return self._planets[key]

In particular, if a user performs the following operations:

p = Planets()
earth = p['Earth']

then Planets will read the statistics for planet Earth from planets.conf, create a new Planet that represents Earth, and add this planet to its private dictionary of planets (self._planets). Thus, the operation of constructing a planet from a configuration file is only performed if that planet is accessed. On subsequent accesses of that planet, Planets returns the memoized Planet object.

Note that, for fun, we have Planets implement the __len__ and __getitem__ magic methods, thereby fulfilling the protocol of an immutable mapping.

The entire program is listed below.

lazy_planets.py


#!/usr/bin/env python

from ConfigParser import SafeConfigParser
import os

__metaclass__ = type # new-style classes

class Planet:
    def __init__(self, name, orbit, diameter, mass, satellites = []):
        self._name = name
        self._orbit = orbit
        self._diameter = diameter
        self._mass = mass
        self._satellites = satellites

    def __str__(self):
        return '%s%s\torbit: %.2f%s\tdiameter: %.2f%s\tmass: %g%s' +
            '\tsatellites: %s%s' \
            % (self._name, os.linesep,  \
            self._orbit, os.linesep, \
            self._diameter, os.linesep, \
            self._mass, os.linesep, \
            ', '.join(self._satellites), os.linesep)
    @property
    def name(self): return self._name
    @property
    def orbit(self): return self._orbit
    @property
    def diameter(self): return self._diameter
    @property
    def mass(self): return self._mass
    @property
    def satellites(self): return self._satellites

class Planets:
    _NUM_PLANETS = 9
    _PLANET_NAMES = ['Mercury', 'Venus', 'Earth', 'Mars', 'Jupiter', 'Saturn',
    'Uranus', 'Neptune', 'Pluto']

    def __init__(self):
        self._planets = {}
        self._parser = SafeConfigParser()
        self._parser.read('planets.conf')

    def __len__(self):
        return self._NUM_PLANETS

    def __getitem__(self, key):
        if key in self._planets:
            return self._planets[key]
        if not self._parser.has_section(key):
            raise KeyError(key)
        orbit = self._parser.getfloat(key, 'orbit')
        diameter = self._parser.getfloat(key, 'diameter')
        mass = self._parser.getfloat(key, 'mass')
        satellites = []
        if self._parser.has_option(key, 'satellites'):
            satellites = self._parser.get(key, 'satellites').split()
        self._planets[key] = Planet(key, orbit, diameter, mass, satellites)
        return self._planets[key]

if __name__ == '__main__':
    p = Planets()
    print('Number of planets: %d' % (len(p), ))
    earth = p['Earth']
    print(earth)
    mars = p['Mars']
    print('The moons of mars are: %s' % (' ,'.join(mars.satellites), ))
    try: ceres = p['Ceres']
    except KeyError, e:
        print 'Ceres is not a planet!'
Here is the output of the program:
$ ./lazy_planets.py 
Number of planets: 9
Earth
 orbit: 149600000.00
 diameter: 12756.30
 mass: 5.972e+24
 satellites: Moon

The moons of mars are: Phobos ,Deimos
Ceres is not a planet!