3
\$\begingroup\$

There are some exercises about islands and water. I have seen other solutions in Java, but they are developed in procedural style in one-two methods. I tried to develop an object-oriented solution with code reuse. I have never got code reviews before, so I would happy to see any suggestions to improve my code.


Exercise 1.

There is a beach with a ground configuration like

[ 1, 2, 3, 2, 3, 4, 5, 1, 4, 6, 7, 6, 7, 2, 3, 1 ]

A wave come from a sea to the left of the beach. Its height is 5, for example. Then the wave come back to the sea. In the beach's hollows we find trapped water. If the wave is higher than beach it covers the full beach and goes away to both directions.

Task: write a program for counting all trapped water on the whole beach.


Exercise 2.

There is an island with a ground configuration like

 [
  [ 5, 3, 4, 5 ],
  [ 6, 2, 1, 4 ],
  [ 3, 1, 1, 4 ],
  [ 8, 5, 4, 3 ]
 ]

A rain was many days. It filled by water every hollow in the island. Water can go away only to 4 directions: north, south, west, east.

Task: write a program for counting all trapped water in whole island. For example, the answer for a given configuration is 7.


At first, I developed the common class for a single column of land with water on it:

package trappedwater;

import java.util.Arrays;

public class LithosphereSection {

    /* Height is above mean sea level in each case */
    public final int groundHeight;
    private int waterHeight;

    public LithosphereSection(int _groundHeight) {
        this.groundHeight = _groundHeight;
        this.waterHeight = 0;
    }

    public void setWaterHeight(int _waterHeight) {
        this.waterHeight = _waterHeight;
    }

    public void extraWaterPourOff(LithosphereSection... neighborSections) {
        if (hasPrecipiceForWater(neighborSections)) {
            this.waterHeight = 0;
        } else {
            for (LithosphereSection neighbor : neighborSections) {
                int support = Integer.max(neighbor.waterHeight, neighbor.groundHeight);
                this.waterHeight = Integer.min(this.waterHeight, support);
            }
        }
    }

    private boolean hasPrecipiceForWater(LithosphereSection... neighborSections) {
        return neighborSections == null
                || neighborSections.length == 0
                || Arrays.asList(neighborSections).contains(null);
    }

    public int getTrappedWater() {
        int trappedWater = this.waterHeight - this.groundHeight;
        return (trappedWater > 0) ? trappedWater : 0;
    }
}

Then I solved the first exercise.

package trappedwater;

public class Beach {

    private final LithosphereSection[] litSections;
    private final int m; // alias to litSections.length

    public Beach(int[] _groundScheme) {
        this.m = _groundScheme.length;
        this.litSections = new LithosphereSection[this.m];
        for (int i = 0; i < this.m; i++) {
            this.litSections[i] = new LithosphereSection(_groundScheme[i]);
        }
    }

    public void takeWaveFromLeft(int _waveHeight) {
        boolean waveStillMoves = true;
        for (int i = 0; i < this.m; i++) {
            if (waveStillMoves) {
                if (_waveHeight > this.litSections[i].groundHeight) {
                    this.litSections[i].setWaterHeight(_waveHeight);
                } else {
                    waveStillMoves = false;
                }
            }
        }
    }

    public void extraWaterPourOff() {
        // Pour water on boarders
        this.litSections[0].extraWaterPourOff();
        this.litSections[this.m - 1].extraWaterPourOff();

        // Pour water to the left
        for (int i = 1; i < this.m - 1; i++) {
            this.litSections[i].extraWaterPourOff(this.litSections[i - 1]);
        }

        // Pour water to the right
        for (int i = this.m - 2; i > 0; i--) {
            this.litSections[i].extraWaterPourOff(this.litSections[i + 1]);
        }
    }

    public int getTrappedWater() {
        int sumWater = 0;
        for (LithosphereSection litSection : this.litSections) {
            sumWater += litSection.getTrappedWater();
        }
        return sumWater;
    }

    public void dry() {
        for (int i = 0; i < this.m; i++) {
            this.litSections[i].setWaterHeight(0);
        }
    }
}

