Facebook Interview Question
Country: United States
Interview Type: Written Test
This is taken from Facebook's demo puzzles.
You can see it on Facebook. This is not an interview question.
This is a coding puzzle intended to be solved at home.
Why -1 to this, when I read this it looks like Tower of Hanoi. If not please provide the answer why it is not?
i solved it using array of stacks and traversing the stacks with ID-DFS so give it a try guys i think it works .. i passed all the test cases 2 + 4 hidden on interviewstreet
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace FB_test1
{
class Program
{
int N_numberOfDiscs = 0, K_numberOfPegs = 0;
int inputLines = 2;
int[][] data;
Stack<int>[] initStack;
Stack<int>[] FinalStack;
int reclimit = 7;
List<string> res = new List<string>();
void readIn(char splitter)
{
String[] firstLineArgs = Console.ReadLine().Split(splitter);
N_numberOfDiscs = int.Parse(firstLineArgs[0]);
K_numberOfPegs = int.Parse(firstLineArgs[1]);
data = new int[inputLines][];
for (int i = 0; i < inputLines; i++)
{
String[] line = Console.ReadLine().Split(splitter);
data[i] = parseStringArr(line);
}
initStack = new Stack<int>[K_numberOfPegs];
stackBuilder(ref initStack, data[0]);
FinalStack = new Stack<int>[K_numberOfPegs];
stackBuilder(ref FinalStack, data[1]);
}
void stackBuilder(ref Stack<int>[] stack, int[] numbers)
{
for (int i = 0; i < stack.Length; i++)
{
stack[i] = new Stack<int>();
}
for (int i = numbers.Length - 1; i >= 0; i--)
{
int col = numbers[i];
stack[col - 1].Push(i + 1);
}
}
int[] parseStringArr(string[] arr)
{
int[] ret = new int[arr.Length];
for (int i = 0; i < arr.Length; i++)
{
try
{
ret[i] = int.Parse(arr[i]);
}
catch (Exception e)
{
int x = 0;
}
}
return ret;
}
bool jumping(string moving, int from, int to)
{
if (string.IsNullOrEmpty(moving))
return false;
char[] c = { '\n' };
var numbers = moving.Split(c, StringSplitOptions.RemoveEmptyEntries).Last().Split(' ').Select(x => int.Parse(x));
if (numbers.ElementAt(0) == to && numbers.ElementAt(1) == from)
return true;
return false;
//return (from == oldTo && to == oldFrom && to != 0 )? true : false;
}
void move(Stack<int>[] init, Stack<int>[] final, int from, int to, string moving, int max, List<int[]> validmoves)
{
if (reclimit <= max)
{
return;
}
if (needsWork(init, final))
{
for (int i = 0; i < validmoves.Count; i++)
{
Stack<int>[] temp = copyStacks(init);
validmoves = validMoves(temp);
if (i < validmoves.Count)
{
from = validmoves.ElementAt(i)[0];
to = validmoves.ElementAt(i)[1];
//if (jumping(moving, from, to))
// continue;
moveDisc(temp, from, to);
string str = moving + from + " " + to + "\n";
//Console.WriteLine(str);
move(temp, final, from, to, str, max + 1, validmoves);
}
}
}
else
{
res.Add(moving);
return;
}
}
Stack<int>[] copyStacks(Stack<int>[] init)
{
Stack<int>[] ret = new Stack<int>[init.Length];
int i = 0;
foreach (Stack<int> s in init)
{
ret[i++] = new Stack<int>(s.Reverse());
}
return ret;
}
void moveDisc(Stack<int>[] init, int from, int to)
{
int popped = init[from - 1].Pop();
init[to - 1].Push(popped);
}
bool needsWork(Stack<int>[] init, Stack<int>[] final)
{
for (int i = 0; i < init.Length; i++)
{
if (init[i].Count != final[i].Count)
return true;
for (int j = 0; j < init[i].Count; j++)
{
if (init[i].ElementAt(j) != final[i].ElementAt(j))
return true;
}
}
return false;
}
List<int[]> validMoves(Stack<int>[] stacks)
{
List<int[]>[] ret = new List<int[]>[stacks.Length];
for (int i = 0; i < stacks.Length; i++)
{
if (stacks[i].Count() != 0)
{
int toMove = stacks[i].Peek();
ret[i] = new List<int[]>();
for (int j = 0; j < stacks.Length; j++)
{
if (j != i)
{
int[] subarr = { i + 1, j + 1 };
if (stacks[j].Count != 0)
{
int targetPeek = stacks[j].Peek();
if (targetPeek - 1 == toMove && FinalStack[j].Count != 0 && FinalStack[j].Peek() <= toMove)
{
ret[i].Clear();
ret[i].Add(subarr);
break;
}
if (toMove < targetPeek)
{
ret[i].Add(subarr);
}
}
else
{
ret[i].Add(subarr);
}
}
}
}
}
List<int[]> append = new List<int[]>();
foreach (List<int[]> l in ret)
{
if (l != null)
append.AddRange(l);
}
return append;
}
void move()
{
int i = 1;
while (res.Count==0)
{
reclimit = i++;
move(initStack, FinalStack, 0, 0, "", 0, validMoves(initStack));
}
}
void writeRes(List<string> sorted)
{
string[] x = sorted.ElementAt(0).Split('\n');
Console.WriteLine(x.Length - 1);
foreach (string s in x)
{
Console.WriteLine(s);
}
}
static void Main(string[] args)
{
Program p = new Program();
p.readIn(' ');
p.move();
p.res = p.res.OrderBy((x) => x.Length).ToList();
p.writeRes(p.res);
}
}
}
I was able to write a program with a recursive "move" method which moves disks starting from the largest to the smallest to its corresponding target keg. But in that method, several other disks need to be moved as well. How can we tell which move will result in minimum moves? and how to not run into an infinite loop of moves?
Well here is the solution...plz explain this solution in the link given below :
" blog.csdn.net/maqingli20/article/details/7361057 "
This problem can be seen as a search problem -- searching for the optimal solution (minimal number of steps leading to the final state). We can search all possible states using either depth first search (recursion) or breadth first search. The problem with the dfs is that it will take a significant amount of time because it will first find the worst possible solution (the furthest from the initial state) and then go back to the optimal, so we pretty much have to find all possible solutions, using recursion, and return the one that is completed in the minimum number of steps.
With the bfs approach, however, we can return the first solution we find, because we know that every other solution will involve at least one additional step, hence it is not the optimal solution. This approach is much faster.
Here is the solution. I solved it using backtracking and a modification of breath first search.
import java.util.*;
public class Solution{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
StringBuffer start = new StringBuffer();
for(int i=0;i<N;i++)start.append(sc.next()).append(" ");
StringBuffer end = new StringBuffer();
for(int i=0;i<N;i++)end.append(sc.next()).append(" ");
String prev = null;
LinkedList<String> result = movesTrack(start.toString().trim(), end.toString().trim(), N, K);
System.out.println(result.size()-1);
for(String s : result)
{
if(prev!=null)System.out.println(Solution.deltaMove(s, prev));
prev=s;
}
}
public static LinkedList<String> movesTrack(String start, String end, int N, int K)
{
Queue<String> actionQ = new LinkedList<String>();
Set<String> visitedSet = new HashSet<String>();
Map<String, String> backtrackMap = new TreeMap<String, String>();
actionQ.add(start);
visitedSet.add(start);
while(!actionQ.isEmpty())
{
String source = actionQ.poll();
for(String next : Solution.getNextMoves(source, N, K))
{
if(next.equals(end))
{
LinkedList<String> list = new LinkedList<String>();
list.add(next);
while(source!=null)
{
list.add(0,source);
source = backtrackMap.get(source);
}
return list;
}
if(!visitedSet.contains(next))
{
actionQ.add(next);
visitedSet.add(next);
backtrackMap.put(next, source);
}
}
}
return null;
}
public static Set<String> getNextMoves(String pos, int N, int K)
{
Set<String> moves = new TreeSet<String>();
String[] discPositions = pos.split(" ");
for(int disc=1; disc<=N; disc++)
{
int peg = Integer.parseInt(discPositions[disc-1]);
if(Solution.topOfPeg(discPositions, peg) == disc)
{
for(int targetPeg=1; targetPeg<=K; targetPeg++)
{
int targetTop = Solution.topOfPeg(discPositions, targetPeg);
if(targetPeg!=peg & (targetTop>disc || targetTop==0))
{
String state = pos;
moves.add(state.replaceFirst(discPositions[disc-1], String.valueOf(targetPeg)));
}
}
}
}
return moves;
}
public static int topOfPeg(String[] discPositions, int peg)
{
for(int i=1; i<=discPositions.length; i++)
if(Integer.parseInt(discPositions[i-1]) == peg)
return i;
return 0;
}
public static String deltaMove(String curr, String prev)
{
String[] start = prev.split(" ");
String[] end = curr.split(" ");
for(int i=1;i<=start.length;i++)
if(!start[i-1].equals(end[i-1]))
return (start[i-1]+" "+end[i-1]);
return null;
}
}
Try this input
7 4
2 2 4 3 1 1 4
3 3 3 3 2 2 1
Your code returns 8 moves. I don't think its correct.
Also, in your approach, which seems correct, how do you avoid getting in to infinite loop?
I think the code is correct, but facebook judge will not give questions which involve more than 6 movements. Because it clearly states that... The thing is, I was unable to figure out the solution to your test case manually, can you tell me the solution set involving "less than" 7 moves?
Cheers!
even I am stuck, especially with the test case like
7 4
2 2 4 3 1 1 4
3 3 3 3 2 2 1
you can check out my code in PHP nishantarora.in/?p=846 , but still I am unable to solve for cases like the one mentioned above. I might be wrong! Please keep me updated
<?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 && $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);
/*
foreach($conf as $key=>$val){
foreach($conf[$key] as $key1=>$val1){
if($conf[$key][$key1] !== $peg[$key][$key1]){
echo $conf[$key][$key1] ." is on not on the right position\n";
}else{
echo $conf[$key][$key1] ." is on the right position\n";
}
}
}
*/
// fwrite($op, sprintf("%d\n", $cand));
//echo search_peg(0, $peg);
//echo search_peg(0, $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 && !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";
}
?>
basically this is a depth-first-search over all possible moves.
its getting the start and end configuration and then initializes the pegs in the way that each peg holds its smallest disc number (respectively the top-most disc).
then it iterates over all combinations of 2 pegs.
if it is possible to move the disc from peg i to j it does so, and checks, if this is already the desired configuration.
if so then set the minDepth(which i would call maxDepth because its the maximal depth until where a better/equal solution can be found), to the current depth, so any calls with higher depths are now simply returned, because we already found a better solution. additionally memorize the steps done to this point.
if we dont have the desired configuration, we "start" with the current configuration the whole thing again.
on return of the recursion, it reconstructs the old configuration(before the last iteration) and iterates again(tries another move at this depth).
rest is output.
well explaining code literally is really hard for me, but i hope you could get at least an idea how it actually works...
This code in ruby is working fine...
require 'set'
class Node
attr_reader :situation, :moves
def initialize(situation, moves = [])
@situation = situation
@moves = moves
end
def ==(other)
situation == other.situation
end
end
def read_line
gets.strip.split(' ').map(&:to_i)
end
n, k = read_line
current_node = Node.new(read_line)
final_node = Node.new(read_line)
queue = Array.new
visited_nodes = Set.new
loop do
available_pegs = (1..k).to_a
current_node.situation.each_with_index do |orig_peg, index|
if available_pegs.include? orig_peg
available_pegs.delete orig_peg
break if available_pegs.empty?
available_pegs.each do |dest_peg|
new_situation = current_node.situation.dup
new_situation[index] = dest_peg
new_moves = current_node.moves.dup
new_moves << "#{ orig_peg } #{ dest_peg }"
new_node = Node.new(new_situation, new_moves)
if new_node == final_node
puts new_node.moves.count, new_node.moves
exit
end
queue << new_node unless visited_nodes.include?(new_node) || queue.include?(new_node)
end
end
end
visited_nodes.add current_node
current_node = queue.shift
end
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.Vector;
/**
* @author thiagogenez
*
* Facebook hiring sample test
*
* 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:
*
* 2 3
* 1 1
* 2 2
*
* Sample Output #00:
*
* 3
* 1 3
* 1 2
* 3 2
*
* Sample Input #01:
*
* 6 4
* 4 2 4 3 1 1
* 1 1 1 1 1 1
*
* Sample Output #01:
*
* 5
* 3 1
* 4 3
* 4 1
* 2 1
* 3 1
*
* 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"
*
*/
public class Solution {
public Solution() {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));
String input[] = br.readLine().split(" ");
@SuppressWarnings("unused")
int n = Integer.parseInt(input[0]);
int k = Integer.parseInt(input[1]);
String begin_config = br.readLine();
String end_config = br.readLine();
Vector<String> moves = breadthFirstSearch(k, begin_config,
end_config);
System.out.println(moves.size());
for (String move : moves) {
System.out.println(move);
}
} catch (Exception e) {
System.err.println("Error:" + e.getMessage());
e.printStackTrace();
}
}
private Vector<String> breadthFirstSearch(int k, String begin_config,
String end_config) {
Node node = new Node(null, null, begin_config);
Queue<Solution.Node> queue = new LinkedList<Solution.Node>();
queue.add(node);
while (!queue.isEmpty()) {
node = queue.remove();
if (!node.isVisited()) {
node.setVisited(true);
if (node.getConfig().equals(end_config))
break;
ArrayList<Node> nextsNodes = node.getNexts(k);
queue.addAll(nextsNodes);
}
}
queue.clear();
queue = null;
Vector<String> moves = new Vector<String>();
while (node.getFather() != null) {
moves.add(node.getLast_move());
node = node.getFather();
}
Collections.reverse(moves);
return moves;
}
public static void main(String args[]) {
new Solution();
}
private class Node {
private Node father;
private String last_move;
private String config;
private boolean visited = false;
public Node(Node father, String last_move, String config) {
super();
this.father = father;
this.last_move = last_move;
this.config = config;
}
public ArrayList<Node> getNexts(int k) {
ArrayList<Node> nexts = new ArrayList<Solution.Node>();
Vector<Stack<Integer>> pegs = getPegs(k);
for (int from = 0; from < k; from++) {
for (int to = 0; to < k; to++) {
if (from != to) {
if (!pegs.get(from).isEmpty()
&& (pegs.get(to).isEmpty() || pegs.get(from)
.peek() < pegs.get(to).peek())) {
String s[] = this.config.split(" ");
s[pegs.get(from).peek() - 1] = String
.valueOf(to + 1);
String config = "";
for (int i = 0; i < s.length; i++) {
config += s[i] + " ";
}
config = config.trim();
String last_move = String.valueOf(from + 1) + " "
+ String.valueOf(to + 1);
nexts.add(new Node(this, last_move, config));
}
}
}
}
return nexts;
}
private Vector<Stack<Integer>> getPegs(int k) {
Vector<Stack<Integer>> pegs = new Vector<Stack<Integer>>(k);
for (int i = 0; i < k; i++) {
pegs.add(new Stack<Integer>());
}
String s[] = this.config.split(" ");
for (int i = s.length - 1; i >= 0; i--) {
pegs.get(Integer.parseInt(s[i]) - 1).add(i + 1);
}
return pegs;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + getOuterType().hashCode();
result = prime * result
+ ((config == null) ? 0 : config.hashCode());
result = prime * result
+ ((father == null) ? 0 : father.hashCode());
result = prime * result
+ ((last_move == null) ? 0 : last_move.hashCode());
result = prime * result + (visited ? 1231 : 1237);
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (!getOuterType().equals(other.getOuterType()))
return false;
if (config == null) {
if (other.config != null)
return false;
} else if (!config.equals(other.config))
return false;
if (father == null) {
if (other.father != null)
return false;
} else if (!father.equals(other.father))
return false;
if (last_move == null) {
if (other.last_move != null)
return false;
} else if (!last_move.equals(other.last_move))
return false;
if (visited != other.visited)
return false;
return true;
}
public Node getFather() {
return father;
}
public String getLast_move() {
return last_move;
}
public String getConfig() {
return config;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
private Solution getOuterType() {
return Solution.this;
}
}
}
Here is a Java code which prepares the graph with neighboring configurations and solves it. I tried to use Object-Oriented way, but I still feel there might be better hack way to solve this faster. Hope it helps.
import FBSample.Node.Move;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
/**
*
* @author Sada Kurapati <sadakurapati@gmail.com>
*/
public class FBSample {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
//pegs initial config
Node source = readPegsConfiguration(k, n, sc);
//read target configuration
Node target = readPegsConfiguration(k, n, sc);
//To keep track what config we visited and avoid cycles
Set<Node> visited = new HashSet<Node>();
try {
minMovesToTarget(source, target, visited);
} catch (Exception ex) {
System.out.println("Exception = " + ex);
}
}
private static void minMovesToTarget(Node source, Node target, Set<Node> visited) throws CloneNotSupportedException {
//Perform BFS
//add soource node to Queue
Queue<Node> q = new LinkedList<Node>();
q.add(source);
Node current = source;
while (!q.isEmpty()) {
current = q.poll();
if (current.equals(target)) { //found the target configuration
break;
}
List<Node> neighbors = current.neighbors();
if (neighbors.size() > 0) {
for (Node n : neighbors) {
if (!visited.contains(n)) {//if not visited, put it in queue
q.offer(n);
visited.add(n);
}
}
}
}
//Printing path and moves if target config found
if (current.equals(target)) {
printOutput(current);
}
}
private static Node readPegsConfiguration(int k, int n, Scanner sc) {
Stack<Integer>[] initialState = new Stack[k];
for (int i = 0; i < k; i++) {
initialState[i] = new Stack<Integer>();
}
//reading and reversing the line as we need to put the elements in decresing size
//disc is key and peg is value.
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(Collections.reverseOrder());
for (int i = 0; i < n; i++) {
map.put(i, sc.nextInt());
}
//prepare pegs
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
initialState[entry.getValue() - 1].push(entry.getKey());
}
return new Node(initialState);
}
static void printOutput(Node target) {
Stack<Move> stack = new Stack<>(); //using stack as we need to print the trail from Source - target config
while (target.parent != null) {
stack.add(target.move);
target = target.parent;
}
System.out.println(stack.size());
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
static class Node implements Cloneable {
//pegs
Stack<Integer>[] state = null;
Node parent = null; //for backtracking trail
Move move = null; // The move we made to go to next neighbor config
public Node(Stack<Integer>[] st) {
state = st;
}
@Override
protected Node clone() throws CloneNotSupportedException {
Stack<Integer>[] cloneStacks = new Stack[state.length];
for (int i = 0; i < state.length; i++) {
cloneStacks[i] = (Stack) state[i].clone();
}
Node clone = new Node(cloneStacks);
return clone;
}
//returns the neghboring configurations.
//What all configurations we can get based on current config.
public List<Node> neighbors() throws CloneNotSupportedException {
List<Node> neighbors = new ArrayList<>();
int k = state.length;
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
if (i != j && !state[i].isEmpty()) {
Node child = this.clone();
//make a move
if (canWeMove(child.state[i], child.state[j])) {
child.state[j].push(child.state[i].pop());
//this is required to backtrack the trail once we find the target config
child.parent = this;
//the move we made to get to this neighbor
child.move = new Move(i, j);
neighbors.add(child);
}
}
}
}
return neighbors;
}
public boolean canWeMove(Stack<Integer> fromTower, Stack<Integer> toTower) {
boolean answer = false;
if (toTower.isEmpty()) {// if destination peg is empty, then we can move any disc
return true;
}
int toDisc = toTower.peek();
int fromDisc = fromTower.peek();
if (fromDisc < toDisc) { //we can only place small disc on top
answer = true;
}
return answer;
}
@Override
public int hashCode() {
int hash = 7;
return hash;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final Node other = (Node) obj;
if (!Arrays.deepEquals(this.state, other.state)) {
return false;
}
return true;
}
class Move {
int pegFrom, pegTo;
public Move(int f, int t) {
pegFrom = f + 1;
pegTo = t + 1;
}
@Override
public String toString() {
return pegFrom + " " + pegTo;
}
}
}
}
Well, if M not mistaken.. this is last years Amazon question.. Unfortunately, it sounds like this is an NP problem and still the proper answer is under research !!!!!
Anyone can redirect to correct direction here ?
Well, I was solving this last year and was not able to code or hv proper algo. So I was searching some articles , where some researchers were having similar trouble as they have marked it as NP.
Mostly U can use either one as a variable (I mean either pegs or disks) not Both.. Complexity rises as we increase the no of pegs..
I was thinking of looping as well like
for (pegs=0;pegs<=NoofPegs;pegs)
recurse;
Still it won't solve this issue..
Lemme knw if some one has better algo..
This looks like "Tower of Hanoi" algorithm. h t t p://en.wikipedia.org/wiki/Tower_of_Hanoi
- Nani May 20, 2012