Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created March 16, 2018 01:22
Show Gist options
  • Save jianminchen/08ce0decf43312a4fe965083823e035a to your computer and use it in GitHub Desktop.
Save jianminchen/08ce0decf43312a4fe965083823e035a to your computer and use it in GitHub Desktop.
Knight tour - dynamic programming - March 15, 2018
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace knightTour
{
/// <summary>
/// problem statement:
/// https://stackoverflow.com/questions/2893470/generate-10-digit-number-using-a-phone-keypad
/// </summary>
class knightTour
{
static void Main(string[] args)
{
var result = CountDifferentPhoneNumbers(1, 1);
var result2 = CountDifferentPhoneNumbers(2, 1);
var result10 = CountDifferentPhoneNumbers(10, 1);
var result10B = CountDifferentPhoneNumbers(10, 6);
}
public static int CountDifferentPhoneNumbers(int kSteps, int start)
{
var knights = prepareKnightTable();
var previousStep = new int[10];
previousStep[start] = 1;
var currentStep = new int[10];
for (int step = 0; step < kSteps; step++)
{
for (int number = 0; number <= 9; number++)
{
var count = previousStep[number];
foreach (var item in knights[number])
{
currentStep[item] += count;
}
}
arrayCopy(previousStep, currentStep);
initalizeCurrentStep(currentStep);
}
return previousStep.Sum();
}
private static void arrayCopy(int[] copyTo, int[] copyFrom)
{
var length = copyFrom.Length;
for (int i = 0; i < length; i++)
{
copyTo[i] = copyFrom[i];
}
}
private static void initalizeCurrentStep(int[] numbers)
{
for (int i = 0; i < numbers.Length; i++)
{
numbers[i] = 0;
}
}
private static int[][] prepareKnightTable()
{
var knights = new int[10][];
knights[0] = new int[] { 4, 6 };
knights[1] = new int[] { 8, 6 };
knights[2] = new int[] { 7, 9 };
knights[3] = new int[] { 4, 8 };
knights[4] = new int[] { 3, 9 };
knights[5] = new int[] { };
knights[6] = new int[] { 0, 1, 7 };
knights[7] = new int[] { 2, 6 };
knights[8] = new int[] { 1, 3 };
knights[9] = new int[] { 2, 4 };
return knights;
}
}
}
@jianminchen
Copy link
Author

Two issues:

  1. First the calculation of knights[4] = new int[]{0, 3, 9}, 0 is missing in my code line 74;
  2. All possible numbers, I need to set start number from 0 to 9, 10 of them.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment