315 Digital Root Clocks

Problem 315

这个题目比较长，下面简单描述一下。

有一个数字表，显示数字的方式可以看原题，其实是老式计算器那个样子，也像小时候做的奥数题，拿火柴棍摆正正方方的数字。

给它一个输入，比如说 137，首先它会显示 137，然后计算 137 各个数字之和，得到 11，然后显式 11，再计算得到 2，显示 2。

显示数字或者是不显示，都需要一次转换，比如显示 4，要 4 次转换，比如显示 8 然后什么都不显示，需要 7 次转换。

Sam 的表显示的方式很直接：

比如输入 137，显示 137，再关掉，一共需要 次转换，137 各个数字之和是 11，显示 11 再关掉， 次转换，最后的数字 2，需要 次转换。一共需要 40 次转换。

Max 的表稍微智能一点：

比如137变成11的时候，3和1是有公共部分的，7和1也是有公共部分的，那么在关掉137的时候，对应下个数字的地方就不关掉了，显示下一个数字的时候就不需要再打开，用此方法较少转换的次数。
打开137，2 + 5 + 4 = 11次转换，关掉的时候，11的那4个地方不关闭，那么关闭需要7次转换；显示11不需要打开了，关闭11显示2，第二个1的右上角那一个也不要关闭，所以关闭11需要3次转换，打开2，只需要4次转换而不是5次，关闭2需要5次转换。总共需要30次转换。
相比Sam的少了10次。

题目的输入是 到 之间的所有质数，求省下来的转换次数。

其实这个题目看似很难，如果找对了关键点，其实很简单。

所谓省下来的次数，就是 2 个数字直接重叠的那一部分，比如 0 和 8 重叠就是整个 0，6 条边，2 和 4 就重叠了两条边。

于是乎，一个二维数组表示任意两个数字之间的重叠个数。 

private static int[,] Overlap = new int[10, 10]
{
    { 6,2,4,4,3,4,5,4,6,5},
    { 2,2,1,2,2,1,1,2,2,2},
    { 4,1,5,4,2,3,4,2,5,4},
    { 4,2,4,5,3,4,4,3,5,5},
    { 3,2,2,3,4,3,3,3,4,4},
    { 4,1,3,4,3,5,5,3,5,5},
    { 5,1,4,4,3,5,6,3,6,5},
    { 4,2,2,3,3,3,3,4,4,4},
    { 6,2,5,5,4,5,6,4,7,6},
    { 5,2,4,5,4,5,5,4,6,6}
};

万一人为计算的时候搞错了呢？我又搞了个函数检查一下，我把数字的边从上到下，从左到右编号。比如数字 1 的两条边就是 3,6，数字 7 的边就是 1,2,3,6。然后计算数字的重叠部分，看看和我手写的矩阵是否一致。第一遍运算的时候，还真发现矩阵里面的一个错误。 

private static void Check()
{
    var digital = new List<List<int>>();
    digital.Add(new List<int>() { 1, 2, 3, 5, 6, 7 });
    digital.Add(new List<int>() { 3, 6 });
    digital.Add(new List<int>() { 1, 3, 4, 5, 7 });
    digital.Add(new List<int>() { 1, 3, 4, 6, 7 });
    digital.Add(new List<int>() { 2, 3, 4, 6 });
    digital.Add(new List<int>() { 1, 2, 4, 6, 7 });
    digital.Add(new List<int>() { 1, 2, 4, 5, 6, 7 });
    digital.Add(new List<int>() { 1, 2, 3, 6 });
    digital.Add(new List<int>() { 1, 2, 3, 4, 5, 6, 7 });
    digital.Add(new List<int>() { 1, 2, 3, 4, 6, 7 });
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            int overlap = digital[i].Intersect(digital[j]).Count();
            if (overlap != Overlap[i, j])
            {
                Console.WriteLine(i + "\t" + j + "\t" + overlap);
            }
        }
    }
}
反过来，有没有可能人为写边的数字集合的时候出了问题呢？也是有可能的。所谓测试，就是测试代码和运行代码相互验证的过程。如果通过测试，那么运行代码和测试代码大概率没问题，除非都错了，错错为对。

接着往下想，给两个数字，比如 137 和 11，如何得到重叠部分呢？很简单，从最后一位开始比就可以了，最后一位的两个数字，去查矩阵，很容易得到重叠的值，然后再考察倒数第二位等等。代码如下： 

private static int GetCount(int num1, int num2)
{
    int count = 0;

    while (num1 > 0 && num2 > 0)
    {
        count += Overlap[num1 % 10, num2 % 10];
        num1 /= 10;
        num2 /= 10;
    }

    return count;
}

能够比较两个数字了，那么给定要给输入，一个几百万大的质数，求各个数字之后，对比两个数字之间的重叠值，然后再计算数字之和的数字之和，再对比重叠值，循环到个位数即可。 

private static int GetCount(int p)
{
    int count = 0;
    while (p >= 10)
    {
        int sum = p.ToString().Select(c => c-'0').Sum();
        count += GetCount(p, sum);
        p = sum;
    }

    return count * 2;
}
为什么要乘以 2 呢？因为从第一个数字过渡到第二个数字，比如 11 到2，重叠部分是 1，关闭 11 的时候可以少关闭 1，显示 2 的时候又可以少打开 1，所有要乘以 2。

万事俱备，最后，拿到 到 之间的所有质数，遍历求和即可。 

public static int GetAnswer()
{
    Check();

    int count = 0;
    var primes = Utils.GenPrimes(20000000).Where(p => p > 10000000);

    foreach (var p in primes)
    {
        count += GetCount((int)p);
    }

    return count;
}