[QUIZ] Word Loop (#149)

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 9, 1:38 pm, Ken Bloom <kbl...@gmail.com> wrote:

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

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, 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.

--
Alex

I guarantee that if you paste the examples into an editor with a
fixed-width font you'll get it immediately. Try vi/emacs/pico/nano
(or Notepad if you're in Windows, I guess?) The Mississippi one is
the key.

···

On Dec 7, 2007 4:32 PM, Drew Olson <olsonas@gmail.com> wrote:

Gavin Kistner wrote:
> On Dec 7, 1:45 pm, Ruby Quiz <ja...@grayproductions.net> wrote:
>>
>> yu
>> mm
>
> Maybe it's because it's a Friday afternoon, but I don't understand the
> quiz problem. Could someone who understands this try explaining it
> (without, of course, discussing any code or even pseudo-code to
> approach it).
>
> I've looked over those examples a few times and I'm totally baffled.
> What does "loop the text around and reuse that letter" mean?

I agree, I'm lost as well...
--
Posted via http://www.ruby-forum.com/\.

Gavin Kistner wrote:
>>
>> yu
>> mm
>
> Maybe it's because it's a Friday afternoon, but I don't understand the
> quiz problem. Could someone who understands this try explaining it
> (without, of course, discussing any code or even pseudo-code to
> approach it).
>
> I've looked over those examples a few times and I'm totally baffled.
> What does "loop the text around and reuse that letter" mean?

I agree, I'm lost as well...
--
Posted via http://www.ruby-forum.com/\.

OH! Fixed width font shows it:

$ ruby word_loop.rb yummy
yu
mm

means

y -> u
/\ \/
> >
m<- m

Hope that helps.

···

On Dec 7, 2007 4:32 PM, Drew Olson <olsonas@gmail.com> wrote:

> On Dec 7, 1:45 pm, Ruby Quiz <ja...@grayproductions.net> wrote:

Quoth Drew Olson:

Gavin Kistner wrote:
>>
>> yu
>> mm
>
> Maybe it's because it's a Friday afternoon, but I don't understand the
> quiz problem. Could someone who understands this try explaining it
> (without, of course, discussing any code or even pseudo-code to
> approach it).
>
> I've looked over those examples a few times and I'm totally baffled.
> What does "loop the text around and reuse that letter" mean?

I agree, I'm lost as well...

They mean make a counter-clockwise "loop" of letters.

Spaced out more (in a fixed width font), this looks like:

start -> 'y' -> 'u'

           ^ v
     
          'm' <- 'm'

= "yummy".

HTH,

···

> On Dec 7, 1:45 pm, Ruby Quiz <ja...@grayproductions.net> wrote:

--
Konrad Meyer <konrad@tylerc.org> http://konrad.sobertillnoon.com/

Very nice visual explanation.

I stared at this quiz for a while and simply could not understand. It
was only when I was about to post a reply begging for an explanation
that I got it.

It's clear to me now I should've posted a reply with the explanation
instead of just moving on.

···

On Dec 7, 3:45 pm, Phrogz <phr...@mac.com> wrote:

On Dec 7, 2:27 pm, Phrogz <phr...@mac.com> wrote:

> On Dec 7, 1:45 pm, Ruby Quiz <ja...@grayproductions.net> wrote:

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

> > or:

> > $ ruby word_loop.rb Markham
> > Ma
> > ar
> > hk

> > or:

> > $ ruby word_loop.rb yummy
> > yu
> > mm

> Maybe it's because it's a Friday afternoon, but I don't understand the
> quiz problem. Could someone who understands this try explaining it
> (without, of course, discussing any code or even pseudo-code to
> approach it).

> I've looked over those examples a few times and I'm totally baffled.
> What does "loop the text around and reuse that letter" mean?

Ah, got it.

[y] -> [u]
^ |
> v
[m] <- [m]

[M] -> [a]
^ |
> v
[a] [r]
^ |
> v
[h] <- [k]

       [i]
        ^
        >
       [p]
        ^
        >
       [p]
        ^
        >
[M] -> [i] -> [s]
        ^ |
        > v
       [s] [s]
        ^ |
        > v
       [s] <- [i]

--
-yossef

Correct, and turns need to be clockwise.

James Edward Gray II

···

On Dec 7, 2007, at 3:50 PM, Alex Fenton wrote:

I'm taking from the MISSISSIPI example that moves have to be in the same direction as the last move, or at a 90 degree angle to it

"Alex Fenton" <alex@deleteme.pressure.to> wrote in message
news:x7j6j.1781$h35.792@newsfe2-gui.ntli.net...

Phrogz wrote:

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

<snip>

Maybe it's because it's a Friday afternoon, but I don't understand the
quiz problem. Could someone who understands this try explaining it
(without, of course, discussing any code or even pseudo-code to
approach it).

It took me a few monents too. The letters have to be arranged in a grid so
that by moving one square at a time, the word is spelled out. The test is
to see whether the word can be spelled out by, at some point, moving over
the same grid square twice.

I'm taking from the MISSISSIPI example that moves have to be in the same
direction as the last move, or at a 90 degree angle to it, otherwise it
could be spelled by moving up back onto "S" after the second "I" in the
bottom right.

a

Hmm..
Looks like mississippi is ambiguous, what about

  I
  P
  P
  I
MISS
  SI

?

EK

···

On Dec 7, 1:45 pm, Ruby Quiz <ja...@grayproductions.net> wrote:

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)
# by Pawel Radecki (pawel.j.radecki@gmail.com).

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

···

--
Paweł Radecki
m: +48 695 34-64-76
e: pawel.j.radecki@gmail.com
w: http://radeckimarch.blogspot.com/

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/\.

/(.*?)(.)(.(?:..)+?)\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 Dec 10, 2007 1:14 PM, Michal Suchanek <hramrach@centrum.cz> wrote:

On 09/12/2007, Ken Bloom <kbloom@gmail.com> wrote:
>
> 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
>
> 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)
>

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

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

