Permutations, Combinations & Probability (Part 2)

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