FLPR

CircularArray Saves the Day - RSpec is Fun

Posted by Pat Sat, 20 May 2006 06:46:52 GMT

My Problem

I’ve been working on an application that generates random poker scenarios. For those of you familiar with poker, you’ll know there are multiple positions (small or big blind, cutoff, button, etc). For the most part, you only care about your own position, and what every other player’s position is in relation to you. In programming terms, if I’ve got an array [“foo”, “bar”, “foobar”, “baz”], I don’t care that index(“baz”) is 3, I care that it’s index(“bar”)+2.

The positions on a poker table are circular – they don’t just start and end. Let’s assume that my player is named bar in the array above. For whatever reason, I want to get the 5th player after “bar”.

irb(main):001:0> players = %w(foo bar foobar baz)
=> ["foo", "bar", "foobar", "baz"]
irb(main):002:0> players[players.index("bar")+5]
=> nil

That’s not very helpful. I don’t want my array to be linear – I’m assuming that any index I ask for is valid, so we should just loop around to the beginning if I ask for an index that’s greater than the size of the array.

My Solution

Computer science gurus might have said from the get go that I should use a circular array or linked list. I did a quick Google for “ruby circular array” and found nothing, so of course I decided to write one. The implementation is ridiculously simple:

class CircularArray < Array
  def [](i)
    index = i
    if i >= size || i < -1
      index = i % size
    end
    super(index)
  end
end

All I’m doing is extending the Array class and overriding the [] method. If the index passed in is greater than the # of elements in the array, it just figures out what index it should be and sets it. So now I can do:

irb(main):003:0> require "circular_array"
=> true
irb(main):004:0> players = CircularArray.new(players)
=> ["foo", "bar", "foobar", "baz"]
irb(main):005:0> players[players.index("bar")+5]
=> "foobar"

Hallelujah

In my hand generator, I have a section that looked like:

opps = s.opponents.sort.reverse
s.button = opps.first.seat
opps.each do |o|
  if o.seat < s.hero.seat
    s.button = o.seat
    break
  end
end

I used that to figure out where the button should be if I want my player to be in the small blind. I wanted to enable the user to give himself any position on the table…but after looking at that code, I thought “fuck this” and just didn’t do it for a while. Then the idea of the circular array hit me, and now my code looks like

case hero_position
when Button then offset = 0
when SB then offset = -1
when UTG then offset = -3
when UTG1 then offset = -4
when MP1 then offset = -5
when MP2 then offset = -6
when MP3 then offset = -7
when CO then offset = 1
end

players = CircularArray.new(s.players)
s.button = players[s.players.index(s.hero) + offset].seat

First I had 8 lines of error-prone ugliness, and that only dealt with one position! My circular array brought it down to a case statement and two lines of logic. Ship it.

An Excuse for RSpec

I heard about RSpec, checked it out, and it looked pretty cool, so I figured I’d write this thing up doing BDD using RSpec. I know I showed the code already, but I promise I wrote all the specs first. What’s really slick is running spec on it gives me

A new circular array
- should be empty
- should not be empty after accepting elements

A circular array with one element
- should treat the element at [1] the same as [0]
- should treat [-2] the same as [0]

A circular array with four elements
- should treat [4] the same as [0]
- should treat [5] the same as [1]
- should treat [9] the same as [1]
- should treat [-5] the same as [3]
- should treat [-9] the same as [3]

Gorgeous.

Get It

I already showed the code for the CircularArray class. If you want to see the spec file that I used to write it, you can get it at http://svn.flpr.org/public/circular_array/.