Succ distance between two strings

ruby-talk
1

Is there an efficient way to calculate the "succ distance" between two strings
(without iterating over each succession)? Examples:

  'a'..'a' 0
  'a'..'b' 1
  'a'..'z' 25
  'a'..'aa' 26

T.

2

Hi --

···

On Sat, 6 Nov 2004, trans. (T. Onoma) wrote:

Is there an efficient way to calculate the "succ distance" between two strings
(without iterating over each succession)? Examples:

  'a'..'a' 0
  'a'..'b' 1
  'a'..'z' 25
  'a'..'aa' 26

'a'...'aa'.to_a.size # would be one way

David

--
David A. Black
dblack@wobblini.net

3

trans. (T. Onoma) ha scritto:

Is there an efficient way to calculate the "succ distance" between two strings (without iterating over each succession)? Examples:

  'a'..'a' 0
  'a'..'b' 1
  'a'..'z' 25
  'a'..'aa' 26

T.

my tentativ impl would be
class String
  def value
     i=-26
     split(//).inject(0){|x,y|
       i+=26
       x+y[0]-?a+i
     }
  end
end

class Range
  def dist
   max.value - min.value
  end
end
p 'aa'.value - 'a'.value
p 'a'.value - 'a'.value
p ('a'..'b').dist
p ('a'..'z').dist

note that '-?a' could be moved in the 'i' initialization but I'm running away :slight_smile:

4

That still iterates over all elements but it looks sweet :slight_smile:
Only for large strings would be a problem

My stab:

def diff_succ s1, s2
   t1 = t2 = 0
   s1.each_byte{|c| t1 = t1*26 + c - 96}
   s2.each_byte{|c| t2 = t2*26 + c - 96}
   t2 - t1
end

def t s1, s2
   puts "#{s1}..#{s2} => #{diff_succ s1, s2}"
end

t 'a', 'a' #0
t 'a', 'b' #1
t 'a', 'z' #25
t 'a', 'aa' #26

t 'A', 'B'
t 'A', 'Z'
t 'A', 'AA'

output:
a..a => 0
a..b => 1
a..z => 25
a..aa => 26
A..B => 1
A..Z => 25
A..AA => -806

Notice how it breaks on multi-letter uppercase strings? that is because of the -96. Maybe one should just lowercase the args...

/Curne

···

On Nov 6, 2004, at 3:07 PM, David A. Black wrote:

Hi --

On Sat, 6 Nov 2004, trans. (T. Onoma) wrote:

Is there an efficient way to calculate the "succ distance" between two strings
(without iterating over each succession)? Examples:

  'a'..'a' 0
  'a'..'b' 1
  'a'..'z' 25
  'a'..'aa' 26

'a'...'aa'.to_a.size # would be one way

--
Mailing lists confuse me. Often I don't recognize my own posts and set about writing a flaming reply where I violently disagree. [curne@curnomatic.dk]

5

For the first 3 examples you can also treat them as characters and do:

?a - ?a #=> 0
?b - ?a #=> 1
?z - ?a #=> 25

Not exactly what you want though.

Chad Fowler
http://chadfowler.com

http://rubygems.rubyforge.org (over 20,000 gems served!)

···

On Sat, 6 Nov 2004 23:07:59 +0900, David A. Black <dblack@wobblini.net> wrote:

Hi --

On Sat, 6 Nov 2004, trans. (T. Onoma) wrote:

>
> Is there an efficient way to calculate the "succ distance" between two strings
> (without iterating over each succession)? Examples:
>
> 'a'..'a' 0
> 'a'..'b' 1
> 'a'..'z' 25
> 'a'..'aa' 26

'a'...'aa'.to_a.size # would be one way

6

Thanks all for the responses. Looks like it _might_ be doable, but the
complexity quickly racks up. The presented quick stabs at it fail on capital
letters and other characters.

Running away might be the best course of action :wink:

T.

···

On Saturday 06 November 2004 09:38 am, gabriele renzi wrote:

trans. (T. Onoma) ha scritto:
> Is there an efficient way to calculate the "succ distance" between two
> strings (without iterating over each succession)? Examples:
>
> 'a'..'a' 0
> 'a'..'b' 1
> 'a'..'z' 25
> 'a'..'aa' 26
>
> T.

my tentativ impl would be
class String
  def value
     i=-26
     split(//).inject(0){|x,y|
       i+=26
       x+y[0]-?a+i
     }
  end
end

class Range
  def dist
   max.value - min.value
  end
end
p 'aa'.value - 'a'.value
p 'a'.value - 'a'.value
p ('a'..'b').dist
p ('a'..'z').dist

note that '-?a' could be moved in the 'i' initialization but I'm running
away :slight_smile:

--
( o _ カラチ
// trans.
/ \ transami@runbox.com

I don't give a damn for a man that can only spell a word one way.
-Mark Twain

[8,16,20,29,78,65,2,14,26,12,12,28,71,114,12,13,12,82,72,21,17,4,10,2,95].
each_with_index{|x,i| $><<(x^'Begin landing your troops'[i]).chr}
-Tadayoshi Funaba

7

That does not work, as the ... have a very low binding. It seems a common error I made often.

bschroed@black:~ $ irb
irb(main):001:0> 'a'...'aa'.to_a.size
=> "a"...1
irb(main):002:0> ('a'...'aa').to_a.size
=> 26

Regards,

Brian

···

On Sat, 6 Nov 2004 23:07:59 +0900 "David A. Black" <dblack@wobblini.net> wrote:

Hi --

On Sat, 6 Nov 2004, trans. (T. Onoma) wrote:

>
> Is there an efficient way to calculate the "succ distance" between two strings
> (without iterating over each succession)? Examples:
>
> 'a'..'a' 0
> 'a'..'b' 1
> 'a'..'z' 25
> 'a'..'aa' 26

'a'...'aa'.to_a.size # would be one way

--
Brian Schröder
http://www.brian-schroeder.de/

8

Hi --

···

On Mon, 8 Nov 2004, Brian [ISO-8859-15] Schröder wrote:

On Sat, 6 Nov 2004 23:07:59 +0900 > "David A. Black" <dblack@wobblini.net> wrote:

> Hi --
>
> On Sat, 6 Nov 2004, trans. (T. Onoma) wrote:
>
> >
> > Is there an efficient way to calculate the "succ distance" between two strings
> > (without iterating over each succession)? Examples:
> >
> > 'a'..'a' 0
> > 'a'..'b' 1
> > 'a'..'z' 25
> > 'a'..'aa' 26
>
> 'a'...'aa'.to_a.size # would be one way

That does not work, as the ... have a very low binding. It seems a common error I made often.

bschroed@black:~ $ irb
irb(main):001:0> 'a'...'aa'.to_a.size
=> "a"...1
irb(main):002:0> ('a'...'aa').to_a.size
=> 26

Whoops -- I did actually do it correctly in irb, to make sure, and
then wrote it out wrongly instead of pasting it.

It's like putting (i.e., putt-ing, in golf) -- you can never take it
for granted :slight_smile:

David

--
David A. Black
dblack@wobblini.net