Ruby Quiz

by Harrison Reiser

Internal Rate of Return (IRR – http://en.wikipedia.org/wiki/Internal_rate_of_return) is a common financial metric, used by investment firms to predict the profitability of a company or project. Finding the IRR of a company amounts to solving for it in the equation for Net Present Value (NPV – http://en.wikipedia.org/wiki/Net_present_value), another valuable decision-making metric:

N C_t
NPV = Σ ------------
t=0 (1 + IRR)**t

This week's quiz is to calculate the IRR for any given variable-length list of numbers, which represent yearly cash flows, the C_t's in the formula above: C_0, C_1, etc. (C_0 is typically a negative value, corresponding to the initial investment into the project.) From the example in the Wikipedia article (http://en.wikipedia.org/wiki/Internal_rate_of_return), for instance, you should be able to produce a rate of 17.09% (to four decimal places, let's say) from this or a similar command:

Keep in mind that an IRR greater than 100% is possible. Extra credit if you can also correctly handle input that produces negative rates, disregarding the fact that they make no sense.

There has been a lot of talk recently about parsing with Ruby. We're seeing some parser generator libraries pop up that make the task that much easier and they've been stirring up interest.

In honor of that, this week's Ruby Quiz is to write a parser for JSON.

JSON turns out to turns out to be a great little example for writing parsers for two reasons. First, it's pretty easy stuff. You can hand-roll a JSON parser in under 100 lines of Ruby. The second advantage is that the data format is wonderfully documented:

JSON

Since JSON is just a data format and Ruby supports all of the data types, I vote we just use Ruby itself as the abstract syntax tree produced by the parse.

Feel free to show off your favorite parser generator, if you don't want to roll your own. Anything goes.

Here are a few tests to get you started:

In "Practical Ruby Projects," the author includes a couple of chapters involving coin simulations. These simulators are used to explore the possibilities of replacing a certain coin or adding a new coin.

One interesting subproblem of these simulations is that of making change. For example, if we need to give 39 cents change in the United States (where there are 25, 10, 5, and 1 cent pieces), we can give:

What if the coins were 10, 7, and 1 cent pieces though and we wanted to make 14 cents change? We would probably want to do:

This week's Ruby Quiz is to complete a change making function with this skeleton:

Your function should always return the optimal change with optimal being the least amount of coins involved. You can assume you have an infinite number of coins to work with.

This week's Ruby Quiz is to write a script that finds the longest repeated substring in a given text.

Your program will be passed some text on STDIN and is expected to print the longest repeated substring within that text to STDOUT.

Repeated substrings may not overlap. If more than one substring is repeated with the same length, you may print any of them. If there is no repeated substring, the result is an empty string (print nothing).

Example:

$ echo banana | ruby longest_repeated_substring.rb
an

OR

$ echo banana | ruby longest_repeated_substring.rb
na

Make sure your code runs efficiently when passed a large text.

Learning to count cards is much easier than Hollywood or the casinos would have us believe. Some systems only require you to track a single running total in your head.

One such system, called the Knock-out system of card counting, is extra easy. You start your count at 4 - (4 x number_of_decks). That gives us an initial running count of 0, -4, -20, or -28 for the common casino shoe sizes of 1, 2, 6, or 8 decks. From there, you add one each time you see a 2, 3, 4, 5, 6 or 7 and subtract one when you see a 10, jack, queen, king, or ace. The 8 and 9 cards do not affect the count. Once you learn to track the running count, you can make strategy decisions and vary your bets based on the times when the count is in your favor.

That's not a lot to remember, but it does take practice to get fast. You really need to get to where you can count a deck in 20 to 30 seconds if you are going to keep up with those fast moving casinos dealers.

This week's Ruby Quiz is to build a training program for helping you learn to count cards.

The program needs to show you one or more cards at a time, running through a Blackjack shoe. As it goes, the program should track the running count. Have it pause at random intervals, ask you the count, and notify you if you are right or wrong.

Both the time to go through the deck and the number of cards displayed at a time should be configurable. It's important to practice with seeing multiple cards at once because you learn to cancel out pairs of high and low cards. It might even be nice to provide a mixed mode, which varies the number of cards shown at a time.

You can show cards as simple Strings, ASCII art, or full graphics as you prefer. You may wish to make cards fully disappear after their display time though, to make the conditions more like they would be in a casino.

The majority of the strategy in Blackjack hinges around the dealer's hand. The reasons are likely obvious to most of you: that's the hand you have to beat and the dealer plays by fixed rules we can predict.

For those unfamiliar with Blackjack, you only need to know a tiny bit about the game for the purposes of this exercise. The goal for both the player and the dealer is to draw cards to make a hand with the highest total possible, without going over 21. Going over 21 is called "busting" and it means you lose the hand. Face cards count for ten, aces are one or eleven (whichever is better for the hand), and all other cards count for their face value. You start with two cards and, if they happen to be a ten valued card and an ace (a count of 21), the hand is called a "natural." A natural is an automatic win in most cases.

The dealer begins with one of his two cards face up and one face down. We call the former the "upcard." The dealer will "hit" or take more cards until he reaches a count of 17 or higher. After that he will "stand" or leave the hand where it is. That tells us that there are only seven possible outcomes for the dealer: get dealt a natural, bust, or hit to a total of 17, 18, 19, 20, or 21.

We start every hand knowing half of what the dealer holds thanks to the upcard. Believe it or not, you can make pretty reliable guesses about how the hand will go with just that knowledge.

Write a Ruby program that shows the percent chance of a dealer reaching each possible outcome based on the upcard showing.

I'll give you some hints to verify your results. Basic Blackjack strategy teaches that we should assume the dealer "has a ten in the hole" (as the face down card). It's not always true, of course, but 17 is a common outcome for a dealer with an upcard of seven. Finally, we call five and six "the dealer's bust cards" for reasons that will become obvious if you are outputting correct percentages.

In the casinos Blackjack is often played with more than one deck shuffled together. One, two, six, and eight deck games are common. You may want to offer the option to adjust the deck size your program uses. Either way, let's default to two decks as an average of what a player will face.

This is a non-traditional Ruby Quiz that changes the rules of the contest. Please read the entire message before playing along. We will be back to normal quizzes next time, for those that end up missing them.

The Game

Eric Hodel described Programmer Ping-Pong in his RubyConf 2007 presentation. I wasn't familiar with the concept before that and it sounds like fun, so let's all try it out together.

The rules are:

* This quiz does not have a no-spoiler period so you may
submit at anytime after reading this message
* I'll make the initial serve, starting the quiz off with
a single failing test
* Anyone can return the ball at anytime by doing exactly
two things, in order: make all tests pass including the
recently added failure and then add a new failing test
of your own

I want to see if we can build an entire library using just that process.

The Task

Let's build a pure Ruby binary AVL tree. An AVL tree is a self-balancing binary tree data structure where insertion, deletion, and lookup all take O(log n) time to execute. This is handy to have for many search problems that must run quickly. It can also be used to build constructs like an OrderedHash.

You can read more about AVL trees on Wikipedia:

AVL tree

There's also a handy document describing their rotations in detail:

AVL tree Rotations Tutorial

What features our AVL tree will support will be decided by you as you write tests. Here are some suggestions of things we might try though, just to get you thinking:

* Support for custom Ruby objects as nodes of the tree
* The ability to customize the comparison code, perhaps with a block
* A String output visualizer, possibly for the inspect() method
* Any other great features you can think of to add

The Details

We will have two files: avl_tree.rb and test_avl_tree.rb. Please pass both files in each submission email you make for this quiz. Let's not complicate this with directory structures or zip files.

Please don't add any external dependencies, unless it's a standard library. We want everyone to be able to easily run this code and play along.

We are using Test::Unit instead of RSpec, or any other tool, for similar reasons.

Please keep your tests short. Under 10 lines is preferred, but don't go over 24.

Also try to test just one aspect of the implementation with each test. I did purposely say "aspect" and not "method." I do test more than one method in the serve and I can imagine other scenarios where it could be useful, like checking support for a handful of the standard Enumerator methods.

You can refactor any code as needed provided you do not change its function and all tests still pass after you do so.

Adds comments if you need to, but writing code that needs no comment would be even better.

Let's use some simple spacing conventions to keep all of us on the same page. Indent two space and do not use tabs. Break up long lines so they do not exceed 80 characters.

Finally, this quiz has the potential to be very chaotic. Take pity on your quizmaster who must track this process and on the rest of the community who may be bothered by a highly active thread. I suggest good email manners:

* Use your client's "Reply" feature and make sure you are replying to
the message that contains the test you made pass
* Trim any unneeded context from the reply, including the previous
version of the code since you will be including the current copy
of the whole thing
* Kindness to your fellow programmers trumps any listed guidelines

The Serve

The initial contents of avl_tree.rb are:

ruby #!/usr/bin/env ruby -wKU

class AVLTree

end

The test file, test_avl_tree.rb, begins as:

ruby #!/usr/bin/env ruby -wKU

require "test/unit"

require "avl_tree"

class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

def test_tree_membership
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))

