Please check my algorithm

Hi, I found a nice programming challenge:
http://acm.uva.es/p/v3/333.html

I have written an entry in Ruby, and I’d like to know if there are
things I could improve.

#!/usr/bin/env ruby

class ISBN
def initialize(code)
@code = code
end

def calc(lst)
ans = []
ans[0] = lst[0]
for i in 1…lst.length
ans[i] = ans[i-1] + lst[i]
end
ans
end

def validChars
stripCode = @code.tr("-", “”)
if stripCode =~ /^[0-9]{9}[0-9X]$/i
true
else
false
end
end

def validate
if validChars then
stripCode = @code.tr("-", “”)
s0 = []
stripCode.each_byte { |c|
s0 << c.chr
}
s0[-1] = 10 if s0[-1] =~ /x/i
s0.map! { |x| x.to_i }
else
raise "Invalid ISBN"
end

s1 = calc(s0)
s2 = calc(s1)

raise "Invalid ISBN" if s2[-1] % 11 != 0

end
end

while true
print "> "
code = gets.strip
begin
isbn = ISBN.new(code)
isbn.validate
puts "#{code}: Valid ISBN"
rescue Exception => e
puts e
end
end

···

Vincent Foley-Bourgon
Email: vinfoley@iquebec.com
Homepage: http://darkhost.mine.nu:81

Hi, I found a nice programming challenge:
http://acm.uva.es/p/v3/333.html

I have written an entry in Ruby, and I’d like to know if there are
things I could improve.
[…]
Vincent Foley-Bourgon

Without comments it’s difficult to understand what you’re trying to do, but I
reckon that if I understood what “validate” does, I could make it
shorter/clearer.

Gavin

···

From: “Vincent Foley” vinfoley@iquebec.com

Hi –

Hi, I found a nice programming challenge:
http://acm.uva.es/p/v3/333.html

That is quite a cool one.

I have written an entry in Ruby, and I’d like to know if there are
things I could improve.

#!/usr/bin/env ruby

class ISBN
def initialize(code)
@code = code
end

def calc(lst)
ans =
ans[0] = lst[0]
for i in 1…lst.length
ans[i] = ans[i-1] + lst[i]
end
ans
end

This struck me as a good candidate for the new #inject method, though
that’s only in 1.7. (See below.)

def validChars
stripCode = @code.tr(“-”, “”)
if stripCode =~ /[1]{9}[0-9X]$/i
true
else
false
end
end

Unless you really need ‘true’ and ‘false’, you could just do:

def valid_chars
/^\d{9}[\dX]$/i.match(@code.delete(“-”))
end

and let the MatchData/nil distinction serve for the Boolean test.

