Thomas.

#!/usr/bin/env ruby
# Author::      Thomas Link (micathom AT gmail com)
# Created::     2007-12-08.

class Quiz149
    Solution = Struct.new(:idx, :width, :height)

    def initialize(word)
        @word      = word
        @wordic    = word.downcase
        @wordsize  = word.size
        @solutions = []
    end

    def find_solutions
        for height in 1 .. (@wordsize - 4)
            for width in 1 .. (@wordsize - 2 * height - 2)
                for idx in 0 .. (@wordsize - 2 * height - 2 * width -
1)
                    if @wordic[idx] == @wordic[idx + width * 2 +
height * 2]
                        @solutions << Solution.new(idx, width, height)
                        return self # Remove this line to find all
solutions
                    end
                end
            end
        end
        self
    end

    def print_solutions
        if @solutions.empty?
            puts 'No loop.'
            puts
        else
            @solutions.each_with_index do |sol, sol_idx|
                canvas_x = sol.idx + sol.width + 1
                canvas_y = @wordsize - sol.idx - sol.height - 2 *
sol.width
                canvas   = Array.new(canvas_y) {' ' * canvas_x}
                pos_x    = -1
                pos_y    = canvas_y - sol.height - 1
                @word.scan(/./).each_with_index do |char, i|
                    if i <= sol.idx + sol.width
                        pos_x += 1
                    elsif i <= sol.idx + sol.width + sol.height
                        pos_y += 1
                    elsif i <= sol.idx + 2 * sol.width + sol.height
                        pos_x -= 1
                    else
                        pos_y -= 1
                    end
                    if canvas[pos_y][pos_x] == 32
                        canvas[pos_y][pos_x] = char
                    end
                end
                puts canvas.join("\n")
                puts
            end
        end
        self
    end

end

Thomas.

#!/usr/bin/env ruby
# Author::      Thomas Link (micathom AT gmail com)
# Created::     2007-12-08.
#
# Nervous letters movie. If you run the script with -c, only clock-
wise
# permutations will be shown.

require 'curses'

class NervousLetters
    class << self
        def solve_clockwise(word)
            @@directions = {
                :right => [ 1,  0, :right, :down],
                :left  => [-1,  0, :left,  :up],
                :up    => [ 0, -1, :right, :up],
                :down  => [ 0,  1, :left,  :down],
            }
            solve(word)
        end

        def solve_any(word)
            @@directions = {
                :right => [ 1,  0, :right, :up,   :down],
                :left  => [-1,  0, :left,  :up,   :down],
                :up    => [ 0,  1, :right, :left, :up],
                :down  => [ 0, -1, :right, :left, :down],
            }
            solve(word)
        end

        def solve(word)
            Curses.init_screen
            Curses.noecho
            Curses.curs_set(0)
            begin
                @@solutions   = []
                @@stepwise    = true
                pos0          = word.size + 1
                @@canvas_size = pos0 * 2
                NervousLetters.new([], ':', word.scan(/./),
                                   pos0, pos0, :right,
                                   false, true)
            ensure
                Curses.curs_set(1)
                Curses.close_screen
            end
            if @@solutions.empty?
                puts 'No loop.'
            else
                puts "#{@@solutions.size} solutions."
            end
        end
    end

    attr_reader :letters, :letter, :pos_x, :pos_y

    def initialize(letters, letter, word, pos_x, pos_y, direction,
has_knot, at_knot)
        @letters = letters.dup << self
        @letter  = letter
        @pos_x   = pos_x
        @pos_y   = pos_y
        if word.empty?
            new_solution if has_knot
        else
            @word        = word.dup
            @next_letter = @word.shift
            @has_knot    = has_knot
            _, _, *turns = @@directions[direction]
            turns.each do |turn|
                next if at_knot and turn != direction
                dx, dy, _ = @@directions[turn]
                try_next(pos_x + dx, pos_y + dy, turn)
            end
        end
    end

    def try_next(pos_x, pos_y, direction)
        has_knot = false
        @letters.each do |nervous|
            if pos_x == nervous.pos_x and pos_y == nervous.pos_y
                if @next_letter.downcase != nervous.letter.downcase
                    return
                else
                    has_knot = true
                    break
                end
            end
        end
        NervousLetters.new(@letters, @next_letter, @word,
                           pos_x, pos_y, direction,
                           @has_knot || has_knot, has_knot)
    end

    def new_solution
        @@solutions.last.draw(self) unless @@solutions.empty?
        draw
        @@solutions << self
        if @@stepwise
            Curses.setpos(@@canvas_size + 1, 0)
            Curses.addstr('-- PRESS ANY KEY (q: quit, r: run) --')
        end
        Curses.refresh
        if @@stepwise
            ch = Curses.getch
            case ch
            when ?q
                exit
            when ?r
                @@stepwise = false
            end
        else
            # sleep 0.1
        end
    end

    def draw(eraser=nil)
        consumed = []
        @letters.each do |nervous|
            if eraser
                next if eraser.letters.include?(nervous)
                letter = ' '
            else
                letter = nervous.letter
            end
            yx = [nervous.pos_y, nervous.pos_x]
            unless consumed.include?(yx)
                Curses.setpos(*yx)
                Curses.addstr(letter)
                consumed << yx
            end
        end
    end

