文章/答案/技术大牛

发布

社区首页 >问答首页 >Java 8中的Euler项目“网格中最大的产品”(#11)

问Java 8中的Euler项目“网格中最大的产品”(#11)
EN

Code Review用户

提问于 2014-02-25 10:21:21

回答 2查看 1.6K关注 0票数 4

我已经针对以下问题提出了一个Java 8解决方案：

在下面的20×20网格中，沿着对角线的四个数字被标记为红色(这里是粗体)。08 02 22 97 38 15 00 40 00 75 04 05 07 78 12 50 77 77 49 49 99 40 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00stackine 81 49 31 73 55 79 14 29 93 71 71 67 67 88 30 03 49 13 36 36 52 95 23 04 60 11 42 69 24 68 56 01 32 71 37 37 36 91 22 71 51 63 89 41 54 40 40 28 66 33 80 24 47 32 60 99 03 45 75 53 78 3684 20 35 17 12 50 92 32 98 81 28 64 23 67 10 26 38 40 40 67 59 59 70 66 18 64 70 92 67 20 68 02 62 12 20 95 63 94 63 08 40 91 66 49 94 21 92 24 55 05 66 73 99 26 97 78 78 76 83 14 88 34 89 63 72 92 21 23 09 75 00 76 44 20 45 45 00 34 00 33 97 34 95 92 17 22 75 31 31 34 04 04 62 16 14 53 53 56 92 92 16 05 42 96 35 31 4755 58 88 24 00 54 24 36 29 85 57 66 86 56 00 48 35 35 71 89 07 05 44 37 44 21 58 51 54 17 58 19 80 81 68 94 47 69 73 92 13 86 52 77 04 74 89 55 40 04 08 83 97 99 16 97 32 32 16 26 26 79 33 27 98 66 88 68 87 57 62 20 03 03 33 67 46 55 12 32 63 53 69stackline 04 16 73 38 25 39 24 94 72 18 08 29 32 40 62 76 36 20 6936 41 72 30 23 88 34 62 99 82 67 85 74 04 36 16 16 20 73 29 78 31 90 01 31 49 71 48 81 16 23 57 05 54 01 70 71 51 54 54 16 16 16 92 33 48 43 52 01 89 19 48这些数字的乘积为26×63×78×14 = 1788696。在20×20网格中，四个相邻数在同一方向(向上、向下、左、右或对角)的最大乘积是什么？

我想就每件事发表意见：

public class Problem11 extends Problem<Integer> {
    /** The n of the n x n grid. */
    private final int n;

    /** The grid. */
    private final Grid grid;

    /**
     * Constructs this class.
     * 
     * @param n             The n of the n x n grid
     * @param gridString    The String representation of the grid
     */
    public Problem11(final int n, final String gridString) {
        this.n = n;
        this.grid = new Grid(n, gridString);
    }

    @Override
    public void run() {
        List<Integer> list = new ArrayList<>(n * n * 8);
        grid.forEach(cell -> processCell(list, cell));
        result = list.stream().mapToInt(x -> x).max().getAsInt();
    }

    /**
     * Processes a cell and adds the result to a list.
     * 
     * @param list  The list of results
     * @param cell  The cell to consider
     */
    private void processCell(final List<Integer> list, final Cell cell) {
        IntBinaryOperator sumOperator = (x, y) -> x * y;
        addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x + 1,  y -> y,     sumOperator));   //right
        addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x - 1,  y -> y,     sumOperator));   //left
        addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x,      y -> y + 1, sumOperator));   //top
        addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x,      y -> y - 1, sumOperator));   //down
        addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x + 1,  y -> y + 1, sumOperator));   //topright
        addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x - 1,  y -> y - 1, sumOperator));   //downleft
        addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x + 1,  y -> y - 1, sumOperator));   //downright
        addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x - 1,  y -> y + 1, sumOperator));   //topleft
    }

    /**
     * Adds an integer to the list if the OptionalInt is not empty.
     * 
     * @param list          The list to be added to
     * @param optionalInt   The OptionalInt
     * @return  The input list, with possibly the element appended
     */
    private List<Integer> addIfNotEmpty(final List<Integer> list, final OptionalInt optionalInt) {
        if (!optionalInt.isPresent()) {
            return list;
        }
        list.add(optionalInt.getAsInt());
        return list;
    }

    /**
     * Returns a calculation on the cell.
     * 
     * @param cell                  The starting cell
     * @param steps                 The number of steps to take to other cells
     * @param steppingXOperator     The operator to apply to go to the next cell on x
     * @param steppingYOperator     The operator to apply to go to the next cell on y
     * @param calculationOperator   The operator to apply to get the result
     * @return  An OptionalInt instance that is empty if and only if the calculation did not work
     */
    private OptionalInt calculationOnCell(final Cell cell, final int steps, final IntUnaryOperator steppingXOperator, final IntUnaryOperator steppingYOperator, final IntBinaryOperator calculationOperator) {
        int x = cell.x;
        int y = cell.y;
        int calculationResult = cell.value;

        for (int i = 0; i < steps; i++) {
            x = steppingXOperator.applyAsInt(x);
            y = steppingYOperator.applyAsInt(y);
            if (!grid.inBounds(x, y)) {
                return OptionalInt.empty();
            }
            calculationResult = calculationOperator.applyAsInt(calculationResult, grid.getCell(x, y).value);
        }

        return OptionalInt.of(calculationResult);
    }

    @Override
    public String getName() {
        return "Problem 11";
    }

    /**
     * Structure holding the cells.
     */
    private static class Grid implements Iterable<Cell> {
        /** The n of the n x n grid. **/
        private final int n;

        /** A double array holding the cells. **/
        private final Cell[][] cells;

        /**
         * Constructs the Grid.
         * 
         * @param n     The n of the n x n grid
         * @param input The String input for the grid
         */
        public Grid(final int n, final String input) {
            this.n = n;
            this.cells = createCellsFromString(input);
        }

        /**
         * Creates the Cell double array from the String input.
         * 
         * @param input The string nput
         * @return  The cell double array
         */
        private Cell[][] createCellsFromString(final String input) {
            Cell[][] returnCells = new Cell[n][n];
            String[] lines = input.split("\\n");
            for (int i = 0; i < lines.length; i++) {
                String[] words = lines[i].split(" ");
                for (int j = 0; j < words.length; j++) {
                    String word = words[j];
                    returnCells[i][j] = new Cell(i, j, Integer.parseInt(word));
                }
            }
            return returnCells;
        }

        /**
         * Checks if the x and y are in bounds.
         * 
         * @param x The x to be tested
         * @param y The y to be tested
         * @return  Whether x and y are in bounds
         */
        public boolean inBounds(final int x, final int y) {
            return (0 <= x && x < n && 0 <= y && y < n);
        }

        /**
         * Returns a cell based on the coordinates.
         * 
         * Throws an IllegalArgumentException if the x and y coordinates are not in bounds
         * 
         * @param x The x coordinate
         * @param y The y coordinate
         * @return  The cell corresponding to the coordinate
         */
        public Cell getCell(final int x, final int y) {
            if (!inBounds(x, y)) {
                throw new IllegalArgumentException("problems.Problem11.Grid.getCell: !inBounds(x, y): x = " + x + " / y = " + y);
            }
            return cells[x][y];
        }

        @Override
        public Iterator<Cell> iterator() {
            return new Iterator<Cell>() {
                /** The current x of the iterator. **/
                private int x = 0;

                /** The current y of the iterator. **/
                private int y = 0;

                @Override
                public boolean hasNext() {
                    return !(x == n && y == 0);
                }

                @Override
                public Cell next() {
                    Cell cell = cells[x][y];
                    advance();
                    return cell;
                }

                /**
                 * Advanced to the next element in the cell double array.
                 */
                private void advance() {
                    y++;
                    if (y == n) {
                        y = 0;
                        x++;
                    }
                }
            };
        }
    }

    /**
     * Structure holding the cell data.
     */
    private static class Cell {
        /** The x coordinate of the cell. **/
        public final int x;

        /** The y coordinate of the cell. **/
        public final int y;

        /** The value of the cell. **/
        public final int value;

        /**
         * Constructs the Cell.
         * 
         * @param x     The x coordinate of the cell
         * @param y     The y coordinate of the cell
         * @param value The value of the cell
         */
        public Cell(final int x, final int y, final int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }
    }
}