(OK, I admit I’m slipping in some subliminal antiCamelCase
propaganda :slight_smile:

def validate
if validChars then
stripCode = @code.tr(“-”, “”)

You’ve got that twice; you might want to have a separate method, or
instance variable, for the tr’d version.

[…]

Well, for what it’s worth, here’s my 1.7-only version (it uses
#inject). I can’t help feeling there’s a way to do some kind of
double inject, and avoid using the ‘t’ accumulator… but anyway, here
is its current incarnation:

#!/usr/local/lib/ruby/1.7/bin/ruby -w

class ISBN < String

ISBN_RE = /^\s*(\d-?){9}(X|\d)\s*$/

def check
  t = 0
  ISBN_RE.match(self) &&
numbers.inject(0) {|x,y| t += x+y; x+y } &&
(t % 11) .zero?
end

def numbers
  strip.delete('-').split(//).map {|i| i.sub(/X/,"10").to_i}
end

end

p ISBN.new(“0-89237-010-6”).check # true
p ISBN.new(“0-89237-010-5”).check # false
p ISBN.new(“blah”).check # nil

END

(The nil/false thing could be smoothed out if necessary.)

David

···

On Tue, 15 Oct 2002, Vincent Foley wrote:


David Alan Black
home: dblack@candle.superlink.net
work: blackdav@shu.edu
Web: http://pirate.shu.edu/~blackdav


  1. 0-9 ↩︎

dblack@candle.superlink.net wrote in message news:Pine.LNX.4.44.0210142141510.7458-100000@candle.superlink.net

Well, for what it’s worth, here’s my 1.7-only version (it uses
#inject). I can’t help feeling there’s a way to do some kind of
double inject, and avoid using the ‘t’ accumulator… but anyway, here
is its current incarnation:

  t = 0
  ISBN_RE.match(self) &&

numbers.inject(0) {|x,y| t += x+y; x+y } &&
(t % 11) .zero?
end

ISBN_RE.match(self) &&
( (numbers.inject([0]){|x,y| x << (x[-1]+y)}.inject(0){|x,y| x+y}) % 11).zero?

martin

dblack@candle.superlink.net wrote in message
news:Pine.LNX.4.44.0210142141510.7458-100000@candle.superlink.net

Well, for what it’s worth, here’s my 1.7-only version (it uses
#inject). I can’t help feeling there’s a way to do some kind of
double inject, and avoid using the ‘t’ accumulator… but anyway, here
is its current incarnation:

  t = 0
  ISBN_RE.match(self) &&
numbers.inject(0) {|x,y| t += x+y; x+y } &&
(t % 11) .zero?
end

ISBN_RE.match(self) &&
( (numbers.inject([0]){|x,y| x << (x[-1]+y)}.inject(0){|x,y| x+y}) % 11).zero?

martin

Was the intent here to shorten the code to beyond obfuscation threshholds?

I thought that was one thing so many on this group rail against perl for…

Well, I personally do not object obfuscation as long as it is
significantly “faster” (much faster, if possible) :slight_smile:

But of course, the best is if it is faster and yet explicit/clear…

Regards,

Bill

···

===========================================================================
Mike Campbell michael_s_campbell@yahoo.com wrote:

  t = 0
  ISBN_RE.match(self) &&
numbers.inject(0) {|x,y| t += x+y; x+y } &&
(t % 11) .zero?
end

ISBN_RE.match(self) &&
( (numbers.inject([0]){|x,y| x << (x[-1]+y)}.inject(0){|x,y| x+y}) % 11).zero?

martin

Was the intent here to shorten the code to beyond obfuscation threshholds?

I thought that was one thing so many on this group rail against perl for…

“Mike Campbell” michael_s_campbell@yahoo.com wrote in message news:NFBBKBEMGLGCIPPFGHOLMEHOCLAA.michael_s_campbell@yahoo.com

ISBN_RE.match(self) &&
( (numbers.inject([0]){|x,y| x << (x[-1]+y)}.inject(0){|x,y| x+y}) % 11).zero?

martin

Was the intent here to shorten the code to beyond obfuscation threshholds?

I thought that was one thing so many on this group rail against perl for…

Nope, just to use two injects rather than an accumulator (which was
what was asked). Which needed the first inject to collect into an
array (since the second inject needed to be passed one).

Besides which, golfing and playing variations on a theme are fun, as
long as you don’t mistake the result for maintainable code :slight_smile:

module Enumerable
def sum
#pick your favourite implementation
end
end

((numbers.inject([0,0]) {|x,y| [x.sum+y, x.pop+y]}.shift) % 11).zero?

martin

Hello –

dblack@candle.superlink.net wrote in message
news:Pine.LNX.4.44.0210142141510.7458-100000@candle.superlink.net

Well, for what it’s worth, here’s my 1.7-only version (it uses
#inject). I can’t help feeling there’s a way to do some kind of
double inject, and avoid using the ‘t’ accumulator… but anyway, here
is its current incarnation:

  t = 0
  ISBN_RE.match(self) &&
numbers.inject(0) {|x,y| t += x+y; x+y } &&
(t % 11) .zero?
end

ISBN_RE.match(self) &&
( (numbers.inject([0]){|x,y| x << (x[-1]+y)}.inject(0){|x,y| x+y}) % 11).zero?

martin

Was the intent here to shorten the code to beyond obfuscation threshholds?

I thought that was one thing so many on this group rail against perl for…

I don’t there exists some particular code-length threshhold, to drop
beneath which in the course of discussing a particular coding problem
signifies a general embrace of code obfuscation. Things can easily
become much too Simon-Says-like (“Ah! Caught you eliminating a
temporary variable – you’re out!”). It’s really more of an on-going
process.

In this case, actually, since #inject is on its way in >=1.7, I’m
inclined to give the code the benefit of the doubt and try to crank up
my own ability to grasp #inject usage.

David

···

On Thu, 17 Oct 2002, Mike Campbell wrote:


David Alan Black
home: dblack@candle.superlink.net
work: blackdav@shu.edu
Web: http://pirate.shu.edu/~blackdav

Yeah, I apologize for my tone there; I didn’t mean to come across as
nasty as it sounded.

It amuses me sometimes to see the accolades for how much easier ruby
is to read/write (or how much harder perl is!) because of the more
regular syntax. Then inevitably when someone asks how to do
something, the responses leapfrog each other in terseness well
beyond reasonable readability. =)

···

— Martin DeMello martindemello@yahoo.com wrote:

“Mike Campbell” michael_s_campbell@yahoo.com wrote in message
news:NFBBKBEMGLGCIPPFGHOLMEHOCLAA.michael_s_campbell@yahoo.com

ISBN_RE.match(self) &&
( (numbers.inject([0]){|x,y| x << (x[-1]+y)}.inject(0){|x,y|
x+y}) % 11).zero?

martin

Was the intent here to shorten the code to beyond obfuscation
threshholds?

I thought that was one thing so many on this group rail against
perl for…

Nope, just to use two injects rather than an accumulator (which was
what was asked). Which needed the first inject to collect into an
array (since the second inject needed to be passed one).

Besides which, golfing and playing variations on a theme are fun,
as
long as you don’t mistake the result for maintainable code :slight_smile:

=====

Use your computer to help find a cure for cancer: http://members.ud.com/projects/cancer/

Yahoo IM: michael_s_campbell


Do you Yahoo!?
Faith Hill - Exclusive Performances, Videos & More
http://faith.yahoo.com

Hello –

“Mike Campbell” michael_s_campbell@yahoo.com wrote in message
news:NFBBKBEMGLGCIPPFGHOLMEHOCLAA.michael_s_campbell@yahoo.com

ISBN_RE.match(self) &&
( (numbers.inject([0]){|x,y| x << (x[-1]+y)}.inject(0){|x,y|
x+y}) % 11).zero?

martin

Was the intent here to shorten the code to beyond obfuscation
threshholds?

I thought that was one thing so many on this group rail against
perl for…

Nope, just to use two injects rather than an accumulator (which was
what was asked). Which needed the first inject to collect into an
array (since the second inject needed to be passed one).

Besides which, golfing and playing variations on a theme are fun,
as
long as you don’t mistake the result for maintainable code :slight_smile:

Yeah, I apologize for my tone there; I didn’t mean to come across as
nasty as it sounded.

OK, then I apologize for the somewhat icy post that just crossed in
the mail with yours :slight_smile:

It amuses me sometimes to see the accolades for how much easier ruby
is to read/write (or how much harder perl is!) because of the more
regular syntax. Then inevitably when someone asks how to do
something, the responses leapfrog each other in terseness well
beyond reasonable readability. =)

I was actually thinking of turning that #inject one into a golf
challenge… :slight_smile: which I enjoy doing, for the mental exercise, and
the insights into Ruby that always seems to crop up, though the
results are generally not very pleasing code.

It seems to me that there are two distinct forms of code-shortening in
Ruby: first, the golf/possibly-obfuscated type, and second, the thing
where you work on a program in Ruby and as you work, it gets shorter
and clearer. I enjoy the first, but I love the second :slight_smile:

David

···

On Thu, 17 Oct 2002, Michael Campbell wrote:

— Martin DeMello martindemello@yahoo.com wrote:


David Alan Black
home: dblack@candle.superlink.net
work: blackdav@shu.edu
Web: http://pirate.shu.edu/~blackdav

Michael Campbell michael_s_campbell@yahoo.com wrote in message news:20021017140152.98861.qmail@web12404.mail.yahoo.com

Yeah, I apologize for my tone there; I didn’t mean to come across as
nasty as it sounded.

'Sok, though I must admit I was taken aback.

It amuses me sometimes to see the accolades for how much easier ruby
is to read/write (or how much harder perl is!) because of the more
regular syntax. Then inevitably when someone asks how to do
something, the responses leapfrog each other in terseness well
beyond reasonable readability. =)

Small problems like this are a great way to explore some of Ruby’s
features, though. And every now and then, as you whittle and hack away
at the code, you break through some sort of obfuscation barrier and
everything suddenly crystallises into a beautiful new form or
technique that is both terse and elegant, but which would never have
been found if you’d stuck to the clear but verbose way of doing it.

martin

It amuses me sometimes to see the accolades for how much easier
ruby
is to read/write (or how much harder perl is!) because of the
more
regular syntax. Then inevitably when someone asks how to do
something, the responses leapfrog each other in terseness well
beyond reasonable readability. =)

Small problems like this are a great way to explore some of Ruby’s
features, though. And every now and then, as you whittle and hack
away
at the code, you break through some sort of obfuscation barrier and
everything suddenly crystallises into a beautiful new form or
technique that is both terse and elegant, but which would never
have
been found if you’d stuck to the clear but verbose way of doing it.

Point well taken. It might be a good idea sometimes however for
those among you who really know the language well (I’m not one) to
point out that this is the “compressed” version of a possible
solution, done at least in part as a intellectual exercise for the
submitter.

My thought here is that if a genuine neophyte comes here asking for
help and gets this 1 liner checksummed line-noise answer, they walk
away thinking “this is easier to read?”, and may drift away. While
I’m sure the person who submitted the answer was at least partially
doing it for his OWN education in How Ruby Works and its capabilites
etc.

Just today I saw, for example, a question on how to split a file into
pieces based on a regex in the file. One of the answers was a very
good, but typical 1-liner that approached APL readability.
Maybe I’m just projecting a thin-skinned personality on the
questioner, too.

···

=====

Use your computer to help find a cure for cancer: http://members.ud.com/projects/cancer/

Yahoo IM: michael_s_campbell


Do you Yahoo!?
Faith Hill - Exclusive Performances, Videos & More
http://faith.yahoo.com