Comments (0)

By derek.illchuk, June 9, 2010 12:57 am

Derek: I flip two coins, hidden from your view, and call out, “one is heads”.  Can you tell me the odds that both coins match?

Dr. Logic: Yes!  1 in 3!  You see, the possibilities are as follows: HH, HT, TH, TT.  But, you said heads, so the last is excluded.  Hence, the possibilities are HH, HT, TH, one matching and two not.  Voila!

Derek: Uh, the odds are 1 in 2. <whisper whisper whisper to Dr. Logic>

Dr. Logic: Oh my!  You’re right!

So, what’s going on?

When I said, “one is heads”, Dr. Logic did not consider how I chose what to say.  And how’s that?  I simply looked at the left-most coin and called out its state, heads or tails, as in “one is heads” or “one is tails”.  Here’s how that plays out:

“One is heads” means HH, HT and yields a match 1 in 2

“One is tails” means TH, TT yields a match 1 in 2

So, when I asked, “Can you tell me the odds that both coins match?”, Dr. Logic should have said, “Not yet, I still have a question.”

Code test

I like to see probability in action, so I’ve coded this to run a million times.

<?php
 
$heads = 0;
$tails = 1;
$counts = array(
  'heads' => 0,
  'tails' => 0,
  'one_is_heads' => array(
    'match'    => 0,
    'no_match' => 0
  ),
  'one_is_tails' => array(
    'match'    => 0,
    'no_match' => 0
  )
);
for ( $i = 0; $i < 1000000; $i++ ) {
  $coin1 = ( rand(0, 1)%2 == 0 )? $heads : $tails;
  if ( $coin1 == $heads ) $counts['heads']++;
  else if ( $coin1 == $tails ) $counts['tails']++;
 
  $coin2 = ( rand(0, 1)%2 == 0 )? $heads : $tails;
  if ( $coin2 == $heads ) $counts['heads']++;
  else if ( $coin2 == $tails ) $counts['tails']++;
 
  $count_ix = ( $coin1 == $heads )? 'one_is_heads' : 'one_is_tails';
  $match_ix = ( $coin1 == $coin2 )? 'match' : 'no_match';
  $counts[$count_ix][$match_ix]++;
}
print_r($counts);

Result:
Everything is 1 in 2.

Array
(
    [heads] => 1000658
    [tails] => 999342
    [one_is_heads] => Array
        (
            [match] => 250567
            [no_match] => 249449
        )
 
    [one_is_tails] => Array
        (
            [match] => 249909
            [no_match] => 250075
        )
 
)

Comments (0)

By derek.illchuk, June 8, 2010 11:45 pm

You say, what good is wealth if you don’t spend it?  I say, what good is wealth if you do?

Comments (0)

By derek.illchuk, June 8, 2010 8:43 pm

“To avoid criticism do nothing, say nothing, be nothing.”

Comments (1)

By derek.illchuk, June 8, 2010 8:40 pm

The situation: you have some food to defrost, and you’d like to place it on a room-temperature surface, one of the following:

a. the table

b. the counter

c. the cutting board

d. a trivet

Which is best?

The answer: touch each surface with your hand for ten seconds. The one that feels the coldest is the winner. Yes, the coldest. Can you explain it?

Comments (0)

By derek.illchuk, June 8, 2010 8:39 pm

Here’s how to check your pulse… hands free!

1. Sit down on a firm chair.

2. Cross your legs.

3. Watch the tip of your big toe, it will bump with every pulse, just ever so slightly.

Comments (0)

By derek.illchuk, June 8, 2010 8:34 pm

Let’s look at another SPOJ problem today, called Square Brackets. The problem is how many proper bracket expressions can be made having a certain length. For added measure, you are given the placement of a few opening brackets (which is trivial to handle, as you’ll see).

For our example, we have an expression with length of six (so, three bracket pairs) and the third place is given as an opening bracket:

