6

Here is a question from 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 any other peg. At any point 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 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

There is no harm in discussing solution for this problem as it is a sample problem.

The solution to the classic Towers of Hanoi problem is really simple to code:

void hanoi(char s, char i, char d, int n)
{
     if(n>0)
     {
            hanoi(s, d, i, n-1);
            cout<<s<<":"<<d<<endl;
            hanoi(i, s, d, n-1);
     }        
}

The above can also be extended to a general 'k' pegs tower of hanoi. But, this knowledge is turning out to be not at all useful to design a solution to this sample puzzle. Any suggestions as to how to approach this and similar kind of problems in future?

4

6 回答 6

8

这是我的动态编程解决方案，它最多可以在 O(K^N) 步中找到最佳移动序列，对于 K = 5、N = 8，它在一秒钟内运行。由于懒惰，我对输入数据进行了硬编码。

它是一个通过状态空间的 BFS，不会两次访问同一个状态。然后它通过从头到尾回溯得到实际路径（这部分与最优序列的长度成线性关系）。基本上，它是“通过迷宫的最短路径”算法，但“迷宫”是问题的状态空间，起始“位置”是初始状态，结束“位置”是期望状态。

许多类似的问题都可以通过这种方式解决，只要你能定义一个有限的状态空间，一个你的目标是最小化的两个状态之间的“距离”，以及一种计算你可以从当前状态移动到哪些状态的方法。

例如，具有任意数量的“传教士和食人者”问题可以使用相同的算法来解决。

此外，如果您需要“所有最优解”而不是“任何最优解”，则很容易修改算法以提供它们。

class Program
{
    static int N = 8;
    static int K = 5;
    static List<int> StartState = new List<int> { 3, 3, 2, 1, 4, 1, 5, 2 };
    static List<int> EndState = new List<int> { 1, 4, 2, 2, 3, 4, 4, 3 };

    static LinkedList<int> StateQueue = new LinkedList<int>();
    static int[] MovesToState = new int[(int)Math.Pow(K, N)];


    static void Main(string[] args)
    {
        for (int i = 0; i < StartState.Count; i++)
        {
            StartState[i]--;
            EndState[i]--;
        }

        int startStateIndex = StateToNum(StartState);
        int endStateIndex = StateToNum(EndState);

        for (int i = 0; i < MovesToState.Length; i++)
            MovesToState[i] = -1;

        MovesToState[startStateIndex] = 0;

        StateQueue.AddFirst(startStateIndex);
        while (StateQueue.Count > 0 && MovesToState[endStateIndex] == -1)
        {
            var legalMoves = LegalMoves(StateQueue.Last.Value);
            foreach (var newStateIndex in legalMoves)
            {
                int currMoves = MovesToState[StateQueue.Last.Value];
                if (MovesToState[newStateIndex] == -1)
                {
                    MovesToState[newStateIndex] = currMoves + 1;
                    StateQueue.AddFirst(newStateIndex);
                }
            }
            StateQueue.RemoveLast();
        }

        var currStateIndex = endStateIndex;
        var moves = new List<Tuple<int, int>>();
        while (currStateIndex != startStateIndex)
        {
            var legalMoves = LegalMoves(currStateIndex);
            int currMoves = MovesToState[currStateIndex];
            foreach (var prevStateIndex in legalMoves)
            {
                if (MovesToState[prevStateIndex] == MovesToState[currStateIndex] - 1)
                {
                    var currState = NumToState(currStateIndex);
                    var prevState = NumToState(prevStateIndex);
                    for (int i = 0; i < N; i++)
                    {
                        if (currState[i] != prevState[i])
                        {
                            moves.Add(new Tuple<int, int>(prevState[i] + 1, currState[i] + 1));
                            currStateIndex = prevStateIndex;
                            break;
                        }
                    }
                }
            }
        }
        Console.WriteLine(MovesToState[endStateIndex]);
        moves.Reverse();
        foreach (var move in moves)
        {
            Console.WriteLine("{0} {1}", move.Item1, move.Item2);
        }

        Console.Read();
    }

