It has been quite some time since the last post...
I got busy in Google AI challenge. Thought of sharing few of interesting games from there.
This list will be updated regularly. Have a look... if you are not already challenging your coding skills in here, after seeing at some of these battles, you might want to check it out!
Few things to note :
1) Use the green filter at your left hand side to view the game as the bot would have seen it. Even though we can see the whole map, bots can see areas only within a radius from their own ants.
2) 2 Points are awarded for every kill while only 1 point for a new spawn. No bonus for remaining with the larger army at the end!
3) List seems to getting longer, I will crop away most of these games and will leave only the most elegant ones here.
4) If you have any beautiful games, feel free to comment the links and I will include them in here. :-)
5) Note on Dec 9th. Old games were taken out from the beta site now that the official tournament is on. So I removed those links and including real games from the official competition.
Sunday, September 18, 2011
Tuesday, May 24, 2011
Bringing Down Towers of Hanoi - part10
So we have come to the final part of this series! As promised, we will be ending the series with the source code which solves 4 tower case (can be generalized to more towers)
For those who are new and like to give it a try before looking at the solutions, part4 is probably a good place to start, unless you are really new to Towers of Hanoi, in which case it should be part1.
I haven't yet seen a java code to solve the general case for towers of hanoi for 4 towers. If you see a code let me know. I will try to format this nicely and add some comments too later. Since earlier posts contained all explanations needed, I hope you will be able to figure out the algorithm easily. Enjoy!
package com.araaya.hanoitowers;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.StringTokenizer;
/**
*@author Ashoka Ekanayaka
* www.it-front.net, www.araaya.com
*/
public class HanoiTowers4 {
//ArrayList<Integer> source1, target1, middle1, middle2;
//int steps = -1;
static Hashtable<Integer, HeightInfo> table = new Hashtable<Integer, HeightInfo>();
static {
table.put(1, new HeightInfo(1,0,1));
}
public static void main(String[] args) {
int height = Integer.parseInt(args[0]);
ArrayList<String> towers = new ArrayList<String>(4);
String s = "";
for (int i=height; i>0; i--) {
s = s + i;
if (i != 1) {
s= s + ",";
}
}
towers.add(s);
towers.add("");
//s = "";
//for (int i=2; i>0; i--) {
// s = s + i;
// if (i != 1) {
// s= s + ",";
// }
//}
towers.add("");
towers.add("");
String moveList = HanoiTowers4.getSolution(height, 4, towers);
String[] moves = moveList.split(",");
System.out.println(moves.length + " Moves");
System.out.println(moveList);
}
public static String getSolution(int diskCount, int towerCount, ArrayList<String> towerContents) {
ArrayList<ArrayList<Integer>> towers = new ArrayList<ArrayList<Integer>>(towerCount);
for (int i=0; i<towerCount; i++) {
String s = towerContents.get(i);
ArrayList<Integer> tower = new ArrayList<Integer>(diskCount);
if (!s.equals("")) {
String[] disks = s.split(",");
for (int j=0; j<disks.length; j++) {
tower.add(Integer.parseInt(disks[j]));
}
}
towers.add(tower);
}
StringBuilder moveList = new StringBuilder();
if (towerCount == 3) {
return buildTower3(diskCount, 0, 0, 2, 1, towers, moveList).toString();
} else if (towerCount == 4) {
return buildTower4(diskCount, 0, 3, 1, 2, towers, moveList).toString();
} else {
return null;
}
}
public static StringBuilder buildTower4(int height, int source, int target, int middle1, int middle2, ArrayList<ArrayList<Integer>> towers, StringBuilder moveList) {
if (height == 0) {
return moveList;
}
ArrayList<Integer> targetTower = towers.get(target);
if (targetTower.contains(Integer.valueOf(height))) {
buildTower4(height-1, source, target, middle1, middle2, towers, moveList);
} else {
ArrayList<Integer> middle1Tower = towers.get(middle1);
ArrayList<Integer> middle2Tower = towers.get(middle2);
if (middle1Tower.contains(Integer.valueOf(height))) {
int temp = middle1;
middle1 = source;
source = temp;
}
if (middle2Tower.contains(Integer.valueOf(height))) {
int temp = middle2;
middle2 = source;
source = temp;
}
int newHeight = getSteps(height).t4Height;
buildTower4(newHeight, source, middle1, middle2, target, towers, moveList);
if (height > 2) {
buildTower3(height-1, newHeight, source, middle2, target, towers, moveList);
}
move(source, target, towers, moveList);
print(towers);
if (height > 2) {
buildTower3(height-1, newHeight, middle2, target, source, towers, moveList);
}
buildTower4(newHeight, middle1, target, middle2, source, towers, moveList);
}
return moveList;
}
public static StringBuilder buildTower3(int height, int ceiling, int source, int target, int middle, ArrayList<ArrayList<Integer>> towers, StringBuilder moveList) {
if (height == ceiling) {
return moveList;
}
ArrayList<Integer> targetTower = towers.get(target);
if (targetTower.contains(Integer.valueOf(height))) {
buildTower3(height-1, ceiling, source, target, middle, towers, moveList);
} else {
ArrayList<Integer> middleTower = towers.get(middle);
if (middleTower.contains(Integer.valueOf(height))) {
int temp = middle;
middle = source;
source = temp;
}
buildTower3(height-1, ceiling, source, middle, target, towers, moveList);
move(source, target, towers, moveList);
print(towers);
buildTower3(height-1, ceiling, middle, target, source, towers, moveList);
}
return moveList;
}
public static HeightInfo getSteps(int height) {
if (table.containsKey(height)) {
return table.get(height);
}
boolean optimalFound = false;
int optimalSteps = Integer.MAX_VALUE;
int t4 = 0;
int steps = 0;
for (int t4Height = height-1; !optimalFound && t4Height>0; t4Height--) {
int t3Height = (height - 1) - t4Height;
steps = 1 + 2*(getSteps(t4Height).steps) + 2*((1 << t3Height) - 1);
if (steps < optimalSteps) {
optimalSteps = steps;
t4 = t4Height;
System.out.println("current minimum steps for height " + height + " is : " + steps + " with " + t4Height + "-" + t3Height);
} else {
optimalFound = true; // no point searching beyond this. current steps are the optimal
}
}
System.out.println("putting => " + height + ":" + optimalSteps + ":" + t4);
HeightInfo info = new HeightInfo(height, t4, optimalSteps);
table.put(height, info);
return info;
}
private static void print(ArrayList<ArrayList<Integer>> towers) {
for (ArrayList<Integer> tower : towers) {
for (Integer i : tower) {
System.out.print(i+",");
}
System.out.print(" : ");
}
System.out.println();
}
private static void move(int source, int target, ArrayList<ArrayList<Integer>> towers, StringBuilder strB) {
ArrayList<Integer> targetTower = towers.get(target);
ArrayList<Integer> sourceTower = towers.get(source);
targetTower.add(sourceTower.get(sourceTower.size()-1)); // add the top most element in source to the top of target
sourceTower.remove(sourceTower.size()-1);
strB.append(source + 1);
strB.append("-");
strB.append(target + 1);
strB.append(",");
}
}
For those who are new and like to give it a try before looking at the solutions, part4 is probably a good place to start, unless you are really new to Towers of Hanoi, in which case it should be part1.
I haven't yet seen a java code to solve the general case for towers of hanoi for 4 towers. If you see a code let me know. I will try to format this nicely and add some comments too later. Since earlier posts contained all explanations needed, I hope you will be able to figure out the algorithm easily. Enjoy!
package com.araaya.hanoitowers;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.StringTokenizer;
/**
*@author Ashoka Ekanayaka
* www.it-front.net, www.araaya.com
*/
public class HanoiTowers4 {
//ArrayList<Integer> source1, target1, middle1, middle2;
//int steps = -1;
static Hashtable<Integer, HeightInfo> table = new Hashtable<Integer, HeightInfo>();
static {
table.put(1, new HeightInfo(1,0,1));
}
public static void main(String[] args) {
int height = Integer.parseInt(args[0]);
ArrayList<String> towers = new ArrayList<String>(4);
String s = "";
for (int i=height; i>0; i--) {
s = s + i;
if (i != 1) {
s= s + ",";
}
}
towers.add(s);
towers.add("");
//s = "";
//for (int i=2; i>0; i--) {
// s = s + i;
// if (i != 1) {
// s= s + ",";
// }
//}
towers.add("");
towers.add("");
String moveList = HanoiTowers4.getSolution(height, 4, towers);
String[] moves = moveList.split(",");
System.out.println(moves.length + " Moves");
System.out.println(moveList);
}
public static String getSolution(int diskCount, int towerCount, ArrayList<String> towerContents) {
ArrayList<ArrayList<Integer>> towers = new ArrayList<ArrayList<Integer>>(towerCount);
for (int i=0; i<towerCount; i++) {
String s = towerContents.get(i);
ArrayList<Integer> tower = new ArrayList<Integer>(diskCount);
if (!s.equals("")) {
String[] disks = s.split(",");
for (int j=0; j<disks.length; j++) {
tower.add(Integer.parseInt(disks[j]));
}
}
towers.add(tower);
}
StringBuilder moveList = new StringBuilder();
if (towerCount == 3) {
return buildTower3(diskCount, 0, 0, 2, 1, towers, moveList).toString();
} else if (towerCount == 4) {
return buildTower4(diskCount, 0, 3, 1, 2, towers, moveList).toString();
} else {
return null;
}
}
public static StringBuilder buildTower4(int height, int source, int target, int middle1, int middle2, ArrayList<ArrayList<Integer>> towers, StringBuilder moveList) {
if (height == 0) {
return moveList;
}
ArrayList<Integer> targetTower = towers.get(target);
if (targetTower.contains(Integer.valueOf(height))) {
buildTower4(height-1, source, target, middle1, middle2, towers, moveList);
} else {
ArrayList<Integer> middle1Tower = towers.get(middle1);
ArrayList<Integer> middle2Tower = towers.get(middle2);
if (middle1Tower.contains(Integer.valueOf(height))) {
int temp = middle1;
middle1 = source;
source = temp;
}
if (middle2Tower.contains(Integer.valueOf(height))) {
int temp = middle2;
middle2 = source;
source = temp;
}
int newHeight = getSteps(height).t4Height;
buildTower4(newHeight, source, middle1, middle2, target, towers, moveList);
if (height > 2) {
buildTower3(height-1, newHeight, source, middle2, target, towers, moveList);
}
move(source, target, towers, moveList);
print(towers);
if (height > 2) {
buildTower3(height-1, newHeight, middle2, target, source, towers, moveList);
}
buildTower4(newHeight, middle1, target, middle2, source, towers, moveList);
}
return moveList;
}
public static StringBuilder buildTower3(int height, int ceiling, int source, int target, int middle, ArrayList<ArrayList<Integer>> towers, StringBuilder moveList) {
if (height == ceiling) {
return moveList;
}
ArrayList<Integer> targetTower = towers.get(target);
if (targetTower.contains(Integer.valueOf(height))) {
buildTower3(height-1, ceiling, source, target, middle, towers, moveList);
} else {
ArrayList<Integer> middleTower = towers.get(middle);
if (middleTower.contains(Integer.valueOf(height))) {
int temp = middle;
middle = source;
source = temp;
}
buildTower3(height-1, ceiling, source, middle, target, towers, moveList);
move(source, target, towers, moveList);
print(towers);
buildTower3(height-1, ceiling, middle, target, source, towers, moveList);
}
return moveList;
}
public static HeightInfo getSteps(int height) {
if (table.containsKey(height)) {
return table.get(height);
}
boolean optimalFound = false;
int optimalSteps = Integer.MAX_VALUE;
int t4 = 0;
int steps = 0;
for (int t4Height = height-1; !optimalFound && t4Height>0; t4Height--) {
int t3Height = (height - 1) - t4Height;
steps = 1 + 2*(getSteps(t4Height).steps) + 2*((1 << t3Height) - 1);
if (steps < optimalSteps) {
optimalSteps = steps;
t4 = t4Height;
System.out.println("current minimum steps for height " + height + " is : " + steps + " with " + t4Height + "-" + t3Height);
} else {
optimalFound = true; // no point searching beyond this. current steps are the optimal
}
}
System.out.println("putting => " + height + ":" + optimalSteps + ":" + t4);
HeightInfo info = new HeightInfo(height, t4, optimalSteps);
table.put(height, info);
return info;
}
private static void print(ArrayList<ArrayList<Integer>> towers) {
for (ArrayList<Integer> tower : towers) {
for (Integer i : tower) {
System.out.print(i+",");
}
System.out.print(" : ");
}
System.out.println();
}
private static void move(int source, int target, ArrayList<ArrayList<Integer>> towers, StringBuilder strB) {
ArrayList<Integer> targetTower = towers.get(target);
ArrayList<Integer> sourceTower = towers.get(source);
targetTower.add(sourceTower.get(sourceTower.size()-1)); // add the top most element in source to the top of target
sourceTower.remove(sourceTower.size()-1);
strB.append(source + 1);
strB.append("-");
strB.append(target + 1);
strB.append(",");
}
}
Friday, April 29, 2011
Bringing Down Towers of Hanoi - part9
As we promised in part8 of this series, In this post we are going to see few sample outputs from Tower4 program in action. Also we will discuss the algorithm behind how to determine the best breakdown of middle towers. (Remember, in four tower case, we have choices on how to distribute the disks between tower 2 and 3 when we want to move disks from tower 1 to 4)
Let's see the case of 5 disks :
6,5,4,3,2, : : 1, :
6,5,4,3, : : 1, : 2,
6,5,4, : 3, : 1, : 2,
6,5,4, : 3,2, : 1, :
6,5,4, : 3,2,1, : :
6,5, : 3,2,1, : : 4,
6, : 3,2,1, : 5, : 4,
6, : 3,2,1, : 5,4, :
: 3,2,1, : 5,4, : 6,
4, : 3,2,1, : 5, : 6,
4, : 3,2,1, : : 6,5,
: 3,2,1, : : 6,5,4,
: 3,2, : 1, : 6,5,4,
2, : 3, : 1, : 6,5,4,
2, : : 1, : 6,5,4,3,
: : 1, : 6,5,4,3,2,
: : : 6,5,4,3,2,1,
17 Moves
If we look at step 8 above (in blue), we will see that the program has distributed top 5 disks as 3 : 2 in the middle 2 towers. It has then moved the 6th disk to 4th tower. It could have distributed them as 4 : 1, but has found that it will be more costly. Mini tower 3-2-1 it has created on tower2 was created using all 4 towers but the Mini tower it has created on tower3 (which has disks 4 and 5) was created using only 3 towers while keeping the already buildup content at tower 2 intact.
Once the biggest disk (disk 6) was moved to tower 4, program has created a mini tower 4-5 at top of tower4 while keeping tower 2 intact. After that step it has created a mini tower 3-2-1 on tower4 using all 4 towers.
Let's have a good look at again and make sure we understand the process!
In general, to solve 4 tower case for n disks, we need to follow these steps :
1) find optimal numbers for x and y such that x+y=n-1
2) build a tower of hight x in tower2 using all 4 towers
3) build a tower of height y (starting from disk x+1) in tower3 while using only 3 towers (since the content we built on tower2 need to be preserved)
4) move the largest disk (which is n) from tower 1 to tower4
5) build a tower of height y on top of tower4 (starting from disk x+1) while using only 3 towers and keeping the content on tower2 intact.
6) build a tower of height x in tower4 using all 4 towers.
Above is a recursive algorithm because to build a tower of n using all 4 towers, we will have to build a tower of x using all 4 towers!
Now, only one problem remaining.
How to decide on the best distribution between tower2 and 3 (in the example it was 3:2 and not 4:1), that is x was 3 and y was 2 how to find x and y ?
Here too we could use recursion!
Following recursive algorithm and the program is something I have come up with and haven't seen in anywhere else yet. If any of you find a similar algorithm or a better one to solve this puzzle please inform me by putting a comment here with your finding. The code for this will appear in the next post
We need some notations here to make things clearer :
Let T4(n) = 'steps to make a tower of height n using 4 towers'
Let T3(n) = 'steps to make a tower of height n using 3 towers'
Then we can express the steps needed for above 6 steps in this form :
T4(n) = 2*(T4(x)+T3(y)) +1
For instance, T4(6) = 2* (T4(3)+T3(2)) + 1
but we know T3(m) is 2m-1, hence T3(2) above is 22-1 = 3
So, T4(6) = 2*T4(3)+7
To build a tower of height 1, we need just 1 step.
According to above algorithm (steps 1 to 6 given above), building a tower of 2 will need 3 steps, since n=2, x=1 and y=0 in this case. (you can work out how we arrived at number 3 as home work!)
Now that we know steps needed to build a tower of 1 and a tower of 2, can we find the steps needed to create a tower of 3 ?
We have 2 choices
n =3, x=1,y=1 and
n=3, x=2, y=0
In the first case, steps needed will be 5. (home work for readers) In the second, it will be 7! (more home work) So we go with option 1. That means T4(3) =5 !!
Now we could revisit the problem of T4(6).
Earlier we found T4(6) = 2 * T4(3) + 7
then T4(6) = 2*5 + 7 = 17 Which is exactly the number of steps our program has taken to solve!
So we could recursively find best x and y for any n
All we need now is to write the nice recursive code. We will give the readers few days to come up with that code before unraveling it in our last post of Towers Hanoi series.
After that we will move to a new game and a new problem !
Your feedback on the Hanoi Towers series so far will be greatly welcome!
Let's see the case of 5 disks :
6,5,4,3,2, : : 1, :
6,5,4,3, : : 1, : 2,
6,5,4, : 3, : 1, : 2,
6,5,4, : 3,2, : 1, :
6,5,4, : 3,2,1, : :
6,5, : 3,2,1, : : 4,
6, : 3,2,1, : 5, : 4,
6, : 3,2,1, : 5,4, :
: 3,2,1, : 5,4, : 6,
4, : 3,2,1, : 5, : 6,
4, : 3,2,1, : : 6,5,
: 3,2,1, : : 6,5,4,
: 3,2, : 1, : 6,5,4,
2, : 3, : 1, : 6,5,4,
2, : : 1, : 6,5,4,3,
: : 1, : 6,5,4,3,2,
: : : 6,5,4,3,2,1,
17 Moves
If we look at step 8 above (in blue), we will see that the program has distributed top 5 disks as 3 : 2 in the middle 2 towers. It has then moved the 6th disk to 4th tower. It could have distributed them as 4 : 1, but has found that it will be more costly. Mini tower 3-2-1 it has created on tower2 was created using all 4 towers but the Mini tower it has created on tower3 (which has disks 4 and 5) was created using only 3 towers while keeping the already buildup content at tower 2 intact.
Once the biggest disk (disk 6) was moved to tower 4, program has created a mini tower 4-5 at top of tower4 while keeping tower 2 intact. After that step it has created a mini tower 3-2-1 on tower4 using all 4 towers.
Let's have a good look at again and make sure we understand the process!
In general, to solve 4 tower case for n disks, we need to follow these steps :
1) find optimal numbers for x and y such that x+y=n-1
2) build a tower of hight x in tower2 using all 4 towers
3) build a tower of height y (starting from disk x+1) in tower3 while using only 3 towers (since the content we built on tower2 need to be preserved)
4) move the largest disk (which is n) from tower 1 to tower4
5) build a tower of height y on top of tower4 (starting from disk x+1) while using only 3 towers and keeping the content on tower2 intact.
6) build a tower of height x in tower4 using all 4 towers.
Above is a recursive algorithm because to build a tower of n using all 4 towers, we will have to build a tower of x using all 4 towers!
Now, only one problem remaining.
How to decide on the best distribution between tower2 and 3 (in the example it was 3:2 and not 4:1), that is x was 3 and y was 2 how to find x and y ?
Here too we could use recursion!
Following recursive algorithm and the program is something I have come up with and haven't seen in anywhere else yet. If any of you find a similar algorithm or a better one to solve this puzzle please inform me by putting a comment here with your finding. The code for this will appear in the next post
We need some notations here to make things clearer :
Let T4(n) = 'steps to make a tower of height n using 4 towers'
Let T3(n) = 'steps to make a tower of height n using 3 towers'
Then we can express the steps needed for above 6 steps in this form :
T4(n) = 2*(T4(x)+T3(y)) +1
For instance, T4(6) = 2* (T4(3)+T3(2)) + 1
but we know T3(m) is 2m-1, hence T3(2) above is 22-1 = 3
So, T4(6) = 2*T4(3)+7
To build a tower of height 1, we need just 1 step.
According to above algorithm (steps 1 to 6 given above), building a tower of 2 will need 3 steps, since n=2, x=1 and y=0 in this case. (you can work out how we arrived at number 3 as home work!)
Now that we know steps needed to build a tower of 1 and a tower of 2, can we find the steps needed to create a tower of 3 ?
We have 2 choices
n =3, x=1,y=1 and
n=3, x=2, y=0
In the first case, steps needed will be 5. (home work for readers) In the second, it will be 7! (more home work) So we go with option 1. That means T4(3) =5 !!
Now we could revisit the problem of T4(6).
Earlier we found T4(6) = 2 * T4(3) + 7
then T4(6) = 2*5 + 7 = 17 Which is exactly the number of steps our program has taken to solve!
So we could recursively find best x and y for any n
All we need now is to write the nice recursive code. We will give the readers few days to come up with that code before unraveling it in our last post of Towers Hanoi series.
After that we will move to a new game and a new problem !
Your feedback on the Hanoi Towers series so far will be greatly welcome!
Tuesday, April 19, 2011
Arrival of the Java Killer ?
The remarkable news of the impending arrival of the new programming language which is already tipped to be the Java Killer is just out.
I had a entire post covering this in araaya blog. What's more the new language is named as Ceylon !! Find out the reasons behing that naming and a pragmatic forcast of things in here.
(Image source http:/www.decidetostayfit.com)
Thursday, April 14, 2011
Towers of Hanoi - part 8
In the earlier post, we learned that still, (surprisingly) there is no mathematical formula for the minimum number of steps needed to solve a Tower of Hanoi puzzle where there can be towers more than 3 and any number of rings. That is no formula exists which gives the number of steps as a function of rings and towers.
In this post, we will do away with mathematical aspects of this puzzle and focus on what we know better. Yea, the algorithm!
Suppose we have 10 rings (all in the 1st tower) there are 4 towers and you want to move all to the 4th tower.
1) We have to place first 9 rings in the 2 middle towers (tower2 and tower3).
2) Move the 10th towers from tower 1 to tower 4
3) build a tower of 9 in tower4 by using the rings in 2 middle towers.
This will lead to a recursive algorithm. Trick is to get the step 1 above right, how best to distribute the first 9 rings among two middle towers ?
What I did was to write a separate method to determine just that! In that method I will calculate steps needed achieve to each of different distribution of 9 rings. Distributions goes like this :
tower2 have first 8 rings, tower 3 have the ring 9 Or
tower2 have first 6 rings, tower 3 has 7 to 9
tower2 have first 5, tower 3 has 6 to 9
and so on....
So my method will calculate steps needed to create each of that distribution and then find the distribution which will need the least number of steps to create. Once we know that, we just call our recursion function to build towers. For instance, if the best configuration is 1-6 in tower2 and 7-9 in tower3, our recursive function will look like this.
buildtower4(tower1,tower2,tower3,tower4,6) // use all 4 towers and build a tower of 1-6 in tower2)
buildtower3(tower1,tower4,tower3,9,7) // use only the give 3 towers and create a tower with rings 9 to 7 in the third tower)
moveRing(tower1, 10, tower4) // ok, we created the optimal distribution of first 9 rings, now move the 10th ring to final destination)
buildTower3(tower3,tower1,tower4,9,7) // build a tower of 9-7 in tower4. don't touch tower2)
buildTower4(tower1,tower4,tower2,tower3,6) // use all 4 towers and build a tower of 1-6 on top of tower4
Implement something like that in any language and you will have a working code which solves the 4 tower puzzle!
Now, 3 challenges from today's post :
1) Write the algorithm to determine the optimal combination to distribute N rings in the two middle towers.
2) Implement that algorithm in code.
3) implement the given algorithm today to solve the 4 tower puzzle once and for all!
In the next post we will see few sample outputs from my code... and few screen shots to ram in what we discussed today, for those who have already got the message from today's post, good luck with the code!
See you soon.....
In this post, we will do away with mathematical aspects of this puzzle and focus on what we know better. Yea, the algorithm!
Suppose we have 10 rings (all in the 1st tower) there are 4 towers and you want to move all to the 4th tower.
1) We have to place first 9 rings in the 2 middle towers (tower2 and tower3).
2) Move the 10th towers from tower 1 to tower 4
3) build a tower of 9 in tower4 by using the rings in 2 middle towers.
This will lead to a recursive algorithm. Trick is to get the step 1 above right, how best to distribute the first 9 rings among two middle towers ?
What I did was to write a separate method to determine just that! In that method I will calculate steps needed achieve to each of different distribution of 9 rings. Distributions goes like this :
tower2 have first 8 rings, tower 3 have the ring 9 Or
tower2 have first 6 rings, tower 3 has 7 to 9
tower2 have first 5, tower 3 has 6 to 9
and so on....
So my method will calculate steps needed to create each of that distribution and then find the distribution which will need the least number of steps to create. Once we know that, we just call our recursion function to build towers. For instance, if the best configuration is 1-6 in tower2 and 7-9 in tower3, our recursive function will look like this.
buildtower4(tower1,tower2,tower3,tower4,6) // use all 4 towers and build a tower of 1-6 in tower2)
buildtower3(tower1,tower4,tower3,9,7) // use only the give 3 towers and create a tower with rings 9 to 7 in the third tower)
moveRing(tower1, 10, tower4) // ok, we created the optimal distribution of first 9 rings, now move the 10th ring to final destination)
buildTower3(tower3,tower1,tower4,9,7) // build a tower of 9-7 in tower4. don't touch tower2)
buildTower4(tower1,tower4,tower2,tower3,6) // use all 4 towers and build a tower of 1-6 on top of tower4
Implement something like that in any language and you will have a working code which solves the 4 tower puzzle!
Now, 3 challenges from today's post :
1) Write the algorithm to determine the optimal combination to distribute N rings in the two middle towers.
2) Implement that algorithm in code.
3) implement the given algorithm today to solve the 4 tower puzzle once and for all!
In the next post we will see few sample outputs from my code... and few screen shots to ram in what we discussed today, for those who have already got the message from today's post, good luck with the code!
See you soon.....
Tuesday, March 8, 2011
Bringing Down Towers of Hanoi - part7
In last post, we planned to discuss more about the problem of multi towers in hanoi and give some hints on the algorithm.
Interestingly, for multiple towers, no one has still come up with a general formula to express the number of steps as a function of number of towers and number of rings. Some general cases have been figured out though. For instance, we don't need to be mathematicians to say whats the number of steps would be for a problem with more towers than there are rings. Say, 11 towers and only 10 rings! what would be the number of steps to solve this ?
Of course, it would take 9 steps to remove top 9 rings into 9 different towers. Then 10 steps to put all rings in the target tower. 19 steps in all. In other words, 2n-1 ! However, people have found that coming up with a general formula when the number of rings are greater than number of towers (which is greater than 3) is little bit harder than that.
In an earlier post we have seen it takes exactly 2n-1 to solve the 3 tower case (worse case) for n rings.
We have just saw that it takes 2n-1 to solve the m tower case for n rings where m > n (best case)
What happens when m =n, Here is my result. I will intentionally leave out the explanations so you can arrive at that independently.
When m = n, it takes (n-1) + 1 + (n-2) + 3 = 2n+1 steps to solve the puzzle!
Similarly, when m = n-1, it becomes 2n+3
It appears like we could express number of steps as (2n-1) + 2*(n-(m+1)) = 4n - 2m + 1
However, these are true only when number of towers are closer to number of rings. When number of towers become less compared to number of rigs, it get complicated. Say, 10 rings in 4 towers. However, solving such a puzzle manually is much easier (in terms of number of steps needed) than solving a similar number of rings with 3 towers. Problem is when we try to find the optimal strategy.
I could display few graphical outputs from the program I currently have but before that, wouldn't you want to give it a try yourself ? Remember, number of steps needed is drastically reduced now. We will still need a recursive solution as the nature of the problem commands....
Interestingly, for multiple towers, no one has still come up with a general formula to express the number of steps as a function of number of towers and number of rings. Some general cases have been figured out though. For instance, we don't need to be mathematicians to say whats the number of steps would be for a problem with more towers than there are rings. Say, 11 towers and only 10 rings! what would be the number of steps to solve this ?
Of course, it would take 9 steps to remove top 9 rings into 9 different towers. Then 10 steps to put all rings in the target tower. 19 steps in all. In other words, 2n-1 ! However, people have found that coming up with a general formula when the number of rings are greater than number of towers (which is greater than 3) is little bit harder than that.
In an earlier post we have seen it takes exactly 2n-1 to solve the 3 tower case (worse case) for n rings.
We have just saw that it takes 2n-1 to solve the m tower case for n rings where m > n (best case)
What happens when m =n, Here is my result. I will intentionally leave out the explanations so you can arrive at that independently.
When m = n, it takes (n-1) + 1 + (n-2) + 3 = 2n+1 steps to solve the puzzle!
Similarly, when m = n-1, it becomes 2n+3
It appears like we could express number of steps as (2n-1) + 2*(n-(m+1)) = 4n - 2m + 1
However, these are true only when number of towers are closer to number of rings. When number of towers become less compared to number of rigs, it get complicated. Say, 10 rings in 4 towers. However, solving such a puzzle manually is much easier (in terms of number of steps needed) than solving a similar number of rings with 3 towers. Problem is when we try to find the optimal strategy.
I could display few graphical outputs from the program I currently have but before that, wouldn't you want to give it a try yourself ? Remember, number of steps needed is drastically reduced now. We will still need a recursive solution as the nature of the problem commands....
Sunday, February 27, 2011
Bringing Down Towers of Hanoi - part6
Today, we are going to see the magic code which solves Towers of Hanoi General Problem. Those who still (bravely) want to give it an own try before looking at the code. Can go through these hints and do so.
Before going to the code, I have something else to show you. This mathematical proof I found from web, which basically gives a formula for the average number of steps for the general case.
wow, that's some formula for you!
Anyway, as you can see, the code below is the simplicity itself! The solution we propose is bounded by 2n-1, and never exceeds that, also when we present a half done problem, it actually solves it optimally. When you look at the code you get the intuitive feeling that this has to be the optimal solution, wish we could device a mathematical proof too for that fact!
private static void buildTower(int height, ArrayList source,
ArrayList target, ArrayList middle) {
if (height < 0) {
return;
}
if (target.contains(Integer.valueOf(height))) {
buildTower(height -1, source, target, middle);
} else {
if (middle.contains(Integer.valueOf(height))) {
ArrayList temp = middle;
middle = source;
source = temp;
}
buildTower(height-1, source, middle, target);
move(source, target);
print();
buildTower(height-1, middle, target, source);
}
}
Bolded are the lines we added to the last solution. (specific case where all rings are in first tower at the beginning.) Now, isn't this simple ?
One more thing : I havn't yet seen this code (or the algorithm) anywhere in the internet. If some one come across this in anywhere else, please post a comment with the link.
In next post, we will discuss few hints on how to solve the 4 tower case.
Have a nice day!
Before going to the code, I have something else to show you. This mathematical proof I found from web, which basically gives a formula for the average number of steps for the general case.
wow, that's some formula for you!
Anyway, as you can see, the code below is the simplicity itself! The solution we propose is bounded by 2n-1, and never exceeds that, also when we present a half done problem, it actually solves it optimally. When you look at the code you get the intuitive feeling that this has to be the optimal solution, wish we could device a mathematical proof too for that fact!
private static void buildTower(int height, ArrayList
ArrayList
if (height < 0) {
return;
}
if (target.contains(Integer.valueOf(height))) {
buildTower(height -1, source, target, middle);
} else {
if (middle.contains(Integer.valueOf(height))) {
ArrayList
middle = source;
source = temp;
}
buildTower(height-1, source, middle, target);
move(source, target);
print();
buildTower(height-1, middle, target, source);
}
}
Bolded are the lines we added to the last solution. (specific case where all rings are in first tower at the beginning.) Now, isn't this simple ?
One more thing : I havn't yet seen this code (or the algorithm) anywhere in the internet. If some one come across this in anywhere else, please post a comment with the link.
In next post, we will discuss few hints on how to solve the 4 tower case.
Have a nice day!
Subscribe to:
Posts (Atom)