And the second one

package trappedwater;

public class Island {

    private final LithosphereSection[][] litSections;
    private final int n; // rows
    private final int m; // columns
    private int highestGround;

    public Island(int[][] _groundScheme) {
        this.n = _groundScheme.length;
        this.m = _groundScheme[0].length;

        this.litSections = new LithosphereSection[this.n][this.m];
        this.highestGround = _groundScheme[0][0];
        for (int i = 0; i < this.n; i++) {
            for (int j = 0; j < this.m; j++) {
                this.litSections[i][j] = new LithosphereSection(_groundScheme[i][j]);
                this.highestGround = Integer.max(this.highestGround, _groundScheme[i][j]);
            }
        }
    }

    public void overfillByWater() {
        for (int i = 0; i < this.n; i++) {
            for (int j = 0; j < this.m; j++) {
                this.litSections[i][j].setWaterHeight(this.highestGround);
            }
        }
    }

    public void extraWaterPourOff() {
        pourOffBoarders();
        boolean countOfPuddlesChanges = true;
        while (countOfPuddlesChanges) {
            int countOfPuddlesBefore = getTrappedWater();
            pourOffToNorthLeft();
            pourOffToSouthRight();
            countOfPuddlesChanges = (getTrappedWater() != countOfPuddlesBefore);
        }
    }

    private void pourOffBoarders() {
        for (int i = 0; i < this.n; i++) {
            for (int j = 0; j < this.m; j++) {
                boolean isBorder = (i == 0) || (i == this.n - 1) || (j == 0) || (j == this.m - 1);
                if (isBorder) {
                    this.litSections[i][j].extraWaterPourOff();
                }
            }
        }
    }

    private void pourOffToNorthLeft() {
        for (int i = 1; i < this.n - 1; i++) {
            for (int j = 1; j < this.m - 1; j++) {
               this.litSections[i][j].extraWaterPourOff(
                        this.litSections[i][j - 1],
                        this.litSections[i - 1][j]
               );
            }
        }
    }

    private void pourOffToSouthRight() {
        for (int i = this.n - 2; i > 0; i--) {
            for (int j = this.m - 2; j > 0; j--) {
                this.litSections[i][j].extraWaterPourOff(
                        this.litSections[i][j + 1],
                        this.litSections[i + 1][j]
                );
            }
        }
    }

    public int getTrappedWater() {
        int sumWater = 0;
        for (int i = 0; i < this.n; i++) {
            for (int j = 0; j < this.m; j++) {
                sumWater += this.litSections[i][j].getTrappedWater();
            }
        }
        return sumWater;
    }
}

Finally I made 3 classes with JUnit5 tests:

package trappedwater;

import static org.junit.jupiter.api.Assertions.*;

import org.junit.jupiter.api.BeforeAll;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class LithosphereSectionTest {

    static LithosphereSection testLitSection;

    @BeforeAll
    static void setUpBeforeClass() throws Exception {
        testLitSection = new LithosphereSection(5);
    }

    @BeforeEach
    void setUp() throws Exception {
        testLitSection.setWaterHeight(10);
    }

    @Test
    void test01() {
        assertEquals(5, testLitSection.getTrappedWater());
    }

    @Test
    void test02() {
        LithosphereSection litSection2 = new LithosphereSection(7);
        LithosphereSection litSection3 = new LithosphereSection(8);
        LithosphereSection litSection4 = new LithosphereSection(6);
        litSection4.setWaterHeight(7);

        testLitSection.extraWaterPourOff(litSection2, litSection3, litSection4);
        assertEquals(2, testLitSection.getTrappedWater());
    }

    @Test
    void test03() {
        testLitSection.extraWaterPourOff();
        assertEquals(0, testLitSection.getTrappedWater());
    }

    @Test
    void test04() {
        LithosphereSection[] sections = null;
        testLitSection.extraWaterPourOff(sections);
        assertEquals(0, testLitSection.getTrappedWater());
    }

    @Test
    void test05() {
        LithosphereSection litSection2 = null;
        testLitSection.extraWaterPourOff(litSection2);
        assertEquals(0, testLitSection.getTrappedWater());
    }
}