    static List<int> LegalMoves(int stateIndex)
    {
        var legalMoves = new List<int>();

        var state = NumToState(stateIndex);

        int[] minOnPeg = new int[K];
        for (int i = 0; i < minOnPeg.Length; i++)
            minOnPeg[i] = N;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < K; j++)
                if (state[i] == j && i < minOnPeg[j])
                    minOnPeg[j] = i;

        bool[] isTop = new bool[N];
        for (int i = 0; i < isTop.Length; i++)
            isTop[i] = false;
        for (int i = 0; i < K; i++)
            if (minOnPeg[i] < N)
                isTop[minOnPeg[i]] = true;

        for (int i = 0; i < N; i++)
        {
            if (!isTop[i])
                continue;

            for (int j = 0; j < K; j++)
            {
                if (minOnPeg[j] <= i)
                    continue;

                var tmp = state[i];
                state[i] = j;
                var newStateIndex = StateToNum(state);
                legalMoves.Add(newStateIndex);
                state[i] = tmp;
            }
        }
        return legalMoves;
    }

    static int StateToNum(List<int> state)
    {
        int r = 0;
        int f = 1;
        foreach (var peg in state)
        {
            r += f * peg;
            f *= K;
        }
        return r;
    }

    static List<int> NumToState(int num)
    {
        var r = new List<int>();
        for (int i = 0; i < N; i++)
        {
            r.Add(num % K);
            num = num / K;
        }
        return r;
    }
}
于 2013-05-17T10:43:39.323 回答
2

在java中找到了这个解决方案。基本上，它将所有可能的移动映射到树中并执行 BFS。

于 2013-05-17T05:14:28.317 回答
2

使用递归解决河内塔问题的绝佳资源 http://sleepingthreads.blogspot.in/2013/05/the-power-of-recursion_3.html

于 2013-05-17T07:05:41.977 回答
0

这是一个 Java 代码，它使用相邻配置准备图形并解决它。我尝试使用面向对象的方式，但我仍然觉得可能有更好的破解方式来更快地解决这个问题。希望能帮助到你。

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;
      }
    }
  }
}
于 2013-11-04T22:08:54.900 回答
0

第一次在这里发帖。我曾将 stackoverflow 用作潜伏者，但从未贡献过，所以我想这次我会这样做，因为我有一些代码要分享。

我也试过这个问题，我花了一段时间才弄清楚！我想我会在这里发布我的辛勤工作。我不可能在 45 分钟内解决这个问题。我是一名计算机工程专业的学生（不是计算机科学专业的学生），所以我对我的数据结构生疏了。我以前从未编写过 BFS 代码！

无论如何，我的程序使用与前面答案中讨论的相同的 BFS 方法工作，但数据结构的处理方式可能略有不同。它基本上首先生成有效的移动宽度（使用 FIFO 队列实现），然后将新的 peg/磁盘配置（状态）放入格式为 {state: previous_state} 的字典中。一旦找到最终状态或达到最大递归深度，程序就会停止搜索新状态。然后它从 dict 中检索最终状态并通过 dict 回溯以找到连续进行的移动。我在程序中使用的主要数据结构是不同状态的字典。我实际上并没有记录输出中所需的（从，到）挂钩编号。当我通过查找两个连续状态之间的一个更改元素来回溯字典树时，会计算此输出。状态被记录为与输入格式相同的元组。

希望这对某人有所帮助，我欢迎任何关于如何改进我的代码或编码风格的意见或建议。

import sys

MAX_MOVES = 10

def main():
    lines = sys.stdin.readlines()

    [discs, npegs] = map(int, lines[0].split())
    #read in the initial and final states
    istate = tuple(int(n) - 1 for n in lines[1].split())
    fstate = tuple(int(n) - 1 for n in lines[2].split())

    #call recursive function to find possible moves and 
    #generate new states to add to tree
    tree = findStates(istate, fstate, npegs)
    solution = findSolution(istate, fstate, tree)

    if solution:
        print solution[0]
        for a, b in solution[1:]:
            print "{} {}".format(a,b) 
    else:
        print "No solution found for {} max moves".format(MAX_MOVES)

def findTopDisks(state, npegs):
    """
    list the pegs with disks and the top disk radius in a dict with key being peg number
    and value being disk radius
    This function is used to find valid disks and their peg positions to make a move from
    """
    topdict = dict()
    for peg in range(npegs):
            if peg in state:
                topdict[peg] = state.index(peg)
    return topdict

