Optimize ice fill

2 files changed, 32 insertions, 84 deletions

diff --git a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java
index 166047b2..9b6e7b1f 100644
--- a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java
+++ b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java
@@ -124,127 +124,73 @@ public class IceFill extends DungeonPuzzle {
         Vector2ic start = new Vector2i(iceFillBoard.length - 1, iceFillBoard[0].length / 2);
         int count = iceFillBoard.length * iceFillBoard[0].length - Arrays.stream(iceFillBoard).mapToInt(Booleans::countTrue).sum();
 
-        List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, new ArrayList<>(List.of(start)));
+        List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, new ArrayList<>(List.of(start)), new HashSet<>(List.of(start)));
         if (newPath != null) {
             iceFillPath.clear();
             iceFillPath.addAll(newPath);
         }
     }
 
-    private List<Vector2ic> solveDfs(boolean[][] iceFillBoard, int count, List<Vector2ic> path) {
+    private List<Vector2ic> solveDfs(boolean[][] iceFillBoard, int count, List<Vector2ic> path, Set<Vector2ic> visited) {
         Vector2ic pos = path.get(path.size() - 1);
-        if (pos.x() == 0 && pos.y() == iceFillBoard[0].length / 2 && count == 0) {
-            return path;
+        if (count == 0) {
+            if (pos.x() == 0 && pos.y() == iceFillBoard[0].length / 2) {
+                return path;
+            } else {
+                return null;
+            }
         }
 
         Vector2ic newPos = pos.add(1, 0, new Vector2i());
-        if (newPos.x() < iceFillBoard.length && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) {
+        if (newPos.x() < iceFillBoard.length && !iceFillBoard[newPos.x()][newPos.y()] && !visited.contains(newPos)) {
             path.add(newPos);
-            List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, path);
+            visited.add(newPos);
+            List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, path, visited);
             if (newPath != null) {
                 return newPath;
-            } else {
-                path.remove(path.size() - 1);
             }
+            path.remove(path.size() - 1);
+            visited.remove(newPos);
         }
 
         newPos = pos.add(-1, 0, new Vector2i());
-        if (newPos.x() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) {
+        if (newPos.x() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !visited.contains(newPos)) {
             path.add(newPos);
-            List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, path);
+            visited.add(newPos);
+            List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, path, visited);
             if (newPath != null) {
                 return newPath;
-            } else {
-                path.remove(path.size() - 1);
             }
+            path.remove(path.size() - 1);
+            visited.remove(newPos);
         }
 
         newPos = pos.add(0, 1, new Vector2i());
-        if (newPos.y() < iceFillBoard[0].length && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) {
+        if (newPos.y() < iceFillBoard[0].length && !iceFillBoard[newPos.x()][newPos.y()] && !visited.contains(newPos)) {
             path.add(newPos);
-            List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, path);
+            visited.add(newPos);
+            List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, path, visited);
             if (newPath != null) {
                 return newPath;
-            } else {
-                path.remove(path.size() - 1);
             }
+            path.remove(path.size() - 1);
+            visited.remove(newPos);
         }
 
         newPos = pos.add(0, -1, new Vector2i());
