聪明的算法,用于查找数字总和等于数字显示中的段数的时间

Question

所以,我的朋友今天早上给我发了一个谜题:

查找一天中不同时间的数量(使用24小时显示并假设早晨时间显示为8:15而不是08:15),其中段的数量等于数字的总和.例如.8:15电子格式有7 + 2 + 5 = 14段,数字之和为8 + 1 + 5 = 14,因此符合条件.

所以我在C#3.0中提出了以下简单(但是迟钝的暴力)解决方案:

// Number of segments in each digit
var digitMap = 
    new Dictionary<char, int>
    {
        {'0',6},{'1',2},{'2',5},{'3',5},{'4',4},
        {'5',5},{'6',5},{'7',3},{'8',7},{'9',5}
    };

var numMatches = (
            from h in Enumerable.Range(0,24)
            from m in Enumerable.Range(0,60)
            select h.ToString() + m.ToString().PadLeft(2,'0') into t 
            let chars = t.ToCharArray()
            where chars.Sum(c => int.Parse(c.ToString())) == chars.Sum(c => digitMap[c])
            select t).Count();

但是,他补充说:

不允许使用蛮力方法.

我已经考虑了一段时间了,我正在努力想出一个更聪明的算法.我正落预滤波的不可能性的路径(例如倍,其中的数字的总和是小于6,因为这是最小段总和) - 但最终我假定只会导致更小的解空间,然后是暴力强迫.

无论如何,我认为把它扔出去是一个有趣的问题,看看是否有人能想出一个更聪明的方法.

Answer 1

每个数字将始终具有相同的偏移量.8总会让你的细分是一个低,1总会让你的链段一个更高,5永远是相同的,等等.一旦你知道价值,你可以很快生成唯一为此您与资金的有效组合平等.