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.