-        if (newPos.y() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) {
+        if (newPos.y() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !visited.contains(newPos)) {
             path.add(newPos);
-            List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, path);
-            if (newPath != null) {
-                return newPath;
-            } else {
-                path.remove(path.size() - 1);
-            }
-        }
-
-        return null;
-    }
-
-    /*
-    void solve(boolean[][] iceFillBoard, List<Vector2ic> iceFillPath) {
-        Vector2ic start = new Vector2i(iceFillBoard.length - 1, iceFillBoard[0].length / 2);
-        int count = iceFillBoard.length * iceFillBoard[0].length - Arrays.stream(iceFillBoard).mapToInt(Booleans::countTrue).sum();
-
-        Vector2ic[] newPath = solveDfs(iceFillBoard, count - 1, new Vector2ic[]{start});
-        if (newPath != null) {
-            iceFillPath.clear();
-            iceFillPath.addAll(Arrays.asList(newPath));
-        }
-    }
-
-    private Vector2ic[] solveDfs(boolean[][] iceFillBoard, int count, Vector2ic[] path) {
-        Vector2ic pos = path[path.length - 1];
-        if (pos.x() == 0 && pos.y() == iceFillBoard[0].length / 2 && count == 0) {
-            return path;
-        }
-
-        Vector2ic newPos = pos.add(1, 0, new Vector2i());
-        if (newPos.x() < iceFillBoard.length && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) {
-            Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1);
-            newPath[path.length] = newPos;
-            newPath = solveDfs(iceFillBoard, count - 1, newPath);
-            if (newPath != null) {
-                return newPath;
-            }
-        }
-
-        newPos = pos.add(-1, 0, new Vector2i());
-        if (newPos.x() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) {
-            Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1);
-            newPath[path.length] = newPos;
-            newPath = solveDfs(iceFillBoard, count - 1, newPath);
-            if (newPath != null) {
-                return newPath;
-            }
-        }
-
-        newPos = pos.add(0, 1, new Vector2i());
-        if (newPos.y() < iceFillBoard[0].length && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) {
-            Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1);
-            newPath[path.length] = newPos;
-            newPath = solveDfs(iceFillBoard, count - 1, newPath);
-            if (newPath != null) {
-                return newPath;
-            }
-        }
-
-        newPos = pos.add(0, -1, new Vector2i());
-        if (newPos.y() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) {
-            Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1);
-            newPath[path.length] = newPos;
-            newPath = solveDfs(iceFillBoard, count - 1, newPath);
+            visited.add(newPos);
+            List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, path, visited);
             if (newPath != null) {
                 return newPath;
             }
+            path.remove(path.size() - 1);
+            visited.remove(newPos);
         }
 
         return null;
     }
-     */
 
     @Override
     public void render(WorldRenderContext context) {
diff --git a/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java b/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java
index 511d1148..a3cbb93f 100644
--- a/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java
+++ b/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java
@@ -1,6 +1,8 @@
 package de.hysky.skyblocker.skyblock.dungeon.puzzle;
 
+import org.joml.Vector2i;
 import org.joml.Vector2ic;
+import org.junit.jupiter.api.Assertions;
 import org.junit.jupiter.api.Test;
 
 import java.util.ArrayList;
@@ -21,7 +23,7 @@ public class IceFillTest {
     @Test
     void testIceFillSolve() {
         IceFill.INSTANCE.solve(iceFillBoard, iceFillPath);
-        System.out.println(iceFillPath);
-        System.out.println(iceFillPath.size());
+        List<Vector2ic> expectedIceFillPath = List.of(new Vector2i(6, 3), new Vector2i(5, 3), new Vector2i(4, 3), new Vector2i(3, 3), new Vector2i(3, 2), new Vector2i(4, 2), new Vector2i(5, 2), new Vector2i(6, 2), new Vector2i(6, 1), new Vector2i(5, 1), new Vector2i(5, 0), new Vector2i(4, 0), new Vector2i(4, 1), new Vector2i(3, 1), new Vector2i(3, 0), new Vector2i(2, 0), new Vector2i(1, 0), new Vector2i(0, 0), new Vector2i(0, 1), new Vector2i(1, 1), new Vector2i(2, 1), new Vector2i(2, 2), new Vector2i(1, 2), new Vector2i(1, 3), new Vector2i(1, 4), new Vector2i(1, 5), new Vector2i(2, 5), new Vector2i(3, 5), new Vector2i(3, 4), new Vector2i(4, 4), new Vector2i(5, 4), new Vector2i(6, 4), new Vector2i(6, 5), new Vector2i(6, 6), new Vector2i(5, 6), new Vector2i(5, 5), new Vector2i(4, 5), new Vector2i(4, 6), new Vector2i(3, 6), new Vector2i(2, 6), new Vector2i(1, 6), new Vector2i(0, 6), new Vector2i(0, 5), new Vector2i(0, 4), new Vector2i(0, 3));
+        Assertions.assertEquals(expectedIceFillPath, iceFillPath);
     }
 }