'(scheme . info)

Back in the 1970s, David Ahl wrote a new game program each month for Creative Computing magazine. Those were the days of all-caps teletypes (if you were rich you could get a new-fangled “glass teletype”) and punched paper tapes (it was fun to play with the confetti they made). MS-BASIC permitted twenty-six single-letter variable names; later they also allowed a single letter followed by a single digit. There were no user-defined functions and no recursion. GOTO was common, resulting in a phenomenon called “spaghetti code.” There was good news, however: it was acceptable programming practice to GOTO the middle of a FOR loop and run the code there, as long as you jumped back out of the loop before the corresponding NEXT — try to do that in your favorite functional language!

One of Ahl’s most memorable games was Hamurabi, in which the player took the role of the administrator of the ancient city of Sumeria, managing the grain and land resources of the city and trying to keep the residents from starvation. It is typical of the genre, with simple numeric input and scrolling text output. Here is a description and sample game, and the original BASIC source code is reproduced on the next page. By my count, there are fourteen lines that are unreachable except by an IF…THEN, GOSUB or GOTO, forty-three lines that redirect control flow away from the line below, and four instances (line 555 to 215, bypassing line 210, 453 and 479 to 440, bypassing 430, 441 to 511, bypassing 510, and 880 and 885 to 565, bypassing 560) of jumping into the middle of a block of code; that’s a fine bowl of spaghetti, considering the entire program is only 120 lines. Variable P represents the current population, S is the number of bushels in stores, and A is the number of acres of farmland owned by the city, but other variables are used inconsistently — for instance D sometimes represents the number of deaths in the current year, but other times it represents the current input value, and other times Q is used to represent the current input value.

Your task is to reimplement HAMURABI.BAS in a more modern computer language. Don’t peek at the solution unless you want to deprive yourself of the sheer joy of working out the spaghetti code and figuring out what the variables really stand for. 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.

While waiting for the Roadcrafter suit to arrive; I decided to get my old leather coat out of storage. Purchased at the flea market in Orange County, CA sometime in the mid-nineties, I’d somehow managed never to wear it. While some may lament the 90’s shoulder-pad styling, it is hard not to like the southwestern influenced design.

Thus far it has been pretty comfortable, the leather seems sturdy, and you know… I don’t mind the smitten looks that I receive while wearing it one bit ;).

My Concours has a little rust-spot on the gas tank. The bike was recently serviced and they didn’t see any rust inside of the gas tank, so you know, I’ve got warm-fuzzies about that but I still need to do something about the rust. Here are some progressively more detailed photos of the bike and the rust-spot (click to zoom):

Talking to four different friends and co-workers, their advice is split two ways:

1. Sand down the rust with wet-grit paper or a dremel and fix it immediately to prevent it from spreading further.
2. Do not break the seal of the OEM paint. As long as the rust doesn’t spread; you don’t need to worry about it. Just leave it.

What would you do and why would you do that?

Over at SteamCode, Scott LaBounty suggests that writing a program to compute the happy numbers less than n makes a good interview question. According to Wikipedia:

A happy number is defined by the following process. Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers (or sad numbers).

For example, 7 is a happy number, as 72=49, 42+92=16+81=97, 92+72=81+49=130, 12+32+02=1+9+0=10, and 12+02=1+0=1. But 17 is not a happy number, as 12+72=1+49=50, 52+02=25+0=25, 22+52=4+25=29, 22+92=4+81=85, 82+52=64+25=89, 82+92=64+81=145, 12+42+52=1+16+25=42, 42+22=16+4=20, 22+02=4+0=4, 42=16, 12+62=1+36=37, 32+72=9+49=58, and 52+82=25+64=89, which forms a loop.

Your task is to write a function to identify the happy numbers less than a given limit; you should work at the level of a programming interview, taking no more than about fifteen minutes, and giving a short explanation of your work to the interviewer. 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.

In today’s exercise we continue the examination of matrix operations that we began previously. Our goal is to be able to solve a system of equations; along the way we will see two methods for decomposing matrices.

