#1
  1. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,641
    Rep Power
    4247

    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 :)
    Last edited by Scorpions4ever; October 31st, 2007 at 12:59 AM.
    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

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Jan 2004
    Location
    Constant Limbo
    Posts
    989
    Rep Power
    363
    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
  4. #3
  5. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,641
    Rep Power
    4247
    I like it, especially your strategy of partitioning the array into two first.
    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

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  6. #4
  7. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,641
    Rep Power
    4247
    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.
    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

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo

IMN logo majestic logo threadwatch logo seochat tools logo