The old Google Groups will be going away soon, but your browser is incompatible with the new version.
This is a Usenet group - learn more
Word Loop (#149) [SOLUTION]
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 Messages 26 - 49 of 49 < Older
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful

From:
To:
Cc:
Followup To:
 Add Cc | Add Followup-to | Edit Subject
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Dec 9 2007, 3:34 pm
Newsgroups: comp.lang.ruby
From: tho_mica_l <micat...@gmail.com>
Date: Sun, 9 Dec 2007 12:34:13 -0800 (PST)
Local: Sun, Dec 9 2007 3:34 pm
Subject: Re: Word Loop (#149) [SOLUTION]
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
# 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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 9 2007, 3:37 pm
Newsgroups: comp.lang.ruby
From: tho_mica_l <micat...@gmail.com>
Date: Sun, 9 Dec 2007 12:37:24 -0800 (PST)
Local: Sun, Dec 9 2007 3:37 pm
Subject: Re: Word Loop (#149) [SOLUTION]
My second solution uses a recursive algorithm and provides a curses
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)
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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
 Discussion subject changed to "Word Loop (#149)" by Ken Bloom
More options Dec 9 2007, 3:38 pm
Newsgroups: comp.lang.ruby
From: Ken Bloom <kbl...@gmail.com>
Date: Sun, 09 Dec 2007 20:38:06 GMT
Local: Sun, Dec 9 2007 3:38 pm
Subject: Re: [QUIZ] Word Loop (#149)

def loopword word
matchinfo=
word.match(/(.*?)(.)(.(?:..)+?)\2(.*)/i)
if matchinfo
_,before,letter,looplets,after=matchinfo.to_a
looplets=looplets.split(//)
puts before+letter+looplets.shift
until looplets.empty?
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/

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
 Discussion subject changed to "Word Loop (#149) [SOLUTION]" by Pawel Radecki
More options Dec 9 2007, 3:46 pm
Newsgroups: comp.lang.ruby
Date: Sun, 9 Dec 2007 15:46:04 -0500
Local: Sun, Dec 9 2007 3:46 pm
Subject: Re: Word Loop (#149) [SOLUTION]
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

# Solution to Ruby Quiz #149 (see http://www.rubyquiz.com/quiz149.html)

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

--
m: +48 695 34-64-76

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
 Discussion subject changed to "Word Loop (#149)" by James Koppel
More options Dec 9 2007, 3:47 pm
Newsgroups: comp.lang.ruby
From: James Koppel <jamesbkop...@yahoo.com>
Date: Sun, 9 Dec 2007 15:47:48 -0500
Local: Sun, Dec 9 2007 3:47 pm
Subject: Re: [QUIZ] Word Loop (#149)
#A loop is possible whenever there are two of the same lettter an even distance
#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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 9 2007, 4:19 pm
Newsgroups: comp.lang.ruby
From: Siep Korteling <s.kortel...@gmail.com>
Date: Sun, 9 Dec 2007 16:19:05 -0500
Local: Sun, Dec 9 2007 4:19 pm
Subject: Re: Word Loop (#149)
James Gray 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 Gray II

I tried Eric's code with the dutch artificial word
"hottentottententententoonstelling". It did not like that.

--
Posted via http://www.ruby-forum.com/.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
 Discussion subject changed to "Word Loop (#149) [SOLUTION]" by James Gray
More options Dec 9 2007, 4:41 pm
Newsgroups: comp.lang.ruby
From: James Gray <ja...@grayproductions.net>
Date: Sun, 9 Dec 2007 16:41:46 -0500
Local: Sun, Dec 9 2007 4:41 pm
Subject: Re: Word Loop (#149) [SOLUTION]
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 Gray II

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
 Discussion subject changed to "Word Loop (#149)" by Eric I.
More options Dec 9 2007, 8:28 pm
Newsgroups: comp.lang.ruby
From: "Eric I." <rubytrain...@gmail.com>
Date: Sun, 9 Dec 2007 17:28:44 -0800 (PST)
Local: Sun, Dec 9 2007 8:28 pm
Subject: Re: Word Loop (#149)
On Dec 9, 4:19 pm, Siep Korteling <s.kortel...@gmail.com> 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.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 10 2007, 3:31 am
Newsgroups: comp.lang.ruby
From: Juraj Plavcan <yam...@gmail.com>
Date: Mon, 10 Dec 2007 03:31:46 -0500
Local: Mon, Dec 10 2007 3:31 am
Subject: Re: Word Loop (#149)

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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
 Discussion subject changed to "Word Loop (#149) [SOLUTION]" by Juraj Plavcan
More options Dec 10 2007, 10:06 am
Newsgroups: comp.lang.ruby
From: Juraj Plavcan <yam...@gmail.com>
Date: Mon, 10 Dec 2007 10:06:46 -0500
Local: Mon, Dec 10 2007 10:06 am
Subject: Re: [QUIZ] Word Loop (#149) [SOLUTION]
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"

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
 Discussion subject changed to "Word Loop (#149)" by James Gray
More options Dec 10 2007, 10:26 am
Newsgroups: comp.lang.ruby
From: James Gray <ja...@grayproductions.net>
Date: Mon, 10 Dec 2007 10:26:09 -0500
Local: Mon, Dec 10 2007 10:26 am
Subject: Re: Word Loop (#149)
On Dec 10, 2007, at 2:31 AM, Juraj Plavcan wrote:

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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 10 2007, 10:38 am
Newsgroups: comp.lang.ruby
From: Eric DUMINIL <eric.dumi...@gmail.com>
Date: Mon, 10 Dec 2007 10:38:30 -0500
Local: Mon, Dec 10 2007 10:38 am
Subject: Re: Word Loop (#149)
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 10/12/2007, Juraj Plavcan <yam...@gmail.com> wrote:

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 10 2007, 11:08 am
Newsgroups: comp.lang.ruby
From: "Eric I." <rubytrain...@gmail.com>
Date: Mon, 10 Dec 2007 08:08:26 -0800 (PST)
Local: Mon, Dec 10 2007 11:08 am
Subject: Re: Word Loop (#149)
On Dec 10, 10:38 am, Eric DUMINIL <eric.dumi...@gmail.com> 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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 10 2007, 1:14 pm
Newsgroups: comp.lang.ruby
From: Michal Suchanek <hramr...@centrum.cz>
Date: Mon, 10 Dec 2007 13:14:40 -0500
Local: Mon, Dec 10 2007 1:14 pm
Subject: Re: [QUIZ] Word Loop (#149)
On 09/12/2007, Ken Bloom <kbl...@gmail.com> wrote:

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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 10 2007, 1:55 pm
Newsgroups: comp.lang.ruby
From: Eric DUMINIL <eric.dumi...@gmail.com>
Date: Mon, 10 Dec 2007 13:55:58 -0500
Local: Mon, Dec 10 2007 1:55 pm
Subject: Re: Word Loop (#149)
Hi!

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:

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 10 2007, 7:06 pm
Newsgroups: comp.lang.ruby
From: Joe <qbpro...@gmail.com>
Date: Mon, 10 Dec 2007 19:06:18 -0500
Local: Mon, Dec 10 2007 7:06 pm
Subject: Re: [QUIZ] Word Loop (#149)
/(.*?)(.)(.(?:..)+?)\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
\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:

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 10 2007, 7:50 pm
Newsgroups: comp.lang.ruby
From: Michal Suchanek <hramr...@centrum.cz>
Date: Mon, 10 Dec 2007 19:50:09 -0500
Local: Mon, Dec 10 2007 7:50 pm
Subject: Re: [QUIZ] Word Loop (#149)
On 11/12/2007, Joe <qbpro...@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.

> (.*) a string of any length at the end

> i - at the end that means case insensitive.

> Joe

Thanks for the nice explanation.

Michal

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 10 2007, 10:08 pm
Newsgroups: comp.lang.ruby
From: Ken Bloom <kbl...@gmail.com>
Date: Tue, 11 Dec 2007 03:08:05 GMT
Local: Mon, Dec 10 2007 10:08 pm
Subject: Re: [QUIZ] Word Loop (#149)

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

--
Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 10 2007, 10:17 pm
Newsgroups: comp.lang.ruby
From: Phrogz <phr...@mac.com>
Date: Mon, 10 Dec 2007 19:17:12 -0800 (PST)
Local: Mon, Dec 10 2007 10:17 pm
Subject: Re: Word Loop (#149)
On Dec 9, 1:38 pm, Ken Bloom <kbl...@gmail.com> wrote:

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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 11 2007, 5:10 pm
Newsgroups: comp.lang.ruby
From: Alex Shulgin <alex.shul...@gmail.com>
Date: Tue, 11 Dec 2007 14:10:24 -0800 (PST)
Local: Tues, Dec 11 2007 5:10 pm
Subject: Re: Word Loop (#149)
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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 12 2007, 2:54 am
Newsgroups: comp.lang.ruby
From: Alex Shulgin <alex.shul...@gmail.com>
Date: Tue, 11 Dec 2007 23:54:00 -0800 (PST)
Subject: Re: Word Loop (#149)
On Dec 12, 12:10 am, Alex Shulgin <alex.shul...@gmail.com> wrote:

> 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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 12 2007, 9:39 am
Newsgroups: comp.lang.ruby
From: James Gray <ja...@grayproductions.net>
Date: Wed, 12 Dec 2007 09:39:11 -0500
Local: Wed, Dec 12 2007 9:39 am
Subject: Re: Word Loop (#149)
On Dec 12, 2007, at 1:55 AM, Alex Shulgin wrote:

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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 12 2007, 10:06 am
Newsgroups: comp.lang.ruby
From: tho_mica_l <micat...@gmail.com>
Date: Wed, 12 Dec 2007 07:06:33 -0800 (PST)
Local: Wed, Dec 12 2007 10:06 am
Subject: Re: Word Loop (#149)

> Eric's code makes some fun loops with that word:

My second solution does this too if I may humbly add. And you can
watch.

tom.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Dec 13 2007, 8:17 am
Newsgroups: comp.lang.ruby
From: Ruby Quiz <ja...@grayproductions.net>
Date: Thu, 13 Dec 2007 08:17:44 -0500
Local: Thurs, Dec 13 2007 8:17 am
Subject: [SUMMARY] Word Loop (#149)
There were two kinds of solvers this week:  hardcore programmers who love a good
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
looplets=looplets.split(//)
puts before+letter+looplets.shift
until looplets.empty?
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
looplets=looplets.split(//)
puts before+letter+looplets.shift
until looplets.empty?
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...

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
 End of messages < Older
 « Back to Discussions « Newer topic Older topic »