public abstract class Problem<T> implements Runnable {
    protected T result;

    public String getResult() {
        return String.valueOf(result);
    }

    abstract public String getName();
}

代码由以下内容调用：

Problem<?> problem11 = new Problem(20, 
"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n" +
"49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n" +
"81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n" +
"52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n" +
"22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n" +
"24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n" +
"32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n" +
"67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n" +
"24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n" +
"21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n" +
"78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n" +
"16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n" +
"86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n" +
"19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n" +
"04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n" +
"88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n" +
"04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n" +
"20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n" +
"20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n" +
"01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48");
problem11.run();
System.out.println(problem11.getResult());

我还有一个关于代码的问题：

是否有可能为最大求值编写代码，使其不使用存储(即。( list)，还是使用手写代码计算和？例如，我不知道用IntStream是否能做到这样的事情。

java

project-euler

lambda

回答 2

Code Review用户

回答已采纳

发布于 2014-02-25 11:19:43

您的代码看起来很棒，我可以看到您已经在其中投入了一些思想和时间。而且，您使用了一些我不知道的非常花哨的概念(这并不像我的Java非常生疏一样难)。然而，在我看来，它看起来有点过于设计了，所以我会尽量让事情变得更简单。

不要搅乱任何人的大脑

IntBinaryOperator sumOperator = (x, y) -> x * y;：将sum称为产品是您可能做的最混乱的事情之一:-)。

