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:0x58a188md.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…