. . [ . . .

So, how many expressions can be made from that above?

My first thought is, uh oh, traverse all permutations, branch at each place in the expression, generate all options and bubble them up to the top. And yes, if we were required to print all proper expressions, this would be required. Fortunately, though, we’re asked only for the proper expression count, and this lets us take a nice shortcut.

What’s the trick? Well, before we start, we’re at bracket depth 0, and when we end, we better be at bracket depth 0 (otherwise, the expression can’t be considered proper). So, we simply keep track of how many branches are at a particular depth, and “branch” at each place by moving our counts around like tokens.

It’s easier to show you with a picture for our example:

Moves at each expression place

0: Before we start, we have a count of 1 at depth 0.

1: Open/close, can only open though (proper expression can’t have negative depth), count 1 at depth 1.

2: Open/close, branch, depth 1 goes to both depth 0 (i.e. close) and 2 (i.e. open).

3. Open only, depth 0 goes to depth 1, depth 2 goes to depth 3

4. Open/close, depth 1 branches to 0 and 2, depth 3 branches to 2 but 4 isn’t valid (since the expression can never close at that depth)

5. Open/close, depth 0 to depth 1, depth 2 to depth 1 and 3.

6. Open/close, depth 1 to depth 0, etc.

After the expression is processed, our answer is in the final place of the 0-depth column. Our answer for this example is three.

General Algorithm

  expression = array[1..num_pairs*2], each item is array[-1,1] // open/close
  each open expression item is array [1] // open only
 
  depth_counts = array[0..num_pairs]
  depth_counts[0] = 1 // to start
 
   for each expression item as depth_changes // loop: O(num_pairs)
 
    depth_counts_past = depth_counts
    depth_counts = array[0..num_pairs]
    for each depth_counts_past index as count // loop: O(num_pairs)
 
      for each depth_changes as depth_change // loop: O(2)
        next_count = count + depth_change
        if next_count >= 0 and next_count <= num_pairs
          depth_counts[next_count] += depth_counts_past[count]
        end if
      end for each
    end for each
  end for each
 
  result = depth_counts[0]

And there we are. What is inherently a permutation problem has been collapsed into complexity O(N²). Calculating the answer for 500 bracket pairs with ruby takes under one second on my system, and the result is a number having 300 places. Not bad!

Comments (0)

By derek.illchuk, June 8, 2010 8:19 pm

Reading through the New Turing OmniBus: 66 Excursions in Computer Science, I turned upon the classic Towers of Hanoi Puzzle. The recursive solution, as many know, is mind-blowing in it’s simplicity; the first time I saw it, I remember saying, “OK… and then what?”

function hanoi( n, from, dest, aux )
{
  if ( n == 1 )
    printline 'Move the plate from ' + from + ' to ' + dest
  else
    hanoi( n-1, from, aux, dest )
    hanoi( 1, from, dest, aux )
    hanoi( n-1, aux , dest, from )
  endif
end

The book goes on to present an iterative solution, as follows:

A. Always move the smallest disc first in a “clockwise” manner.

B. Then, move the smaller remaining disc onto the the other (in fact, that’s the only option).

C. Repeat A & B until finished.

Here’s a straightforward implementation (download).

#include <iostream>
#include <vector>
 
using namespace std;
typedef unsigned int uint32;
typedef int int32;
 
typedef uint32 Stack;
typedef uint32 Disc;
 
Stack next_stack( Stack curr_stack )
{
  return ( curr_stack + 1 ) % 3;
}
 
int32 main( void )
{
  cout << "Calculating tower of hanoi moves" << endl;
  cout << "Enter the number of discs: ";
  uint32 num_discs = 0; cin >> num_discs;
 
  /**
   * Set up the stacks, with discs loaded onto the first one.
   */
  vector<vector> stacks;
  for ( Stack stack_id = 0; stack_id < 3; stack_id++ ) {
    stacks.push_back(
      vector( 1, num_discs+1 ) // sentinel to avoid empty-stack logic
    );
  }
  Stack curr_stack = 0;
  for ( Disc disc = num_discs; disc > 0; disc-- ) {
    stacks[curr_stack].push_back( disc );
  }
 
  uint32 num_moves = 0;
  while ( true ) {
 
    /**
     * Smallest disc always moved one over.
     */
    Disc disc1 = stacks[curr_stack].back();
    stacks[curr_stack].pop_back();
    curr_stack = next_stack( curr_stack );
    stacks[curr_stack].push_back( disc1 );
    num_moves++;
 
    /**
     * Remaining move is forced.
     */
    Stack from_stack = next_stack( curr_stack );
    Stack to_stack = next_stack( from_stack );
    if ( stacks[from_stack].back() > stacks[to_stack].back() ) {
      Stack temp_stack = from_stack;
      from_stack = to_stack;
      to_stack = temp_stack;
    }
    Disc disc2 = stacks[from_stack].back();
    stacks[from_stack].pop_back();
    if ( stacks[from_stack].empty() ) { // we're done
      break;
    }
    stacks[to_stack].push_back( disc2 );
    num_moves++;
  }
 
  cout << "Total moves:" << num_moves << endl;
 
  return 0;
}

Is this particular iterative solution better than the recursive one? Aside from being a nice little exercise, no, it’s not that impressive. It takes longer to run than the recursive solution and requires more code. But, I think it’s easy to get how it works: “Move smallest clockwise then move what you can, repeat until we’re done.”.

There are iterative solutions out there that are much quicker, but they start to look like this:

void hanoi(void)
{
  int x, fr, to;
  unsigned int i, j;
 
  for (x=1; x < (1 << N); x++) {
    i=(x|x-1)+1; to=(i+i/3)&3;
    i=x&x-1; fr=(i+i/3)&3;
    for(i=x, j=1; ; i>>=1, j++) {
      if(i&1) break;
    }
  }
}

Comments (0)

By derek.illchuk, June 8, 2010 8:09 pm

As I looked into my next SPOJ problem, Cross-country, I realized this was clearly the Longest Common Subsequence problem I encountered during my university studies. The solution is well-documented, and I simply need to implement this function, given in Wikipedia as:

function  LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i-1] = Y[j-1]
                C[i,j] := C[i-1,j-1] + 1
            else:
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

This can be turned into C++ rather methodically, with something like the following:

typedef vector<uint32> Sequence;
typedef vector<Sequence> Sequences;
uint32 LCSLength( const Sequence& X, const Sequence& Y )
{
  /**
   * Load top-left edges with zeroes.
   *
   * e.g. X length 2, Y length 5
   * 000000
   * 0SSSSS
   * 0SSSSS
   */
  Sequences C( X.size()+1 );
  for ( uint32 Xix = 0; Xix < C.size(); Xix++ ) {
    C[Xix] = Sequence( Y.size()+1 );
  }
 
  /**
   * Generate the table, giving our result.
   */
  for ( uint32 Xix = 1; Xix < C.size(); Xix++ ) {
    for ( uint32 Yix = 1; Yix < C[Xix].size(); Yix++ ) {
      if ( X[Xix-1] == Y[Yix-1] ) {
        C[Xix][Yix] = C[Xix-1][Yix-1] + 1;
      }
      else {
        C[Xix][Yix] = max( C[Xix][Yix-1], C[Xix-1][Yix] );
      }
    }
  }
  return C[X.size()][Y.size()];
}

An easy optimization pops out: each iteration looks at only the current and previous row of C, yet we’re generating a whole m x n table. Reducing C to only two rows, and flip-flopping between them yields the following:

uint32 LCSLength( const Sequence& X, const Sequence& Y )
{
  /**
   *  Speed & memory optimization: only need the last two rows.
   */
  Sequences C( 2 );
  C[0] = Sequence( Y.size()+1 );
  C[1] = Sequence( Y.size()+1 );
  uint32 CprevIx = 0;
  uint32 CcurrIx = 1;
 
  /**
   * Generate the table, giving our result.
   */
  for ( uint32 Xix = 1; Xix <= X.size(); Xix++ ) {
    for ( uint32 Yix = 1; Yix <= Y.size(); Yix++ ) {
      if ( X[Xix-1] == Y[Yix-1] ) {
        C[CcurrIx][Yix] = C[CprevIx][Yix-1] + 1;
      }
      else {
        C[CcurrIx][Yix] = max( C[CcurrIx][Yix-1], C[CprevIx][Yix] );
      }
    }
    uint32 CtempIx = CprevIx;
    CprevIx = CcurrIx;
    CcurrIx = CtempIx;
  }
  return C[CprevIx][Y.size()];
}

This strategy reduces the algorithm run-time about 40% when testing with inputs generated by my ruby input generator. Yes, it gives the algorithm a good case of tunnel vision, focusing on finding only the length of the longest common subsequence while giving up the ability to actually determine what that subsequence is. But, it certainly does what it’s called to do as well as it can.

Comments (0)

By derek.illchuk, June 8, 2010 7:59 pm

Over at Imran on Tech, they presented a problem which they say stumps many comp sci. graduates (although, I have yet to be convinced).

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

Here’s a table-driven solution in ruby, turning if-else logic into pure data.

# fizzbuzz[is mod 3][is mod 5]
fizzbuzz = {}
fizzbuzz[true]  = {true  => 'FizzBuzz', false => 'Fizz'}
fizzbuzz[false] = {true  => 'Buzz'}
 
for i in 1..100
  fizzbuzz[false][false] = i
  puts fizzbuzz[i%3==0][i%5==0]
end

Comments (0)

By derek.illchuk, June 8, 2010 7:57 pm

I found an interesting little problem called ‘Aggressive Cows‘, and I really like the solution.

Imagine a row of stalls, stretching out far and wide. These stalls are spaced a little strangely, they’re certainly not an equal distance apart. Now, we have a certain number of cows to place, each going into their own stall. What’s the most spaced out these cows can be? Or, in more succinct terms, what’s the maximum minimum distance?

What’s the solution? It turns out, it’s best just to guess!

1. From what you know, determine the minimum and maximum possible guess — cast a wide net here.
2. Your actual guess is halfway between your min and max guess.
3. See if your actual guess works. This is a straightforward O(N) operation: walk through the stalls, placing cows as you can.
4. If it works (all cows were placed), your minimum guess becomes this actual guess.
5. If it doesn’t work, your maximum guess becomes one less than the actual guess.
6. Keep going until you converge onto the highest guess that has been proven to work. The search is binary and makes O(log N) guesses.
7. Total running time: O(N log N)

This solutions depends on two qualities of the problem:

1. The solution space is sorted and limited.
2. Each guess is relatively inexpensive to check.

With those in place, your tricky problem becomes no match for the tried-and-true binary search.