不要重复你自己 - 简单点，蠢货

在许多地方，事情本来可以用更直截了当的方式来完成。

第一个例子：addIfNotEmpty

您不需要让两个return在以下方面做相同的事情：

private List<Integer> addIfNotEmpty(final List<Integer> list, final OptionalInt optionalInt) {
    if (!optionalInt.isPresent()) {
        return list;
    }
    list.add(optionalInt.getAsInt());
    return list;
}

它可以很容易地写成：

private List<Integer> addIfNotEmpty(final List<Integer> list, final OptionalInt optionalInt) {
    if (optionalInt.isPresent()) {
        list.add(optionalInt.getAsInt());
    }
    return list;
}

第二个例子：n

Problem11类有一个private final int n和一个Grid。您的Grid有一个private final int n;和一个数组。Array有一个length属性。

你看到这里的图案了吗？好消息是，你在考虑正方形，因为如果我们这里有二维的话，可能会很混乱。

这显示了你的设计中的一些问题。也许您应该在需要的时候依赖length属性，也许您甚至不需要(cf 漏抽象)。

第三个例子：Cell

你的Cell是一个在Cells数组中包含一个值及其坐标的结构，这让我想起了“停止写作”演示文稿中的一个例子，我觉得我们并不需要它。

我现在没时间继续下去了。我将尝试编辑我的答案，并提供一个工作的代码。同时，由于您已经解决了Euler项目，我建议您查看张贴在板上的解决方案。它们也是学习算法、数学和编程风格的好方法。

票数 4

Code Review用户

发布于 2014-02-25 12:40:11

你的工作量是你需要做的两倍.您陷入了使代码遵循指令的“陷阱”，而没有考虑指令的含义。

在网格中：

 1,  2,  3,  4,
 5,  6,  7,  8,
 9, 10, 11, 12,
13, 14, 15, 16

从右到左的乘积将与从左到右的乘积相同，从上到下将与自下而上相同，等等。没有必要计算两个方向上的所有值。你只需要追踪最大的..。注释掉以下几行：

private void processCell(final List<Integer> list, final Cell cell) {
    IntBinaryOperator sumOperator = (x, y) -> x * y;
    addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x + 1,  y -> y,     sumOperator));   //right
    //addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x - 1,  y -> y,     sumOperator));   //left
    addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x,      y -> y + 1, sumOperator));   //top
    //addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x,      y -> y - 1, sumOperator));   //down
    addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x + 1,  y -> y + 1, sumOperator));   //topright
    //addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x - 1,  y -> y - 1, sumOperator));   //downleft
    //addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x + 1,  y -> y - 1, sumOperator));   //downright
    addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x - 1,  y -> y + 1, sumOperator));   //topleft
}

我同意其他意见，你把产品方法命名为加法和和法是很令人费解的.

票数 1

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/42744

复制

相似问题

问Java 8中的Euler项目“网格中最大的产品”(#11)
EN

回答 2

Code Review用户

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java 8中的Euler项目“网格中最大的产品”(#11)EN

回答 2

Code Review用户

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java 8中的Euler项目“网格中最大的产品”(#11)
EN