Skip to content

Commit 07fe86c

Browse files
javaConductorjavaConductor
committed
Initial commit
0 parents  commit 07fe86c

6 files changed

Lines changed: 214 additions & 0 deletions

File tree

‎.gitignore‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
# Project exclude paths
2+
/target/

‎pom.xml‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns="http://maven.apache.org/POM/4.0.0"
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
5+
<modelVersion>4.0.0</modelVersion>
6+
7+
<groupId>org.collins</groupId>
8+
<artifactId>filepath</artifactId>
9+
<version>1.0-SNAPSHOT</version>
10+
11+
<properties>
12+
<maven.compiler.source>11</maven.compiler.source>
13+
<maven.compiler.target>11</maven.compiler.target>
14+
</properties>
15+
16+
</project>

‎src/main/java/org/collins/FindPathApplication.java‎

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
package org.collins;
2+
3+
import org.collins.model.Point;
4+
5+
import java.util.ArrayList;
6+
import java.util.Arrays;
7+
import java.util.List;
8+
9+
public class FindPathApplication {
10+
11+
static PathFinder pathFinder = new PathFinder();
12+
13+
public static void main(String args[]) {
14+
15+
List<String> plane1 = new ArrayList<>();
16+
plane1.add(" ");
17+
plane1.add(" ");
18+
plane1.add(" ");
19+
plane1.add(" #########");
20+
plane1.add(" ");
21+
22+
List<String> plane2 = new ArrayList<>();
23+
plane2.add(" # ");
24+
plane2.add(" # ");
25+
plane2.add(" # ");
26+
plane2.add(" ");
27+
28+
List<String> plane3 = new ArrayList<>();
29+
plane3.add(" # ");
30+
plane3.add(" # #");
31+
plane3.add(" #");
32+
plane3.add(" ");
33+
plane3.add("# ##");
34+
plane3.add(" ");
35+
36+
testPlane(plane1);
37+
System.out.println("----------------------------------------");
38+
testPlane(plane2);
39+
System.out.println("----------------------------------------");
40+
testPlane(plane3);
41+
System.out.println("----------------------------------------");
42+
}
43+
static void testPlane(List<String> plane){
44+
45+
List<Point> result = pathFinder.findPath(plane);
46+
if (result != null){
47+
List<String> newPlane = printResultsPlane(plane, result);
48+
newPlane.stream()
49+
.forEach(row -> System.out.printf("|%s|\n", row ));
50+
}
51+
}
52+
53+
static void printResults(List<Point> results){
54+
results.stream()
55+
.forEach(point -> System.out.println(point));
56+
}
57+
58+
static List<String> printResultsPlane(List<String> plane, List<Point> results){
59+
List<String> newPlane = new ArrayList<>(plane.size());
60+
for (Point point : results) {
61+
StringBuilder sb = new StringBuilder(plane.get(point.getY()));
62+
sb.setCharAt(point.getX(), '*');
63+
//newPlane = Utils.append(newPlane, sb.toString());
64+
plane.set(point.getY(), sb.toString());
65+
}
66+
return plane;
67+
}
68+
}

‎src/main/java/org/collins/PathFinder.java‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package org.collins;
2+
3+
import org.collins.model.Point;
4+
5+
import java.util.List;
6+
import java.util.stream.Collectors;
7+
import java.util.stream.Stream;
8+
9+
public class PathFinder {
10+
11+
public List<Point> findPath(List<String> plane) {
12+
if (plane.isEmpty())
13+
return null;
14+
15+
Point start = new Point(0, 0);
16+
Point end = new Point(plane.get(0).length() - 1, plane.size() - 1);
17+
18+
return _findPath(plane, start, end, List.of());
19+
}
20+
21+
private List<Point> _findPath(List<String> plane, Point start, Point end, List<Point> path) {
22+
// base case
23+
if (start.equals(end)) {
24+
path.add(end);
25+
return path;
26+
}
27+
28+
if (start.getY() >= plane.size() || start.getX() >= plane.get(0).length()) {
29+
return null;
30+
}
31+
32+
// is this a dead end
33+
if (plane.get(start.getY()).charAt(start.getX()) == '#') {
34+
return null;
35+
}
36+
37+
///// recurse down and to the left
38+
39+
// add this location to the path
40+
List<Point> newPath = Utils.append(path, start);
41+
42+
Point right = new Point(start.getX() + 1, start.getY());
43+
Point down = new Point(start.getX(), start.getY() + 1);
44+
45+
// can we go down
46+
if (down.getY() < plane.size()) {
47+
List<Point> downResult = _findPath(plane, down, end, newPath);
48+
if (downResult != null) {
49+
return downResult;
50+
}
51+
}
52+
53+
// can we go right
54+
if (right.getX() < plane.get(0).length()) {
55+
List<Point> rightResult = _findPath(plane, right, end, newPath);
56+
return rightResult;
57+
}
58+
return null;
59+
}
60+
}

‎src/main/java/org/collins/Utils.java‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package org.collins;
2+
3+
import org.collins.model.Point;
4+
5+
import java.util.List;
6+
import java.util.stream.Collectors;
7+
import java.util.stream.Stream;
8+
9+
public class Utils {
10+
11+
public static <T> List<T> append(List<T> list, T newElement){
12+
return Stream.concat(list.stream(), Stream.of(newElement))
13+
.collect(Collectors.toList());
14+
}
15+
16+
//
17+
// public static <T> List<T> insert(List<T> list, int index, T newElement){
18+
//
19+
// return Stream.concat(list.stream(), Stream.of(newElement))
20+
// .collect(Collectors.toList());
21+
// }
22+
23+
24+
25+
}

‎src/main/java/org/collins/model/Point.java‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package org.collins.model;
2+
3+
4+
import java.util.Objects;
5+
6+
public class Point {
7+
int x,y;
8+
9+
public Point(int x, int y) {
10+
this.x = x;
11+
this.y = y;
12+
}
13+
14+
public int getX() {
15+
return x;
16+
}
17+
18+
public int getY() {
19+
return y;
20+
}
21+
22+
@Override
23+
public String toString() {
24+
return "Point{" +
25+
"x=" + x +
26+
", y=" + y +
27+
'}';
28+
}
29+
30+
@Override
31+
public boolean equals(Object o) {
32+
if (this == o) return true;
33+
if (o == null || getClass() != o.getClass()) return false;
34+
Point point = (Point) o;
35+
return x == point.x && y == point.y;
36+
}
37+
38+
@Override
39+
public int hashCode() {
40+
return Objects.hash(x, y);
41+
}
42+
43+
}

0 commit comments

Comments
 (0)