Looks like mississippi is ambiguous, what about
I don’t see how this works with 90 degree turns in a clockwise
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.
On Dec 8, 2007, at 12:15 PM, tho_mica_l wrote:
Looks like mississippi is ambiguous, what about
I don’t see how this works with 90 degree turns in a clockwise
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)?
The task is to draw one of the possible loops.
James Edward G. II
Konrad M.:
They mean make a counter-clockwise “loop” of letters.
Spaced out more (in a fixed width font), this looks like:
start -> ‘y’ -> ‘u’
^ v 'm' <- 'm'
= “yummy”.
Counter-clockwise? Ah, right, you must be on the other hemisphere…
– SCNR, Shot
I presume allowing multiple overlaps is valid (if not encouraged?).
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
!
Here is my solution. It finds the longest cycle possible.
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
On Dec 9, 2007, at 1:50 PM, Eric I. wrote:
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 G. II
Here is my solution that tries to make all possible arrangements and
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
====
class Grid
attr_reader :overlaps
def initialize
@grid = Array.new
@overlaps = 0
end
def
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
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
def sub_array(index)
sub_array = @grid[index]
sub_array = @grid[index] = Array.new if sub_array.nil?
sub_array
end
def empty_columns
index = 0
index += 1 while @grid.all? { |row| row.nil? || row[index].nil? }
index
end
end
module Direction
RightTurns = {
[0, 1] => [1, 0],
[1, 0] => [0, -1],
[0, -1] => [-1, 0],
[-1, 0] => [0, 1],
}
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
def find_loops(word, letter_index, grid, position, direction, result)
new_position = Direction.move(position, direction)
character_placed = false
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
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
if character_placed
grid[new_position] = nil
else
grid.dec_overlaps
end
end
def solve(word)
size = word.length
grid = Grid.new
position = [size - 5, size - 4]
direction = Direction.rightwards
grid[position] = word[0, 1]
results = []
find_loops(word, 1, grid, position, direction, results)
results
end
def display_best_results(results)
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
My second solution uses a recursive algorithm and provides a curses
interface to show all sorts of knots/loops.
Thomas.
#!/usr/bin/env ruby
wise
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
On Fri, 07 Dec 2007 15:45:02 -0500, Ruby Q. wrote:
Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone on Ruby T. follow the discussion. Please reply to the
original quiz message, if you can.-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
=-=-=-=-=
p
hk
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)
Here is my first solution. By default, it finds the smallest circle.
If you remove one line, it will find all simple loops.
Thomas.
#!/usr/bin/env ruby
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 -
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
And here is my solution. It tries to find first suitable letter
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
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
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
Quoth Shot (Piotr S.):
Counter-clockwise? Ah, right, you must be on the other hemisphere…
– SCNR, Shot
My bad :D.
James G. wrote:
On Dec 9, 2007, at 1:50 PM, Eric I. wrote:
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 G. II
I tried Eric’s code with the dutch artificial word
“hottentottententententoonstelling”. It did not like that.
On Dec 9, 2007, at 1:50 PM, Eric I. wrote:
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 G. II
On Dec 9, 4:19 pm, Siep K. [email protected] wrote:
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.
James G. wrote:
I
|James Edward G. II
When I read it clockwise I see M I S S I S I I P P I
Am I reading it wrong or is there a little mistake?
JP
My solution…
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”
On Dec 10, 2007, at 2:31 AM, Juraj Plavcan wrote:
direction, as mentioned earlier in this thread.
P
You are right, that works too.James Edward G. II
When I read it clockwise I see M I S S I S I I P P I
Am I reading it wrong or is there a little mistake?
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 G. II
Hard specs coming!
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 Dec 10, 10:38 am, Eric DUMINIL [email protected] wrote:
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
This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.
Sponsor our Newsletter | Privacy Policy | Terms of Service | Remote Ruby Jobs