Skip to content

Commit 7887876

Browse files
andrerfcsantosandrerfcsantos
authored
Add POV exercise (exercism#2264)
1 parent 8c4d423 commit 7887876

10 files changed

Lines changed: 647 additions & 0 deletions

File tree

‎config.json‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1895,6 +1895,20 @@
18951895
"difficulty": 7
18961896
},
18971897
{
1898+
"slug": "pov",
1899+
"name": "POV",
1900+
"uuid": "cae26d37-2977-42c4-af10-b6bb83adef19",
1901+
"practices": [],
1902+
"prerequisites": [
1903+
"strings",
1904+
"conditionals-if",
1905+
"lists",
1906+
"for-loops",
1907+
"maps"
1908+
],
1909+
"difficulty": 8
1910+
},
1911+
{
18981912
"slug": "ledger",
18991913
"name": "Ledger",
19001914
"uuid": "6597548e-176d-49c6-be33-789f4c43867a",

‎exercises/practice/pov/.docs/instructions.append.md‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
# Instructions append
2+
3+
## Implementation Notes
4+
5+
Tree object have two attributes:
6+
- `String` label
7+
- `List<Tree>` children
8+
9+
The test program creates trees by repeated application of
10+
`Tree.of` builder function. For example, the statement
11+
12+
```java
13+
Tree tree = Tree.of("a", List.of(Tree.of("b"), Tree.of("c", List.of(Tree.of("d")))));
14+
```
15+
16+
constructs the following tree:
17+
18+
```text
19+
"a"
20+
|
21+
-------
22+
| |
23+
"b" "c"
24+
|
25+
"d"
26+
```
27+
28+
You can assume that there will be no duplicate values in test trees.
29+
30+
---
31+
32+
The methods `FromPov` and `PathTo` are the interesting part of the exercise.
33+
34+
Method `FromPov` takes a string argument `from` which specifies a node in the
35+
tree via its value. It should return a tree with the value `from` in the root.
36+
You can modify the original tree and return it or create a new tree and return
37+
that. If you return a new tree you are free to consume or destroy the original
38+
tree. Of course, it's nice to leave it unmodified.
39+
40+
Method `PathTo` takes two string arguments `from` and `to` which specify two
41+
nodes in the tree via their values. It should return the shortest path in the
42+
tree from the first to the second node.
43+
44+
45+
## Exception messages
46+
47+
Sometimes it is necessary to [throw an exception](https://docs.oracle.com/javase/tutorial/essential/exceptions/throwing.html).
48+
When you do this, you should always include a **meaningful error message** to indicate what the source of the error is.
49+
This makes your code more readable and helps significantly with debugging.
50+
51+
This particular exercise requires that you use the [throw keyword](https://docs.oracle.com/javase/tutorial/essential/exceptions/throwing.html)
52+
to "throw" multiple `UnsupportedOperationException` if the `Tree()` class is passed a tree that cannot be reoriented, or a path cannot be found between a `start node` and an `end node`.
53+
The tests will only pass if you both `throw` the `exception` and include a message with it.
54+
55+
To throw a `UnsupportedOperationException` with a message, write the message as an argument to the `exception` type:
56+
57+
```java
58+
// when a tree cannot be oriented to a new node POV
59+
throw new UnsupportedOperationException("Tree could not be reoriented");
60+
61+
// when a path cannot be found between a start and end node on the tree.
62+
throw new UnsupportedOperationException("No path found");
63+
```

‎exercises/practice/pov/.docs/instructions.md‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
# Instructions
2+
3+
Reparent a tree on a selected node.
4+
5+
A [tree][wiki-tree] is a special type of [graph][wiki-graph] where all nodes are connected but there are no cycles.
6+
That means, there is exactly one path to get from one node to another for any pair of nodes.
7+
8+
This exercise is all about re-orientating a tree to see things from a different point of view.
9+
For example family trees are usually presented from the ancestor's perspective:
10+
11+
```text
12+
+------0------+
13+
| | |
14+
+-1-+ +-2-+ +-3-+
15+
| | | | | |
16+
4 5 6 7 8 9
17+
```
18+
19+
But there is no inherent direction in a tree.
20+
The same information can be presented from the perspective of any other node in the tree, by pulling it up to the root and dragging its relationships along with it.
21+
So the same tree from 6's perspective would look like:
22+
23+
```text
24+
6
25+
|
26+
+-----2-----+
27+
| |
28+
7 +-----0-----+
29+
| |
30+
+-1-+ +-3-+
31+
| | | |
32+
4 5 8 9
33+
```
34+
35+
This lets us more simply describe the paths between two nodes.
36+
So for example the path from 6-9 (which in the first tree goes up to the root and then down to a different leaf node) can be seen to follow the path 6-2-0-3-9.
37+
38+
This exercise involves taking an input tree and re-orientating it from the point of view of one of the nodes.
39+
40+
[wiki-graph]: https://en.wikipedia.org/wiki/Tree_(graph_theory)
41+
[wiki-tree]: https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)

‎exercises/practice/pov/.meta/config.json‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
{
2+
"authors": [
3+
"aky91"
4+
],
5+
"contributors": [
6+
],
7+
"files": {
8+
"solution": [
9+
"src/main/java/Tree.java"
10+
],
11+
"test": [
12+
"src/test/java/PovTest.java"
13+
],
14+
"example": [
15+
".meta/src/reference/java/Tree.java"
16+
]
17+
},
18+
"title": "POV",
19+
"blurb": "Reparent a graph on a selected node.",
20+
"source": "Adaptation of exercise from 4clojure",
21+
"source_url": "https://www.4clojure.com/"
22+
}

‎exercises/practice/pov/.meta/src/reference/java/Tree.java‎

Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,141 @@
1+
import java.util.*;
2+
3+
class Tree {
4+
private final String label;
5+
private final List<Tree> children;
6+
private Map<String, List<String>> graph;
7+
8+
public Tree(String label) {
9+
this(label, new ArrayList<>());
10+
}
11+
12+
public Tree(String label, List<Tree> children) {
13+
this.label = label;
14+
this.children = children;
15+
}
16+
17+
public static Tree of(String label) {
18+
return new Tree(label);
19+
}
20+
21+
public static Tree of(String label, List<Tree> children) {
22+
return new Tree(label, children);
23+
}
24+
25+
@Override
26+
public boolean equals(Object o) {
27+
if (this == o) {
28+
return true;
29+
}
30+
if (o == null || getClass() != o.getClass()) {
31+
return false;
32+
}
33+
Tree tree = (Tree) o;
34+
return label.equals(tree.label)
35+
&& children.size() == tree.children.size()
36+
&& children.containsAll(tree.children)
37+
&& tree.children.containsAll(children);
38+
}
39+
40+
@Override
41+
public int hashCode() {
42+
return Objects.hash(label, children);
43+
}
44+
45+
@Override
46+
public String toString() {
47+
return "Tree{" + label +
48+
", " + children +
49+
"}";
50+
}
51+
52+
public Tree fromPov(String fromNode) {
53+
if (this.graph == null) {
54+
this.graph = new HashMap<>();
55+
convertToGraph(this.label, this.children);
56+
}
57+
58+
if (!this.graph.containsKey(fromNode)) {
59+
throw new UnsupportedOperationException("Tree could not be reoriented");
60+
}
61+
62+
return reconstructTreeFromNode(fromNode, "emptyParentForRoot");
63+
}
64+
65+
public List<String> pathTo(String fromNode, String toNode) {
66+
if (this.graph == null) {
67+
this.graph = new HashMap<>();
68+
convertToGraph(this.label, this.children);
69+
}
70+
71+
if (!this.graph.containsKey(fromNode) || !this.graph.containsKey(toNode)) {
72+
throw new UnsupportedOperationException("No path found");
73+
}
74+
75+
Tree root = fromPov(fromNode);
76+
77+
List<String> path = new ArrayList<>();
78+
generatePath(root, toNode, path);
79+
return path;
80+
}
81+
82+
/**
83+
* Method to convert tree to graph recursively and populate the private class attribute graph
84+
*
85+
* @param label label String of root node
86+
* @param children children list of root node
87+
*/
88+
private void convertToGraph(String label, List<Tree> children) {
89+
this.graph.putIfAbsent(label, new ArrayList<>());
90+
if (children != null) {
91+
for (Tree child : children) {
92+
this.graph.get(label).add(child.label);
93+
this.graph.putIfAbsent(child.label, new ArrayList<>());
94+
this.graph.get(child.label).add(label);
95+
convertToGraph(child.label, child.children);
96+
}
97+
}
98+
}
99+
100+
/**
101+
* Method to create Tree object recursively with node as root.
102+
* It utilizes the previously populated class attribute graph
103+
*
104+
* @param node string label of current node
105+
* @param parent string label of parent node of current node
106+
* @return Tree object of root node
107+
*/
108+
private Tree reconstructTreeFromNode(String node, String parent) {
109+
List<Tree> children = new ArrayList<>();
110+
for (String nbr : this.graph.get(node)) {
111+
if (!nbr.equals(parent)) {
112+
children.add(reconstructTreeFromNode(nbr, node));
113+
}
114+
}
115+
return Tree.of(node, children);
116+
}
117+
118+
/**
119+
* Method to traverse the tree and populate the path object
120+
*
121+
* @param node Root node Tree object
122+
* @param target String label of target node
123+
* @param path List of String, to be populated
124+
* @return boolean value representing if path was found in the subtree
125+
*/
126+
private boolean generatePath(Tree node, String target, List<String> path) {
127+
path.add(node.label);
128+
if (node.label.equals(target)) {
129+
return true;
130+
}
131+
132+
for (Tree child : node.children) {
133+
if (generatePath(child, target, path)) {
134+
return true;
135+
}
136+
}
137+
138+
path.remove(path.size() - 1);
139+
return false;
140+
}
141+
}

‎exercises/practice/pov/.meta/tests.toml‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
# This is an auto-generated file.
2+
#
3+
# Regenerating this file via `configlet sync` will:
4+
# - Recreate every `description` key/value pair
5+
# - Recreate every `reimplements` key/value pair, where they exist in problem-specifications
6+
# - Remove any `include = true` key/value pair (an omitted `include` key implies inclusion)
7+
# - Preserve any other key/value pair
8+
#
9+
# As user-added comments (using the # character) will be removed when this file
10+
# is regenerated, comments can be added via a `comment` key.
11+
12+
[1b3cd134-49ad-4a7d-8376-7087b7e70792]
13+
description = "Reroot a tree so that its root is the specified node. -> Results in the same tree if the input tree is a singleton"
14+
15+
[0778c745-0636-40de-9edd-25a8f40426f6]
16+
description = "Reroot a tree so that its root is the specified node. -> Can reroot a tree with a parent and one sibling"
17+
18+
[fdfdef0a-4472-4248-8bcf-19cf33f9c06e]
19+
description = "Reroot a tree so that its root is the specified node. -> Can reroot a tree with a parent and many siblings"
20+
21+
[cbcf52db-8667-43d8-a766-5d80cb41b4bb]
22+
description = "Reroot a tree so that its root is the specified node. -> Can reroot a tree with new root deeply nested in tree"
23+
24+
[e27fa4fa-648d-44cd-90af-d64a13d95e06]
25+
description = "Reroot a tree so that its root is the specified node. -> Moves children of the new root to same level as former parent"
26+
27+
[09236c7f-7c83-42cc-87a1-25afa60454a3]
28+
description = "Reroot a tree so that its root is the specified node. -> Can reroot a complex tree with cousins"
29+
30+
[f41d5eeb-8973-448f-a3b0-cc1e019a4193]
31+
description = "Reroot a tree so that its root is the specified node. -> Errors if target does not exist in a singleton tree"
32+
33+
[9dc0a8b3-df02-4267-9a41-693b6aff75e7]
34+
description = "Reroot a tree so that its root is the specified node. -> Errors if target does not exist in a large tree"
35+
36+
[02d1f1d9-428d-4395-b026-2db35ffa8f0a]
37+
description = "Given two nodes, find the path between them -> Can find path to parent"
38+
39+
[d0002674-fcfb-4cdc-9efa-bfc54e3c31b5]
40+
description = "Given two nodes, find the path between them -> Can find path to sibling"
41+
42+
[c9877cd1-0a69-40d4-b362-725763a5c38f]
43+
description = "Given two nodes, find the path between them -> Can find path to cousin"
44+
45+
[9fb17a82-2c14-4261-baa3-2f3f234ffa03]
46+
description = "Given two nodes, find the path between them -> Can find path not involving root"
47+
48+
[5124ed49-7845-46ad-bc32-97d5ac7451b2]
49+
description = "Given two nodes, find the path between them -> Can find path from nodes other than x"
50+
51+
[f52a183c-25cc-4c87-9fc9-0e7f81a5725c]
52+
description = "Given two nodes, find the path between them -> Errors if destination does not exist"
53+
54+
[f4fe18b9-b4a2-4bd5-a694-e179155c2149]
55+
description = "Given two nodes, find the path between them -> Errors if source does not exist"

‎exercises/practice/pov/build.gradle‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
apply plugin: "java"
2+
apply plugin: "eclipse"
3+
apply plugin: "idea"
4+
5+
// set default encoding to UTF-8
6+
compileJava.options.encoding = "UTF-8"
7+
compileTestJava.options.encoding = "UTF-8"
8+
9+
repositories {
10+
mavenCentral()
11+
}
12+
13+
dependencies {
14+
testImplementation "junit:junit:4.13"
15+
testImplementation "org.assertj:assertj-core:3.15.0"
16+
}
17+
18+
test {
19+
testLogging {
20+
exceptionFormat = 'full'
21+
showStandardStreams = true
22+
events = ["passed", "failed", "skipped"]
23+
}
24+
}

0 commit comments

Comments
 (0)