# All possible ways to reach an ending position

http://www.cstutoringcenter.com/problems/problems.php?id=103

For those who doesn't want to click it, it basically says there's a stepping stone, "-" and soldier "#", soldiers can only move right. If the soldier is behind another soldier, he must wait for the soldier to move first. The ending condition is when all soldiers reaches the end.

The number of ways 2 soldier can move across 5 stepping stones.

1) ##--- #-#-- -##-- -#-#- --##- --#-# ---## 2) ##--- #-#-- -##-- -#-#- -#--# --#-# ---## 3) ##--- #-#-- #--#- -#-#- --##- --#-# ---## 4) ##--- #-#-- #--#- -#-#- -#--# --#-# ---## 5) ##--- #-#-- #--#- #---# -#--# --#-# ---##

I'm using a breadth first search, with 5 stones, it's running within seconds, but with 10 stones, it's taking hours, the time is increasing exponentially with the depth. How can I deal with this?

My Codes:

States.java

import java.util.ArrayList; public class State { public int stones; public Soldiers[] soldiers; public String currentState =""; public boolean visited = false; public State(int stones,int Numsoldiers){ System.out.println(Numsoldiers); this.stones = stones; soldiers = new Soldiers[Numsoldiers]; System.out.println("length" + soldiers.length); initState(); } public State(int stones,Soldiers[] soldiers){ this.stones = stones; this.soldiers = soldiers; paintState(); } public void initState(){ for(int i=0;i<soldiers.length;i++) { soldiers[i] = new Soldiers(); soldiers[i].position =i; currentState+="#"; } for(int j=soldiers.length;j<stones;j++) { currentState+="-"; } } private void paintState(){ for(int j=0;j<stones;j++) { currentState+="-"; } char[] stateChar = currentState.toCharArray(); currentState = ""; for(int i=0;i<soldiers.length;i++){ stateChar[soldiers[i].position] = '#'; } for(int k=0; k<stateChar.length;k++){ currentState += stateChar[k]; } } public void printState(){ System.out.println(currentState); } public ArrayList<State> getNextStates(){ ArrayList<State> States = new ArrayList<State>(); for(int i=0;i<soldiers.length;i++){ Soldiers[] newSoldiers = new Soldiers[soldiers.length]; for(int j=0;j<soldiers.length;j++){ newSoldiers[j] = new Soldiers(soldiers[j].position); } if(!((newSoldiers[i].position+1)==stones)) { if((currentState.charAt((newSoldiers[i].position+1))=='-')) { newSoldiers[i].move(); States.add(new State(stones,newSoldiers)); } } } if(States.size()==0) { TestSoldiers.count++; } return States; } }

Soldiers.java

public class Soldiers { int position = 0; public Soldiers(){ position =0; } public Soldiers(int pos){ position = pos; } public void move(){ position ++; } }

TestSoldiers.java

import java.util.LinkedList; import java.util.Queue; public class TestSoldiers { public static int count=0; public static void main(String[] args){ TestSoldiers t = new TestSoldiers(); } public TestSoldiers() { State s = new State(10,3); breadthFirstTraversal(s); System.out.println(count); } public void breadthFirstTraversal(State rootNode){ Queue<State> q = new LinkedList<State>(); q.add(rootNode); while(!q.isEmpty()){ State n = (State)q.poll(); n.printState(); for(State adj : n.getNextStates()){ q.add(adj); } } } }

How can I make it so that I will only consider each State once while maintaining the integrity of the total number of ways to end (counts in TestSoldiers.java)?

For those of you who want to modify the parameters, it's the new State(n,k) where n is the number of stones and k is the number of soldiers.

## Answers

Memoization might come in handy.

The idea would be to run depth-first search to count the number of ways to get from the current state to the end, and store this result, then look up the already-calculated value if ever that state is repeated.

For instance, there are 2 ways to reach the end from -#-#-, so, storing this result when we get there via -##--, we could simply look up 2 when we get there via #--#-.

The simplest (but far from most efficient) way to store these would simply be to have a:

Map<Pair<Integer (Position1), Integer (Position2)>, Integer (Count)>

More generically, you could perhaps make that Pair a List.

A more efficient approach would be to have a bitmap where each bit corresponds to whether or not there's a soldier at some given position. So -#-#- would correspond to 01010, which could simply be stored in an int as 10 in decimal - if there are more than 64 stones (i.e. what would fit into a long), you could use a BitSet.

You might be better using combinatorics to compute the number of paths.

For example, suppose there are 2 soldiers and 5 steps.

Represent the distance the first soldier has moved by y, and the distance the second soldier has moved by x.

You are trying to count the number of monotonic paths from 0,0 to 3,3 such that y is never greater than x.

This is a well known problem and the answer is given by the Catalan numbers. In this case, the answer is given by the Catalan number for n=3, which is 5.

When you have more than 2 soldiers you will need to use multidimensional Catalan numbers. A useful guide and formula can be found on OEIS:

T(m, n) = 0! * 1! * .. * (n-1)! * (m * n)! / ( m! * (m+1)! * .. * (m+n-1)! )

My solution runs 10 positions in less than 1 second. The solution is quick and dirty, but the algorithm is what you should be interested in right?

The idea of my algorithm is:

- manage a set of paths to compute. start with the path where both soldiers are at the left most positions.
- if the set of paths to compute is not empty pick any path and remove it from the set.
- if the path is terminated (both soldiers are at the most right positions) print the path. continue with 2.
- extend the path by moving the head soldier if possible and put it into the set.
- extend the path by moving the tail soldier if possible and put it into the set.

That's it.

public static void main(String[] args) { List<Node> nodes = Node.newRootNode(10); while (!nodes.isEmpty()) { Node node = nodes.remove(0); if (node.isLeaf()) node.printPath(); else { if (node.headSoldierCanMove()) nodes.add(node.moveHeadSoldier()); if (node.tailSoldierCanMove()) nodes.add(node.moveTailSoldier()); } } } static final class Node { static List<Node> newRootNode(final int maxPos) { return new ArrayList<Node>() {{ add(new Node(1, 2, maxPos, "")); }}; } private final int maxPos; private final String path; private int tailPos = 1; private int headPos = tailPos + 1; private Node(int tailPos, int headPos, int maxPos, String path) { this.maxPos = maxPos; this.tailPos = tailPos; this.headPos = headPos; this.path = addPath(path); } boolean tailSoldierCanMove() { return tailPos < headPos - 1; } Node moveTailSoldier() { return new Node(tailPos + 1, headPos, maxPos, path); } boolean headSoldierCanMove() { return headPos < maxPos; } Node moveHeadSoldier() { return new Node(tailPos, headPos + 1, maxPos, path); } void printPath() { System.out.println(path); } boolean isLeaf() { return headPos == maxPos && tailPos == headPos - 1; } private String addPath(String prefix) { StringBuilder builder = new StringBuilder(prefix); for (int pos = 1; pos <= maxPos; pos++) { builder.append(tailPos == pos || headPos == pos ? "#" : "-"); } return builder.append(" ").toString(); } }