package trappedwater;

import static org.junit.jupiter.api.Assertions.*;

import org.junit.jupiter.api.BeforeAll;
import org.junit.jupiter.api.Test;

class BeachTest {

    static Beach beach;

    @BeforeAll
    static void setUpBeforeClass() throws Exception {
        int[] groundScheme = new int[] { 1, 2, 3, 2, 3, 4, 5, 1, 4, 6, 7, 6, 7, 2, 3, 1 };
        beach = new Beach(groundScheme);
    }

    private int run(int waveHeight) {
        beach.dry();
        beach.takeWaveFromLeft(waveHeight);
        beach.extraWaterPourOff();
        return beach.getTrappedWater();
    }

    @Test
    void test() {
        assertEquals(0, run(1));
        assertEquals(0, run(2));
        assertEquals(0, run(3));
        assertEquals(1, run(4));
        assertEquals(1, run(5));
        assertEquals(6, run(6));
        assertEquals(6, run(7));
        assertEquals(8, run(8));
        assertEquals(8, run(9));
    }
}

package trappedwater;

import static org.junit.jupiter.api.Assertions.*;

import org.junit.jupiter.api.Test;

class IslandTest {

    private int run(int[][] _groundScheme) {
        Island island = new Island(_groundScheme);
        island.overfillByWater();
        island.extraWaterPourOff();
        return island.getTrappedWater();
    }

    @Test
    void test01() {
        int[][] groundScheme = new int[][] {
            { 5, 3, 4, 5 },
            { 6, 2, 1, 4 },
            { 3, 1, 1, 4 },
            { 8, 5, 4, 3 }
        };
        assertEquals(7, run(groundScheme));
    }

    @Test
    void test02() {
        int[][] groundScheme = new int[][] {
            { 8, 6, 8, 8 },
            { 8, 2, 2, 4 },
            { 8, 2, 2, 8 },
            { 8, 8, 8, 8 }
        };
        assertEquals(8, run(groundScheme));
    }
}

Edited

These are 2 different challenges. Someone can offer to make 2 different questions. But I think I found a universal solution for family of problems. The challenges seems to be different, but solutions are identical for me. For example, here is a new challenge.


We have an island:

[
 [ 3, 3, 4, 5, 2 ],
 [ 6, 2, 1, 4, 4 ],
 [ 3, 1, 7, 4, 6 ],
 [ 4, 5, 4, 3, 2 ],
 [ 2, 3, 5, 2, 3 ]
]

Winter was cold. The island is covered by snow layers:

[
 [ 0, 0, 0, 0, 0 ],
 [ 0, 1, 2, 0, 0 ],
 [ 0, 1, 4, 0, 0 ],
 [ 0, 0, 0, 0, 0 ],
 [ 0, 0, 0, 0, 0 ]
]

Summer come. Will melt water reach the ocean?


I would not change class LithosphereSection to solve this new challenge.

Or, we have a hexagonically divided map of island. Each lithosphere section can have up to 6 neighbors in this challenge. I would not change class LithosphereSection. LithosphereSection can have any amount of neighbors: 2 for 2D challenge, 4 for 3D quadratic challenge, 6 for 3D hexagonic challenge, 8 for 3D quadratic challenge with additional diagonal directions for water pouring. So, I think class LithosphereSection solves a family of similar problems, I wanted to show this.

\$\endgroup\$
  • \$\begingroup\$ Tests help reviewers tremendously when reviewing your code. If you have them you should definitely provide them. \$\endgroup\$ – AGirlHasNoName Dec 31 '18 at 17:03
  • \$\begingroup\$ These are 2 different challenges. Perhaps it would have been better to have asked 2 separate questions. \$\endgroup\$ – dfhwze Sep 8 at 7:09
  • 1
    \$\begingroup\$ @dfhwze, I've answered to you in footer of the question. It's just my own opinion, you may be right. \$\endgroup\$ – AMURWOLF Sep 9 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.