We begin with some terminology. All the matrices we will be looking at are square, meaning that they have the same number of rows and columns. A lower-triangular matrix L has all entries Lij = 0 for i < j; thus, all entries above the main northwest-to-southeast diagonal are zero. An upper-triangular matrix U has all entries Uij = 0 for i > j; thus, all entries below the main northwest-to-southeast diagonal are zero. A lower- or upper-triangular matrix is unit lower- or upper-triangular if all the entries along the main diagonal are 1. A permutation matrix P has exactly one 1 in each row and column and 0 elsewhere; it is called a permutation matrix because multiplying a vector X by a permutation matrix has the effect of permuting the elements of X. The identity matrix I has 1 in each entry along the main diagonal and 0 elsewhere. A matrix M is singular if it has no inverse, that is, there is no matrix M-1 such that M M-1 = I.

An LU decomposition of a matrix A finds two matrices L, which is unit lower-triangular, and U, which is upper-triangular, such that A = L U. The algorithm is called Gaussian elimination, and works from top to bottom. First, multiples of the first equation are subtracted from the other equations so that the first variable is removed from those equations. Then multiples of the second equation are subtracted from the remaining equations so that the second variable is removed from those equations. Then the third equation, and the fourth, and so on, until all the equations have been processed and the matrix is in upper-triangular form. Here is an example of the LU decomposition of matrix A into its factors L × U:

There are two problems with LU decomposition: First, the algorithm leads to a divide-by-zero error on singular matrices. Second, it is prone to numerical instability for small divisors. The solution is to rearrange, or permute, the equations so that the pivot element is always the largest remaining element, greatly reducing the likelihood of numerical instability.

An improved decomposition is the LUP decomposition, which finds for an input matrix A three matrices L, U, and a permutation matrix P such that P A = L U. Rather than actually moving equations, the permutation matrix records the rearrangements. For example, here is the LUP decomposition of the matrix A given by P × A = L × U:

Given the LUP decomposition, it is simple to solve a system of linear equations. Forward substitution solves the lower-triangular system by calculating the first variable, which is part of an equation with one unknown, then substitutes that into the second equation, reducing it from two unknowns to one unknown, and so on. Then back substitution runs backward, calculating the final values of the variables in the original matrix. Here’s an example, where we wish to solve for the vector X given A X = B:

The LUP decomposition P A = L U is

,

the result of forward substitution L Y = P B is

, giving ,

and the result of the back substitution U X = Y is

, giving ,

which is the solution.

Your task is to write functions that perform LU-decomposition and LUP-decomposition and solve systems of linear equations. 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.

The previous post describes the basics on how to use the web API.  This post will focus on integrating your module with the web API.

As shown before, you can create a web API by creating an SHP script as follows:

;; /api/add2 
(:api-args (a number?) (b number?)) 
(+ a b) 

Where both a and b are validated as number?.  It would be nice if we can validate any type of scheme values, as long as the value can be created via the request input. 

For example - let's say that you have a struct with the following definition:

(define-struct foo (bar baz)) 

We want to do the following:

(:api-args (foo foo?)) ;; takes in the foo struct 

And let web API handle the rest.   This is achieved via converters.

Converters The mappings between the request and the api args are done via converters, which maps the parameter key against the type's test function (such as number?).   And when you want to use the converter in the api-args expression, you specify the <test?> function in the parameter position in one of the following forms:

(<name> <test?> <default>) ;; this form means this parameter is an optional parameter, and if no values are passed in it will return the default value.

(<name> <test?>) ;; this form means the parameter is a required parameter – if no value passed in it will error.  Any value passed in will be validated and converted (if it fails the conversion it will error)

<name> ;; this form means the parameter does not have any validation – any value will be passed verbatim. 

Because the <test?> function is used as the mapping to the actual underlying converter object, we will call the underlying converter object as the "<test?> converter". i.e., the actual converter mapped by number? is called the "number? converter" (the quotes are dropped going forward).

You can define your own converters to use in the api-args expression to validate your own objects.  To do so, you can define either a scalar or a struct converter as of bzlib/shp:1:3. 

Scalar vs. Struct Converters
There are two different types of converters - scalar and struct. They differ in the type of input required. This is best explained with a JSON request.

Scalar maps to the JSON number and strings, while struct maps to JSON objects (JSON arrays are automatically mapped to lists).

