6
\$\begingroup\$

(This post has an continuation: Snail matrix in Java - version II.)

Inspired by this post, I decided to solve that problem in Java. The idea is to decide on an \$n \in \mathbb{N}\$, create a square matrix \$M_n = \mathbb{N}^{n \times n}, \$ and set the integers \$1, 2, \ldots, n^2\$ in \$M_n\$ such that they resemble a «snail pattern». For example, for \$n = 3,\$ \$M_3\$ is

1 2 3
8 9 4
7 6 5

com.github.coderodde.fun.snailmatrix.SnailMatrixGenerator.java:

package com.github.coderodde.fun.snailmatrix;

/**
 * This class provides a static method for generating snail matrices. A snail 
 * matrix is any square matrix with all the cell values {@code 1, 2, ..., n x n}
 * in a snail pattern. For example, for {@code n = 3}, the matrix will look like
 * <code>
 * 1 2 3
 * 8 9 4
 * 7 6 5
 * </code>
 */
public final class SnailMatrixGenerator {

    private final SnailMatrix matrix;
    private final IntPair currentCursor = new IntPair();
    private final IntPair[] deltas = 
              { 
                new IntPair(1, 0),
                new IntPair(0, 1),
                new IntPair(-1, 0),
                new IntPair(0, -1)
              };
    
    private int deltaIndex = 0;
    
    private SnailMatrixGenerator(final int n) {
        this.matrix = new SnailMatrix(n);
    }
    
    public static SnailMatrix generateSnailMatrix(final int n) {
        final SnailMatrixGenerator state = new SnailMatrixGenerator(n);
        int value = 1;
        
        while (true) {
            state.setValueAtCursor(value);
            
            if (value == n * n) {
                return state.matrix;
            }
            
            value++;
            state.moveCursorToNextLocation();
        }
    }
    
    private void setValueAtCursor(final int value) {
        matrix.set(currentCursor.x, 
                   currentCursor.y,
                   value);
    }
    
    private void moveCursorToNextLocation() {
        final int saveX = currentCursor.x;
        final int saveY = currentCursor.y;
        
        while (true) {
            final int x = saveX + deltas[deltaIndex].x;
            final int y = saveY + deltas[deltaIndex].y;
        
            if (checkCurrentCursorIsValid(x, y)) {
                currentCursor.x = x;
                currentCursor.y = y;
                return;
            }
            
            getNextCursorDirection();
        }
    }
    
    private boolean checkCurrentCursorIsValid(final int x, final int y) {
        final int n = matrix.getWidth();
        
        if (x == -1 || x == n || y == -1 || y == n) {
            return false;
        }
        
        return matrix.get(x, y) == 0;
    }
    
    private void getNextCursorDirection() {
        if (deltaIndex == 3) {
            deltaIndex = 0;
        } else {
            deltaIndex++;
        }
    }
    
    public static void main(String[] args) {
        final int n = 3;
        final SnailMatrix matrix = SnailMatrixGenerator.generateSnailMatrix(n);
        System.out.println(matrix);
    }
    
    private static final class IntPair {
        IntPair(final int x, final int y) {
            this.x = x;
            this.y = y;
        }
        
        IntPair() {}
        
        int x;
        int y;
    }
}

com.github.coderodde.fun.snailmatrix.SnailMatrix.java:

package com.github.coderodde.fun.snailmatrix;

public final class SnailMatrix {
    
    private final int[][] data;
    
    SnailMatrix(final int n) {
        this.data = new int[n][n];
    }
    
    public int getWidth() {
        return data.length;
    }
    
    public int getCapacity() {
        return data.length * data.length;
    }
    
    public int get(final int x, final int y) {
        return data[y][x];
    }
    
    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();
        final int capacity = getCapacity();
        final int cellLength = Integer.toString(capacity).length();
        final String cellFormat = String.format("%%%dd ", cellLength);
        
        for (int y = 0; y < getWidth(); y++) {
            for (int x = 0; x < getWidth(); x++) {
                sb.append(String.format(cellFormat, get(x, y)));
            }
            
            sb.append("\n");
        }
        
        sb.deleteCharAt(sb.length() - 1); // Delete last newline character.
        return sb.toString();
    }
    
    void set(final int x, final int y, final int value) {
        data[y][x] = value;
    }
}

Typical output

