On Dec 7, 10:45 pm, Ruby Quiz <ja... / grayproductions.net> wrote:
>
> 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

OK, here is my solution to this extremly fun quiz! :)

#!/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. ;-)


--
Alex Shulgin