end

loopword "Mississippi"
puts
loopword "Markham"
puts
loopword "yummy"
puts
loopword "Dana"
puts
loopword "Organization"

outputs:

 i
 p
 p
Mis
 ss
 si

Ma
ar
hk

yu
mm

No loop.

n
Or
ig
ta
an
zi

(The last is a testcase which makes sure that I get the #shifts and #pops
right)

#!/usr/bin/env ruby

# Solution to Ruby Quiz #149 (see http://www.rubyquiz.com/quiz149.html)
# by Pawel Radecki (pawel.j.rade...@gmail.com).

require 'logger'

$LOG = Logger.new($stderr)

#logging
#$LOG.level = Logger::DEBUG #DEBUG
$LOG.level = Logger::ERROR  #PRODUCTION

NO_LOOP_TEXT = "No loop."

class String
    private
    def compose_word_loop_array (index1, index2)
        a = Array.new(self.length) {|i| Array.new(self.length, " ") }

        i=0
        while (i<index1)
            a[1][i] = self[i].chr
            i+=1
        end

        #repeated letter, first occurrence, loop point
        a[1][index1]=self[index1].chr

        i=index1+1
        boundary = (index2-index1)/2+index1
        while(i<boundary)
            a[1][i] = self[i].chr
            i+=1
        end

        i=index2-1; j=index1
        while(i>boundary-1)
            a[0][j] = self[i].chr
            j+=1; i-=1
        end

        i=index2+1; j=2
        while (i<self.length)
            a[j][index1] = self[i].chr
            i+=1; j+=1
        end

        #cut all empty rows
        a.slice!(j..self.length-1)
        a
    end

    public
    def word_loop
        if (self.length<=4)
            return NO_LOOP_TEXT
        end
        s = self
        index1 = index2 = nil
            #find repeated letter suitable for a loop by
            #taking 1st letter and comparing to 5th, 7th, 9th, 11th, etc.
            #taking 2nd letter and comparing to 6th, 8th, 10th, 12th, etc.
            #taking 3rd letter and comparing to 7th, 9th, 11th etc.
            #etc.
            i = 0
            while i<s.length-1
                j=i+4
                while j<s.length
                    $LOG.debug("i: #{i}")
                    $LOG.debug("j: #{j}")
                    $LOG.debug("s[i]: #{s[i].chr}")
                    $LOG.debug("s[j]: #{s[j].chr}")
                    $LOG.debug("\n")
                    if s[i] == s[j]
                        return compose_word_loop_array(i, j)
                    end
                    j+=2
                end
                i+=1
            end
        return NO_LOOP_TEXT
    end
end

USAGE = <<ENDUSAGE
Usage:
   word_loop <message>
ENDUSAGE

if ARGV.length!=1
    puts USAGE
    exit
end

input_word = ARGV[0]
a = input_word.word_loop
if a.instance_of? Array
    a.each {|x| puts x.join("") }
else
    print a
end

exit

