用java解决百度之星移动火柴的问题 part 1

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.

 

 

评论

3 楼 wodentt 2012-01-17  

....为什么楼主都英文的博客

2 楼 cowboycool 2009-08-21  

看起来很清晰。

1 楼 epanthere 2009-06-09  

讲的非常清楚，代码写的真漂亮