- 浏览: 75953 次
文章分类
最新评论
-
wodentt:
....为什么楼主都英文的博客
用java解决百度之星移动火柴的问题 part 1 -
wensonzhou86:
思路明确,代码清晰,通俗易懂
visit 淘宝面试题:如何充分利用多核CPU,计算很大的List中所有整数的和 -
carydeepbreathing:
代码比较干净
visit 淘宝面试题:如何充分利用多核CPU,计算很大的List中所有整数的和 -
meiowei:
yangguo 写道i don't think it is a ...
用java解决百度之星移动火柴的问题 part 2 -
yangguo:
i don't think it is a good way ...
用java解决百度之星移动火柴的问题 part 2
Recently, I saw a post:
http://www.iteye.com/topic/399628
Though I am too busy at work, can't help to spare some time on this subject because
- It is a small enough topic to talk about how to design a better component give a (business) requirement, and it is complicated enough to talk about what I want to say(Sometimes, trivial examples just don't help much).
- Most of the readers can understand the domain problem easily so there is no communication problem
- to share a view on domain driven design since I am not satisfied with the code presented in that post. No offending, but I would say it is really a spaghetti code because it has so many embeded if-else and for loops. I have no intention to blame the writer, but to solve the problem I see in an effort.
Now let us look at the problem itself, we are given an expression consisting of numbers, operators and =. We can change the numbers somehow, i.e., by moving the matches only once. After the moving, the equality should hold.
The solution is just a brutal force search, move all matches to all possible places to check the equality. So the domain driven logic should be something like this
for all digits for all matches take this match and move it to somewhere so that we have two new valid numbers check whether the equality holds if it holds, send out results.
Since there are "transformations" on the numbers, it would be better if we model the numbers first. A simple way is to code the digit like this:
TOP - UPPERLEFT | | UPPERRIGHT MIDDLE - LOWERLEFT | | LOWERRIGHT BOTTOM -
So clearly we need an enum to represent these positions:
public enum MatchPosition { TOP, UPPERLEFT, UPPERRIGHT, MIDDLE, LOWERLEFT, LOWERRIGHT, BOTTOM; }
Since at each match position, there either has a match or not, so we could encode the presence of a match in a binary format, 0 for no match, 1 for match. So the data representation of the digits are:
int[] digitEncodings = { Integer.valueOf("1110111", 2), //119 Integer.valueOf("0010010", 2), //18 Integer.valueOf("1011101", 2), //93 Integer.valueOf("1011011", 2), //91 Integer.valueOf("0111010", 2), //58 Integer.valueOf("1101011", 2), //107 Integer.valueOf("1101111", 2), //111 Integer.valueOf("1010010", 2), //82 Integer.valueOf("1111111", 2), //127 Integer.valueOf("1111011", 2), //123 };
Here the string binary sequence follows the order in the enum class MatchPosition. For example, 0 is represented as:
-
| |
| |
-
only the middle match is not there, so the string 1110111 has 0 in the middle. The number 8 has all matches, so the string is all 1's.
In order to save space, we convert the string representation to integers.
Now let's turns to the behaviors of the digits. From the pseudo code, we need several methods from the digits:
- get all matches from a digit to loop through
- take a match from a digit to form a new digit
- set a match to a particular position to form a new digit
The final implementation is as follows. There are a few decisions on the implementation, but they don't affect the overall interface design, such as:
- when taking a match off a digit, we may not have a valid digit anymore, e.g., take a match off the number one, we end up something not a number. In this case, we return a null object. Then later on the caller side we check whether it is null in order to know whether we can take a match out.
- Internally, we maintain a hashmap to map number values to the digit, this hashmap is used in several places.
- For convenience, we add a method hasMatch(MatchPosition p) to check whether there is a match at a particular position for this digit.
The full class is here:
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /** * A match digit is like this: * _ * |_| * |_| * * we are going to use a binary bit array to represent this. */ public class MatchDigit { private static final int[] digitEncodings = { Integer.valueOf("1110111", 2), //119 Integer.valueOf("0010010", 2), //18 Integer.valueOf("1011101", 2), //93 Integer.valueOf("1011011", 2), //91 Integer.valueOf("0111010", 2), //58 Integer.valueOf("1101011", 2), //107 Integer.valueOf("1101111", 2), //111 Integer.valueOf("1010010", 2), //82 Integer.valueOf("1111111", 2), //127 Integer.valueOf("1111011", 2), //123 }; public static final MatchDigit ZERO = new MatchDigit(0); public static final MatchDigit ONE = new MatchDigit(1); public static final MatchDigit TWO = new MatchDigit(2); public static final MatchDigit THREE = new MatchDigit(3); public static final MatchDigit FOUR = new MatchDigit(4); public static final MatchDigit FIVE = new MatchDigit(5); public static final MatchDigit SIX = new MatchDigit(6); public static final MatchDigit SEVEN = new MatchDigit(7); public static final MatchDigit EIGHT = new MatchDigit(8); public static final MatchDigit NINE = new MatchDigit(9); private static Map<Integer, MatchDigit> digits = new HashMap<Integer, MatchDigit>(); static { digits.put(digitEncodings[0], ZERO); digits.put(digitEncodings[1], ONE); digits.put(digitEncodings[2], TWO); digits.put(digitEncodings[3], THREE); digits.put(digitEncodings[4], FOUR); digits.put(digitEncodings[5], FIVE); digits.put(digitEncodings[6], SIX); digits.put(digitEncodings[7], SEVEN); digits.put(digitEncodings[8], EIGHT); digits.put(digitEncodings[9], NINE); } private int encodedDigit; public MatchDigit(int digit) { encodedDigit = digitEncodings[digit]; } public MatchDigit setMatch(MatchPosition position) { // if there is already a match at this position, return null if (hasMatch(position)) return null; int x = (int)Math.pow(2.0, 6 - position.ordinal()); int value = encodedDigit + x; return digits.get(value); } public MatchDigit takeMatch(MatchPosition position) { // if there is no match at this position, return null if (!hasMatch(position)) return null; int x = (int)Math.pow(2.0, 6 - position.ordinal()); int value = encodedDigit - x; return digits.get(value); } public boolean hasMatch(MatchPosition position) { return ((encodedDigit >> (6 - position.ordinal())) & 1)== 1; } public MatchPosition[] getAllMatches() { List<MatchPosition> ret = new ArrayList<MatchPosition>(); for (MatchPosition position : MatchPosition.values()) { if (hasMatch(position)) ret.add(position); } return ret.toArray(new MatchPosition[0]); } public int value() { for (int i=0; i<digitEncodings.length; i++) { if (encodedDigit == digitEncodings[i]) return i; } throw new RuntimeException("can't find the value for encoded digit: " + encodedDigit); } public String toString() { String s = Integer.toBinaryString(encodedDigit); String zeros = "0000000"; s = zeros.substring(0, 7 - s.length()) + s; String ret = " " + rep(s.charAt(0), "-") + "\n"; ret += rep(s.charAt(1), "|") + " " + rep(s.charAt(2), "|") + "\n"; ret += " " + rep(s.charAt(3), "-") + "\n"; ret += rep(s.charAt(4), "|") + " " + rep(s.charAt(5), "|") + "\n"; ret += " " + rep(s.charAt(6), "-") + "\n"; return ret; } private String rep(char c, String d) { if (c == '1') return d; else return " "; } }
The toString() method is just to print out the digit.
A simple testcase is as follows:
import junit.framework.TestCase; public class MatchDigitTest extends TestCase { public void testToString() { for (int i=0; i<=9; i++) { MatchDigit md = new MatchDigit(i); System.out.println(md.toString()); System.out.println("value=" + md.value()); assertTrue(md.value() == i); } } public void testHasMatch() { MatchDigit md = new MatchDigit(9); for (MatchPosition p : MatchPosition.values()) { System.out.println(md.hasMatch(p)); if (p == MatchPosition.LOWERLEFT) assertTrue(!md.hasMatch(p)); else assertTrue(md.hasMatch(p)); } System.out.println("-----------------------------------------"); md = new MatchDigit(8); for (MatchPosition p : MatchPosition.values()) { System.out.println(md.hasMatch(p)); assertTrue(md.hasMatch(p)); } System.out.println("-----------------------------------------"); md = new MatchDigit(7); for (MatchPosition p : MatchPosition.values()) { System.out.println(md.hasMatch(p)); if (p == MatchPosition.TOP || p == MatchPosition.UPPERRIGHT || p == MatchPosition.LOWERRIGHT) assertTrue(md.hasMatch(p)); else assertTrue(!md.hasMatch(p)); } System.out.println("-----------------------------------------"); md = new MatchDigit(6); for (MatchPosition p : MatchPosition.values()) { System.out.println(md.hasMatch(p)); if (p == MatchPosition.UPPERRIGHT) assertTrue(!md.hasMatch(p)); else assertTrue(md.hasMatch(p)); } System.out.println("-----------------------------------------"); md = new MatchDigit(5); for (MatchPosition p : MatchPosition.values()) { System.out.println(md.hasMatch(p)); if (p == MatchPosition.UPPERRIGHT || p == MatchPosition.LOWERLEFT) assertTrue(!md.hasMatch(p)); else assertTrue(md.hasMatch(p)); } System.out.println("-----------------------------------------"); md = new MatchDigit(4); for (MatchPosition p : MatchPosition.values()) { System.out.println(md.hasMatch(p)); if (p == MatchPosition.TOP || p == MatchPosition.LOWERLEFT || p == MatchPosition.BOTTOM) assertTrue(!md.hasMatch(p)); else assertTrue(md.hasMatch(p)); } System.out.println("-----------------------------------------"); md = new MatchDigit(3); for (MatchPosition p : MatchPosition.values()) { System.out.println(md.hasMatch(p)); if (p == MatchPosition.UPPERLEFT || p == MatchPosition.LOWERLEFT) assertTrue(!md.hasMatch(p)); else assertTrue(md.hasMatch(p)); } System.out.println("-----------------------------------------"); md = new MatchDigit(2); for (MatchPosition p : MatchPosition.values()) { System.out.println(md.hasMatch(p)); if (p == MatchPosition.UPPERLEFT || p == MatchPosition.LOWERRIGHT) assertTrue(!md.hasMatch(p)); else assertTrue(md.hasMatch(p)); } System.out.println("-----------------------------------------"); md = new MatchDigit(1); for (MatchPosition p : MatchPosition.values()) { System.out.println(md.hasMatch(p)); if (p == MatchPosition.UPPERRIGHT || p == MatchPosition.LOWERRIGHT) assertTrue(md.hasMatch(p)); else assertTrue(!md.hasMatch(p)); } System.out.println("-----------------------------------------"); md = new MatchDigit(0); for (MatchPosition p : MatchPosition.values()) { System.out.println(md.hasMatch(p)); if (p == MatchPosition.MIDDLE) assertTrue(!md.hasMatch(p)); else assertTrue(md.hasMatch(p)); } } public void testSetMatch() { MatchDigit md = new MatchDigit(5); md = md.setMatch(MatchPosition.LOWERLEFT); System.out.println(md); } public void testTakeMatch() { MatchDigit md = new MatchDigit(9); md = md.takeMatch(MatchPosition.UPPERLEFT); System.out.println(md); } }
As they shows, these classes are no more than 200 lines. An average developer can digest them without much headache.
评论
发表评论
-
Spreadsheet Dependency graph
2010-11-19 03:00 2040In spreadsheets, such as Excel, ... -
Composition
2010-07-03 03:56 0I saw a post in the forum some ... -
Revisit again: 一道应聘智力题的编程求解, Einstein puzzle
2010-06-30 04:30 1566Continue on: http://jellyfish.i ... -
Domain Driven Design
2010-01-16 02:42 1175Having read a lot of discussion ... -
用java解决百度之星移动火柴的问题 part 2
2009-06-09 02:07 1554The next task is to evaluate a ... -
CEP
2007-07-11 02:54 1209http://www.eventstreamprocessin ...
相关推荐
JAVA拿火柴的小游戏,使用JDK编写,JAVA初学者的范例程序,有出错循环,
java 拿火柴游戏实验报告 里面含有源代码,可以运行,希望对您有所帮助
用C语言写的算法,四位数火柴棍移动其中一根变四位最大数。
次程序是用JAVA编写的火柴游戏。电脑有一定的智能。
这个小游戏是用java编写的,就是让电脑ramdom选择火柴根数,然后用户选择根数。
学校java课程设计做的数火柴小游戏的源代码 每行都有注释
程序随机产生20—50根火柴,由人与计算机轮流拿,每次拿的数量不超过3根,拿到最后一根为胜
人机对拿火柴的游戏程序 游戏过程要显示火柴总数 选择谁先拿
基于c++Bulider做的一款小游戏,移动火柴棍游戏,含整个工程文件
移动一根火柴使等式成立js版本
java编写的一个小游戏,可以用来当做java课程设计。
Swing Star 摇摆之星 Unity火柴人横版跳跃抓绳闯关项目源码C# 支持Unity版本2018.2.6f1及以上 描述 准备在 Android 和 iOS 上发布 摇摆之星来了! 捕捉、摆动、滑行,享受。 各种皮肤和主题。 特征 易于重新换肤 令...
移动一根火柴令等式成立(递归)
近日空虚,用java编写了一个火柴棍的小游戏。还是练练手。其中使用线程有些要改进,也想好了点,但现在很懒,不想写。例如线程中可以使用wait()方法,但本人没有用,这点可以加以改进。还有许多类似的情况。能力...
良心出品!...大学JAVA课程设计合集。这里有你想要的课程设计系统。亲测全部调试运行成功,有需要的下载吧! 压缩包包括:贪吃蛇,21点,火柴人,俄罗斯方块,拼图游戏等多款课程设计游戏!如有问题,请联系
利用U3d写的 移动其中一根火柴使等式成立的趣味游戏 源码
火柴人java源码火柴人游戏 介绍 一个用 Java 编写的关于角色的 2D 平台游戏:火柴人。 扮演火柴人,打败敌人并在穿越不同级别直到达到最终目标的同时获得能量提升。 程序运行说明: 转到您的终端并输入程序的路径,...
用java写的项目,免费分享给大家,比较适合新手入门学习,欢迎下载使用。用java写的项目,免费分享给大家,比较适合新手入门学习,欢迎下载使用。用java写的项目,免费分享给大家,比较适合新手入门学习,欢迎下载...
flash as2.0制作的小游戏智力移动火柴
java火柴游戏课程设计报告