Skip to content

Commit 8699054

Browse files
kzlsahinkzlsahin
committed
Solved.
1 parent eb8c0d9 commit 8699054

File tree

1 file changed

+88
-34
lines changed

1 file changed

+88
-34
lines changed

‎algorithm-1/C#/Solution-a1-3/solution-3.cs

Lines changed: 88 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -4,10 +4,25 @@
44
using System.Text;
55

66

7-
Test();
7+
Test1();
8+
Test2();
9+
Test3();
810

11+
static void Test1()
12+
{
13+
Console.WriteLine("==============");
14+
Console.WriteLine("Test2");
15+
Console.WriteLine("_____");
16+
int reqStepCount = 1;
17+
Game game_2 = new("[[1,2,3],[4,0,5]]");
18+
GameState resolvedState = game_2.GetSolution();
19+
Console.WriteLine(resolvedState.ToString());
20+
Console.WriteLine(resolvedState.Status.ToString());
21+
Console.WriteLine($"resolved in {resolvedState.StepCount} steps");
22+
Console.WriteLine($"Test result {(resolvedState.StepCount == reqStepCount ? "passed" : "failed")}.");
23+
}
924

10-
static void Test()
25+
static void Test2()
1126
{
1227
Console.WriteLine("==============");
1328
Console.WriteLine("Test2");
@@ -17,10 +32,23 @@ static void Test()
1732
GameState resolvedState = game_2.GetSolution();
1833
Console.WriteLine(resolvedState.ToString());
1934
Console.WriteLine(resolvedState.Status.ToString());
20-
Console.WriteLine($"resolved in {resolvedState.moveHist.Count} steps");
21-
Console.WriteLine($"Test result {(resolvedState.moveHist.Count == reqStepCount ? "passed" : "failed")}.");
35+
Console.WriteLine($"resolved in {resolvedState.StepCount} steps");
36+
Console.WriteLine($"Test result {(resolvedState.StepCount == reqStepCount ? "passed" : "failed")}.");
2237
}
2338

39+
static void Test3()
40+
{
41+
Console.WriteLine("==============");
42+
Console.WriteLine("Test2");
43+
Console.WriteLine("_____");
44+
int reqStepCount = -1;
45+
Game game_2 = new("[[1,2,3],[5,4,0]]");
46+
GameState resolvedState = game_2.GetSolution();
47+
Console.WriteLine(resolvedState.ToString());
48+
Console.WriteLine(resolvedState.Status.ToString());
49+
Console.WriteLine($"resolved in {resolvedState.StepCount} steps");
50+
Console.WriteLine($"Test result {(resolvedState.StepCount == reqStepCount ? "passed" : "failed")}.");
51+
}
2452

