[QUIZ] Itinerary for a Traveling Salesman (#142)

Yes, thank you. I seem to recall accidentally striking a key with my cursor somewhere in the middle of Ruby code on more than one occasion; I guess that happened, and I failed to notice it.


On Oct 7, 2007, at 12:28 PM, James Edward Gray II wrote:

On Oct 7, 2007, at 9:20 AM, James Koppel wrote:

First, before I get to my main solution, I would like to show that,
as Morton pointed out, yes, it is very possible to have a quick,
exact solution. Here's one that does so for N >= 3 (N=2 and N=1
nevertheless draw correctly; a call to uniq would make them work).

require 'RMagick'
require 'enumerator'

<definitions of Grid and draw_itin removed - see main solution below>

n = ARGV[0].to_i

itin = ([0]*n).zip((0...n).to_a)

1.step(n-3, 2) do |x|
  itin += ([x]*(n-1)).zip((1...n).to_a.reverse)
  itin += ([x+1]*(n-1)).zip((1...n).to_a)

if n%2==0
  itin += ([n-1]*(n-1)).zip((0...n).to_a.reverse)
  (n-1)..step(2, -2) do |y|
    itin += [[n-2,y],[n-1,y],[n-1,y-1],[n-2,y-1]]

itin += (0...n).to_a.reverse.zip([0]*n)

$grid = Grid.new(n) #Because draw_itin asks for it
draw_itin(itin, "#{n}x#{n}tour2.jpg")

I believe there's a typo in the above. Shouldn't it be:

  (n-1).step(2, -2) do |y| # I removed a .


James Edward Gray II

Be a better Globetrotter. Get better travel answers from someone who knows. Yahoo! Answers - Check it out.