[QUIZ] Word Loop (#149)
Ruby Quiz
1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.
2. Support Ruby Quiz by submitting ideas as often as you can:
3. Enjoy!
Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
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.
Phrogz
> 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
Maybe it's because it's a Friday afternoon, but I don't understand the
quiz problem. Could someone who understands this try explaining it
(without, of course, discussing any code or even pseudo-code to
approach it).
I've looked over those examples a few times and I'm totally baffled.
What does "loop the text around and reuse that letter" mean?
Christian von Kleist
I read this quiz on the mailing list in GMail and I didn't get this
challenge at first. Then I realized that you need to imagine the
examples in a fixed-width font.
Just FYI. :)
Drew Olson
I agree, I'm lost as well...
--
Posted via http://www.ruby-forum.com/.
Christian von Kleist
I guarantee that if you paste the examples into an editor with a
fixed-width font you'll get it immediately. Try vi/emacs/pico/nano
(or Notepad if you're in Windows, I guess?) The Mississippi one is
the key.
Jason Roelofs
On Dec 7, 2007 4:32 PM, Drew Olson <ols...@gmail.com> wrote:
> OH! Fixed width font shows it:
$ ruby word_loop.rb yummy
yu
mm
means
y -> u
/\ \/
| |
m<- m
Hope that helps.
Phrogz
Ah, got it.
[y] -> [u]
^ |
| v
[m] <- [m]
[M] -> [a]
^ |
| v
[a] [r]
^ |
| v
[h] <- [k]
[i]
^
|
[p]
^
|
[p]
^
|
[M] -> [i] -> [s]
^ |
| v
[s] [s]
^ |
| v
[s] <- [i]
Phrogz
> On Dec 7, 2007 4:32 PM, Drew Olson <olso...@gmail.com> wrote:
>
>
>
> > Gavin Kistner wrote:
> > > On Dec 7, 1:45 pm, Ruby Quiz <ja...@grayproductions.net> wrote:
>
> > >> yu
> > >> mm
>
> > > Maybe it's because it's a Friday afternoon, but I don't understand the
> > > quiz problem. Could someone who understands this try explaining it
> > > (without, of course, discussing any code or even pseudo-code to
> > > approach it).
>
> > > I've looked over those examples a few times and I'm totally baffled.
> > > What does "loop the text around and reuse that letter" mean?
>
> > I agree, I'm lost as well...
> > --
>
> I guarantee that if you paste the examples into an editor with a
> fixed-width font you'll get it immediately. Try vi/emacs/pico/nano
> (or Notepad if you're in Windows, I guess?) The Mississippi one is
> the key.
I guarantee you're wrong, only because I *was* reading it with a fixed-
width font, both in email and on comp.lang.ruby. The pattern just
didn't jump out at first.
But I got it now, thanks :)
Alex Fenton
> On Dec 7, 1:45 pm, Ruby Quiz <ja...@grayproductions.net> wrote:
>> 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
<snip>
> Maybe it's because it's a Friday afternoon, but I don't understand the
> quiz problem. Could someone who understands this try explaining it
> (without, of course, discussing any code or even pseudo-code to
> approach it).
It took me a few monents too. The letters have to be arranged in a grid
so that by moving one square at a time, the word is spelled out. The
test is to see whether the word can be spelled out by, at some point,
moving over the same grid square twice.
I'm taking from the MISSISSIPI example that moves have to be in the same
direction as the last move, or at a 90 degree angle to it, otherwise
it could be spelled by moving up back onto "S" after the second "I" in
the bottom right.
a
Jason Roelofs
On Dec 7, 2007 4:37 PM, Jason Roelofs <james...@gmail.com> wrote:
>
> On Dec 7, 2007 4:32 PM, Drew Olson <ols...@gmail.com> wrote:
>
> > Gavin Kistner wrote:
> > > On Dec 7, 1:45 pm, Ruby Quiz <ja...@grayproductions.net> wrote:
> > >>
> > >> yu
> > >> mm
> > >
> > > Maybe it's because it's a Friday afternoon, but I don't understand the
> > > quiz problem. Could someone who understands this try explaining it
> > > (without, of course, discussing any code or even pseudo-code to
> > > approach it).
> > >
> > > I've looked over those examples a few times and I'm totally baffled.
> > > What does "loop the text around and reuse that letter" mean?
> >
> > I agree, I'm lost as well...
> > --
> > Posted via http://www.ruby-forum.com/.
> >
> > OH! Fixed width font shows it:
>
> $ ruby word_loop.rb yummy
> yu
> mm
>
> means
>
> y -> u
> /\ \/
> | |
> m<- m
>
> Hope that helps.
>
(Sorry for double post)
Look at the actual Ruby Quiz page for this quiz:
http://www.rubyquiz.com/quiz149.html
For the Mississippi example, start with M and follow the spelling of the
word. You'll go right, down, left, and up, reusing one of the 'i's
Jason
Ball, Donald A Jr (Library)
> What does "loop the text around and reuse that letter" mean?
Imagine your word as a string. You're trying to make a knot, just a fold
really, in the string, and the bit where the string folds over itself is
a repeated letter.
- donald
Sam Larbi
I wish I read read that before I wasted too much time staring at the
examples. Thanks.
Yossef Mendelssohn
Very nice visual explanation.
I stared at this quiz for a while and simply could not understand. It
was only when I was about to post a reply begging for an explanation
that I got it.
It's clear to me now I should've posted a reply with the explanation
instead of just moving on.
--
-yossef
James Gray
> Maybe it's because it's a Friday afternoon, but I don't understand the
> quiz problem. Could someone who understands this try explaining it
> (without, of course, discussing any code or even pseudo-code to
> approach it).
I apologize for all of the confusion. I had trouble explaining this
one, which is why I pretty much punted and showed a bunch of
examples. ;)
There are some better visual descriptions in this thread now though,
so hopefully everyone gets it now.
James Edward Gray II
James Gray
> I'm taking from the MISSISSIPI example that moves have to be in the
> same direction as the last move, or at a 90 degree angle to it
Correct, and turns need to be clockwise.
James Edward Gray II
Eugene Kalenkovich
news:x7j6j.1781$h35...@newsfe2-gui.ntli.net...
Hmm..
Looks like mississippi is ambiguous, what about
I
P
P
I
MISS
SI
?
EK
James Gray
I don't see how this works with 90 degree turns in a clockwise
direction, as mentioned earlier in this thread.
Of course, I'm never one to discourage experimentation.
James Edward Gray II
Eugene Kalenkovich
news:853F208B-1F25-4509...@grayproductions.net...
I
P
|
P
|
I
|
M -> I -> S -> S
| |
S <- I
James Gray
Ah, I see it now. Sorry. The letters didn't line up for me correctly
in the previous message.
You are right, that works too.
James Edward Gray II
tho_mica_l
>
> direction, as mentioned earlier in this thread.
I get 5 possible solutions for Mississippi. Some solutions could be
considered redundant though.
Is the task rather to find possible loops (5 solutions) or letters at
possible intersections (3 solutions)?
thomas.
James Gray
The task is to draw one of the possible loops.
James Edward Gray II
Eric I.
For example, "absolvable" can make use of three overlaps:
.....
.abs.
.vlo.
..e..
.....
And "chincherinchee", which is a South African perennial, can be
arranged with seven overlaps. I'll leave it as a mini-challenge you
can try....
Eric
====
On-site, hands-on Ruby training is available from http://LearnRuby.com
!
Eric I.
displays solutions with the maximum number of overlaps.
Eric
----
Are you interested in on-site Ruby training that uses well-designed,
real-world, hands-on exercises? http://LearnRuby.com
====
# Solution to Ruby Quiz #149 provided by LearnRuby.com
#
# The code to this solution can also be found at:
# http://learnruby.com/examples/ruby-quiz-149.shtml
#
# This solution tries to find all solutions and then selects those
# with the maximum number of overlaps. Good words to try are
# "absolvable" and "chincherinchee". It is implemented with a
# recursive search.
# The Grid class is used to hold a grid where each cell contains a
# character or, if it's empty, nil. Furthermore, the grid keeps track
# of how many overlaps there are in the word that spins within it,
# since that's the measure of how good the arrangement is.
class Grid
attr_reader :overlaps
def initialize
@grid = Array.new
@overlaps = 0
end
def [](position)
sub_array(position[0])[position[1]]
end
def []=(position, value)
sub_array(position[0])[position[1]] = value
end
def inc_overlaps
@overlaps += 1
end
def dec_overlaps
@overlaps -= 1
end
def to_s
@grid.map do |row|
if row
row.map { |c| c || ' ' }.join('')
else
''
end
end.join("\n")
end
def dup
other = Grid.new
@grid.each_with_index do |row, i|
other.grid[i] = row.dup unless row.nil?
end
other.overlaps = @overlaps
other
end
# Trim grid so it's as small as possible. Assumes that filled areas
# are contiguous, so that an empty row would not sit between
# non-empty rows.
def trim!
@grid.delete_if { |row| row.nil? || row.all? { |c| c.nil? } }
trim_columns = empty_columns
@grid.each_index do |i|
@grid[i] = @grid[i][trim_columns..-1]
@grid[i].pop while @grid[i].last.nil?
end
self
end
protected
attr_reader :grid
attr_writer :overlaps
# Utility method that returns the sub-array of @grid at index.
# Since the sub-array may have not yet been created, will create it
# if necessary.
def sub_array(index)
sub_array = @grid[index]
sub_array = @grid[index] = Array.new if sub_array.nil?
sub_array
end
# returns the number of entries at the start of each sub-array that
# are empty, so the grid can be "left-trimmed".
def empty_columns
index = 0
index += 1 while @grid.all? { |row| row.nil? || row[index].nil? }
index
end
end
# This module contains some convenience methods to move a position in
# a direction, and to figure out a new direction when a right turn is
# made.
module Direction
RightTurns = {
[0, 1] => [1, 0],
[1, 0] => [0, -1],
[0, -1] => [-1, 0],
[-1, 0] => [0, 1],
}
# returns the rightwards direction
def self.rightwards
[0, 1]
end
def self.turn_right(direction)
RightTurns[direction]
end
def self.move(position, direction)
[position[0] + direction[0], position[1] + direction[1]]
end
end
# Recursively tries placing characters on grid until the full word is
# placed or a conflict is found. During the recursion we try two
# options -- continuing in same direction or making a right turn.
# Results are accumulated in result parameter, which is an array of
# Grids.
def find_loops(word, letter_index, grid, position, direction, result)
new_position = Direction.move(position, direction)
character_placed = false
# one of three conditions -- cell is empty, cell contains a letter
# that matches the current word letter, cell contains a letter that
# doesn't match current word letter
if grid[new_position].nil?
# empty cell -- put character in
grid[new_position] = word[letter_index, 1]
character_placed = true
elsif grid[new_position] == word[letter_index, 1]
# cell with matching character, increment overlap count
grid.inc_overlaps
else
# cell with non-matching character, quit searching this branch
return
end
# have we placed the entire word; add to results, otherwise recurse
# continuting in same direction and after making a right turn
if letter_index == word.size - 1
result << grid.dup
else
# try going in the same direction and also try making a right turn
find_loops(word, letter_index + 1, grid,
new_position, direction, result)
find_loops(word, letter_index + 1, grid,
new_position, Direction.turn_right(direction), result)
end
# restore the grid or overlap count depending on earlier condition
if character_placed
grid[new_position] = nil
else
grid.dec_overlaps
end
end
# This is the entry point to the loop-finding process. It places
# first letter in a new grid and calls the recursive find_loops
# methods.
def solve(word)
size = word.length
grid = Grid.new
# starting position allows room for word to go leftwards or upwards
# without bumping into left or top edges; assumes initially heading
# rightwards and only right turns can be made
position = [size - 5, size - 4]
direction = Direction.rightwards
# put first character at starting position
grid[position] = word[0, 1]
# generate solutions in results parameter
results = []
find_loops(word, 1, grid, position, direction, results)
results
end
# find the best results and display them
def display_best_results(results)
# the best results have most overlaps, so sort so most overlaps
# appear at front of array, and then use the first element's
# overlaps as best score
results = results.sort_by { |r| -r.overlaps }
best_score = results.first.overlaps
puts "Number of overlaps: #{best_score}"
puts "=" * 40
results.select { |r| r.overlaps == best_score }.each do |result|
puts result.trim!
puts "=" * 40
end
end
if $0 == __FILE__
if ARGV.size == 1
display_best_results(solve(ARGV[0].downcase))
else
$stderr.puts "Usage: #{$0} _word_"
exit 1
end
end
Joe
Joe L
input = ARGV.first
size = input.length
size -= 1 if size % 2 == 0
a = nil
in2 = input.downcase
while !a && size > 2 do
a = in2.index(/(.).{#{size}}(\1)/)
size -= 2 if !a
end
if a then
b = a + size + 1
(input.length-1).downto(b+1) do |i|
puts input[i,1].rjust(a+1)
end
puts input[0,a+2]
space = a
a += 2
b -= 1
while a < b do
puts "#{"".rjust(space)}#{input[b,1]}#{input[a,1]}"
a += 1
b -= 1
end
else
puts "No Loop."
end
James Gray
> I presume allowing multiple overlaps is valid (if not encouraged?).
> For example, "absolvable" can make use of three overlaps:
>
> .....
> .abs.
> .vlo.
> ..e..
> .....
That's just awesome. Great find!
James Edward Gray II
tho_mica_l
If you remove one line, it will find all simple loops.
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
if __FILE__ == $0
if ARGV.empty?
Quiz149.new('Mississippi').find_solutions.print_solutions
Quiz149.new('Markham').find_solutions.print_solutions
Quiz149.new('yummy').find_solutions.print_solutions
Quiz149.new('Dana').find_solutions.print_solutions
else
ARGV.each {|w| Quiz149.new(w).find_solutions.print_solutions}
end
end
tho_mica_l
interface to show all sorts of knots/loops.
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
if __FILE__ == $0
case ARGV[0]
when '--clockwise', '-c'
clockwise = true
ARGV.shift
else
clockwise = false
end
for word in ARGV
if clockwise
NervousLetters.solve_clockwise(word)
else
NervousLetters.solve_any(word)
end
end
end
Ken Bloom
> The three rules of Ruby Quiz:
>
> 1. Please do not post any solutions or spoiler discussion for this quiz
> until 48 hours have passed from the time on this message.
>
> 2. Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rubyquiz.com/
>
> 3. Enjoy!
>
> Suggestion: A [QUIZ] in the subject of emails about the problem helps
> everyone on Ruby Talk follow the discussion. Please reply to the
> original quiz message, if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
=-=-=-=-=
>
> 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.
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
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)
--
Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
Pawel Radecki
repetition and print the whole word on the screen with the very tight
loop. Suitable repetition exists when distance between identical letters
is an even number greater or equal to four.
#!/usr/bin/env ruby
# Solution to Ruby Quiz #149 (see http://www.rubyquiz.com/quiz149.html)
# by Pawel Radecki (pawel.j...@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
--
Paweł Radecki
m: +48 695 34-64-76
e: pawel.j...@gmail.com
w: http://radeckimarch.blogspot.com/
James Koppel
#greater than 2 from each other
def first_loop(letters)
0.upto(letters.length-1) do |idx1|
(idx1+4).step(letters.length-1,2) do |idx2|
return [idx1,idx2] if letters[idx1].casecmp(letters[idx2])==0
end
end
nil
end
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
3. Enjoy!
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
or:
or:
____________________________________________________________________________________
Be a better friend, newshound, and
know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ
Siep Korteling
"hottentottententententoonstelling". It did not like that.
James Gray
> Here is my solution that tries to make all possible arrangements and
> displays solutions with the maximum number of overlaps.
Here is the much-less-clever code used to create the quiz:
#!/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__
James Edward Gray II
Eric I.
> I tried Eric's code with the dutch artificial word
> "hottentottententententoonstelling". It did not like that.
Yeah, that would be problematic. If L is the number of characters,
then the search space is 2 ** (L - 2) [see reason below]. So with a
33-character word, 2 ** 31 is 2.1 billion. That might take a while in
Ruby 1.8.6. But in 1.9 .... ;)
Eric
P.S. The second character always follows the first character to the
right. Each subsequent character could continue in the same direction
as the previous direction or make a right turn.
Juraj Plavcan
Am I reading it wrong or is there a little mistake?
JP
Juraj Plavcan
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"
James Gray
It wasn't aligned perfectly for me. The | bar coming up from the S
needed to move one space right to line up.
James Edward Gray II
Eric DUMINIL
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.
Eric I.
> Hard specs coming!
>
> Loop of
> -"Entitlements" should be:
>
> me
> Ent
> lti
> _s_
I'm not sure what you mean by "should". My solution found six
solutions all of which have three overlaps. I don't know if there's a
reason to favor one over the others. Perhaps you could favor those
rectangles that have the fewest unused cells, in which case the third
below would be best.
ment
elti
..s.
emen
ltit
...s
men
est
lti
me.
ent
lti
.s.
ments
elti.
ents
m.i.
elt.
Eric
====
Are you interested in on-site Ruby training that's been highly
reviewed by former students? http://LearnRuby.com
Michal Suchanek
I thought this one is too easy once you understand what it is about
but people always come up with difficult solutions. I wish I knew what
the regexp does :S
For those who cannot understand it either:
def indexes l, i
res = []
ptr = 0
while (ptr = l.index i, ptr)
res << ptr
ptr+=1
end
res
end
# .
#.c1=c5..c2
# . .
# c4.....c3
def draw_loop word, c1, c5
length = (c5 - c1) -4
width = length/4
height = length/2 - width
word = word[0..0].upcase + word[1..-1]
c2 = c1 + width +1
c3 = c2 + height +1
c4 = c3 + width +1
word[(c5+1)..-1].reverse.scan(/./).map{|c| " "*c1 + c + "\n"}.join +
word[0..c2] + "\n" +
(1..height).map{|i| " "*c1 + word[c5 - i].chr + " "*width +
word[c2 + i].chr + "\n"}.join +
" "*c1 + word[c3..c4].reverse + "\n"
end
def wloop word
word=word.downcase
tried=[]
ptr=0
while ptr < word.length
if tried.include? word[ptr]
ptr+=1
next
end
char = word[ptr]
tried << char
pos = indexes word, char
next unless pos.length > 1
i, j = 0
while i < pos.length - 1
j=pos.length - 1
while j > i
diff = pos[j] - pos[i]
if (diff)>=4 && (diff) % 2 == 0
return draw_loop word, pos[i], pos[j]
end
j-=1
end
i+=1
end
ptr += 1
end
"No loop \n"
end
Eric DUMINIL
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
Joe
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
Michal Suchanek
> /(.*?)(.)(.(?:..)+?)\2(.*)/i
>
> 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
Yes, makes sense. This group would not be used in the match result.
> \2 matches the any character from before
I wonder if these are still regular epxpressions with those backreferences.
> (.*) a string of any length at the end
>
> i - at the end that means case insensitive.
>
> Joe
Thanks for the nice explanation.
Michal
Ken Bloom
> On 11/12/2007, Joe <qbpr...@gmail.com> wrote:
>> /(.*?)(.)(.(?:..)+?)\2(.*)/i
>>
>> 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
>
> Yes, makes sense. This group would not be used in the match result.
>
>> \2 matches the any character from before
>
> I wonder if these are still regular epxpressions with those
> backreferences.
They're not. They're not even necessarily context-free anymore (although
in this case it still is --- since the backreference can only ever match
something of finite length, we can enumerate all possibilities as
seperate rules in a CFG).
--Ken
Phrogz
> 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
Marvelously tight! However, it outputs this:
loopword "chinchilla"
#=> a
#=> l
#=> l
#=> i
#=> h
#=> ch
#=> ni
when I would have expected this:
loopword "chinchilla"
#=> ch
#=> ni
#=> l
#=> l
#=> a
Alex Shulgin
>
> 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
> 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
Alex Shulgin
> 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.
Yeah, and I've finally found one which can form a loop with some empty
space in it. :-)
Antidisestablishmentarianism:
..........nemh..
..........t..s..
antidisestablism
..........rian..
--
Alex
James Gray
Eric's code makes some fun loops with that word:
$ 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
========================================
James Edward Gray II
tho_mica_l
My second solution does this too if I may humbly add. And you can
watch.
http://groups.google.com/group/comp.lang.ruby/msg/5bf9e41a34f39ec4?dmode=source
tom.
Ruby Quiz
challenge and cheaters like me. Both approaches are neat, but I want to focus
on the under appreciated cheater this time. Contrary to the best practices for
gamblers, cheater is a wonderful label for a programmer to have.
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.
Tomorrow we will tackle a typical programming task in a completely non-typical
manner...