def findValidMoves(state, npegs):
    """
    Finds the valid moves given the current state and number of pegs.
    Yields tuples consisting of source and destination pegs
    """
    #find the top disk of every peg number
    top_disks = findTopDisks(state, npegs)
    for from_peg, disk_r in top_disks.items():
        for dest_peg in range(npegs):
            if not top_disks.has_key(dest_peg): #dest peg is empty
                    yield (from_peg, dest_peg)
            elif top_disks[dest_peg] > disk_r:
                    yield (from_peg, dest_peg)

def findStates(istate, fstate, npegs):
    """
    Generates new states first by calling findValidMoves on current state to get valid moves.
    Then generates the new states and put them in the tree implemented using a dict.
    Key of the dict is the current state, and value is the state that leads to that state.
    """
    queue = [(istate, 0)]
    tree = {istate: None}
    while queue and (queue[0][1] < MAX_MOVES):
        cstate = queue[0][0]
        cmove = queue[0][1]
        queue.pop(0)
        #enumerate and find all valid moves and add to queue
        for from_peg, dest_peg in findValidMoves(cstate, npegs):
            if from_peg in cstate:
                nstate = list(cstate)
                nstate[cstate.index(from_peg)] = dest_peg
                nstate = tuple(nstate)
                if nstate not in tree: #new state never been found!
                    tree[nstate] = cstate
                    if nstate == fstate:
                        return tree
                    queue.append((nstate, cmove+1))
    return tree


def findSolution(istate, fstate, tree):
    """
    back track through dict and find the moves taken to get from istate and final state
    """
    solution = []
    cstate = fstate
    if fstate in tree:
        while (cstate != istate):
            #compare current state and previous
            #find the difference, record in tuple and add to list of solution moves
            pstate = tree[cstate]
            for p, c in zip(pstate, cstate):
                if p != c:
                    solution.insert(0, (p+1, c+1)) #add one to adjust for 0 offset
                    break
            cstate = pstate
        solution.insert(0, len(solution))

    return solution

if __name__ == "__main__":
   main()
于 2013-10-05T20:32:17.857 回答
0

上面链接的博客中有一个很好的算法基准（请注意 MAX_MOVES 应该增加到 11）：

6 4
3 3 2 1 4 1
1 4 2 2 3 4

来自此评论的 Leandro Facchinetti 的 Ruby 版本在大约 10 秒内解决了它。e-digga 的Java 版本~0.5 秒。我的 python 版本运行时间约为 30 毫秒。我不确定为什么我的实施如此之快。这里是：

import sys

MAX_MOVES = 11

def valid_moves(state, K):
    pegs, tops = [-1] * K, []
    for r, peg in enumerate(state):
        if pegs[peg] < 0:
            pegs[peg] = r
            for top_r, top_peg in tops:
                yield (top_r, top_peg, peg)
            tops.append((r, peg))
    for dst_peg, peg_r in enumerate(pegs):
        if peg_r < 0:
            for top_r, top_peg in tops:
                yield (top_r, top_peg, dst_peg)

def move_apply(state, move):
    r, src, dst = move
    return state[:r] + (dst,) + state[r + 1:]

def solve_bfs(initial_state, final_state, K):
    known_states = set()
    next_states = [(initial_state, [])]
    depth = 0
    while next_states and depth < MAX_MOVES:
        states, next_states = next_states, []
        for state, moves in states:
            for move in valid_moves(state, K):
                new_state = move_apply(state, move)
                if new_state in known_states:
                    continue
                new_moves = moves + [move]
                if new_state == final_state:
                    return new_moves
                next_states.append((new_state, new_moves))
                known_states.add(new_state)
        depth += 1

lines = sys.stdin.readlines()
N, K = [int(i) for i in lines[0].strip().split()]
initial_state = tuple(int(i) - 1 for i in lines[1].strip().split())
final_state = tuple(int(i) - 1 for i in lines[2].strip().split())

solution = solve_bfs(initial_state, final_state, K)
if solution:
    print len(solution)
    for disk, src, dst in solution:
        print src + 1, dst + 1
于 2013-08-31T09:20:01.333 回答