mtecl.prg
BAN USERc#
public static void Start()
{
TestStones(true, new bool[] { true, true, true, true });
TestStones(false, new bool[] { false, false, false });
TestStones(true, new bool[] { true, true, false, true, false });
TestStones(false, new bool[] { false, true, false, false, true, false });
}
public static bool CheckPath(bool[] stones)
{
for (int initialJump = 1; initialJump < (stones.Length / 2) + 1; initialJump++)
{
if (CheckPath(stones, initialJump, initialJump))
return true;
}
return false;
}
public static bool CheckPath(bool[] stones, int currentStone, int prevJumpLen)
{
if (currentStone >= stones.Length)
return true;
if (!stones[currentStone])
return false;
for (int lenMod = (prevJumpLen > 1) ? -1 : 0; lenMod < 2; lenMod++ )
{
int jumpLen = prevJumpLen + lenMod;
if(CheckPath(stones, currentStone + jumpLen, jumpLen))
return true;
}
return false;
}
private static void TestStones(bool expectedResult, bool[] stones)
{
if (expectedResult != CheckPath(stones))
throw new Exception("Failed");
Console.WriteLine("ok");
}
Actually there should ne different approach to find initial jump length - at least it should iterate from longest initial step.
But should be also cleared what is last jump - if it is every jump from stone to somewhere after end of the array (as I expected in my code), then actually each river with one stone has solution :) So let's assume that latest jump must point exactly to index equals to river width:
- mtecl.prg December 02, 2015