Before discussing how to get nice fonts for emacs, it might be reasonable to ask, “why emacs?” I haven’t fully answered that question myself, but had I not been able to get nice, readable fonts on emacs, I probably wouldn’t continue researching it. For the info on getting nice fonts to work, scroll down to “Nice Fonts” below.

After many years of using large IDEs to develop software, I switched to vim about a year and a half ago when I began developing with Ruby on Rails. Although the learning curve for vim was a bit steep, I quickly got to the point of being more productive with vim than I was with my previous IDE, and I’m continually learning features of vim that save me time and effort.

Ok, if vim is so great, why am I considering emacs? In a word, Lisp. Emacs, has great Lisp support. For the little bit of Lisp dabbling I’ve been doing, vim has been fine, but from what I’ve seen demonstrated with emacs and slime, I think it’s worth researching. Another important factor is that emacs is scripted with elisp, a dialect of Lisp. I’ve never taken the time to read up on vim scripting, but scripting emacs with elisp seems easy. Type in some elisp code into the scratch buffer, evaluate it, and it’s integrated immediately into emacs. I haven’t written any vim scripts in a year and a half, but within a few hours of researching emacs, I had implemented several elisp scripts (from source obtained online).

Here’s one to simulate the % command in vim which moves the cursor to the matching paren:

(defun match-paren (arg)
  "Go to the matching paren if on a paren; otherwise insert %."
  (interactive "p")
  (cond ((looking-at "\s(") (forward-list 1) (backward-char 1))
	((looking-at "\s)") (forward-char 1) (backward-list 1))
        (t (self-insert-command (or arg 1)))))