@tree << 3

assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(3))
end
end

Here's a fun little challenge from the Educational Computing Organization of Ontario.

Given a single word as input try to find a repeated letter inside of it such that you can loop the text around and reuse that letter. For example:

$ ruby word_loop.rb Mississippi
i
p
p
Mis
ss
si

or:

$ ruby word_loop.rb Markham
Ma
ar
hk

or:

$ ruby word_loop.rb yummy
yu
mm

If a loop cannot be made, your code can just print an error message:

$ ruby word_loop.rb Dana
No loop.

There are many different ways to write mathematical equations. Infix notation is probably the most popular and yields expressions like:

2 * (3 + 5)

Some people like to work with a postfix notation (often called Reverse Polish Notation or just RPN) though, which doesn't require parentheses for the same equation:

2 3 5 + *

You can compare the results of these equations using the Unix utilities bc (infix) and dc (postfix):

$ bc <<< '2 * (3 + 5)'
16
$ dc <<< '2 3 5 + * p'
16

The "p" instruction tacked onto the end of the expression for dc just tells it to print the result.

This week's quiz is to write a script that translates postfix expressions into the equivalent infix expression. In the simplest form, your script should function as such:

$ ruby postfix_to_infix.rb '2 3 +'
2 + 3

At minimum, try to support the four basic math operators: +, -, *, and /. Feel free to add others though. For numbers, remember to accept decimal values.

