Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

#1
October 31st, 2007, 12:56 AM
 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
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```

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

Will post my solution on Friday. [/edit]
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.

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

#3
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.

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

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

 Viewing: Dev Shed Forums > Programming Languages > Ruby Programming > Ruby Puzzle of the Month - For Entertainment Only