Ruby Puzzle of the Month - For Entertainment Only

Dev Shed Forums Sponsor:

October 31st, 2007, 12:56 AM

Scorpions4ever

Banned ;)

Dev Shed God 9th Plane (9000 - 9499 posts)

Join Date: Nov 2001

Location: Woodland Hills, Los Angeles County, California, USA

Posts: 9,382

Time spent in forums: 1 Month 4 Weeks 1 Day 20 h 34 m 6 sec
Reputation Power: 4080

Ruby Puzzle of the Month - For Entertainment Only

Hey guys,
I do post puzzles of the month in some of the other forums here and figure this one could use one too. I was recently playing around with ruby and RoR and came up with an interesting scenario, which I found a rather neat (and IMHO elegant) solution for. Here's a simplified situation:

You have the following array:

Code:

array = ['92256a', '10a', '4567b', '4567a', '1000a',
              'C1234', '245W5', '500a', '500', 'D418', 'C2456']

The goal is to sort the array according to the following rules:
1. If the elements both begin with digits, then sort by the digits first (i.e. numerically), followed by the letters afterwards
2. If one or both of the elements start with letters, then do an alphabetical sort.

Your result should look like this:

Code:

mb@deeppurple:~/ruby$ ./sort.rb 
Sorted Output
=========
10a
245W5
500
500a
1000b
4567a
4567b
92256a
C1234
C2456
D418

Post your solutions here.

HINT: I used a DSU (schwartzian) sort_by in my method. You could also use an Orcish manouever or some other method.

[edit]Will post my solution on Friday. [/edit]

Comments on this post

L7Sqr agrees: Finally! I love these little diversions

__________________
Up the Irons
What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
"Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
Down with Sharon Osbourne

Last edited by Scorpions4ever : October 31st, 2007 at 12:59 AM.

October 31st, 2007, 12:42 PM

L7Sqr

Contributing User

Join Date: Jan 2004

Location: Constant Limbo

Posts: 989

Time spent in forums: 2 Weeks 2 Days 22 h 45 m 6 sec
Reputation Power: 362

Solution:

Code:

#!/usr/bin/env ruby

a = [
    "92256a", "10a", "4567b", "4567a",
    "1000b", "C1234", "245W5", "500a",
    "500", "D418", "C2456"]

digit, letter = a.partition { |n| n =~ /^\d/ }
parts = digit.collect { |n| n =~ /(\d+)(\D+.*)/ ? [$1.to_i, $2] : [n.to_i] }
puts "Sorted Output\n" + "="*9
(parts.sort.collect { |n| n.join } + letter.sort).each { |n| puts n }

Explanation:
I take advantage here of the fact that

Code:

['A', 'a', '1'].sort
=>  ["1", "A", "a"]

By that I can just partition the items starting with characters to be sorted at the end since they will end there anyway. The rest is just Enumerable operations and a little regex.

Output:

Code:

Sorted Output
=========
10a
245W5
500
500a
1000b
4567a
4567b
92256a
C1234
C2456
D418

__________________
True happiness is not getting what you want, it's wanting what you've already got.

My Blog

October 31st, 2007, 02:07 PM

Scorpions4ever

Banned ;)

Join Date: Nov 2001

Location: Woodland Hills, Los Angeles County, California, USA

Posts: 9,382

Time spent in forums: 1 Month 4 Weeks 1 Day 20 h 34 m 6 sec
Reputation Power: 4080

I like it, especially your strategy of partitioning the array into two first.

November 4th, 2007, 10:20 PM

Scorpions4ever

Banned ;)

Join Date: Nov 2001

Location: Woodland Hills, Los Angeles County, California, USA

Posts: 9,382

Time spent in forums: 1 Month 4 Weeks 1 Day 20 h 34 m 6 sec
Reputation Power: 4080

Whoops. Forgot to post my solution on Friday. Anyway here's how I tackled it.

Code:

#!/usr/bin/env ruby

class IntStrType
  attr_reader :has_int
  attr_reader :int_part
  attr_reader :string_part
  attr_reader :string_item

  @@reg = Regexp.new('^(\d+)(\D*)', 'msxo')

  def initialize(item)
    @has_int = false
    @string_item = item
    if match = @@reg.match(item)
      @has_int     = true
      @int_part    = match[1].to_i
      @string_part = match[2]
    else
      @string_part = item
    end
  end

  def <=>(other)
    if (self.has_int == true) and (other.has_int == true)
      if self.int_part == other.int_part
        self.string_part <=> other.string_part
      else
        self.int_part <=> other.int_part
      end
   else
      self.string_item <=> other.string_item
    end
  end
end

array = ['92256a', '10a', '4567b', '4567a', '1000b',
         'C1234', '245W5', '500a', '500', 'D418', 'C2456']

array2 = array.sort_by { |x| IntStrType.new(x) }

puts "Sorted Output"
puts '=' * 15
array2.each { |i| puts i }

Basically, I declared a new class and overloaded the <=> operator for this class to do what I want. Since I actually have quite a few arrays that I sort using this method, I figured this might be the best option for reusable code, since my sort code is now reduced to:

Code:

array2 = array.sort_by { |x| IntStrType.new(x) }

sort_by() implements its own schwartzian transform internally, so I don't have to worry about doing it myself. The nice thing about using a class is that in the actual project that I needed code like this for, I had to change the sort requirement a little while later to make the order case-insensitive. All I needed to do was make the changes to the constructor of my class and voila, all the places that were sorting in this order automatically just worked!

Also note that I precompiled the regular expression as an object, so that I could (a) sling it around and (b) it didn't need to be re-evaluated each time. Note that @@reg is shared by all instances of class IntStrType because of @@ (i.e. each instance of the class doesn't get a separate copy of @@reg). You could use a good ol /regexp/, but I figure I like the object form better. Always thought $1, $2, $3 etc. are a bit inelegant, as they're global vars. That's just my personal opinion though.

Ruby Puzzle of the Month - For Entertainment Only

Developer Shed Advertisers and Affiliates