问基于启发式的8字谜状态线性冲突的计数
EN

Code Review用户

提问于 2014-03-15 01:49:59

回答 1查看 5.6K关注 0票数 7

需要找出8种状态的线性冲突，状态用int[9]表示，目标状态为{1,2,3,4,5,6,7,8,0}。线性冲突是，如果在一条线中，应该在这条线上的两个瓷砖被反转。

例如，在目标状态中，如果第一行为2, 1 ,3，则第一行为1,2,3，即由tiles 2和1造成的线性冲突。

我的代码很好用，但是太长了，太尴尬了。下面是：

public static int linearConflicts(int[] state) {
    ArrayList<Integer> row1 = new ArrayList<Integer>();
    ArrayList<Integer> row2 = new ArrayList<Integer>();
    ArrayList<Integer> row3 = new ArrayList<Integer>();
    ArrayList<Integer> column1 = new ArrayList<Integer>();
    ArrayList<Integer> column2 = new ArrayList<Integer>();
    ArrayList<Integer> column3 = new ArrayList<Integer>();
    int[] columnMarkers = new int[] { 0, 3, 6, 1, 4, 7, 2, 5, 8 };
    for (int i = 0; i < 9; i++) {
        if (i < 3) {
            row1.add(state[i]);
            column1.add(state[columnMarkers[i]]);
        } else if (i < 6) {
            row2.add(state[i]);
            column2.add(state[columnMarkers[i]]);
        } else {
            row3.add(state[i]);
            column3.add(state[columnMarkers[i]]);
        }
    }
    return row1Conflicts(row1) + row2Conflicts(row2) + row3Conflicts(row3)
            + column1Conflicts(column1) + column2Conflicts(column2)
            + column3Conflicts(column3);

}

public static int row1Conflicts(ArrayList<Integer> rowState) {
    int conflicts = 0;
    if (rowState.contains(1)) {
        if ((rowState.contains(2))
                && rowState.indexOf(1) > rowState.indexOf(2)) {
            conflicts++;
        }
        if ((rowState.contains(3))
                && rowState.indexOf(1) > rowState.indexOf(3)) {
            conflicts++;
        }

    }
    if (rowState.contains(2) && rowState.contains(3)
            && rowState.indexOf(2) > rowState.indexOf(3))
        conflicts++;
    return conflicts;
}

public static int row2Conflicts(ArrayList<Integer> rowState) {
    int conflicts = 0;
    if (rowState.contains(4)) {
        if ((rowState.contains(5))
                && rowState.indexOf(4) > rowState.indexOf(5)) {
            conflicts++;
        }
        if ((rowState.contains(6))
                && rowState.indexOf(4) > rowState.indexOf(6)) {
            conflicts++;
        }

    }
    if (rowState.contains(5) && rowState.contains(6)
            && rowState.indexOf(5) > rowState.indexOf(6))
        conflicts++;
    return conflicts;
}

public static int row3Conflicts(ArrayList<Integer> rowState) {
    int conflicts = 0;
    if (rowState.contains(7) && rowState.contains(8)
            && rowState.indexOf(7) > rowState.indexOf(8))
        conflicts++;
    return conflicts;
}

public static int column1Conflicts(ArrayList<Integer> columnState) {
    int conflicts = 0;
    if (columnState.contains(1)) {
        if ((columnState.contains(4))
                && columnState.indexOf(1) > columnState.indexOf(4)) {
            conflicts++;
        }
        if ((columnState.contains(7))
                && columnState.indexOf(1) > columnState.indexOf(7)) {
            conflicts++;
        }

    }
    if (columnState.contains(4) && columnState.contains(7)
            && columnState.indexOf(4) > columnState.indexOf(7))
        conflicts++;
    return conflicts;
}

public static int column2Conflicts(ArrayList<Integer> columnState) {
    int conflicts = 0;
    if (columnState.contains(2)) {
        if ((columnState.contains(5))
                && columnState.indexOf(2) > columnState.indexOf(5)) {
            conflicts++;
        }
        if ((columnState.contains(8))
                && columnState.indexOf(2) > columnState.indexOf(8)) {
            conflicts++;
        }

    }
    if (columnState.contains(5) && columnState.contains(8)
            && columnState.indexOf(5) > columnState.indexOf(8))
        conflicts++;
    return conflicts;
}