For \$n = 10\$, the output is:

  1   2   3   4   5   6   7   8   9  10 
 36  37  38  39  40  41  42  43  44  11 
 35  64  65  66  67  68  69  70  45  12 
 34  63  84  85  86  87  88  71  46  13 
 33  62  83  96  97  98  89  72  47  14 
 32  61  82  95 100  99  90  73  48  15 
 31  60  81  94  93  92  91  74  49  16 
 30  59  80  79  78  77  76  75  50  17 
 29  58  57  56  55  54  53  52  51  18 
 28  27  26  25  24  23  22  21  20  19 

Critique request

As always, I would be glad to receive any commentary on my work here.

\$\endgroup\$
0

2 Answers 2

8
\$\begingroup\$

Expose behavior / Don't manipulate the internal state directly

Object-orientation is about exposing behavior (not data), defining methods that are tailored for the problem at hand, that are meant to ensure data integrity and enable reuse of logic.

Take a look at this method, and tell what's wrong with it.

private void moveCursorToNextLocation() {
    final int saveX = currentCursor.x;
    final int saveY = currentCursor.y;
    
    while (true) {
        final int x = saveX + deltas[deltaIndex].x;
        final int y = saveY + deltas[deltaIndex].y;
    
        if (checkCurrentCursorIsValid(x, y)) {
            currentCursor.x = x;
            currentCursor.y = y;
            return;
        }
        getNextCursorDirection();
    }
}

Did you notice currentCursor.x, currentCursor.y and then currentCursor.x = x, currentCursor.y = y?

You're manually controlling the state of a dumb type IntPair instead of leveraging the Object-oriented paradigm through introducing useful behavior and properly encapsulating the data.

Another example in the very same method:

... + deltas[deltaIndex].x; // deltas[deltaIndex][0]
... + deltas[deltaIndex].y; // deltas[deltaIndex][1]

It looks almost as the code dialing with a nested array on the right, isn't? Objects seem to be in play, but we don't gain a lot.

Would it be nicer from the reader's perspective to see something like this:

... + xDelta();
... + yDelta();

And on the inside, xDelta() and yDelta() can perfectly well operate with an array of integers int[][] instead of IntPair[].

Refactoring

Your SnailMatrixGenerator class has a lot of knowledge about SnailMatrix, since it knows how to traverse it. Meanwhile, the noun Generator in its name suggests that it should be responsible for instantiation of SnailMatrix, basically matrix factory. But there's nothing intricate (at least for now) in obtaining the instance of SnailMatrix to warrant the existence of a factory.

Populating the matrix is a different concern, and the matrix factory should not dial with it.

In my opinion, abstraction that possesses knowledge on how to traverse and populate SnailMatrix should reside rather inside the SnailMatrix as a private nested class, than on the outside.

This way we can hide mutating method set() of SnailMatrix by making it private (it would be still visible to the nested class), and also hide this class tasked with initialization.

Based on the responsibility of this class, it makes sense to call it Initializer.

To populate the matrix, Initializer features the following methods:

  • void set(int value) - initializes the element at the current position;
  • boolean hasNext() - returns true if current position points to the uninitialized element;
  • void next() - advances to the next position;

Here's how it might be implemented (deltas transformed into static field int[][] DIRECTIONS and deltaIndex became direction):

public class SnailMatrix {
    
    private final int[][] data;
    
    private SnailMatrix(int n) {
        this.data = new int[n][n];
    }
    
    public static SnailMatrix ofSize(int n) {
        var matrix = new SnailMatrix(n);
        var initializer = new MatrixInitializer(matrix);
        
        initialize(initializer);
        
        return matrix;
    }
    
    private static void initialize(MatrixInitializer initializer) {
        int value = 1;
        
        while (initializer.hasNext()) {
            initializer.set(value++);
            initializer.next();
        }
    }
    
    public int size() {
        return data.length;
    }
    
    public int get(final int x, final int y) {
        return data[y][x];
    }
    
    private void set(final int x, final int y, final int value) {
        data[y][x] = value;
    }
    
    // ...

    private static class MatrixInitializer {
        private static final int[][] DIRECTIONS =
            new int[][]{
                {1, 0}, {0, 1}, {-1, 0}, {0, -1}
            };
        private final SnailMatrix matrix;
        private int direction = 0;
        private int x;
        private int y;
        
        public MatrixInitializer(SnailMatrix matrix) {
            this.matrix = matrix;
        }
        
        public void set(int value) {
            matrix.set(x, y, value);
        }
        
        public boolean hasNext() {
            return  isValid(x, y)
                && !isInitialized();
        }
        
        private boolean isValid(int x, int y) {
            return x >= 0 && x < matrix.size()
                && y >= 0 && y < matrix.size();
        }
        
        private boolean isInitialized() {
            return isInitialized(x, y);
        }
        