You can count on the postfix expressions having spaces between each term, if you like. While dc is content with 2 3+p, you don't have to support it unless you want to.

For an added bonus, try to keep the parentheses added to infix expressions to the minimum of what is needed. For example, prefer these results:

$ ruby postfix_to_infix.rb '56 34 213.7 + * 678 -'
56 * (34 + 213.7) - 678
$ ruby postfix_to_infix.rb '1 56 35 + 16 9 - / +'
1 + (56 + 35) / (16 - 9)

to these:

$ ruby postfix_to_infix.rb '56 34 213.7 + * 678 -'
((56 * (34 + 213.7)) - 678)
$ ruby postfix_to_infix.rb '1 56 35 + 16 9 - / +'
(1 + ((56 + 35) / (16 - 9)))

Posting equations and your output is not a spoiler.

by Hugh Sasse

In the book "Starburst" by Frederik Pohl ISBN 0-345-27537-3, page 56, without really spoiling the plot, some characters complain about the verbosity of communications and encode a message by Gödelizing it (detailed on page 58).

The encoding works by taking each successive character of a message and raising each successive prime to some function of that character, and multiplying these powers of primes together. So for example we could use the ASCII code + 1 to allow for nulls to be encoded. Then "Ruby\r\n" would end up as:

(2 ** R) * (3 ** u) * (5 ** b)....

10992805522291106558517740012022207329045811217010725353610920778
28664749233402453985379760678149866991742205982820039955872246774
86029159248495553882158351479922840433375701904296875000000000000
00000000000000000000000000000000000000000000000000000000000000000
000000

The idea is partly to obscure the message by the amount of factorization needed. This quiz is to write a program to Gödelize a message, and a program to deGödelize it.

The funtion used to map characters described in the book is "A" => 1, "B" => 2, etc and an example is given where spaces are 0. Nothing further is said about punctuation, or lower case. The message sent in the book is:

msg = (3.875 * (12 ** 26)) +
(1973 ** 854) + (331 ** 852) +
(17 ** 2008) + (3 ** 9707) + (2 ** 88) - 78

which it turns out has lots of 0 powers in it, so I strictly don't need the ASCII + 1 I've used in my example, I could use just ASCII, and the nulls would not increase the size of the resulting number. This further means that if a list of characters is sent in decreasing frequency order with the message, the most frequent could be encoded as 0 and the number would be that much smaller. In English it is likely to be an "e" or " " which ends up coded as 0.