public static int column3Conflicts(ArrayList<Integer> columnState) {
    int conflicts = 0;
    if (columnState.contains(3) && columnState.contains(6)
            && columnState.indexOf(3) > columnState.indexOf(6))
        conflicts++;
    return conflicts;
}

有谁知道怎么做更短，更少笨拙？如果我继续这样做，我的代码将很难阅读。

java

algorithm

mathematics

matrix

数字工厂场景解决方案

帮助企业实现数字化、智能化，解决企业工厂内设备数据采集、设备指标分析、企业信息系统间数据孤岛打通、数据应用困难的问题

回答 1

Code Review用户

回答已采纳

发布于 2014-03-15 03:33:20

关键是要像疯了一样概括！

强迫您的代码处理任何方块谜题。
努力为行和列重用相同的代码。

附加提示：

使其面向对象，以减少参数传递杂波。
对行号和列号使用基于0的索引。
避免ArrayList -你的列表不会增加。数组具有更整洁的语法和更好的性能。

// Use Arrays.binarySearch() like ArrayList.indexOf()
import static java.util.Arrays.binarySearch;

public class Puzzle {
    public static enum Axis { ROW, COL };

    private int[] state;
    private int side;

    public Puzzle(int[] state) {
        this.state = state;
        this.side = (int)Math.sqrt(state.length);
        if (side * side != state.length) {
            throw new IllegalArgumentException("Puzzle must be square");
        }
    }

    /**
     * Returns the squares of the puzzle for a specified row or column.
     *
     * @param rc row or col number (0-based)
     */
    private int[] tuple(Axis dir, int rc) {
        int[] result = new int[this.side];
        switch (dir) {
          case ROW:
            System.arraycopy(this.state, rc * this.side, result, 0, this.side);
            break;
          case COL:
            for (int i = 0, j = rc; i < this.side; i++, j += this.side) {
                result[i] = this.state[j];
            }
            break;
        }
        return result;
    }

    /**
     * Returns the squares of the puzzle of this size as if it were in
     * its solved state for a specified row or column.
     *
     * @param rc row or col number (0-based)
     */
    private int[] idealTuple(Axis dir, int rc) {
        int[] result = new int[this.side];
        switch (dir) {
          case ROW:
            for (int i = 0, j = rc * this.side + 1; i < this.side; i++, j++) {
                result[i] = (j < this.state.length) ? j : 0;
            }
            break;
          case COL:
            for (int i = 0, j = this.side + rc + 1; i < this.side; i++, j += this.side) {
                result[i] = (j < this.state.length) ? j : 0;
            }
            break;
        }
        return result;
    }

    /**
     * Count inversions (linear conflicts) for a row or column.
     */
    public int inversions(Axis dir, int rc) {
        int[] have = this.tuple(dir, rc);
        int[] want = this.idealTuple(dir, rc);
        int inversions = 0;

        // For each pair of squares, if both numbers are supposed to be in this
        // tuple, and neither is 0 (blank)...
        for (int i = 1, iPos; i < this.side; i++) {
            if (have[i] != 0 && 0 <= (iPos = binarySearch(want, have[i]))) {
                for (int j = 0, jPos; j < i; j++) {
                    if (have[j] != 0 && 0 <= (jPos = binarySearch(want, have[j]))) {
                        // ... and are inverted, count it as a conflict.
                        if ((have[i] < have[j]) != (i < j)) {
                            inversions++;
                        }
                    }
                }
            }
        }
        return inversions;
    }

    public static void main(String[] args) {
        Puzzle p = new Puzzle(new int[] {
            3, 2, 1,
            4, 7, 5,
            8, 6, 0
        });
        System.out.printf("Row %d inversions = %d\n", 0, p.inversions(Axis.ROW, 0));
        System.out.printf("Row %d inversions = %d\n", 1, p.inversions(Axis.ROW, 1));
        System.out.printf("Row %d inversions = %d\n", 2, p.inversions(Axis.ROW, 2));
        System.out.printf("Col %d inversions = %d\n", 0, p.inversions(Axis.COL, 0));
        System.out.printf("Col %d inversions = %d\n", 1, p.inversions(Axis.COL, 1));
        System.out.printf("Col %d inversions = %d\n", 2, p.inversions(Axis.COL, 2));
    }
}