(global-set-key "%" 'match-paren)

Here’s one to simulate the vim o and O commands which open a new line either below or above the cursor and position the cursor properly indented, so you can start typing immediately. I use this quite often in vim:

(defun bja-open-line-below ()
  (interactive)
  (end-of-line)
  (open-line 1)
  (next-line 1)
  (indent-according-to-mode))

(global-set-key [?C-o] 'bja-open-line-below)

(defun bja-open-line-above ()
  (interactive)
  (beginning-of-line)
  (open-line 1)
  (indent-according-to-mode))

(global-set-key [?M-o] 'bja-open-line-above)

After my brief exposure to emacs, I think vim is more concise. In other words, it appears that vim can accomplish a given task with fewer keystrokes than emacs. I’m curious to see how hard it is to extend emacs to have some of the niceties I’m used to with vim. Maybe I can have the best of both worlds - the conciseness of vim and the extensibility and Lisp support of emacs. Lennart Borgman passed on a link to vimpulse.el, so I’ll take a look at it soon.

I swapped my caps-lock with my left control key a long time ago, so the emacs chording isn’t quite as much of a problem, but I still wonder if vim might be easier on the hands/wrists since it requires very little chording.

I know some famous lispers use vi(m) for Lisp development, so I don’t think emacs is a must-have. Also, if I end up using a commercial Lisp such as Lispworks or Allegro, I may consider returning to an IDE for lisp development. So, at this stage, I’m still very much a vim user who is researching emacs.

UPDATE:Well, sometime between the original post and now I became a die-hard GNU Emacs user, so I figured I’d update the post

Nice Fonts

But enough of that, how do you get nice fonts on emacs? I had heard that the new version of emacs (22) provided anti-aliased fonts, but apparently I was mistaken. I spent hours Googling and rebuilding emacs to no avail - quite a frustrating experience. Then I posted a question on the gnu.emacs.help usenet group and received a helpful reply in a few minutes which did the trick. Here’s the thread.

Here’s what I did:

cvs -z3 -d:pserver:anonymous@cvs.savannah.gnu.org:/sources/emacs co emacs
cd emacs
./configure --enable-font-backend --with-gif=no
make bootstrap
make
sudo make install

After that, I was able to use the ‘Bitstream Vera Sans Mono-10′ font, and it looks great!

emacs -r -fn ""Bitstream Vera Sans Mono-10"

The -r flag is for reverse video. I much prefer a black background. After making emacs from the cvs sources, it reports its version as 23.0.60.2.

After editing my ~/.Xresources file to have the following line:

Emacs.font: Bitstream Vera Sans Mono-10

And running the command:

xrdb -merge ~/.Xresources

Emacs automatically uses that font at startup.

During my hours of Googling, I had seen the page with the correct information here. But in my haste, I read the statement, “Note: Since the emacs-unicode-2 branch which had the xft support is merged into trunk, the current page is obsolete.“, and somehow got the impression that the entire page was obsolete, but apparently that is not the case.*

Fortunately, the helpful folks on gnu.emacs.help set me straight - thanks guys!

*UPDATE: I edited the wiki page referenced above, so the “obsolete” notice is further down the page.

This has been a long time in coming. Paul Graham and Robert Morris have released an initial version of the Arc programming language.

Announcement
Language Web Site
Software
Tutorial
Forum

They recommend using version 352 of MzScheme because the latest version apparently breaks Arc. I already had 360 installed and was in a hurry, so I tried it, and most of the tutorial seemed to work fine except for the web server which failed. I’ll try later with 352 and see how it goes.

The language is still quite volatile, so I’m not sure if anyone is too interested in investing a lot of time creating libraries yet, but when the language settles down, I’m very curious about the acceptance level of Arc.

It seems to have quite a bit of Lispy goodness, and I’ve agreed with Paul’s language philosophy from what I’ve read about what he wants Arc to become. Hopefully it will live up to those ideas. On the one hand, I can see benefits in having a standard such as the one for Common Lisp, but on the other hand, Ruby & Python have done extremely well with the BDFL model with Matz & Guido, and I think Paul Graham could pull off that role if he wants to.

A problem with a “standards” approach is the proliferation of implementations dividing the community; whereas, the single implementation languages seem to have a more unified community.

If Arc can retain the best of Lisp, add some niceties from other languages and attract an active developer community, I think it may become very interesting.

rlwrap

Probably one of the best things I’ve gotten out of the Arc release so far was a tip from a guy on the forum on how to add readline support to the Arc REPL using rlwrap. I’d never heard of rlwrap before, and it’s awesome! I can not get readline support for logo and arc without needing to rebuild them with native support.

sudo apt-get install rlwrap
rlwrap logo

What a great idea

I’ve learned a number of programming languages since I began programming 25 years ago. Earlier in my career, my choice of which programming language to learn was largely driven by external factors such as a class or job requirement, or the expectation of job demand in the future.

More recently I’ve enjoyed learning new programming languages both for the joy of learning something new, and for an increase in productivity.

While it’s true that no programming language is a silver bullet, I’ve found that the choice of programming language can provide a dramatic increase in productivity - much more so than many have asserted. The benefit can be direct, by allowing the creation of a solution to a particular problem with less time and effort than it would take using another language, or it can be an indirect by providing new ways to think about a solution.

Do you think language affects how we think?

The Past

In 1982, I spotted a Radio Shack Color Computer in a store window and immediately applied for a Radio Shack credit card which had a credit limit ($500) sufficient to purchase the computer which had 4K of RAM (I later upgraded to 16K) and no external storage (unless you count the ability to hook up a cassette recorder). Contrast the 16K RAM of that early machine with my current 2,097,152K RAM

That was the beginning of a life long interest in programming.

In the language list below, bold indicates a more significant professional involvement, and the year indicates when I first learned the language. I’ve also likely forgotten a few:

1. 1982 - Radio Shack Extended Color BASIC
2. 1983 - 6809e Assembler
3. 1983 - Pascal
4. 1984 - HP 48SX RPL
5. 1984 - S/360 Assembler
6. 1985 - COBOL
7. 1985 - dBase III / Metafile
8. 1985 - C
9. 1985 - 8088/8086 Assembler
10. 1986 - C++
11. 1996 - Java
12. 1997 - Perl
13. 2002 - C#
14. 2004 - Python
15. 2005 - JavaScript
16. 2006 - Ruby
17. 2007 - PHP

The Present

Currently, I program primarily in Ruby, followed by JavaScript and the occasional PHP script. Ruby is the most productive programming language I’ve used thus far. The combination of power, pragmatism & pleasure in programming is hard to beat. If it also had performance, it would be a truly great language.

I’ve also begun learning Logo as I teach my daughter how to program. Logo is a great introduction to the Lisp family, so I hope to leverage it as I learn Scheme and Common Lisp later this year.

The Future

After completing the Logo course with my daughter, I plan on moving on to Scheme as I go through Structure and Interpretation of Computer Programs which some have called the greatest computer science text ever written.

After Scheme I plan on learning Common Lisp which has the potential to replace Ruby as my primary programming language.

Beyond Logo/Scheme/Common Lisp, the following languages are of interest:

• Haskell
• Erlang
• Lua
• ML
• OCaml

If you know of candidates for a future programming language, feel free to add it in a comment.

You may notice that Smalltalk is lacking from the lists above. Despite its prominence in programming language history, I currently don’t feel that Smalltalk is sufficiently better/different than Ruby to warrant an investment in learning it.

After focusing on object oriented for twenty years, I have more of an interest in the functional world of programming languages (and multiple dispatch is cool ).

Update: I was just over at Hacker News and saw something I’ve seen many times before. In a nutshell, some guy was stating that Paul Graham’s success with ViaWeb had little to do with his choice of programming language (Lisp) and more to do with him just being a good hacker. In other words, he could’ve written it in any language. I’m so glad Paul responded because his response confirms my thoughts on the matter:

What a weird situation. I keep trying to tell people Lisp is great, and they say, no, no, you guys were just really good programmers. But if I’m such a good programmer, why don’t they believe me?

Paul Graham has written a lot on Lisp and is one of the main factors in me becoming interested in Lisp (along with the fact that Ruby pulled a lot of good ideas from it), but the simple quote above communicates volumes IMO.

I decided last spring that it was a good time to begin teaching my eldest daughter how to program. She was eleven at the time and had demonstrated both interest and aptitude. So after researching various programming languages, I chose to use the Logo programming language - specifically, Berkeley Logo.

There are many good programming languages to choose from to teach children how to program depending on their abilities and interests, but I felt the benefits of Logo gave it the edge. It has much of the power of the Lisp family of languages but with a simpler syntax. The syntax is very uniform which saves children from having to learn too many inconsistent oddities of other languages (including my current favorite, Ruby). I had a preconceived idea that Logo was primarily about turtle graphics, so I was quite surprised when I dug a little deeper and found a very expressive language built on a solid foundation. Having said that, I think the availability of turtle graphics in Berkeley Logo is a big plus for allowing visual feedback for children.

In August, I wrote a blog post comparing a short function (from Brian Harvey’s home page) in Logo and several other languages. Several people added other versions in the comments. It may give you a glimpse of the conciseness and expressiveness of Logo.

In deciding on a programming language, I purposely ignored IDEs. In fact, I’ve discovered that more powerful languages are much less dependent on the availability of good IDEs. For example, when I switched from Java to Ruby, I didn’t miss Eclipse at all, and I’m much more productive with Ruby and a good text editor than I was with Eclipse and Java. On the other hand, I’ve heard some glowing testimonial from Smalltalk and Lisp IDE users, so I expect I’ll be experimenting with Lisp IDEs in the future.

Getting Started

Many thanks to Brian Harvey of UC Berkeley both for UCBLogo (along with other contributors) and for making excellent teaching materials freely available.

On Ubuntu Linux, simply install the ucblogo package. This will also install a PDF reference manual for Berkeley Logo which I recommend becoming familiar with.

You can also find links for other platforms on Brian Harvey’s home page.

Here are links to the free text books:
Computer Science Logo Style Volume 1: Symbolic Computing
Computer Science Logo Style Volume 2: Advanced Techniques
Computer Science Logo Style Volume 3: Beyond Programming

There is also a comp.lang.logo usenet group. You can access that via an nntp reader, or via Google below:
http://groups.google.com/group/comp.lang.logo/topics?hl=en

Methodology

My teaching methodology thus far has simply been to have my daughter read a chapter, and then complete a short assignment of questions and programming exercises that I’ve designed to ensure she’s mastered the important concepts in the chapter. I’ll spend some time with her explaining the solutions to problems she may have missed.

If there’s interest, I can provide the complete set of chapter assignments including questions & answers and programming problems & solutions once we’ve completed volume 1. Feel free to leave a comment, if you’d like a copy.

Some Quotes

Here are some quotes from the preface of “Computer Science Logo Style vol 1″ to whet your appetite

The truth is that Logo is one of the most powerful programming languages available for home computers.

In Logo there is only one syntax, the one that invokes a procedure.

More powerful languages are based on some particular mathematical model of computing and use that model in a consistent way. For example, APL is based on the idea of matrix manipulation; Proglog is based on predicate calculus, a form of mathematical logic. Logo, like Lisp, is based on the idea of composition of functions.

Conclusion

I highly recommend learning Logo whether you’re teaching your children to program or you simply want to learn another programming language. I’ve found both to be beneficial to my professional programming career. The Berkeley version of Logo is very powerful and has the following special features (from the intro to the UCBLogo reference manual):

• Source file compatible among Unix, Windows & Mac
• Random-access arrays
• Variable number of inputs to user-defined procedures
• Mutators for list structure
• First-class instruction and expression templates
• Macros

I’ve entitled this Part One because I intend to follow up with some more posts as we become more familiar with the language.

We’ve also been dabbling in some simple robotics projects. I would love to find a robotics controller, or kit, that allows programming in Logo - if anyone knows of such a thing, please let me know.

Happy programming

I came across a web site recently that prompted me to enter two names before I could view the site. So I wondered how difficult it would be to write a Ruby program that could pass the challenge. As you’d expect, it’s trivial in Ruby. If you encounter such a site, please don’t use the code in part two unless it’s permitted by the terms of service of the site in question.

Part One - Obtain a file of names

I found a government site that provided lists of the 1,000 most popular names for each decade, so I wrote a Ruby program to screen scrape the names into a list in order of popularity.

Make the open-uri library available.

require 'open-uri'

Create a simple Struct to contain the url for each decade along with an array for boy names and girl names (the site provides an ordered list for each gender). Then create an array of Decade instances for 80’s, 90’s and 00’s.

Decade = Struct.new(:url, :boy_names, :girl_names)
decades = [
  Decade.new('http://www.ssa.gov/OACT/babynames/decades/names1980s.html', [], []),
  Decade.new('http://www.ssa.gov/OACT/babynames/decades/names1990s.html', [], []),
  Decade.new('http://www.ssa.gov/OACT/babynames/decades/names2000s.html', [], [])
]

Iterate over each decade and screen scrape the list of boy names and girl names.

decades.each do |decade|
  str = open(decade.url).read
  str.scan(/<tr><td align="right">.*?<td width="15%">(w+)</td>.*?<td width="15%">(w+)</td>/m) do
    decade.boy_names << $1
    decade.girl_names << $2
  end
end

Now we have a pair of lists (boys & girls) for each decade with each list in order of popularity - 6 lists in total. We want to form a single list by selecting the most popular name from each of the 6 lists, followed by the second most popular name, etc. The zip function comes to mind, so we’ll first create an array of the 6 lists.

name_lists = decades.inject([]) do |result, decade|
  result << decade.boy_names
  result << decade.girl_names
  result
end

Now we have a list containing 6 lists. Here is where the “everything is an object” aspect of ruby is a bit of a pain. What I want to do is simply zip the 6 lists together, for example:

x = zip(one, two, three, four, five, six)

but I’m forced to pick one of the lists to be the instance for the zip method, for example:

x = one.zip(two, three, four, five, six)

I suppose my dissatisfaction is due in part to my recent research in functional programming.

The line below will do the following (I really like Ruby ):

1. pop one of the lists off of the main list (leaving 5) to be the instance for zip
2. explode the list of 5 remaining lists into 5 individual arguments via the * operator
3. zip the 6 lists together
4. flatten the resulting list of lists produced by zip into one list
5. remove duplicate entries
6. write each name to standard output

(name_lists.shift).zip(*name_lists).flatten.uniq.each {|name| puts name }

Run the program as follows to create a file named names.txt which will be used in part two.

ruby scrape_names.rb > names.txt

Part Two - Brute force form submission

Now that we have a list of over 2,000 names, it’s a simple matter of repeatedly trying pairs of names in order of popularity. Here’s the program in its entirety with comments following:

 1  require 'net/http'

 2  names = ARGF.inject([]) {|result, line| result << line.chomp; result } 

 3  Net::HTTP.start('www....com') do |query|
 4    headers = { 'Content-Type' => ‘application/x-www-form-urlencoded’ }
 5    (1…names.length).each do |i|
 6      (0..i).each do |j|
 7        response = query.post(’/guess/’,
 8          “name1=#{names[i]}&name2=#{names[j]}”, headers)
 9        if !response.body.include?(’Failed’)
10          puts “Answer: #{names[i]}, #{names[j]}”
11          exit
12        end
13      end
14    end
15  end

Line 1: makes the HTTP library accessible.

Line 2: reads a list of names from standard input into an array.

Line 3: opens a TCP connection to the specified web server (site withheld for privacy).

Line 4: through trial and error I discovered that contrary to the example in the Pick Axe p. 700, I need to add this header to get the form submission to work.

Lines 5-6: setup the iteration to compare each name (beginning with the second) with each of the previous names up to and including the current one (in case the answer is two identical names).

Lines 7-8: perform an HTTP post with the pair of names.

Lines 9-11: if the retrieved page doesn’t contain a failure string, print the solution to standard output and exit.

Run the program as follows:

ruby guess_names.rb < names.txt

There you have it - a pair of Ruby programs to pass a “guess two names to enter” challenge. The amount of time to find a solution will depend on the uncommonness of the names used. This is an O(n^2) algorithm, so if the names in the solution are near the bottom of the popularity scale, expect a long run time. The name list I produced had 2,697 names, so the worst case scenario is (2697 * 2698) /2 -1 = 3,638,252 requests. If only the first 100 names need to be compared there would be 5,049 requests.

This algorithm is trivial to parallelize - just change line 5 above from (1…names.length) to multiple non-overlapping ranges (one per process), and let her fly.

Ruby has many benefits and is currently my most productive programming language, but I think it particularly shines in this type of ad-hoc, web-enabled task because of the expressiveness of the language and the availability of useful libraries. I highly recommend putting it high on your list of languages to learn if you don’t already use it.

This is one of the coolest ideas I’ve seen in a while. Bug Labs is developing some technology that should be very interesting to any geek. Another great find by Robert Scoble. The video quality isn’t high because they were recorded on his cell phone, but I’m glad he had a video capable cell phone with him when he bumped into Peter.

Part One
Part Two
Part Three

I prefer using vimdiff or gvimdiff to view differences between files. When researching ways to allow using vimdiff to view subversion differences, I came across this article.

The bottom line is that subversion passes the two relevant arguments as the 6th and 7th arguments, so the following shell script wrapper does the trick:

#!/bin/sh
/usr/bin/gvimdiff ${6} ${7}


Save the script as gvimdiff_wrapper.sh, make it executable and accessible on your path. Then modify $HOME/.subversion/config to have the following line:

diff-cmd = gvimdiff_wrapper.sh


That will allow you to use gvimdiff to display the diff generated by svn diff my_file.txt

Someone posted a question on comp.lang.ruby recently asking for help with solving anagrams. The poster originally asked about ways of generating permutations and several people pointed him to the facets library which has some permutation utility functions. As it turns out, I benchmarked the following naive permutation generator as 3 times faster than the facets library code:

def words chars, result='', &b
  if chars.empty?
    yield result
  else
    chars.length.times do |i|
      c = (x = chars.clone).slice!(i)
      words(x, result + c, &b)
    end
  end
end

However, generating all possible combinations of letters in an anagram is a very bad approach which doesn’t take into consideration key knowledge about the problem. Rather than generating all permutations of an anagram, which is infeasible for longer words, we can precompute a hash from our dictionary by using the sorted letters of words as keys. Then to solve an anagram, we simply sort the letters in the anagram and look it up in the hash.

The first program creates the hash and serializes it to disk for future anagram solving:

words = Hash.new([])

File.open("/usr/share/dict/words", "r") do |file|
  while line = file.gets
    word = line.chomp
    words[word.split('').sort!.join('')] += [word]
  end
end

File.open("word_hash", "w") do |file|
  Marshal.dump(words, file)
end

The second program loads the serialized hash from disk to solve anagrams that we type at the console:

words = nil

File.open("word_hash", "r") do |file|
  words = Marshal.load(file)
end

while true
  print "Enter word: "
  anagram = gets.chomp
  sorted_anagram = anagram.split('').sort!.join('')
  p  words[sorted_anagram]
end

This is really fast, but there are probably better methods. If you have one, feel free to add a comment with the code.

I was reading an article about adding code to JavaScript to make it more functional, and one of the blog commenters mentioned some built-in features that were added to JavaScript 1.6 & 1.7 on Firefox, so I checked out the links (see below) - very cool stuff.

• Array methods
  • indexOf
  • lastIndexOf
  • every
  • filter
  • forEach
  • map
  • some
• Array & String generics
• Generators & Iterators
• Array Comprehensions
• Block Scope w/ let
• Destructuring Assignment
• etc.

They won’t help if you have to target IE also, but it should be possible to conditionally include your own code to implement the ones that don’t require syntactic changes for pages loaded from IE. That would reduce network load for customers using Firefox.

New in JavaScript 1.6 (Firefox 1.5)

New in JavaScript 1.7 (Firefox 2.0)

Hopefully IE will catch up someday, but if not, I can see taking advantage of Firefox specific JavaScript enhancements for niche applications. Firefox is so easy to install, that it should be easy to convince customers to use it for certain custom applications.

Did you know you can write C code directly within a Ruby program? I learned that at the Ruby Hoedown here in Raleigh and thought I’d share it for those who aren’t aware of it.

First install the rubyinline gem.

sudo gem install rubyinline

Then code

require 'rubygems'
require 'inline'

class MyTest
  inline do |builder|
    builder.c "
      long factorial(int max) {
        long result = 1;
        while (max >= 2) {
          result *= max--;
        }
        return result;
      }"
  end
end
t = MyTest.new
puts t.factorial(10)

The first time you run this it will be slower than subsequent runs because the C code will be compiled and cached. Typically you’ll find the generated C code in ~/.ruby_inline

Enjoy,
Brian

I came across a web site that required job candidates to solve a puzzle to be able to access a job application page. I’m a sucker for puzzles. The original puzzle is at the following site:

http://www.telogis.co.nz/

But in case, they take it down at some point, here is the plain text version nicely formatted:

z = 4254145 * 0x18712495;
b = (z & 1) << 4;
a = b--;
o = [];
c = a - b;
x = b - a;
while (z) {
  x = a & x ? a & b : c + x;
  {
    o[z & b^x] = (x + 6 * a + b / 5 - c).chr;
    z = z / a / a;
  } if (!(z / a & b^x))
}

To apply go to “http://www.telogis.co.nz/” + o + “.html”

I don’t think this will parse correctly in any language, but I decided to solve the puzzle using Ruby since it wasn’t that far from it and Ruby is my main programming language currently. I had a couple false starts due to a subtlety in Ruby compared to other languages.

I’ll come back in a while and post the Ruby solution, but I don’t want to post a spoiler too soon.

Lojic Technologies is gearing up for new business projects. I finally got around to putting up a portfolio page with a few past projects.

http://www.lojic.com/portfolio/

We’re currently offering a 10% referral fee, so if you become aware of businesses or individuals in need of web sites or web applications, let me know. Once my referral advertising system is completed (in the next few weeks), we’ll integrate it with the corporate site to track referrals automatically.

Brian

I came across a puzzle article that mentioned the 8 Queens problem. It’s been a long time since I encountered it, but I can’t recall if I ever took the time to code it up, so I took a few minutes to code up a couple versions in Ruby. I was impressed with how easy it was in Ruby. If Ruby had the macros and efficiency of Lisp, I’d be pleased.

In a nutshell, the idea is to determine all possible ways to arrange 8 queens on a chessboard so that none are attacking another.

I’m sure my solution is naive since it was pretty much the first approach I thought of, but it cranks out all solutions in a quarter of a second, so it’ll do

require 'pp'

def valid? stack
  q2 = stack.length - 1
  (0..stack.length-2).each do |q1|
    return false if stack[q1] == stack[q2] || (q1-q2).abs == (stack[q1]-stack[q2]).abs
  end
end

def queens stack, n
  if n == 8
    pp stack
  else
    (1..8).each do |rank|
      stack.push(rank)
      queens(stack, n+1) if valid?(stack)
      stack.pop
    end
  end
end

queens [], 0

I then became curious about abstracting away the concept of:
1) push something onto a stack
2) do something with the stack
3) pop something off the stack

So, I opened up the Array class and modified push to accept a block.

require 'pp'

class Array
  alias_method :orig_push, :push
  def push obj
    orig_push(obj)
    if block_given?
      yield self
      pop
    end
  end
end

def valid? stack
  q2 = stack.length - 1
  (0..stack.length-2).each do |q1|
    return false if stack[q1] == stack[q2] || (q1-q2).abs == (stack[q1]-stack[q2]).abs
  end
end

def queens stack, n
  if n == 8
    pp stack
  else
    (1..8).each do |rank|
      stack.push(rank) {|s| queens(s, n+1) if valid?(s) }
    end
  end
end

queens [], 0

It makes the code 15% slower, and I don’t like modifying the existing push method in this way, but it does show the convenience of Ruby blocks and how you can extend existing classes. I think a better approach would be to introduce a new function - either standalone as below, or in the Array class.

def push_with_block stack, obj
  stack.push(obj)
  yield stack
  stack.pop
end

I came across a little programming puzzle on comp.lang.ruby.

The author blogged about it here - nice solution. He refers to the original paper that got things started, but I haven’t had time to read it in depth yet.

I thought I’d try something a little different. I was going for simple and came up with a 3 function solution using just hashes and arrays. It’s not very general except for the handy combinations(array, n) function I wrote, and it certainly doesn’t feel Rubyish, but it was fun.

Something tells me that Lisp can handle this nicely, so I’ll probably write a Lisp version later.

require 'pp'
TOYS = { :buzz => 5, :woody => 10, :rex => 20, :hamm => 25 }

def combinations array, n
  result = []
  if n > 0
    (0 .. array.length - n).each do |i|
      combs = [[]] if (combs = combinations(array[i + 1 .. -1], n - 1)).empty?
      combs.collect {|comb| [array[i]] + comb}.each {|x| result << x}
    end
  end
  return result
end

def generate_states state
  forward = state[:position] == :forward
  args = forward ? [state[:source], 2] : [state[:destination], 1]
  combinations(*args).inject([]) do |states, movers|
    states << {
      :minutes => state[:minutes] - TOYS[movers.max {|a,b| TOYS[a] <=> TOYS[b] }],
      :source => forward ? state[:source] - movers : state[:source] + movers,
      :destination => forward ? state[:destination] + movers : state[:destination] - movers,
      :position => forward ? :backward : :forward,
      :history => state[:history] + [[ state[:position], movers ]] }
    states
  end
end

def play_game state
  if state[:source].empty?
    pp(state[:history]) unless state[:minutes] < 0
  else
    generate_states(state).each {|new_state| play_game new_state }
  end
end

play_game({
  :minutes => 60,
  :source => [ :buzz, :woody, :rex, :hamm ],
  :destination => [],
  :position => :forward,
  :history => [] })

UPDATE: Something didn’t quite feel right about my first solution, so I took a second look at the op’s solution and decided I liked his use of Ruby blocks. They add some flexibility and efficiency in this case. Instead of computing a full array of possible states at each level of recursion (not as bad as precomputing the entire tree, but still not good), the new solution does a depth first search via block yields. I also removed the hardcoded print statement in play_game and yield the solution to the caller’s block to do with as they please.

require 'pp'
TOYS = { :buzz => 5, :woody => 10, :rex => 20, :hamm => 25 }

def combinations array, n
  result = []
  if n > 0
    (0 .. array.length - n).each do |i|
      combs = [[]] if (combs = combinations(array[i + 1 .. -1], n - 1)).empty?
      combs.collect {|comb| [array[i]] + comb}.each {|x| result << x}
    end
  end
  result
end

def execute_move state, forward, movers
  { :minutes => state[:minutes] - TOYS[movers.max {|a,b| TOYS[a] <=> TOYS[b] }],
    :source => forward ? state[:source] - movers : state[:source] + movers,
    :destination => forward ? state[:destination] + movers : state[:destination] - movers,
    :position => forward ? :backward : :forward,
    :history => state[:history] + [[ state[:position], movers ]] }
end

def each_state state
  combinations(*(
    forward = state[:position] == :forward) ?
    [state[:source], 2] :
    [state[:destination], 1]).each {|movers| yield execute_move(state, forward, movers) }
end

def play_game state, &b
  if state[:source].empty?
    yield(state[:history]) unless state[:minutes] < 0
  else
    each_state(state) {|new_state| play_game new_state, &b }
  end
end

play_game({
  :minutes => 60,
  :source => [ :buzz, :woody, :rex, :hamm ],
  :destination => [],
  :position => :forward,
  :history => [] }) {|history| pp history }

I’ve been teaching my eldest daughter to program in Logo over the summer. Brian Harvey has posted PDF files for a set of excellent books on learning to program in Logo on his web site. The Berkeley version of Logo he’s produced is really excellent. It’s not just your typical turtle graphics language; it has arrays, macros, file processing, graphics, etc.

While perusing his site, I came across a tiny Logo program that demonstrates a little of its power. I was curious what it would look like in Ruby, so I ported it, then I had to see what it looked like in JavaScript.

The formatting is a little messed up due to Wordpress, but each of the three choices functions is 4 lines long.

If anyone wants to add other languages, that would be great!

See the sample page for example output.

Logo

to choices :menu [:sofar []]
  if emptyp :menu [print :sofar stop]
  foreach first :menu [(choices butfirst :menu
      sentence :sofar ?)]
end
choices [[small medium large]
  [vanilla [ultra chocolate] lychee [rum raisin] ginger]
  [cone cup]]


UPDATE 9/2/07: Got an even more concise solution from Brian Harvey:

to choices :menu
   foreach crossmap "sentence :menu "print
end

Ruby

def choices menu, sofar=[]
  if menu.empty?: puts sofar.join(' ')
  else menu[0].each {|item| choices(menu[1..-1],
    sofar + [item]) } end
end
choices [['small', 'medium', 'large'],
  ['vanilla', 'ultra chocolate', 'lychee', 'rum raisin', 'ginger'],
  ['cone', 'cup']]


JavaScript

function choices(menu, sofar) {
  if (emptyp(menu)) print(sofar);
  else foreach(menu[0],
   function (x) {
    choices(menu.slice(1), sofar.concat(x)); });
}
choices([['small', 'medium', 'large'],
  ['vanilla', 'ultra chocolate', 'lychee', 'rum raisin','ginger'],
  ['cone', 'cup']], []);


I had to create a few helpers for the JavaScript version:

function emptyp(a) {
  return a.length === 0;
}
function print(list) {
  foreach(list, function (x) { document.write(x + ' '); });
  document.write('<br />');
}
function foreach(arr, f) {
  for (var idx in arr) { f(arr[idx]); }
}


UPDATE: Use <pre> </pre> tags to allow easier formatting of code. Bummer, I just discovered that Wordpress strips the <pre> tags from normal users I’ll go ahead and wrap code with it as they come in, so if your comment looks bad at first, it’ll be cleaned up shortly.

I wrote an article back in May about a way to give half star ratings on Netflix. It had the advantage of working in any browser and not requiring any software installation, but it wasn’t very user friendly.

Since then, I’ve been doing a lot of JavaScript coding, so I thought I’d give Greasemonkey a try. I found a script here to give half-star ratings, but I didn’t care for the hover captions and JSLint pointed out a few issues, so I cleaned it up a little:

Code

// ==UserScript==
// @name Netflix Half Stars
// @description allows half star user ratings on Netflix
// @include http://*netflix.com/*
// ==/UserScript==
// http://userscripts.org/scripts/review/8118
// Modified by Brian Adkins

return 0;
};