Interesting things arising from this:

1 Finding the power once a prime is selected
2 Getting the list of primes in the first place
3 encoding of characters, as mentioned above
4 representing the number that results from encoding.

by Gavin Kistner

You have been hired to work for a small city government. The city recently bought a vehicle counter, one of those kinds that uses pneumatic rubber hoses stretched across the road. The company that sells the machine also sells software to interpret the raw data. However, the city has asked you to see if you can interpret it instead, saving them some money.

The data from the machine looks like this:

A268981
A269123
A604957
B604960
A605128
B605132
A1089807
B1089810
A1089948
B1089951

The numbers are the number of milliseconds since midnight when the mark occurred. Thus, the first line above represents a pair of tires driving by at 12:04:28am. The second line represents another pair of tires going by 142ms later (almost certainly the 2nd axle of the car).

The vehicle counter has two tubes - one stretches across both lanes of traffic, and one goes just across traffic in one direction. Each hose independently records when tires drive over it. As such, cars going in one direction (say, northbound) only record on one sensor (preceded with an 'A'), while cars going in the direction (say, southbound) are recorded on both sensors. Lines 3-6 above represent a second car going in the other direction. The first set of tires hit the 'A' sensor at 12:10:04am, and then hit the 'B' sensor 3ms later. The second set of tires then hit the 'A' sensor 171ms later, and then the 'B' sensor 4ms later.

The machine was left to run for 5 days in a row (starting on a Monday). This is obvious because the times in the data make several sudden drops:

A86328771
B86328774
A86328899
B86328902
A582668
B582671
A582787
B582789

The city has asked you to see how many analysis features you can provide from what the manufacturer's software offers:

* Total vehicle counts in each direction: morning versus evening,
per hour, per half hour, per 20 minutes, and per 15 minutes.
* The above counts can be displayed for each day of the session,
or you can see averages across all the days.
* Peak volume times.
* The (rough) speed distribution of traffic.
* Rough distance between cars during various periods.

Luckily for you, you know that:

* The speed limit on the road where this is recorded is 40mph
(that doesn't mean that everyone drives this speed, or that
no one exceeds it, but it's a good starting point).
* The average wheelbase of cars in the city is around 100 inches
between axles.
* Only 2-axle vehicles were allowed on this road during the
recording sessions.

The full data can be found at:

Vehicle Counter Data

by Eric Mahurin

Have you ever wondered how a text buffer might be represented in a text editor or word processor? A simple string to represent text buffer isn't efficient enough because inserting (i.e. typing) and deleting (backspace) in the middle would result in moving all of the text to the end for each operation. A data structure that can efficiently insert and delete in the middle is needed.

The task is to implement data structures for efficiently editing text. One common data structure is a gap buffer:

Gap buffer

Other options to consider include: ropes (see quiz #137), linked lists, simple strings, or a multi-level combination of data structures (i.e. for lines vs. characters in a line). There are many data structures that may work efficiently with simple editing operations, but not all of those data structures will work well for more complex functionality.

All of the basic operations occur around a text cursor. The minimal operations on/at the cursor should be:

* Insert a character before or after the cursor.
* Delete a character before or after the cursor and return the
deleted character.
* Move the cursor left or right (crossing line boundaries if
necessary) and return the character or nil at the beginning
or end of the buffer.
* Move the cursor up or down a line and return nil/false only if a
line boundary could not be crossed. The cursor may be placed in
the most natural column for the data structure.

Additional useful operations that you might find in a typical text editor can also be added:

* Get current line and column numbers
* Copy some amount of text before or after the cursor and return
this buffer.
* Display some context around the cursor.
* Cut some amount of text before or after the cursor and return
this buffer.
* Paste a copy/cut buffer before or after the cursor.
* Insert a file.
* Write to a file.
* Goto a specific line or column.
* Goto the begin/end of the line/buffer.
* Copy or cut to a specific line/column.
* Filter some text through a ruby block.
* Search (and possibly replace) using a regular expression.
* Undo/redo.

Major bonus points for the following where gap buffers probably won't work:

* Only store changes to a file.
* Handle multiple efficient cursors in a text buffer.

Although the focus is on data structures and making the ruby DSL equivalent to unix "ed" or DOS "edlin", a GUI could be added to make a full-screen/window text editor.

Here is a benchmark for testing that needs the minimal implementation (#insert_before, #insert_after, #delete_before, #delete_after, #left, #right, #up, #down):

ruby # edit_test.rb
# usage: ruby -r klass.rb edit_test.rb <iter> \
# [<constructor> [<lines> <columns>] ...]

require 'benchmark'
require 'test/unit/assertions'
include Test::Unit::Assertions

# char = byte pre 1.9, each_char already defined in 1.9
unless "".respond_to?(:each_char)
class String;alias_method(:each_char, :each_byte);end
end

iterations = ARGV.shift.to_i

while cursor = ARGV.shift
nlines = (ARGV.shift || 10000).to_i
ncolumns = (ARGV.shift || 100).to_i
n = nlines*ncolumns
chars = (?a..?z).to_a
line = (0...ncolumns).inject("") { |line, i|
line << chars[i%chars.length]
}
line[-1] = ?\n

iterations.times { eval(cursor).instance_eval {
Benchmark.benchmark(
"#{cursor}: #{nlines}x#{ncolumns}\n",16,nil,"total"
) { |b|

total = b.report("insert_before") {
nlines.times { line.each_char { |ch| insert_before(ch) } }
}
i = 0
total += b.report("left") { i += 1 while left }
assert_equal(n, i)
i = 0
total += b.report("right") { i += 1 while right }
assert_equal(n, i)
i = 0
total += b.report("up") { i += 1 while up }
assert_equal(nlines, i)
i = 0
total += b.report("down") { i += 1 while down }
assert_equal(nlines, i)
total += b.report("insert_after") {
nlines.times { line.each_char { |ch| insert_after(ch) } }
}
i = 0
total += b.report("delete_before") {
i += 1 while delete_before
}
assert_equal(n, i)
i = 0
total += b.report("delete_after") {
i += 1 while delete_after
}
assert_equal(n, i)

[total]

}
} }
end

by Brian Candler

Write a Ruby class which can tell you whether the current time (or any given time) is within a particular "time window". Time windows are defined by strings in the following format:

ruby # 0700-0900 # every day between these times
# Sat Sun # all day Sat and Sun, no other times
# Sat Sun 0700-0900 # 0700-0900 on Sat and Sun only
# Mon-Fri 0700-0900 # 0700-0900 on Monday to Friday only
# Mon-Fri 0700-0900; Sat Sun # ditto plus all day Sat and Sun
# Fri-Mon 0700-0900 # 0700-0900 on Fri Sat Sun Mon
# Sat 0700-0800; Sun 0800-0900 # 0700-0800 on Sat, plus 0800-0900 on Sun

Time ranges should exclude the upper bound, i.e. 0700-0900 is 07:00:00 to 08:59:59. An empty time window means "all times everyday". Here are some test cases to make it clearer:

ruby class TestTimeWindow < Test::Unit::TestCase
def test_window_1
w = TimeWindow.new("Sat-Sun; Mon Wed 0700-0900; Thu 0700-0900 1000-1200")

assert ! w.include?(Time.mktime(2007,9,25,8,0,0)) # Tue
assert w.include?(Time.mktime(2007,9,26,8,0,0)) # Wed
assert ! w.include?(Time.mktime(2007,9,26,11,0,0))
assert ! w.include?(Time.mktime(2007,9,27,6,59,59)) # Thu
assert w.include?(Time.mktime(2007,9,27,7,0,0))
assert w.include?(Time.mktime(2007,9,27,8,59,59))
assert ! w.include?(Time.mktime(2007,9,27,9,0,0))
assert w.include?(Time.mktime(2007,9,27,11,0,0))
assert w.include?(Time.mktime(2007,9,29,11,0,0)) # Sat
assert w.include?(Time.mktime(2007,9,29,0,0,0))
assert w.include?(Time.mktime(2007,9,29,23,59,59))
end

def test_window_2
w = TimeWindow.new("Fri-Mon")
assert ! w.include?(Time.mktime(2007,9,27)) # Thu
assert w.include?(Time.mktime(2007,9,28))
assert w.include?(Time.mktime(2007,9,29))
assert w.include?(Time.mktime(2007,9,30))
assert w.include?(Time.mktime(2007,10,1))
assert ! w.include?(Time.mktime(2007,10,2)) # Tue
end

def test_window_nil
w = RDS::TimeWindow.new("")
assert w.include?(Time.mktime(2007,9,25,1,2,3)) # all times
end
end

by Benjohn Barnes

Usually, you write a regular expression and then search for it in a text string. How about doing the opposite? Given a regular expression, generate all of the strings that it will match.

Rather amazingly, this has independently come up a couple of times in conversations with friends, so perhaps it's actually useful. I wanted to use it to specify possible domain names for a potential new company...

/(lovely|delicious|splendid)(food|snacks|munchies)/.generate
=> [lovelyfood, deliciousfood, splendidfood,
lovelysnacks, delicioussnacks, splendidsnacks,
lovelymunchies, deliciousmunchies, splendidmunchies]

The full regular expression grammar is pretty complex, so maybe you'll want to just go with a small subset. :-)

by Morton Goldberg

A salesman wants to call on his customers, each of which is located in a different city. He asks you to prepare an itinerary for him that will minimize his driving miles. The itinerary must take him to each city exactly once and return him to his starting point. Can you write a Ruby program to generate such an itinerary?

This problem is famous and known to be NP-complete. So how can you be expected to solve it as a weekend Ruby Quiz project? It's unreasonable isn't it? Yes, it is, unless the conditions are relaxed somewhat.

First, let's restrict the problem to a space for which the solution is known: a grid of points as defined by the following Ruby code:

ruby # Square grid (order n**2, where n is an integer > 1). Grid points are
# spaced on the unit lattice with (0, 0) at the lower left corner and
# (n-1, n-1) at the upper right.

class Grid
attr_reader :n, :pts, :min
def initialize(n)
raise ArgumentError unless Integer === n && n > 1
@n = n
@pts = []
n.times do |i|
x = i.to_f
n.times { |j| @pts << [x, j.to_f] }
end
# @min is length of any shortest tour traversing the grid.
@min = n * n
@min += Math::sqrt(2.0) - 1 if @n & 1 == 1
end
end

Second, let's relax the requirement that the itinerary be truly minimal. Let's only require that it be nearly minimal, say, within 5%. Now you can tackle the problem with one of several heuristic optimization algorithms which run in polynomial time. In particular, you could use a genetic algorithm (GA).

Genetic Algorithm (GA)

From one point of view a GA is a stochastic technique for solving an optimization problem--for finding the extremum of a function. From another point of view it is applied Darwinian evolution.

To see how a GA works, let's look at some pseudocode.

Step 1. Generate a random initial population of itineraries.
Step 2. Replicate each itinerary with some variation.
Step 3. Rank the population according to a fitness function.
Step 4. Reduce the population to a prescribed size,
keeping only the best ranking itineraries.
Step 5. Go to step 2 unless best itinerary meets an exit criterion.

Simple, isn't it? But perhaps some discussion will be useful.

Step 1. You can get the points you need to generate a new random itinerary by calling *pts* on an instance *grid* of the Grid class shown above.

Step 2. GAs apply what are called *genetic operators* to replicas of the population to produce variation. Genetic operators are usually referred to by biological sounding names such *mutation*, *recombination*, or *crossover*. Recombination means some kind of permutation. In my GA solution of the problem proposed here, I used two recombination operators, *exchange* and *reverse*. Exchange means cutting an itinerary at three points (yielding four fragments) and swapping the middle two fragments. Reverse means cutting an itinerary at two points (yielding three fragments) and reversing the order of the middle fragment.

Step 3. The fitness function for the traveling salesman problem can be the total distance traversed when following an itinerary (including the return to the starting point), or it can be a related function that reaches its minimum for exactly the same itineraries as does the total distance function.

A GA can be rather slow, but has the advantage of being easy to implement. My experience with problem I have proposed is that a GA can produce a solution meeting the 5% criterion reasonably quickly and that it can find an exact solution if given enough time.

An Exact Solution

To give you an idea of how a solution looks when plotted, here is a picture of a minimal tour on a 7 X 7 grid.

*--*--*--* *--*--*
| | | |
* *--* *--* *--*
| | | |
* * *--*--*--* *
| | / |
* *--*--*--*--* *
| |
*--* *--*--*--* *
| | | |
*--* * *--*--* *
| | | |
*--*--* *--*--*--*

This exact solution was found by my Ruby GA solver in about two minutes.

Wikipedia Links

Two Wikipedia pages have a great deal of relevant information on the topic of this quiz.

Traveling salesman problem

Genetic algorithm