letters = ARGV.first.split(//)

first,last = first_loop(letters)

if first==nil
  puts "No loop"
  exit
end

letters[(last+1)..-1].reverse_each {|l| puts ' '*first + l}
puts letters[0..(first+1)].join
1.upto((last-first-1)/2) do |n|
  puts ' '*first + letters[last-n] + letters[first+1+n]
end

#!/usr/bin/env ruby -wKU

word = ARGV.first or abort "Usage:  #{File.basename($PROGRAM_NAME)}  
WORD"
if word.downcase =~ /([a-z]).(?:.{2})+\1/
   before, during, after = word[0,          $`.length],
                           word[$`.length,  $&.length],
                           word[-$'.length, $'.length]
   indent                = " " * before.length
   after.split("").reverse_each { |char| puts indent + char }
   puts before + during[0..1]
   ((during.length - 3) / 2).times do |i|
     puts indent + during[-(i + 2), 1] + during[2 + i, 1]
   end
else
   puts "No loop."
end

__END__

Eric

def find_knot letters     #returns first and last index which become a
"knot"
  letters.each_with_index do |letter1, ind1|
    (ind1+4).upto(letters.length - 1) do |ind2|
      if (ind2 - ind1) % 2 == 0
        if letters[ind2].casecmp(letter1) == 0
          return [ind1, ind2]
        end
      end
    end
  end
  return nil
end

def loop word
  letters = word.split(//)
  first, last = find_knot letters
  if first.nil?
    puts "No loop"
  else
    (letters.length-1).downto(last+1) { |i|
      print " "*first
      puts letters[i]
    }
    print letters[0..first+(last-first)/2-1]
    puts " "*first
    first.times {print " "}
    (last-1).downto(first+(last-first)/2) { |i| print letters[i] }
    puts
  end

end

loop "Mississippi"
puts
loop "Markham"
puts
loop "Yummy"
puts
loop "Dana"

Loop of
-"Entitlements" should be:

me
Ent
lti
_s_

-"Arbeitsberichten" ('work reports' in German dative) should be:
____ch_
Arbeits
____reb
_____n_

-"Gesundheitsdienste" ('medical service' in German) should be:
_it_
Gesu
_hdn
__i_
_te_
_sn_

(I'm not quite sure about this one, since it could involve an infinite
loop with the 4 last letters)

Have fun!

PS: you can also use
"satisfactoriamente"
"indefinidamente"
for spanich specs.

On 10/12/2007, Juraj Plavcan <yam...@gmail.com> wrote:

ment
elti
..s.

emen
ltit
...s

men
est
lti

me.
ent
lti
.s.

ments
elti.

ents
m.i.
elt.

Eric

====

For those who cannot understand it either:

Sorry, I still hadn't seen your solution when I wrote those specs.
Impressive stuff!
I was just a bit disappointed by the fact that the quiz seemed to
propose only basic "u-turn words", and I wanted to find  something
juicier.
I sure found it with your results!

To be sure we're talking about the same problem, I was taking into
account the fact  a knot-word should still be readable if you know
that:

-the first letter is the only uppercase one in the knot
-the first direction is rightwards
-as long as you can go on reading in one direction, you should
-once you cannot go further, try to turn right
-if you can turn right, keep on reading!
-if you cannot turn either, the word is complete

I suppose that nobody could guess that
Chee
nir

actually is "chincherinchee".

Taking this readability into account, the only possible knot for
"Entitlements" is:

me
Ent
lti
_s_

Eric AsWell

On 10/12/2007, Eric I. <rubytrain...@gmail.com> wrote:

break it up:
(.*?) looks for a non-greedy string of anything
(.) any character
(.(?:..)+?) non-greedy matching of an odd number of characters.  I'm
not sure what the ?: adds to the regular expression.
I got this: "(?: )      grouping without backreferences" from here:
http://www.zenspider.com/Languages/Ruby/QuickRef.html#11
\2 matches the any character from before
(.*) a string of any length at the end

i - at the end that means case insensitive.

Joe

On Dec 10, 2007 1:14 PM, Michal Suchanek <hramr...@centrum.cz> wrote:

--Ken

loopword "chinchilla"
#=> a
#=> l
#=> l
#=> i
#=> h
#=> ch
#=> ni

when I would have expected this:

#!/usr/bin/ruby

class Quiz149
  def initialize(word)
    @word = word
    @pos = 0      # currently observed char
    @knots = []   # current knots positions
    @combos = {}  # a set of knot combos found so far
    @size = @word.length*2 - 1
    @arr = Array.new(@size) { Array.new(@size, ?.) } # a size x size
of dots
    @hist = []    # position history
  end

  def [](x, y)
    @arr[y][x]
  end

  def []=(x, y, c)
    @arr[y][x] = c
  end

  def print
    @arr.each { |line| puts line.map{ |c| c.chr }.join }
    puts
  end

  def length
    @word.length
  end

  def loop(x = self.length - 1, y = self.length - 1)
    @hist.push([x, y])
    c = self[x, y]
    self[x, y] = @word[@pos]
    @pos += 1
    if @pos >= length # reached end of the word
      if !...@knots.empty?
        self.print unless @combos[@knots]
        @combos[@knots] = true
      end
    else
      looptry(x + 1, y    ) # right
      looptry(x,     y - 1) # up
      looptry(x - 1, y    ) # left
      looptry(x,     y + 1) # down
    end
    @pos -= 1
    self[x, y] = c
    @hist.pop()
  end

  def no_loop? # was there any solution?
    @combos.empty?
  end

######################################################################
  private

  def looptry(x, y)
    # could not make this look any uglier ;-)
    return if @hist.size >= 2 && x == @hist[-2][0] && y == @hist[-2]
[1]

    c = @word[@pos]
    f = self[x, y]
    if f == c || f == ?.
      @knots.push(@pos) if f == c
      loop(x, y)
      @knots.pop() if f == c
    end
  end
end

STDIN.each do |line|
  quiz = Quiz149.new(line.chomp.downcase)
  quiz.loop()
  puts "No loop." if quiz.no_loop?
end

I think it finds all of the possible solutions.  A set of already
known solutions is kept to track down the equivalent ones and do not
print them.

It outputs something like this:

$ ./loop.rb
mississippi
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
..............ppi....
..........mississ....
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................

.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
...........ssi.......
..........miss.......
...........ppi.......
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................

.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
...........pi........
...........psi.......
..........miss.......
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................

.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
............si.......
..........miss.......
............ippi.....
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................
.....................

markham
.............
.............
.............
.............
.............
......ahk....
......mar....
.............
.............
.............
.............
.............
.............

.............
.............
.............
.............
.............
.......hk....
......mar....
.............
.............
.............
.............
.............
.............

.............
.............
.............
.............
.............
.......hk....
......mar....
.......m.....
.............
.............
.............
.............
.............

yummy
.........
.........
.........
....mm...
....yu...
.........
.........
.........
.........

dana
No loop.

Of course, it could be tweaked to remove the unneeded dots when
printing, however I pretty much love it this way. ;-)

Antidisestablishmentarianism:

..........nemh..
..........t..s..
antidisestablism
..........rian..

$ ruby word_loop.rb Antidisestablishmentarianism
Number of overlaps: 5
========================================
  ant
ianism
r  d
abli
tses
nemh
========================================
    sm
antidish
    n lem
    a bse
    iratn
========================================
    m
    s
antidish
    n lem
    a bse
    iratn
========================================
  ant
ianis
r  dm
abli
tses
nemh
========================================
   an
    t
ianis
r  dm
abli
tses
nemh
========================================
   an
    t
ianism
r  d
abli
tses
nemh
========================================

Cheaters always find the system and make it work for them.  So what's the system
this time?  Have another look at one of the quiz examples:

         i
         p
         p
        Mis
         ss
         si

Okay, the first priority is to find a possible loop.  We need a repeated letter
with some letters between the two occurrences, obviously.  How many letters
between though?  Well, the minimum loop is:

        *.
        ..

The next smallest loop is what we see in Mississippi:

        *.
        ..
        ..

That's three and five and we can already see that each size must add two more
letters.  So, we need an odd number of letters and at least three of those.  Now
we can find loops.

Once we see the loop, it becomes clear that the loop divides the word into
pieces.  Let me call them out:

         ^     > = before the loop characters
         ^     * = the repeated letter
         ^     . = loop characters
        >*.    ^ = after the loop characters
         ..
         ..

Seeing these makes a cheater wonder, can I output each part naturally down the
lines?  To do that, we would first need to spit out those after the loop
characters, in reverse order.  That shouldn't be tough since we already know how
to find a loop, but notice that each of those is also indented.  It turns out
that they are just indented by the length of characters before the loop, so
that's trivial to deal with.

Now we would need the get those before the loop characters in the output.  No
problem there, it's a simple print statement.

The loop is the trickiest part.  First, we see that the repeated letter and the
first loop character can be printed along with the before characters.  The rest
of the characters have an indent, but it's the same thing we figured out earlier
and we can deal with that.  Then outputting the remaining characters of the loop
can be as simple as printing two columns:  one pulling letters off the back of
the loop and the other pulling letters off the front.

Wow, cheaters work harder than you think, eh?  If we can do all of those pieces,
we can print the word loop as we go.  The reason I like trying an approach like
this is that each step is pretty simple and easy to understand.  We had to do a
bit of thinking that the computer probably could have done for us, but then you
have to be smart enough to tell the computer how to do the thinking.

Let's move the ideas into code at this point.  We will examine Ken Bloom's
solution.  Ken is a cheater and a better one than I am at that!  I'll tell you
what Ken taught me shortly, but for first let's see the code.  Brace yourself
because I'm giving you the whole thing in one shot:

        def loopword word
         matchinfo=
           word.match(/(.*?)(.)(.(?:..)+?)\2(.*)/i)
         if matchinfo
           _,before,letter,looplets,after=matchinfo.to_a
           pad=" "*before.size
           after.reverse.split(//).each{|l| puts pad+l}
           looplets=looplets.split(//)
           puts before+letter+looplets.shift
           until looplets.empty?
             puts pad+looplets.pop+looplets.shift
           end
         else
           puts "No loop."
         end
        end

        # ...

Isn't it great to be a cheater?

Let's break it down.  Probably the hardest part to understand is the very first
step.  Ken hits the word with a tricky Regexp to figure out if it has a loop in
it.  That's right, you can count an odd number of at least three characters with
a regular expression.  Let's examine the pieces:

        / (.*?)        # characters before the loop, if any
          (.)          # the first appearance of our repeated character
          (.(?:..)+?)  # an odd number of at least three loop characters
          \2           # the repeat of our repeated character
          (.*)         # characters after the loop, if any
          /ix          # make the expression case insensitive

There are two good tricks in there.  First, matching at least three odd
characters is shown to be just any character followed by one or more groups of
two characters.  That's handy to remember.

The other trick is using a back-reference to catch the repeated character.  What
I didn't know about this trick though was that Ruby's regular expression engine
is smarter than I gave it credit for.  I knew this would match:

        >> "-i---i-"[/(\w).+\1/]
        => "i---i"

However, I didn't know the following would work if you made the expression case
insensitive:

        >> "-I---i-"[/(\w).+\1/i]
        => "I---i"

I spent too much effort in my code to get a match to work on the word Markham
when I could have just used the /i switch.  Thanks for the tip, Ken.

Once we have tried the expression, the if statement checks to see if we found a
loop.  If we didn't the else clause can print our error message and we're done.

When we did find a match, Ken starts by pulling out each capture of the
expression into easy to manage variables.  Here's my chance to teach Ken a new
trick though.  See how he created an unused variable (_) to capture the match as
a whole?  It's not really needed if you switch the method call on the MatchData
object:

        >> md = "Mississippi".match(/(.*?)(.)(.(?:..)+?)\2(.*)/i)
        => #<MatchData:0x58a188>
        >> md.to_a
        => ["Mississippi", "M", "i", "ssiss", "ppi"]
        >> md.captures
        => ["M", "i", "ssiss", "ppi"]

Let's get back to the code.  Here it is again to save scrolling:

        def loopword word
         matchinfo=
           word.match(/(.*?)(.)(.(?:..)+?)\2(.*)/i)
         if matchinfo
           _,before,letter,looplets,after=matchinfo.to_a
           pad=" "*before.size
           after.reverse.split(//).each{|l| puts pad+l}
           looplets=looplets.split(//)
           puts before+letter+looplets.shift
           until looplets.empty?
             puts pad+looplets.pop+looplets.shift
           end
         else
           puts "No loop."
         end
        end

        # ...

The rest of the code prints the word as I described earlier.  First, a variable
is set to that indent we will need in multiple places.  The next line reverse()s
and split()s the after loop characters, printing each one with the indent.
After that, Ken breaks up the loop characters into an Array for easy removal at
both ends.  The next line prints the before the loop characters, the repeat, and
the first loop character.  Finally, the until loop handles the remaining loop
character two at a time, one from each end.  That process prints the entire word
and makes a complete solution.

The rest of Ken's code just called the method on a set of sample words:

        # ...

        loopword "Mississippi"
        puts
        loopword "Markham"
        puts
        loopword "yummy"
        puts
        loopword "Dana"
        puts
        loopword "Organization"

The non-cheating solutions are also very interesting.  They decided that this
problem wasn't hardcore enough for them and they could maximize the fun by
trying to create multiple loops and reuse as many characters as possible.  It's
great code that leads to insane output, so be sure to check those out as well.

My thanks to cheaters and hardcore solvers alike.  You always give me more
interesting material than I can even talk about.