Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do …
public class Solution
{
private static IEnumerable<string> ReadInputLine()
{
var input = Console.ReadLine();
return input == null ? null : input.Split(' ');
}
private delegate bool Parse<T>(string str, out T result);
private static List<T> ReadTypesValues<T>(Parse<T> parse)
{
var list = new List<T>();
var input = ReadInputLine();
if (input == null)
return list;
foreach (var s in input)
{
T res;
if (parse(s, out res))
list.Add(res);
}
return list;
}
private static byte[] GetPegsConfiguration(byte n, byte k)
{
var pegs = new byte[k];
var diskConfig = ReadTypesValues<byte>(byte.TryParse);
for (byte diskInd = 0; diskInd < n; diskInd++)
{
var pegIndex = diskConfig[diskInd] - 1;
pegs[pegIndex] = (byte)(pegs[pegIndex] | (1 << diskInd));
}
return pegs;
}
private static byte GetLowBit(byte b)
{
if (b == 0)
return 0xFF;
byte bit = 0;
while((b & 1) == 0)
{
b >>= 1;
bit++;
}
return bit;
}
private static List<byte[]> GetAvailableMoves(byte[] pegsConfig)
{
var movesList = new List<byte[]>();
for (byte i = 0; i < pegsConfig.Length;i++ )
{
var peg = pegsConfig[i];
var topDisk = GetLowBit(peg);
if(topDisk == 0xFF)
continue;
for(byte j=0; j<pegsConfig.Length;j++)
{
var nextTopDisk = GetLowBit(pegsConfig[j]);
if(nextTopDisk == 0xFF || nextTopDisk > topDisk)
movesList.Add(new byte[]{i, j});
}
}
return movesList;
}
private static byte[] DoMoveConfiguration(byte[] config, byte[] move)
{
var newConfig = new byte[config.Length];
for(var i = 0; i<newConfig.Length;i++)
{
newConfig[i] = config[i];
}
var sourceIndex = move[0];
var targetIndex = move[1];
var mask = (byte) (1 << GetLowBit(newConfig[sourceIndex]));
newConfig[sourceIndex] ^= mask;
newConfig[targetIndex] |= mask;
return newConfig;
}
private static bool ArraysEquals(byte[] array1, byte[] array2)
{
for(var i=0;i<array1.Length;i++)
{
if (array1[i] != array2[i])
return false;
}
return true;
}
private static void Solve(byte[] initConfig, byte[] finalConfig, List<byte[]> prevMoves, ref List<byte[]> solution)
{
if(ArraysEquals(initConfig, finalConfig))
{
if(solution == null || prevMoves.Count < solution.Count)
{
solution = prevMoves;
}
}
if (prevMoves.Count == 7)
{
return;
}
var moves = GetAvailableMoves(initConfig);
foreach (var move in moves)
{
var newConfig = DoMoveConfiguration(initConfig, move);
var newMoves = new List<byte[]>(prevMoves) {move};
Solve(newConfig, finalConfig, newMoves, ref solution);
}
}
public static void Main(string[] args)
{
var firstLine = ReadTypesValues<byte>(byte.TryParse);
var n = firstLine[0]; // numbers of disks
var k = firstLine[1]; // number of pegs
var initConfig = GetPegsConfiguration(n, k);
var finalConfig = GetPegsConfiguration(n, k);
List<byte[]> solution = null;
var timer = new Stopwatch();
timer.Start();
Solve(initConfig, finalConfig, new List<byte[]>(), ref solution);
Console.WriteLine(solution.Count);
foreach (var prevMove in solution)
{
Console.WriteLine("{0} {1}", prevMove[0] + 1, prevMove[1] + 1);
}
timer.Stop();
//Console.WriteLine("found solution for {0} ms", timer.ElapsedMilliseconds);
Console.ReadLine();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.