refactor: BoardPath (TheAlgorithms#5431)

alxkm · alxkm · web-flow · commit f8ff6af893b4 · 2024-08-30T10:12:31.000+02:00
refactor: BoardPath

Co-authored-by: alxkm &lt;alx@alx.com&gt;
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/BoardPath.java b/src/main/java/com/thealgorithms/dynamicprogramming/BoardPath.java
@@ -1,46 +1,16 @@
 package com.thealgorithms.dynamicprogramming;
 
-/*
-* this is an important Algo in which
-* we have starting and ending of board and we have to reach
-* we have to count no. of ways
-* that help to reach end point i.e number by rolling dice
-* which have 1 to 6 digits
-
-Test Case:
-here target is 10
-
-int n=10;
-                startAlgo();
-                System.out.println(bpR(0,n));
-                System.out.println(endAlgo()+"ms");
-                int[] strg=new int [n+1];
-                startAlgo();
-                System.out.println(bpRS(0,n,strg));
-                System.out.println(endAlgo()+"ms");
-                startAlgo();
-                System.out.println(bpIS(0,n,strg));
-                System.out.println(endAlgo()+"ms");
-
-
-
- */
 public final class BoardPath {
     private BoardPath() {
     }
 
-    public static long startTime;
-    public static long endTime;
-
-    public static void startAlgo() {
-        startTime = System.currentTimeMillis();
-    }
-
-    public static long endAlgo() {
-        endTime = System.currentTimeMillis();
-        return endTime - startTime;
-    }
-
+    /**
+     * Recursive solution without memoization
+     *
+     * @param start - the current position
+     * @param end   - the target position
+     * @return the number of ways to reach the end from the start
+     */
     public static int bpR(int start, int end) {
         if (start == end) {
             return 1;
@@ -54,6 +24,14 @@ public static int bpR(int start, int end) {
         return count;
     }
 
+    /**
+     * Recursive solution with memoization
+     *
+     * @param curr - the current position
+     * @param end  - the target position
+     * @param strg - memoization array
+     * @return the number of ways to reach the end from the start
+     */
     public static int bpRS(int curr, int end, int[] strg) {
         if (curr == end) {
             return 1;
@@ -71,15 +49,23 @@ public static int bpRS(int curr, int end, int[] strg) {
         return count;
     }
 
+    /**
+     * Iterative solution with tabulation
+     *
+     * @param curr - the current position (always starts from 0)
+     * @param end  - the target position
+     * @param strg - memoization array
+     * @return the number of ways to reach the end from the start
+     */
     public static int bpIS(int curr, int end, int[] strg) {
         strg[end] = 1;
         for (int i = end - 1; i >= 0; i--) {
             int count = 0;
-            for (int dice = 1; dice <= 6 && dice + i < strg.length; dice++) {
+            for (int dice = 1; dice <= 6 && dice + i <= end; dice++) {
                 count += strg[i + dice];
             }
             strg[i] = count;
         }
-        return strg[0];
+        return strg[curr];
     }
 }
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/BoardPathTest.java b/src/test/java/com/thealgorithms/dynamicprogramming/BoardPathTest.java
@@ -0,0 +1,33 @@
+package com.thealgorithms.dynamicprogramming;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.stream.Stream;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+public class BoardPathTest {
+
+    @ParameterizedTest
+    @MethodSource("provideTestCases")
+    void testBpR(int start, int end, int expected) {
+        assertEquals(expected, BoardPath.bpR(start, end));
+    }
+
+    @ParameterizedTest
+    @MethodSource("provideTestCases")
+    void testBpRS(int start, int end, int expected) {
+        assertEquals(expected, BoardPath.bpRS(start, end, new int[end + 1]));
+    }
+
+    @ParameterizedTest
+    @MethodSource("provideTestCases")
+    void testBpIS(int start, int end, int expected) {
+        assertEquals(expected, BoardPath.bpIS(start, end, new int[end + 1]));
+    }
+
+    private static Stream<Arguments> provideTestCases() {
+        return Stream.of(Arguments.of(0, 10, 492), Arguments.of(0, 5, 16), Arguments.of(0, 6, 32), Arguments.of(0, 3, 4), Arguments.of(0, 1, 1));
+    }
+}
