# Word Loop (#149)

**URL:** <https://www.ruby-forum.com/t/word-loop-149/123024>\
**Category:** Ruby\
**Created:** [December 13, 2007, 2:22pm UTC](https://www.ruby-forum.com/t/word-loop-149/123024 "2007-12-13T14:22:38Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [December 13, 2007, 2:22pm UTC](https://www.ruby-forum.com/t/word-loop-149/123024/1 "2007-12-13T14:22:38Z")

</div>

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  
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…