Skip to content

Commit 137e182

Browse files
parthkariamaibin
parthkaria
authored and
maibin
committed
BAEL-875 Example of Hill Climbing algorithm (eugenp#1968)
* Dependency Injection examples Dependency Injection examples for evaluation article * Junit test cases added for dependency injection Junit test cases added for dependency injection * ClassNotFoundException vs NoClassDefFoundError Example to reproduce ClassNotFoundException & NoClassDefFoundError * JUnit test cases for ClassNotFoundException & NoClassDefFoundError test cases to reproduce ClassNotFoundException & NoClassDefFoundError * Deleting exampls for evaluation article * BAEL-831 Examples for ClassNotFoundException & NoClassDefFoundError * BAEL-831 Removed wrapper class * Removing evaluation article example * BAEL-831 removed wrapper class * BAEL-875 - Hill Climbing Algorithm BAEL-875 - Implementation for Hill Climbing Algorithm * BAEL-875 Modified algorithm with stream api
1 parent 97c1291 commit 137e182

3 files changed

Lines changed: 307 additions & 0 deletions

File tree

‎algorithms/src/main/java/com/baeldung/algorithms/hillclimbing/HillClimbing.java‎

Lines changed: 199 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,199 @@
1+
package com.baeldung.algorithms.hillclimbing;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
import java.util.Objects;
6+
import java.util.Optional;
7+
import java.util.Stack;
8+
import java.util.stream.Collectors;
9+
10+
public class HillClimbing {
11+
public static void main(String[] args) {
12+
HillClimbing hillClimbing = new HillClimbing();
13+
String blockArr[] = { "B", "C", "D", "A" };
14+
Stack<String> startState = hillClimbing.getStackWithValues(blockArr);
15+
String goalBlockArr[] = { "A", "B", "C", "D" };
16+
Stack<String> goalState = hillClimbing.getStackWithValues(goalBlockArr);
17+
try {
18+
List<State> solutionSequence = hillClimbing.getRouteWithHillClimbing(startState, goalState);
19+
solutionSequence.forEach(HillClimbing::printEachStep);
20+
} catch (Exception e) {
21+
e.printStackTrace();
22+
}
23+
}
24+
25+
public static void printEachStep(State state) {
26+
List<Stack<String>> stackList = state.getState();
27+
System.out.println("----------------");
28+
stackList.forEach(stack -> {
29+
while (!stack.isEmpty()) {
30+
System.out.println(stack.pop());
31+
}
32+
System.out.println(" ");
33+
});
34+
}
35+
36+
public Stack<String> getStackWithValues(String[] blocks) {
37+
Stack<String> stack = new Stack<String>();
38+
for (String block : blocks)
39+
stack.push(block);
40+
return stack;
41+
}
42+
43+
/**
44+
* This method prepares path from init state to goal state
45+
*
46+
* @param initStateStack
47+
* @param goalStateStack
48+
* @return
49+
* @throws Exception
50+
*/
51+
public List<State> getRouteWithHillClimbing(Stack<String> initStateStack, Stack<String> goalStateStack) throws Exception {
52+
List<Stack<String>> initStateStackList = new ArrayList<Stack<String>>();
53+
initStateStackList.add(initStateStack);
54+
int initStateHeuristics = getHeuristicsValue(initStateStackList, goalStateStack);
55+
State initState = new State(initStateStackList, initStateHeuristics);
56+
57+
List<State> resultPath = new ArrayList<>();
58+
resultPath.add(new State(initState));
59+
60+
State currentState = initState;
61+
boolean noStateFound = false;
62+
while (!currentState.getState()
63+
.get(0)
64+
.equals(goalStateStack) || noStateFound) {
65+
noStateFound = true;
66+
State nextState = findNextState(currentState, goalStateStack);
67+
if (nextState != null) {
68+
noStateFound = false;
69+
currentState = nextState;
70+
resultPath.add(new State(nextState));
71+
}
72+
}
73+
74+
if (noStateFound)
75+
throw new Exception("No path found");
76+
return resultPath;
77+
}
78+
79+
/**
80+
* This method finds new state from current state based on goal and
81+
* heuristics
82+
*
83+
* @param currentState
84+
* @param goalStateStack
85+
* @return a next state
86+
*/
87+
public State findNextState(State currentState, Stack<String> goalStateStack) {
88+
List<Stack<String>> listOfStacks = currentState.getState();
89+
int currentStateHeuristics = currentState.getHeuristics();
90+
91+
Optional<State> newState = listOfStacks.stream()
92+
.map(stack -> {
93+
State tempState = null;
94+
List<Stack<String>> tempStackList = new ArrayList<Stack<String>>(listOfStacks);
95+
String block = stack.pop();
96+
if (stack.size() == 0)
97+
tempStackList.remove(stack);
98+
tempState = pushElementToNewStack(tempStackList, block, currentStateHeuristics, goalStateStack);
99+
if (tempState == null) {
100+
tempState = pushElementToExistingStacks(stack, tempStackList, block, currentStateHeuristics, goalStateStack);
101+
}
102+
if (tempState == null)
103+
stack.push(block);
104+
return tempState;
105+
})
106+
.filter(Objects::nonNull)
107+
.findFirst();
108+
109+
return newState.orElse(null);
110+
}
111+
112+
/**
113+
* Operation to be applied on a state in order to find new states. This
114+
* operation pushes an element into a new stack
115+
*
116+
* @param currentStackList
117+
* @param block
118+
* @param currentStateHeuristics
119+
* @param goalStateStack
120+
* @return a new state
121+
*/
122+
private State pushElementToNewStack(List<Stack<String>> currentStackList, String block, int currentStateHeuristics, Stack<String> goalStateStack) {
123+
State newState = null;
124+
Stack<String> newStack = new Stack<String>();
125+
newStack.push(block);
126+
127+
currentStackList.add(newStack);
128+
int newStateHeuristics = getHeuristicsValue(currentStackList, goalStateStack);
129+
if (newStateHeuristics > currentStateHeuristics) {
130+
newState = new State(currentStackList, newStateHeuristics);
131+
} else {
132+
currentStackList.remove(newStack);
133+
}
134+
return newState;
135+
}
136+
137+
/**
138+
* Operation to be applied on a state in order to find new states. This
139+
* operation pushes an element into one of the other stacks to explore new
140+
* states
141+
*
142+
* @param stack
143+
* @param currentStackList
144+
* @param block
145+
* @param currentStateHeuristics
146+
* @param goalStateStack
147+
* @return a new state
148+
*/
149+
private State pushElementToExistingStacks(Stack currentStack, List<Stack<String>> currentStackList, String block, int currentStateHeuristics, Stack<String> goalStateStack) {
150+
151+
Optional<State> newState = currentStackList.stream()
152+
.filter(stack -> stack != currentStack)
153+
.map(stack -> {
154+
stack.push(block);
155+
int newStateHeuristics = getHeuristicsValue(currentStackList, goalStateStack);
156+
if (newStateHeuristics > currentStateHeuristics) {
157+
return new State(currentStackList, newStateHeuristics);
158+
}
159+
stack.pop();
160+
return null;
161+
})
162+
.filter(Objects::nonNull)
163+
.findFirst();
164+
165+
return newState.orElse(null);
166+
}
167+
168+
/**
169+
* This method returns heuristics value for given state with respect to goal
170+
* state
171+
*
172+
* @param currentState
173+
* @param goalStateStack
174+
* @return
175+
*/
176+
public int getHeuristicsValue(List<Stack<String>> currentState, Stack<String> goalStateStack) {
177+
178+
Integer heuristicValue = 0;
179+
heuristicValue = currentState.stream()
180+
.mapToInt(stack -> {
181+
int stackHeuristics = 0;
182+
boolean isPositioneCorrect = true;
183+
int goalStartIndex = 0;
184+
for (String currentBlock : stack) {
185+
if (isPositioneCorrect && currentBlock.equals(goalStateStack.get(goalStartIndex))) {
186+
stackHeuristics += goalStartIndex;
187+
} else {
188+
stackHeuristics -= goalStartIndex;
189+
isPositioneCorrect = false;
190+
}
191+
goalStartIndex++;
192+
}
193+
return stackHeuristics;
194+
})
195+
.sum();
196+
return heuristicValue;
197+
}
198+
199+
}

‎algorithms/src/main/java/com/baeldung/algorithms/hillclimbing/State.java‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package com.baeldung.algorithms.hillclimbing;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
import java.util.Stack;
6+
7+
public class State {
8+
List<Stack<String>> state;
9+
int heuristics;
10+
11+
public State() {
12+
}
13+
14+
public State(List<Stack<String>> state) {
15+
this.state = state;
16+
}
17+
18+
public State(List<Stack<String>> state, int heuristics) {
19+
this.state = state;
20+
this.heuristics = heuristics;
21+
}
22+
23+
public State(State state) {
24+
if (state != null) {
25+
this.state = new ArrayList<Stack<String>>();
26+
for (Stack s : state.getState()) {
27+
Stack s1 = new Stack();
28+
s1 = (Stack) s.clone();
29+
this.state.add(s1);
30+
}
31+
this.heuristics = state.getHeuristics();
32+
}
33+
}
34+
35+
public List<Stack<String>> getState() {
36+
return state;
37+
}
38+
39+
public void setState(List<Stack<String>> state) {
40+
this.state = state;
41+
}
42+
43+
public int getHeuristics() {
44+
return heuristics;
45+
}
46+
47+
public void setHeuristics(int heuristics) {
48+
this.heuristics = heuristics;
49+
}
50+
}

‎algorithms/src/test/java/algorithms/HillClimbingAlgorithmTest.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package algorithms;
2+
3+
import com.baeldung.algorithms.hillclimbing.HillClimbing;
4+
import com.baeldung.algorithms.hillclimbing.State;
5+
import org.junit.Before;
6+
import org.junit.Test;
7+
8+
import java.util.ArrayList;
9+
import java.util.List;
10+
import java.util.Stack;
11+
12+
import static org.junit.Assert.assertEquals;
13+
import static org.junit.Assert.assertNotNull;
14+
import static org.junit.Assert.assertTrue;
15+
16+
public class HillClimbingAlgorithmTest {
17+
Stack<String> initStack;
18+
Stack<String> goalStack;
19+
20+
@Before
21+
public void initStacks() {
22+
String blockArr[] = { "B", "C", "D", "A" };
23+
String goalBlockArr[] = { "A", "B", "C", "D" };
24+
initStack = new Stack<String>();
25+
for (String block : blockArr)
26+
initStack.push(block);
27+
goalStack = new Stack<String>();
28+
for (String block : goalBlockArr)
29+
goalStack.push(block);
30+
}
31+
32+
@Test
33+
public void givenInitAndGoalState_whenGetPathWithHillClimbing_thenPathFound() {
34+
HillClimbing hillClimbing = new HillClimbing();
35+
36+
List<State> path;
37+
try {
38+
path = hillClimbing.getRouteWithHillClimbing(initStack, goalStack);
39+
assertNotNull(path);
40+
assertEquals(path.get(path.size() - 1)
41+
.getState()
42+
.get(0), goalStack);
43+
} catch (Exception e) {
44+
e.printStackTrace();
45+
}
46+
}
47+
48+
@Test
49+
public void givenCurrentState_whenFindNextState_thenBetterHeuristics() {
50+
HillClimbing hillClimbing = new HillClimbing();
51+
List<Stack<String>> initList = new ArrayList<Stack<String>>();
52+
initList.add(initStack);
53+
State currentState = new State(initList);
54+
currentState.setHeuristics(hillClimbing.getHeuristicsValue(initList, goalStack));
55+
State nextState = hillClimbing.findNextState(currentState, goalStack);
56+
assertTrue(nextState.getHeuristics() > currentState.getHeuristics());
57+
}
58+
}

0 commit comments

Comments
 (0)