        private boolean isInitialized(int x, int y) {
            return matrix.get(x, y) != 0;
        }
        
        private void next() {
            checkDirection();
            x += xDelta();
            y += yDelta();
        }
        
        private void checkDirection() {
            int nextX = x + xDelta();
            int nextY = y + yDelta();
            if (!isValid(nextX, nextY) || isInitialized(nextX, nextY)) {
                changeDirection();
            }
        }
        
        public int xDelta() {
            return DIRECTIONS[direction][0];
        }
        
        public int yDelta() {
            return DIRECTIONS[direction][1];
        }
        
        private void changeDirection() {
            direction = (direction + 1) % DIRECTIONS.length;
        }
    }
}

Avoid name parts that add no meaning

Avoid name parts that doesn't give new information about the code element.

Example:

private final IntPair currentCursor = new IntPair();

The expressiveness of the code would not suffer if we simply name it cursor.

Method name moveCursorToNextLocation can be shortened to moveCursor and still be informative. And when this method is being placed inside the class, solely task with traversal name next is sufficient to communicate its purpose.

Avoid magic numbers

private void getNextCursorDirection() {
    if (deltaIndex == 3) {
        // ...
}

3 is a "magic number", it should be deltas.length - 1 instead.

\$\endgroup\$
0
3
\$\begingroup\$

Advice I - Rename IntPair

I guess, the better name for IntPair would be IntCoordinate.

Advice II - Simplfiy moveCursorToNextLocation

private void moveCursorToNextLocation() {
    while (true) {
        final int x = currentCursor.x + deltas[deltaIndex].x;
        final int y = currentCursor.y + deltas[deltaIndex].y;
    
        if (checkCurrentCursorIsValid(x, y)) {
            currentCursor.x = x;
            currentCursor.y = y;
            return;
        }
        
        getNextCursorDirection();
    }
}

Summa summarum

All in all, I had this in mind: com.github.coderodde.fun.snailmatrix.SnailMatrixGenerator.java:

package com.github.coderodde.fun.snailmatrix;

/**
 * This class provides a static method for generating snail matrices. A snail 
 * matrix is any square matrix with all the cell values {@code 1, 2, ..., n x n}
 * in a snail pattern. For example, for {@code n = 3}, the matrix will look like
 * <code>
 * 1 2 3
 * 8 9 4
 * 7 6 5
 * </code>
 */
public final class SnailMatrixGenerator {

    private final SnailMatrix matrix;
    private final IntCoordinate currentCursor = new IntCoordinate();
    private final IntCoordinate[] deltas = 
              { 
                new IntCoordinate(1, 0),
                new IntCoordinate(0, 1),
                new IntCoordinate(-1, 0),
                new IntCoordinate(0, -1)
              };
    
    private int deltaIndex = 0;
    
    private SnailMatrixGenerator(final int n) {
        this.matrix = new SnailMatrix(n);
    }
    
    public static SnailMatrix generateSnailMatrix(final int n) {
        final SnailMatrixGenerator state = new SnailMatrixGenerator(n);
        int value = 1;
        
        while (true) {
            state.setValueAtCursor(value);
            
            if (value == n * n) {
                return state.matrix;
            }
            
            value++;
            state.moveCursorToNextLocation();
        }
    }
    
    private void setValueAtCursor(final int value) {
        matrix.set(currentCursor.x, 
                   currentCursor.y,
                   value);
    }
    
    private void moveCursorToNextLocation() {
        while (true) {
            final int x = currentCursor.x + deltas[deltaIndex].x;
            final int y = currentCursor.y + deltas[deltaIndex].y;
        
            if (checkCurrentCursorIsValid(x, y)) {
                currentCursor.x = x;
                currentCursor.y = y;
                return;
            }
            
            getNextCursorDirection();
        }
    }
    
    private boolean checkCurrentCursorIsValid(final int x, final int y) {
        final int n = matrix.getWidth();
        
        if (x == -1 || x == n || y == -1 || y == n) {
            return false;
        }
        
        return matrix.get(x, y) == 0;
    }
    
    private void getNextCursorDirection() {
        if (deltaIndex == 3) {
            deltaIndex = 0;
        } else {
            deltaIndex++;
        }
    }
    
    public static void main(String[] args) {
        final int n = 5;
        final SnailMatrix matrix = SnailMatrixGenerator.generateSnailMatrix(n);
        System.out.println(matrix);
    }
    
    private static final class IntCoordinate {
        IntCoordinate(final int x, final int y) {
            this.x = x;
            this.y = y;
        }
        
        IntCoordinate() {}
        
        int x;
        int y;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.