As an example - the following JSON object has a scalar value for both foo and bar key, but a struct value for the baz key:

{ foo : 1 , bar : "test me" , baz : { abc : 1 , def : 2 } } 

So we will use a scalar converter for both foo and bar field (number? and string? respectively), and we will use a struct converter for the baz field that takes in an abc and def fields as number?.

The mapping is pretty straightforward for XMLRPC request as well, except that XMLRPC request method call does not handle named parameters, so we will map the arguments by positions. Otherwise, XMLRPC's string and integers maps to scalars, and struct maps to struct converters (the XMLRPC array maps to lists automatically).

The mapping in query-based request is a bit more complicated, since the query string is only consisted of key/value pairs, it does not handle nested hierarchy of objects by default. We solve this problem by using the dot notation (familiar to most OOP developers) to simulate the hierarchy in the key name themselves. As an example, the query string below maps to the JSON object above:

&foo=1&bar=test%20me&baz.abc=1&baz.def=2

The baz JSON object is flattened into baz.abc and baz.def key/value pairs. This flattening can be done for arbitrary levels.

Hence - you need to ensure that the request are constructed correctly based on the above rules. The rules for JSON & XMLRPC are specified in their corresponding specs, and the query-string rules are specified here.

Define a Scalar Converter
To define a scalar converter, we use the define-scalar-converter! syntax.

(define-scalar-converter! <test?> 
  (<type?> <transform-from-type?>) ...) 

For example – the following is the definition of the number? converter:

(define-scalar-converter! number? (string? string->number)) 

It roughly means the following:

(lambda (x) 
  (cond ((number? x) x) 
        ((string? x) 
         (let ((x (string->number x))) 
           (if x
               x 
               (error 'invalid-conversion "~s" x))))
        (else (error 'invalid-type "~s" x))))

If the passed in value is already the desired type, we just let it pass through.  Otherwise we test to see if it is one of the known types (or error out), and try to convert the value.  If the converter succeeds, return the value, otherwise, throw an exception.

Although the other type of converters is called struct converter, we can define a scalar converter for a struct as well, as long as the struct can be mapped from a scalar value. NOTE - you cannot define both a scalar and struct converter for a struct, since all converters shares the same namespace.

Here's an example of a scalar converter for a struct – we will create a scalar converter for url? from net/url.

(define-scalar-converter! url? 
  (string? string->url) 
  (bytes? (compose string->url bytes->string/utf-8))

Define Struct Converters
To define a struct converter, we use the define-struct-converter! syntax.

(define-struct-converter! name ((field converter?) ...)) 

For example – the following defines a struct converter for the foo struct above:

(define-struct-converter! foo ((bar number?) (baz string?))) 

The struct converter looks like the struct form in provide/contract, but instead of contract expressions, each field is accompanied by a converter instead.

The field converter must already have been defined, or else the definition will fail and throw an exception.

The field converter can of course be either a scalar converter or a struct converter as well.

Converter Definition Orders and Other Design Decisions
Converters should be defined in the order from the most general types to the most specific types, similarly to how object hierarchies are defined.  For example, if you have a sub struct, you should define the converter for the sub struct after you have defined the converter for the parent struct.  And if you want to have converter for both number? and integer?, you should first define the number? converter and then define the integer? converter.

One of the design decisions for the converters is that once a converter is defined it is immutable – future definitions are simply ignored.

Furthermore, both scalar converter and struct converter shares the same namespace.

The above two points means that you can only define either a scalar converter or a struct converter for any given type, and once it is defined it cannot be changed.

Where to Define Converters
Since the design philosophy behind bzlib/shp is that shp scripts should be used for presentations and the application logics should reside in regular PLT Scheme/Racket module/packages, converters are best defined in the respective modules.

However, for ad hoc purposes, the required script (the single shp script that is responsible for loading the required modules) has been extended with bzlib/shp 0.4 so it can now handle ad hoc defintions as well. So if you want to define converters in the required script you can do so, but remember that if it seems like these definition should be shared they might need to eventually migrate into their respective modules.

That's it for now.  Feel free to leave comment if there are any questions.  Enjoy.

Pavel Samolisov wrote a very good blog post on how to get started with SchemeScript. It's in Russian, but Google can translate it to English (the translation is definitely not very good, but it is better than nothing).
Pavel noted that SchemeScript does not work well on Eclipse Helios. I just pushed a fix on the github repository (and the sourceforge git repository as well) that makes the interpreters work. If you find problems with Eclipse Helios and SchemeScript, please let me know.

In two previous exercises, we looked at the programs behind the tables of contents pages in chronological order and permuted by keywords. In today’s exercise, we complete this trio of exercises by writing the program that creates the themed table of contents page. Like the others, it is based on the praxis.info file, which was described previously. We won’t give the output format here, except to say that it is similar to the others, but with an additional header section for the list of themes.

Your task is to write a program that extracts needed data from the praxis.info file and writes the themed table of contents. 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.

In this post, a person going by the initials CC declares: There's a good reason almost no software has been written in lisp. Lisp sucks. Not just lisp, but the whole way the logic is arranged as nested things. The simplest problem becomes a mind-bending puzzle. Instead of easy to understand:

if (a equals b) { 
  c = not d; 
} else { 
  c = d + b; 
}

You have this nested inner to outer logic where if is a function.

c = if(equals(a,b), not(d), plus(d,b)) 

The first is definitely more readible [sic] and it reads like we think of the logic. No one thinks of if as a function that takes three arguments, and forcing you to work that way just makes you crazy. I suppose it is futile to argue with an admittedly crazy person, but perhaps being forced to work with conditionals has made me crazy as well. A closer translation of the original code would be this:

(if (equals a b)
    (setq c (not d))
    (setq c (+ d b)))

If these sorts of differences are a ``mind-bending puzzle'', perhaps the author should consider a career in the housekeeping or food-service industries.

Word cube is game in which players form words from the nine letters in a cube. Words must have four or more letters and must use the central letter from the cube; at least one word will use all nine letters in the cube. The player who forms the most words wins. Many newspapers publish a word cube on their puzzle page, and Stealthcopter publishes a word cube on line daily. Wikipedia describes word cubes under the caption “word polygon.” There are twelve words formed from the word cube at right: bonnie, bunion, coin, concubine, conic, cubic, ennui, icon, nice, nine, nuncio, and union.

Your task is to write a program that finds all matching words for a given word cube. 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.

The MSF beginner’s riders class that I took a month or so ago required shoes that covered the ankles and I ended up buying a pair of the Brahma Hutch II lace-less steel-toe boots from Walmart. Wearing now for a about a month I’ve been really impressed; they are comfortable, broke in really easily, and slip on and off pretty quickly. Perhaps the only downside for motorcycle-riding is that the steel-toe makes for awkward shifting and breaking. For that reason I’m looking at buying some real motorcycle boots pretty soon; in particular the TCX X-Five.

All in all for only $30USD this is a really nice boot.

After a good bit of research I decided to go with a Shoei RF1100. After a few hundred miles I’ve found it to be really nice; comfortable, a lot of air goes through it, and it doesn’t squeal when you are sitting behind a windshield like a couple of reviews that I had read suggested.

Perhaps the most bothersome discovery is the ridge on the top of my head that is going to force me to purchase some extra padding or something to level out the top of the helmet so it quits giving me a headache!

One “funny” thing I found in the owner’s manual was a warning that if you purchase the Matte Black helmet then you need to be extra, extra-careful about protecting its finish. Great!

We examined in a previous exercise a program that extracts a chronological listing of the exercises on the Programming Praxis website from the praxis.info file. We also discussed in a previous exercise a program that creates a permuted index. In today’s exercise we will combine those two programs into the program that is used to create the Permuted Table of Contents page at Programming Praxis.

The format of the praxis.info file was given in a previous exercise. The output from today’s program should look like this:

<table cellpadding="10">
<tr><td>129</td><td>20 Apr 2010</td><td align="right">&nbsp;</td><td>145 Puzzle: Build and evaluate expressions using the digits one through nine and the simple arithmetic operators</td><td><a href="/2010/04/20/145-puzzle/">exercise</a> <a href="/2010/04/20/145-puzzle/2/">solution</a> <a href="http://programmingpraxis.codepad.org/SzbrJbjx">codepad</a></td></tr>
<tr><td>51</td><td>17 Jul 2009</td><td align="right">International Mathematical Olympiad: Three exercises from</td><td>1960s math competitions</td><td><a href="/2009/07/17/international-mathematical-olympiad/">exercise</a> <a href="/2009/07/17/international-mathematical-olympiad/2/">solution</a> <a href="http://programmingpraxis.codepad.org/JRGmt2wZ">codepad</a></td></tr>
...
</table>

Your task is to write a program that reads praxis.info and produces the permuted table of contents. 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.

A new version of SHP.plt is now available via planet.  This is a major rewrite of SHP and provides two main upgrades:

• a "web API" interface - your web script can now be exposed as an "API" (think XMLRPC/JSON), and it automatically works with either XMLRPC or JSON (details below)
  
• general performance enhancement - the scripts are now compiled and cached to reduce disk IO.  If the scripts are updated then they are automatically recompiled
  

As usual, the code is released under LGPL.

Installation 

(require (planet bzlib/shp:1:3)) 

SHP requires some newer dependencies (bzlib/base:1:6, bzlib/date:1:3, bzlib/parseq:1:3, bzlib/xml:1:3, bzlib/mime:1:0), and the current versions of PLT Scheme and Racket have issues with version dependencies (the link: module mismatch bug), so you might have to clear out the planet cache and recompile them again.

As usual, SHP comes with a small example site that you can play with under the example sub directory - cd to the example directory and run (require "web.ss") will start the example site.  The example site is still just trivial code right now - it will eventually be enhanced and separated into its own package.

Cached Compiled Script All of the scripts are now compiled and cached.  This has some potential performance benefit, since we will only access the file content when the file timestamp changes (meaning the file has been touched and/or modified).  As this is a non-visible feature, we won't spend much time discussing it, except to note that the change is not just done for performance reasons - it is also done to enable and simplify the design of web api, which is discussed below.

Web APIUnder the example site you can find the script shp/api/add2, which contains the following:

;; -*- scheme -*- -p 
(:api-args (a number?) (b number?)) 
(+ a b)

This is the new *web api* - it takes in 2 numbers, a and b, and return the added result. To write an api script, you must use the :api-args expression, and then supply the arguments inside. The arguments can be specified in the following forms:

(:api-args a b) ;; both a & b are non-validating and you get what's passed in

(:api-args (a number?) (b string?)) ;; a expects a number, and b expects a string 

(:api-args (a number? 3) (b number? 5)) ;; a & b both expect numbers, and both have default values if they are not passed in (a defaults to 3, and b defaults to 5). 

When you run the example site you can access the api via the following http call:

GET /api/add2 HTTP/1.0 

When running the above in browser you should get back an XMLRPC response:

Content-Type: text/xml; charset=utf-8 

<methodResponse>
<fault>
<value>
<string>required: a</string>
</value>
</fault>
</methodResponse>

XMLRPC is the default response mode for web APIs.  What it returns by default as shown above is an error message, because neither a or b is passed in.

To pass in the values - you just need to specify them in the query string as following:

GET /api/add2?&a=50&b=90 HTTP/1.0 

which will return the following:

Content-Type: text/xml; charset=utf-8

<methodResponse>
<params>
<param>
<value>
<int>140</int>
</value>
</param>
</params>
</methodResponse>

The add2 script contains args of (a number?) and (b number?), which mean that both a & b expects a number input.  So if we pass a non-number to the api

GET /api/add2?&a=not-a-number&b=also-not-a-number HTTP/1.0 

we get the following:

<methodResponse>
<fault>
<value>
<string>invalid-conversion: "not-a-number"</string>
</value>
</fault>
</methodResponse>

Which shows that the validation takes place for each of the arguments.  We will talk about how the underlying validation magic works later.

XMLRPC Request Payload Now the API doesn't just work for query string parameters - you can pass in an XMLRPC payload as well.  To do so you need to use POST instead of GET, and put the following XMLRPC request into the payload:

POST /api/add2 HTTP/1.0 
Content-Type: text/xml; charset=utf-8 

<methodCall>
<methodName>add2</methodName>
<params>
<param><name>a</name><value><int>50</int></value></param>
<param><name>b</name><value><int>90</int></value></param>
</params>
</methodCall>

Which will return the same result:

Content-Type: text/xml; charset=utf-8

<methodResponse>
<params>
<param>
<value>
<int>140</int>
</value>
</param>
</params>
</methodResponse>

Partial Path Dispatch with XMLRPC methodName You might have noticed in the above that the token add2 is specified twice in the request - once in the path, and once in the methodName parameter in the payload.  And if you were to use a bogus method name such such as add3 in the methodName parameter, you will see that it is being ignored - the path has precedence.

So - the dispatch rule is - if the path matches the script exactly, the methodName parameter will be ignored.

This is designed to follow the same dispatching rule of regular SHP scripts, and to ensure that one script compiles into one api. 

But if you like to use the regular XMLRPC dispatch, it also works - you just need to remove the add2 from the path, as follows:

POST /api HTTP/1.0 # notice - no add2 here 
Content-Type: text/xml; charset=utf-8 

<methodCall>
<methodName>add2</methodName>
<params>
<param><name>a</name><value><int>50</int></value></param>
<param><name>b</name><value><int>90</int></value></param>
</params>
</methodCall>

So instead of posting to /api/add2, just post to /api, and specify add2 in the methodName parameter.  This is called partial path dispatch, for the lack of a better term for now.

NOTE - in order for partial dispatch to work, the /api directory must not contain an index script, because otherwise the index script will be matched first prior to the partial dispatch kicking in.

Partial Path Dispatch With Query String There is another way of doing partial path dispatch, and that involve the using of query string.  Yes, you can specify query string with POST requests, and the query string values will be parsed properly in SHP.

The way to do it is to specify a query key that starts with **.  So for example, if we want to dispatch to /api/add2, we can dispatch as follows:

POST /api?**add2 HTTP/1.0 # note the **add2 key in the query string. 
Content-Type: text/xml; charset=utf-8 

<methodCall>
<methodName>add3</methodName><!-- note the wrong method name --> 
<params>
<param><name>a</name><value><int>50</int></value></param>
<param><name>b</name><value><int>90</int></value></param>
</params>
</methodCall>

The above has exactly the same effect as if you have done a direct dispatch - the ** prefix will be stripped, and then appended to the path.  And this rule, along with the direct dispatch, supersedes the method name in the xmlrpc payload.

This design exists for a reason - to deal with web forms that have multiple submit buttons. 

Web forms that have multiple submit buttons usually have each button mapped to different actions, and instead of requiring you to do manual dispatch on the server side based on which button is clicked (the name & value of the submit button clicked gets submitted to the server side along with the data), you can partition the API calls based on the name of the button (partition on name instead of the value is better, because that way it allows you to localize the value without worrying about breaking the script). 

For example, if you have a server-side-based calculator that has the +, -, *, /, = submit buttons, you can theoretically have the following scripts:

/api/add 
/api/subtract
/api/multiply
/api/divide
/api/equal 

And then have the buttons mapped to the name of **add, **subtract, **multiply, **divide, and **equal, and map the form's action to /api.  SHP will do the dispatching for you correctly.

JSON Request & Responses Besides working with query strings and XMLRPC request and responses, the same api script also can handle JSON requset & responses - you just need to POST the payload with the appropriate content-type, which is text/json.

POST /api/add2 HTTP/1.0 
Content-Type: text/json; charset=utf-8 

{ a : 50 , b : 90 } 

And the response will automatically be a JSON as well:

Content-Type: text/json; charset=utf-8 

140 

Since JSON does not have a method name parameter, it does not have a corresponding partial path dispatch rule, but the query string's partial path dispatch rule remains in effect. 

And of course if you are using JSON you will want to use JSONP, which you can by specifying an additional ~jsonp query string parameter as follows:

POST /api/add2?~jsonp=myCallback HTTP/1.0 
Content-Type: text/json; charset=utf-8 

{ a : 50 , b : 90 } 

Which will generate the following response as a JSONP result:

Content-Type: text/json; charset=utf-8

return myCallback( 140 ); 

That explains the basic rules with regards to using the web api.  The next post will discuss the syntax of the web API, as well as how to extend it so you can use other types.

Chris Aldrich reads a lot of good books. I enjoy hearing about what he has read lately and thought that it would be nice to share his thoughts so I offered that he could post here if he was interested (or until he blogged elsewhere or whatever). He said yes. His user-name is caldrich.

See here.

In 1918, John Byrne invented a two-disk cryptographic machine, which he called a chaocipher; he drew up blueprints, but was unsuccessful in his efforts to sell the machine to the US Signal Corps and Navy. He left several challenge messages in his 1954 autobiography, but no one successfully deciphered the messages. Recently, following the death of Byrne’s son, the son’s widow donated Byrne’s complete archives, including a mock-up of the machine, to the National Cryptologic Museum at Fort Meade, Maryland. Last Friday, Moshe Rubin published the first public description of the chaocipher algorithm.

The algorithm uses two key sequences, one for cipher-text and one for plain-text. Encryption and decryption look up the desired character on one sequence and report the corresponding character on the other sequence, working from plain-text to cipher-text for encryption and from cipher-text to plain-text for decryption.

After each character, both sequences are permuted, each by a different method. Thus, the chaocipher is similar to an autokey cipher, because the key is modified according to the plain-text.

The left disk, which normally represents the cipher-text, is permuted in two steps. First, the entire alphabet is shifted left as far as cipher-text of the current character (so the current cipher-text character becomes the first character in the sequence), with the shifted-off portion of the sequence reattached at the end. Second, the second through fourteenth characters are shifted left one character, and cycled; the third character becomes the second, the fourth character becomes the third, and so on, until the fourteenth character becomes the thirteenth and the second character becomes the fourteenth. For instance, given the sequence HXUCZVAMDSLKPEFJRIGTWOBNYQ and the current character P, the entire sequence is shifted to bring P to the front, giving PEFJRIGTWOBNYQHXUCZVAMDSLK, then the second through fourteenth characters are shifted to move E after Q, giving PFJRIGTWOBNYQEHXUCZVAMDSLK. Byrne invented the terms zenith and nadir to represent the first and fourteenth characters, Rubin refers to zenith and zenith+13, but we’ll just call them by their ordinal positions in the sequence.

The right disk, which normally represents the plain-text, is permuted in three steps. First, the entire alphabet is shifted left as far as the plain-text of the current character (so the current plain-text character becomes the first character in the sequence), with the shifted-off portion of the sequence reattached at the end. Second, the first character is shifted to the end (so the current plain-text character becomes the last character in the sequence). Third, the third through fourteenth characters are shifted left one character, and cycled, similar to the left disk except for the different starting position. For instance, given the sequence PTLNBQDEOYSFAVZKGJRIHWXUMC and the current character A, the final sequence is VZGJRIHWXUMCPKTLNBQDEOYSFA.

Thus, the encryption of WELLDONEISBETTERTHANWELLSAID, given the above cipher-text and plain-text sequences, is OAHQHCNYNXTSZJRRHJBYHQKSOUJY.

Your task is to write functions that perform encryption and decryption according to the algorithm given 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.

You may have noticed that the Contents page changed recently. Previously the Contents page listed all the exercises in chronological order. Now, there are four listings of the exercises, in chronological order, reverse chronological order, permuted by the words in the title and summary, and organized manually by themes.

The four listings all derive from a single source. The file praxis.info consists of records separated by blank lines, fields on a single line with field name followed by a tab character followed by the data element. Here is an excerpt, which shows the header at the beginning of the file followed by the first two records:

praxis.info

number  exercise number
file    base name of files
pubmon  month of publication
pubday  day of publication
pubyear year of publication
title   formatted title
ptitle  plain title
blurb   formatted blurb
pblurb  plain blurb
exer    exercise sub-page number
soln    solution sub-page number
extra   extra info sub-page number
codepad eight-character codepad index
theme   category in which exercise appears

name/value pairs on a line separated by tabs,
with records separated by blank lines

the "number" field must appear first, others
may be in any order, and are optional

----+----1----+----2----+----3----+----4----+----5----+----6

number  1
file    rpn-calculator
pubmon  2
pubday  19
pubyear 2009
title   RPN Calculator
blurb   Evaluate numeric expressions at the command line
exer    1
soln    2
codepad fjzlC50x
theme   Parsing

number  2
file    sieve-of-eratosthenes
pubmon  2
pubday  19
pubyear 2009
title   Sieve of Eratosthenes
blurb   A Scheme implementation of an ancient algorithm
exer    1
soln    2
codepad wI14BJ8Q
theme   Prime Numbers

Four programs manipulate the data from the praxis.info file to produce the four listings. The output has elements of html, but WordPress adds the surrounding context; here is the corresponding excerpt from the listing in chronological order:

<table cellpadding="10">

<tr><td>1</td><td>19 Feb 2009</td><td><a href="/2009/02/19/rpn-calculator/">RPN Calculator</a>: Evaluate numeric expressions at the command line</td><td><a href="/2009/02/19/rpn-calculator/">exercise</a> <a href="/2009/02/19/rpn-calculator/2/">solution</a> <a href="http://programmingpraxis.codepad.org/fjzlC50x">codepad</a></td></tr>

<tr><td>2</td><td>19 Feb 2009</td><td><a href="/2009/02/19/sieve-of-eratosthenes/">Sieve of Eratosthenes</a>: A Scheme implementation of an ancient algorithm</td><td><a href="/2009/02/19/sieve-of-eratosthenes/">exercise</a> <a href="/2009/02/19/sieve-of-eratosthenes/2/">solution</a> <a href="http://programmingpraxis.codepad.org/wI14BJ8Q">codepad</a></td></tr>

</table>

Your task is to write programs that read praxis.info and write the two listing files for exercises in chronological order and reverse chronological order. 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.

On Saturday morning, inspired by Andrew Moylan’s article on Wolfram’s Blog, I sat down to work out a simulation of the knockout stage of the World Cup competition. I used the bracket shown at right, and found elo ratings of the sixteen teams, as of that morning, at Wikipedia:

 1 BRA Brazil        2082
 2 ESP Spain         2061
 3 NED Netherlands   2045
 4 ARG Argentina     1966
 5 ENG England       1945
 6 GER Germany       1930
 7 URU Uruguay       1890
 8 CHI Chile         1883
 9 POR Portugal      1874
10 MEX Mexico        1873
15 USA United States 1785
19 PAR Paraguay      1771
25 KOR Korea         1746
26 JPN Japan         1744
32 GHA Ghana         1711
45 SVK Slovakia      1654

The table shows that there are forty-four national teams with ratings higher than Slovakia’s rating of 1654; they are lucky to be in the tournament.

The likelihood that a team will win its match can be computed from the elo rankings of the team and its opponent according to the formula . Thus, the United States had a 60.5% expectation of winning its match against Ghana this afternoon, and Ghana had a 39.5% expectation of defeating the United States. Harrumph!

Every time a match is played, the elo rating of a team changes. The amount of the change is based on the actual result as compared to the expected result. If a team wins when they have a high expectation of winning, their elo rating goes up by a small amount, since they were expected to win. However, if a team wins when they have a low expectation of winning, their elo rating goes up by a large amount. The formula is , where K is a weighting for the importance of the game (K is 60 for the World Cup), G is a parameter based on the goal differential (we’ll assume that all games are won by a single goal, so G = 1), W is 1 for a win and 0 for a loss, and We is the winning expectation calculated by the formula given above.

Your task is to use the data and formulas described above to simulate the knockout stage of the World Cup a million times and report the number of times each nation wins. 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.

Last Friday I took my first real ride on the bike. It was a lot of fun. Riding a bike with a 10k redline was also a new experience for me which made it fun. Honestly, it was sort of shocking to me, the engine seemed to have 3 moods:

1. Meditating
2. Purring
3. Roaring!

I wondered where the engine should live for normal cruising, and Dale explained that where it seems happy, it is happy. Great. I can’t wait to get back out again to spend some time with my M.U.T.T. Who is M.U.T.T?

As Dan explained… the “Monster Under The Tank”!