Installation

Save the JavaScript code with .user.js extension e.g. netflix_halfstar.user.js and then open that file in Firefox and Greasemonkey should prompt you to install it.

Peter Seibel is working on a book, “Coders at Work”, that will “contain interviews with around sixteen of the most interesting computer programmers alive today”. He has a page that lists 284 programmers, with links to more info on each one, that I think is worth perusing:

284 Coders

Peter is the author of Practical Common Lisp which I highly recommend.

Also see his Google Talk on Common Lisp.

I noticed on Rick DeNatale’s blog that the videos for Ruby Hoedown 2007 are now available.

Here’s Peter Seibel’s “Practical Common Lisp” talk at Google (about an hour):

Google Video Link

I just signed up for the Ruby Hoedown conference. It’s being held here in Raleigh at Red Hat headquarters on August 10 & 11, and the cost is only $100. Speakers include Bruce Tate, Marcel Molina Jr., Ken Auer, Ezra Zygmuntowicz (cool name ), Andrea O. K. Wright, Jay Phillips & Jared Richardson.

I also signed up for the charity workshop on testing techniques put on by Marcel Molina, Jr., Bruce Tate, and Chad Fowler - the donation proceeds for that workshop go to the Food Bank of Central & Eastern NC. It will probably be a smaller group with more interaction.

Should be an interesting and fun time - gain some knowledge, make some contacts. Let me know if you’re also planning on attending.

Some links:

• “Programming Ruby” by Dave Thomas
• “Agile Web Development with Rails” by Thomas & Heinemeier Hansson
• The Ruby Language
• Ruby on Rails
• Mongrel - Ruby web server