2553
[Flags]
2654
public enum Movements
@@ -40,8 +68,25 @@ public enum StateStatus
4068
}
4169
public class GameState
4270
{
43-
public static int RowNumber = 2;
44-
public static int ColNumber = 3;
71+
public static int rowNumber = 2;
72+
public static int colNumber = 3;
73+
74+
int _stepCount;
75+
public int StepCount
76+
{
77+
get
78+
{
79+
if(Status == StateStatus.FAILED)
80+
{
81+
return -1;
82+
}
83+
return _stepCount;
84+
}
85+
private set
86+
{
87+
_stepCount = value;
88+
}
89+
}
4590
public int[][] Values { get; set; }
4691
public int[] AddressOfVoid { get; set; } = new int[2];
4792
public Movements LastMovementFrom { get; set; }
@@ -57,9 +102,10 @@ public class GameState
57102
/// </remarks>
58103
/// <param name="initialState"></param>
59104
/// <param name="lastMovementFrom"></param>
60-
public GameState(int[][] initialState, Movements lastMovementFrom, List<Movements> movesHistory)
105+
public GameState(int[][] initialState, Movements lastMovementFrom, List<Movements> movesHistory, int t)
61106
{
62107
Status = StateStatus.IN_PROGRESS;
108+
StepCount = t;
63109
Values = new int[initialState.Length][];
64110
LastMovementFrom = lastMovementFrom;
65111
moveHist = new();
@@ -113,6 +159,7 @@ public void Move(Movements movement)
113159
break;
114160
}
115161
moveHist.Add(movement);
162+
StepCount++;
116163
}
117164
public override string ToString()
118165
{
@@ -142,25 +189,25 @@ public void SetAvailableMovements()
142189
{
143190
NextMovements |= Movements.TOP;
144191
}
145-
if (row + 1 < RowNumber)
192+
if (row + 1 < rowNumber)
146193
{
147194
NextMovements |= Movements.BOTTOM;
148195
}
149196
if (col - 1 >= 0)
150197
{
151198
NextMovements |= Movements.LEFT;
152199
}
153-
if (col + 1 < ColNumber)
200+
if (col + 1 < colNumber)
154201
{
155202
NextMovements |= Movements.RIGHT;
156203
}
157204
NextMovements ^= LastMovementFrom; // do not repeat last movement
158205
}
159206
private void _getAddressOfVoid()
160207
{
161-
for (int i = 0; i < RowNumber; i++)
208+
for (int i = 0; i < rowNumber; i++)
162209
{
163-
for (int j = 0; j < ColNumber; j++)
210+
for (int j = 0; j < colNumber; j++)
164211
{
165212
if (Values[i][j] == 0)
166213
{
@@ -176,7 +223,7 @@ class Game
176223
int rowNumber;
177224
int colNumber;
178225
GameState _initState;
179-
public HashSet<string> stateHist { get; set; }
226+
public Dictionary<string, int> stateHist { get; set; }
180227

181228
/// <summary>
182229
/// init state as "n,n,n/n,n,n" or "[[n,n,n],[n,n,n]]"
@@ -221,14 +268,14 @@ public Game(int[][] initialState)
221268
}
222269
public void SetState(int[][] initialState)
223270
{
224-
rowNumber = GameState.RowNumber;
225-
colNumber = GameState.ColNumber;
271+
rowNumber = GameState.rowNumber;
272+
colNumber = GameState.colNumber;
226273
if (!ValidateInput(initialState))
227274
{
228275
Console.WriteLine("Invalid game state as a starting point!");
229276
return;
230277
}
231-
_initState = new GameState(initialState, Movements.NONE, new List<Movements>());
278+
_initState = new GameState(initialState, Movements.NONE, new List<Movements>(), 0);
232279
stateHist = new();
233280
}
234281
public GameState GetSolution()
@@ -237,64 +284,71 @@ public GameState GetSolution()
237284
}
238285
private GameState GetSolution(GameState state)
239286
{
240-
if (!stateHist.Add(state.ToString()))
287+
string stateToken = state.ToString();
288+
if (!stateHist.TryAdd(stateToken, state.StepCount))
241289
{
242-
state.Status = StateStatus.FAILED;
243-
return state;
290+
// This state has been passed before
291+
// if this rout reaches this state by longer path, then this path is failed.
292+
// -> The other one is more closer to the solution then this branch, no need to continue on this rout
293+
if(state.StepCount >= stateHist[stateToken])
294+
{
295+
state.Status = StateStatus.FAILED;
296+
return state;
297+
}
298+
stateHist[stateToken] = state.StepCount;
244299
}
245300
if (_isSolved(state))
246301
{
247302
state.Status = StateStatus.SUCCESS;
248303
return state;
249304
}
250305
state.SetAvailableMovements();
251-
List<GameState> newStates = new();
252-
CheckMovement(state, Movements.LEFT, newStates);
253-
CheckMovement(state, Movements.TOP, newStates);
254-
CheckMovement(state, Movements.RIGHT, newStates);
255-
CheckMovement(state, Movements.BOTTOM, newStates);
256-
306+
List<GameState> nextStates = new();
307+
CheckMovement(state, Movements.TOP, nextStates);
308+
CheckMovement(state, Movements.BOTTOM, nextStates);
309+
CheckMovement(state, Movements.RIGHT, nextStates);
310+
CheckMovement(state, Movements.LEFT, nextStates);
257311

258312
GameState resolvedState = state;
259313
int count = int.MaxValue;
260314
bool successFound = false;
261-
foreach (GameState newState in newStates)
315+
foreach (GameState newState in nextStates)
262316
{
263317
GameState newResolvedState = GetSolution(newState);
264318
if (successFound == false && newResolvedState.Status == StateStatus.SUCCESS)
265319
{
266320
successFound = true;
267321
resolvedState = newResolvedState;
268-
count = resolvedState.moveHist.Count;
322+
count = resolvedState.StepCount;
269323
}
270324
else if (successFound && newResolvedState.Status == StateStatus.SUCCESS)
271325
{
272-
if (newResolvedState.moveHist.Count < count)
326+
if (newResolvedState.StepCount < count)
273327
{
274328
resolvedState = newResolvedState;
275-
count = resolvedState.moveHist.Count;
329+
count = resolvedState.StepCount;
276330
}
277331
}
278332
else if(successFound == false)
279333
{
280-
if (newResolvedState.moveHist.Count < count)
334+
if (newResolvedState.StepCount < count)
281335
{
282336
resolvedState = newResolvedState;
283-
count = resolvedState.moveHist.Count;
337+
count = resolvedState.StepCount;
284338
}
285339
}
286340
}
287341
return resolvedState;
288342
}
289-
private void CheckMovement(GameState state, Movements movement, List<GameState> newStates)
343+
private void CheckMovement(GameState state, Movements movement, List<GameState> nexStates)
290344
{
291345
// check availablity
292346
bool isMovementAvailable = state.NextMovements.HasFlag(movement);
293-
if (isMovementAvailable == false) return;
347+
if (!isMovementAvailable) return;
294348
// we return early if this movement is not available
295349
GameState _state;
296-
_state = new GameState(state.Values, state.LastMovementFrom, state.moveHist);
297-
newStates.Add(_state);
350+
_state = new GameState(state.Values, state.LastMovementFrom, state.moveHist, state.StepCount);
351+
nexStates.Add(_state);
298352

299353
_state.Move(movement);
300354
}

0 commit comments

Comments
 (0)