Word Loop (#149)

On 09/12/2007, Ken B. [email protected] wrote:

until looplets.empty?

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

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

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

/(.?)(.)(.(?:…)+?)\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:


\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 11/12/2007, Joe [email protected] 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:
Ruby | zenspider.com | by ryan davis

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

On Mon, 10 Dec 2007 19:50:09 -0500, Michal S. wrote:

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

On Dec 9, 1:38 pm, Ken B. [email protected] wrote:

  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

On Dec 7, 10:45 pm, Ruby Q. [email protected] wrote:

     p
    Mis
     ss
     si

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

#!/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 :wink:
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. :wink:

On Dec 12, 12:10 am, Alex S. [email protected] wrote:

On Dec 7, 10:45 pm, Ruby Q. [email protected] 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. :slight_smile:

Antidisestablishmentarianism:

…nemh…
…t…s…
antidisestablism
…rian…

On Dec 12, 2007, at 1:55 AM, Alex S. wrote:

Antidisestablishmentarianism:

…nemh…
…t…s…
antidisestablism
…rian…

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 G. II

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.
http://groups.google.com/group/comp.lang.ruby/msg/5bf9e41a34f39ec4?dmode=source

tom.