fork(8) download
copy 
  1. <?php
  2. /*********************
  3. 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.
  4.  
  5. A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg.
  6. At anypoint of time, the decreasing radius property of all the pegs must be maintained.
  7.  
  8. Constraints:
  9. 1<= N<=8
  10. 3<= K<=5
  11.  
  12.  
  13. Input Format:
  14. N K
  15. 2nd line contains N integers.
  16. 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.
  17. 3rd line denotes the final configuration in a format similar to the initial configuration.
  18.  
  19.  
  20. Output Format:
  21. The first line contains M - The minimal number of moves required to complete the transformation. 
  22. The following M lines describe a move, by a peg number to pick from and a peg number to place on.
  23. 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.
  24.  
  25. Sample Input #00:
  26.  
  27.  
  28. 2 3
  29. 1 1
  30. 2 2
  31. Sample Output #00:
  32.  
  33.  
  34. 3
  35. 1 3
  36. 1 2
  37. 3 2
  38.  
  39.  
  40. Sample Input #01:
  41.  
  42. 6 4
  43. 4 2 4 3 1 1
  44. 1 1 1 1 1 1
  45. Sample Output #01:
  46.  
  47. 5
  48. 3 1
  49. 4 3
  50. 4 1
  51. 2 1
  52. 3 1
  53. NOTE: You need to write the full code taking all inputs are from stdin and outputs to stdout 
  54. If you are using "Java", the classname is "Solution"
  55.  
  56.  
  57. *********************/
  58.  
  59.  
  60.  
  61.  
  62.  
  63. $ip     = fopen('php://stdin', "r");
  64. $op     = fopen('php://stdout',"w");
  65.  
  66. function search_peg($disk, $pegs){
  67. 	foreach($pegs as $key1=>$val1){
  68. 		foreach($pegs[$key1] as $key2=>$val2){
  69. 			if($val2 == $disk){
  70. 				return $key1;
  71. 			}
  72. 		}
  73. 	}
  74. }
  75.  
  76. function is_on_top($num, $peg){
  77. 	$comp = count($peg)-1;
  78. 	foreach($peg as $key=>$val){
  79. 		if($val == $num && $key == $comp){
  80. 			return true;
  81. 		}
  82. 	}
  83. 	return false;
  84. }
  85.  
  86. function what_is_on_top($peg){
  87. 	return $peg[count($peg)-1];
  88. }
  89.  
  90. function best_peg($not, $peg, $tobe){
  91. 	foreach($peg as $key=>$val){
  92. 		if($key !== $not){
  93. 			$temp = count($val);
  94. 			if($temp ==0){
  95. 				return $key;
  96. 			}
  97. 		}
  98. 	}
  99. 	foreach($peg as $key=>$val){
  100. 		if($key !== $not){
  101. 			$temp = $val[count($val)-1];
  102. 			if($temp < $tobe){
  103. 				if(empty($ret) || $temp<$ret){
  104. 					$ret = $temp;
  105. 				}
  106. 			}
  107. 		}
  108. 	}
  109. 	return $ret;
  110. }
  111.  
  112. $init = explode(" ", trim(fgets($ip)));
  113. $n = $init[0];
  114. $k = $init[1];
  115. $vals = explode(" ", trim(fgets($ip)));
  116. $i = $n;
  117. while($i>0){
  118. 	if(!is_array($peg[$vals[$i-1]])){
  119. 		$peg[$vals[$i-1]] = array();
  120. 	}
  121. 	array_push($peg[$vals[$i-1]], $i);
  122. 	$i--;
  123. }
  124. //protective
  125. for($i=1;$i<=$k;$i++){
  126. 	if(!is_array($peg[$i])){
  127. 		$peg[$i] = array();
  128. 	}
  129.  
  130. }
  131. //print_r($peg);
  132. $config = explode(" ", trim(fgets($ip)));
  133. $i = $n;
  134. while($i>0){
  135. 	if(!is_array($conf[$config[$i-1]])){
  136. 		$conf[$config[$i-1]] = array();
  137. 	}
  138. 	array_push($conf[$config[$i-1]], $i);
  139. 	$i--;
  140. }
  141. //print_r($conf);
  142.  
  143. for($i=$n;$i>0;$i--){
  144. 	$init_peg = search_peg($i, $peg);
  145. 	$fina_peg = search_peg($i, $conf);
  146. 	if($init_peg !== $fina_peg){
  147. 		//echo $i." => ". what_is_on_top($peg[$fina_peg]). "\n";
  148. 		while(what_is_on_top($peg[$fina_peg]) < $i && !empty($peg[$fina_peg])){
  149. 			$best = best_peg($fina_peg, $peg, $i);
  150. 			if(!is_array($peg[$best])){
  151. 				$peg[$best] = array();
  152. 			}
  153. 			array_push($peg[$best], array_pop($peg[$fina_peg]));
  154. 			$movem[] = $fina_peg.' '.$best;
  155. 		}
  156. 		if(is_on_top($i, $peg[$init_peg])){
  157. 			array_push($peg[$fina_peg], array_pop($peg[$init_peg]));
  158. 			$movem[] = $init_peg.' '.$fina_peg;
  159. 		}else{
  160. 			while(!is_on_top($i, $peg[$init_peg])){
  161. 				$best = best_peg($fina_peg, $peg, $i);
  162. 				if(!is_array($peg[$best])){
  163. 					$peg[$best] = array();
  164. 				}
  165. 				array_push($peg[$best], array_pop($peg[$init_peg]));
  166. 				$movem[] = $init_peg.' '.$best;
  167. 			}
  168. 			array_push($peg[$fina_peg], array_pop($peg[$init_peg]));
  169. 			$movem[] = $init_peg.' '.$fina_peg;
  170. 		}
  171. 	}
  172. }
  173. //print_r($peg);
  174. echo count($movem)."\n";
  175. foreach ($movem as $moves){
  176. 	echo $moves ."\n";
  177. }
  178. ?>
Success #stdin #stdout 0.02s 13064KB
comments (?)
stdin
copy 
6 4
4 2 4 3 1 1
2 2 2 1 1 1
stdout
copy 
6
3 1
2 3
4 1
4 2
3 2
1 2
https://ideone.com/Le8pw
language:
PHP (php 7.3.5)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!