Hi Readers,

I have not updated even a single thing on my blog, since past so many days, I do not need to make you guess what I was up to. But have been trying to polish my skill set as much as possible.

The other day I came across this problem, from the Facebook Sample Puzzle (unfortunately they are using this puzzle also as a sample for interview questions), the worst part is. The solution is not available anywhere, nor does the sample submitter validates it.

Here is the Problem Statment:

There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.

• A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg.
• At anypoint of time, the decreasing radius property of all the pegs must be maintained.

Constraints:
1<= N<=8
3<= K<=5

Input Format:
N K
2nd line contains N integers.
Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration.
3rd line denotes the final configuration in a format similar to the initial configuration.
Output Format:
The first line contains M - The minimal number of moves required to complete the transformation. 
The following M lines describe a move, by a peg number to pick from and a peg number to place on.
If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one.

Sample Input #00:

<em> 2 3 1 1 2 2 </em>

Sample Output #00:

<em> 3 1 3 1 2 3 2 </em>

Sample Input #01:

<em>6 4 4 2 4 3 1 1 1 1 1 1 1 1 </em>

Sample Output #01:

<em>5 3 1 4 3 4 1 2 1 3 1 </em>

NOTE: You need to write the full code taking all inputs are from stdin and outputs to stdout 
If you are using "Java", the classname is "Solution"

The first thought for everyone should be Tower of Hanoi. But actually the problem is far more complex, as ToH is a recursive 101 program. What I found most complex in the statement is the line "You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one" which somewhat means that it won't offer you problems with results more than 6 (should be less than 7). Because lets say the case is as follows:

7 4
2 2 4 3 1 1 4
3 3 3 3 2 2 1

How come can it be in less than 7 moves?.. Please correct me if i am missing something...

My Take:

I just sat up and wrote the code, debugged it like 150 times to solve at least some test cases (Moves ~ 6) . But the case mentioned above is still not solvable by the code.

<?php
$ip     = fopen('php://stdin', "r");
$op     = fopen('php://stdout',"w");

function search_peg($disk, $pegs){
  foreach($pegs as $key1=>$val1){
    foreach($pegs[$key1] as $key2=>$val2){
      if($val2 == $disk){
        return $key1;
      }
    }
  }
}

function is_on_top($num, $peg){
  $comp = count($peg)-1;
  foreach($peg as $key=>$val){
    if($val == $num &amp;&amp; $key == $comp){
      return true;
    }
  }
  return false;
}

function what_is_on_top($peg){
  return $peg[count($peg)-1];
}

function best_peg($not, $peg, $tobe){
  foreach($peg as $key=>$val){
    if($key !== $not){
      $temp = count($val);
      if($temp ==0){
        return $key;
      }
    }
  }
  foreach($peg as $key=>$val){
    if($key !== $not){
      $temp = $val[count($val)-1];
      if($temp < $tobe){
        if(empty($ret) || $temp<$ret){
          $ret = $temp;
        }
      }
    }
  }
  return $ret;
}

$init = explode(" ", trim(fgets($ip)));
$n = $init[0];
$k = $init[1];
$vals = explode(" ", trim(fgets($ip)));
$i = $n;
while($i>0){
  if(!is_array($peg[$vals[$i-1]])){
    $peg[$vals[$i-1]] = array();
  }
  array_push($peg[$vals[$i-1]], $i);
  $i--;
}
//protective
for($i=1;$i<=$k;$i++){
  if(!is_array($peg[$i])){
    $peg[$i] = array();
  }

}
//print_r($peg);
$config = explode(" ", trim(fgets($ip)));
$i = $n;
while($i>0){
  if(!is_array($conf[$config[$i-1]])){
    $conf[$config[$i-1]] = array();
  }
  array_push($conf[$config[$i-1]], $i);
  $i--;
}
//print_r($conf);

for($i=$n;$i>0;$i--){
  $init_peg = search_peg($i, $peg);
  $fina_peg = search_peg($i, $conf);
  if($init_peg !== $fina_peg){
    //echo $i." => ". what_is_on_top($peg[$fina_peg]). "\n";
    while(what_is_on_top($peg[$fina_peg]) < $i &amp;&amp; !empty($peg[$fina_peg])){
      $best = best_peg($fina_peg, $peg, $i);
      if(!is_array($peg[$best])){
        $peg[$best] = array();
      }
      array_push($peg[$best], array_pop($peg[$fina_peg]));
      $movem[] = $fina_peg.' '.$best;
    }
    if(is_on_top($i, $peg[$init_peg])){
      array_push($peg[$fina_peg], array_pop($peg[$init_peg]));
      $movem[] = $init_peg.' '.$fina_peg;
    }else{
      while(!is_on_top($i, $peg[$init_peg])){
        $best = best_peg($fina_peg, $peg, $i);
        if(!is_array($peg[$best])){
          $peg[$best] = array();
        }
        array_push($peg[$best], array_pop($peg[$init_peg]));
        $movem[] = $init_peg.' '.$best;
      }
      array_push($peg[$fina_peg], array_pop($peg[$init_peg]));
      $movem[] = $init_peg.' '.$fina_peg;
    }
  }
}
//print_r($peg);
echo count($movem)."\n";
foreach ($movem as $moves){
  echo $moves ."\n";
}
?>

Again I might be wrong, my code is messy, my algo is just not clean, whosoever understands this better, please guide me and correct me. Here is the working version on IdeOne: http://ideone.com/Le8pw

Cheers!