Permutations, Combinations & Probability (Part 2)

Posted by James Mead Fri, 02 Jan 2009 11:15:58 GMT

Monte Carlo Method

I seem to be having a bit of a probability-fest at the moment. I enjoyed reading Jeff Atwood’s probability puzzle earlier this week: The Problem of the Unfinished Game and the explanation: Finishing The Game. And I’m in the middle of reading Fooled by Randomness: The Hidden Role of Chance in Life and in the Markets, a book that Chris Roos recommended to me a while back – I’m really enjoying it. The author is a big fan of the Monte Carlo method which is effectively how I solved the probability problem in my previous post

So when Nathan Zook emailed me to suggest that I might have got my previous calculation wrong, I was interested enough to do what I should have done originally i.e. write some tests to check my solution. I extracted the critical bit of logic from both my solution and from Nathan’s solution and wrote tests against this method.

Nathan’s Solution

def matches(index, base)
  counts = [0] * base
  4.times do
    counts[index % base] += 1
    index /= base
  end
  count = 0
  4.times do
    count += counts[index % base]
    index /= base
  end
  count
end

James’ Solution

def matches(index, base)
  places = 4
  permutation = "%0#{places * 2}d" % index.to_s(base)
  original = (0...places).map { |i| permutation[i].chr }
  guess = (places...(places * 2)).map { |i| permutation[i].chr }
  matches = 0 
  guess.each do |g| 
    (0...places).each do |i| 
      if g == original[i]
        original[i] = nil 
        matches += 1
        break
      end 
    end 
  end 
  matches
end

Failing Tests

You can see the full set of tests here, but the critical ones turn out to be the ones below. It appears that Nathan’s solution doesn’t work when there are duplicates. But I’m glad he pushed me into writing these tests – now I have more confidence in the answer I calculated previously.

def test_should_have_two_duplicate_matches_in_same_positiion
  assert_equal 2, matches(11341178, 10)
end

def test_should_have_two_duplicate_matches_in_different_positiion
  assert_equal 2, matches(11345611, 10)
end

def test_should_have_three_duplicate_matches_in_same_positiion
  assert_equal 3, matches(11141118, 10)
end

def test_should_have_three_duplicate_matches_in_different_positiion
  assert_equal 3, matches(11145111, 10)
end

def test_should_have_four_duplicate_matches
  assert_equal 4, matches(11111111, 10)
end

def test_should_have_one_match_when_digit_appears_twice_on_lhs_but_once_on_rhs
  assert_equal 1, matches(11345178, 10)
end

def test_should_have_one_match_when_digit_appears_once_on_lhs_but_twice_on_rhs
  assert_equal 1, matches(12345118, 10)
end

def test_should_have_two_matches_when_digit_appears_three_times_on_lhs_but_twice_on_rhs
  assert_equal 2, matches(11145118, 10)
end

def test_should_have_two_matches_when_digit_appears_twice_on_lhs_but_three_times_on_rhs
  assert_equal 2, matches(12315111, 10)
end

def test_should_have_three_matches_when_digit_appears_four_times_on_lhs_but_three_times_on_rhs
  assert_equal 3, matches(11115111, 10)
end

def test_should_have_three_matches_when_digit_appears_three_times_on_lhs_but_four_times_on_rhs
  assert_equal 3, matches(11141111, 10)
end

TextMate Bug

While running these tests, I noticed a bug in TextMate’s Ruby syntax highlighting, which I’ve now reported

textmate-ruby-syntax-highlighting-bug

Tags , , ,  | 2 comments

Comments

  1. Nathan Zook said 17 days later:

    I should have checked your post sooner. I did not intend to suggest that you got it wrong. As I said in my email, “we count differently”.

    Specifically, your sixth test drives home the point: 11345178. If you are counting master-mind style, there is one match. My intuition is that position 1 matches position 6 and position 2 matches position 6, so there are two matches. In the limit, I count sixteen matches for the sequence 11111111.

    The real question is what exactly you want counted. The nice thing about test cases is that they clear these things up.

  2. Floehopper said 27 days later:

    Nathan: Aha. Now I see what you mean. Thanks anyway for pushing me into writing the tests – they really helped clarify things for me :-)

RSS feed for this post

Comments are disabled