$ ruby word_loop.rb Antidisestablishmentarianism
Number of overlaps: 5

···

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

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. :slight_smile:

Antidisestablishmentarianism:

..........nemh..
..........t..s..
antidisestablism
..........rian..

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

(Sorry for double post)

Look at the actual Ruby Quiz page for this quiz:

http://www.rubyquiz.com/quiz149.html

For the Mississippi example, start with M and follow the spelling of the
word. You'll go right, down, left, and up, reusing one of the 'i's

Jason

···

On Dec 7, 2007 4:37 PM, Jason Roelofs <jameskilton@gmail.com> wrote:

On Dec 7, 2007 4:32 PM, Drew Olson <olsonas@gmail.com> wrote:

> Gavin Kistner wrote:
> > On Dec 7, 1:45 pm, Ruby Quiz <ja...@grayproductions.net> wrote:
> >>
> >> yu
> >> mm
> >
> > Maybe it's because it's a Friday afternoon, but I don't understand the
> > quiz problem. Could someone who understands this try explaining it
> > (without, of course, discussing any code or even pseudo-code to
> > approach it).
> >
> > I've looked over those examples a few times and I'm totally baffled.
> > What does "loop the text around and reuse that letter" mean?
>
> I agree, I'm lost as well...
> --
> Posted via http://www.ruby-forum.com/\.
>
> OH! Fixed width font shows it:

$ ruby word_loop.rb yummy
yu
mm

means

y -> u
/\ \/
> >
m<- m

Hope that helps.

I guarantee you're wrong, only because I *was* reading it with a fixed-
width font, both in email and on comp.lang.ruby. The pattern just
didn't jump out at first.

But I got it now, thanks :slight_smile:

···

On Dec 7, 2:37 pm, Christian von Kleist <cvonkle...@gmail.com> wrote:

On Dec 7, 2007 4:32 PM, Drew Olson <olso...@gmail.com> wrote:

> Gavin Kistner wrote:
> > On Dec 7, 1:45 pm, Ruby Quiz <ja...@grayproductions.net> wrote:

> >> yu
> >> mm

> > Maybe it's because it's a Friday afternoon, but I don't understand the
> > quiz problem. Could someone who understands this try explaining it
> > (without, of course, discussing any code or even pseudo-code to
> > approach it).

> > I've looked over those examples a few times and I'm totally baffled.
> > What does "loop the text around and reuse that letter" mean?

> I agree, I'm lost as well...
> --
> Posted viahttp://www.ruby-forum.com/.

I guarantee that if you paste the examples into an editor with a
fixed-width font you'll get it immediately. Try vi/emacs/pico/nano
(or Notepad if you're in Windows, I guess?) The Mississippi one is
the key.

I don't see how this works with 90 degree turns in a clockwise direction, as mentioned earlier in this thread.

Of course, I'm never one to discourage experimentation.

James Edward Gray II

···

On Dec 7, 2007, at 11:40 PM, Eugene Kalenkovich wrote:

"Alex Fenton" <alex@deleteme.pressure.to> wrote in message
news:x7j6j.1781$h35.792@newsfe2-gui.ntli.net...

Phrogz wrote:

On Dec 7, 1:45 pm, Ruby Quiz <ja...@grayproductions.net> wrote:

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
       Mis
        ss
        si

<snip>

Maybe it's because it's a Friday afternoon, but I don't understand the
quiz problem. Could someone who understands this try explaining it
(without, of course, discussing any code or even pseudo-code to
approach it).

It took me a few monents too. The letters have to be arranged in a grid so
that by moving one square at a time, the word is spelled out. The test is
to see whether the word can be spelled out by, at some point, moving over
the same grid square twice.

I'm taking from the MISSISSIPI example that moves have to be in the same
direction as the last move, or at a 90 degree angle to it, otherwise it
could be spelled by moving up back onto "S" after the second "I" in the
bottom right.

a

Hmm..
Looks like mississippi is ambiguous, what about

I
P
I
MISS
SI

?

Konrad Meyer:

They mean make a counter-clockwise "loop" of letters.

Spaced out more (in a fixed width font), this looks like:

start -> 'y' -> 'u'

           ^ v
     
          'm' <- 'm'

= "yummy".

*Counter*-clockwise? Ah, right, you must be on the other hemisphere…

-- SCNR, Shot

···

--
a alphabetically be in organised sentence should words -- Atob

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 .... :wink:

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.

···

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.

/(.*?)(.)(.(?:..)+?)\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 11/12/2007, Joe <qbproger@gmail.com> wrote:

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.

"James Gray" <james@grayproductions.net> wrote in message
news:853F208B-1F25-4509-BCB5-0A6C18DBCA33@grayproductions.net...

Hmm..
Looks like mississippi is ambiguous, what about

I
P
P
I
MISS
SI

?

I don't see how this works with 90 degree turns in a clockwise
direction, as mentioned earlier in this thread.

Of course, I'm never one to discourage experimentation.

James Edward Gray II

          I
          P
          >
          P
          >
          I
          >
M -> I -> S -> S
          > >
          S <- I

···

On Dec 7, 2007, at 11:40 PM, Eugene Kalenkovich wrote: