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

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的时间，因为那是最小的分段和），但最终这只会导致更小的解空间，然后再进行暴力搜索。

无论如何，我认为这是一个有趣的问题，想看看是否有人能想出更聪明的方法。

- Winston Smith

---

好的，也许我比较慢，我不理解例子中的8:15有7+2+5=14个分段是什么意思。我不明白所谓的电子分段是什么。 - Jay

我认为他们指的是LED显示器中组成每个数字的段数，#8 = 7段，#1 = 2段，#5由5段组成。 - Andrew

http://en.wikipedia.org/wiki/Seven-segment_display - Ken

Answer 1

每个数字始终具有相同的偏移量。8始终会使您的分段数减少1，1始终会使您的分段数增加1，5始终保持不变等等。一旦您知道该值，就可以快速生成仅包含有效组合的结果，以确保它们的总和相等。

- bwarner

---

大多数情况下，一旦你看到了答案，它就很简单。我以错误的角度来处理它。 - Winston Smith

Answer 2

不要存储映射到片段数的值，而是存储数字值映射到它们的偏移量。显然，任何产生零的组合都可以使用。但我们可以进一步缩小范围。

请注意，某些数字会“破坏”组合。例如，任何带有两个零（-12）的组合都会破坏它；没有足够的剩余数字给您+12。因此，在1000和2000小时的十分钟间隔内的所有时间都被排除在外（1000、1010等），在这个小时的早晨时间的前10分钟内的任何时间也都被排除在外（1000..1009）。

其中三个“破坏”组合消除了搜索空间的三分之二。我将把它留给读者作为练习，让他们自己找出哪些组合是这样的（我不确定这是否是某种作业）。

- John Feminella

---

你忽略了一个事实，即在10:00之前的时间中，前导零是被排除在外的。 - Tony van der Peet

Answer 3

我对暴力破解这件事很困惑。难道暴力破解不是指遍历整个列表并选择正确的答案吗？那么我们如何只产生符合要求的结果，而不需要遍历整个时间列表呢？或者这里的暴力破解是指在数字和段之间进行比较的总和吗？

无论如何，这里提供了一种使用Python（初学者）和上述算法的解决方案。

def sum_offset(time):
                    #( 0,  1,  2,  3,  4,  5,  6,  7,  8,  9)
    segment_offset = (+6, +1, +3, +2, +0, +0, -1, -4, -1, -4) 
    total = 0
    for digit in time:
        total += segment_offset[int(digit)]
    return total

alltime = ['%d%02d' %(h, m)
      for h in range(0,24)
      for m in range(60)]
#result_totals = map(sum_offset, alltime)
filtered = [t for t in alltime if sum_offset(t)==0]
print filtered

共有88个结果

['127', '129', '146', '148', '156', '158', '217', '219', '337', '339', '416', '418', '444', '445', '454', '455', '516', '518', '544', '545', '554', '555', '614', '615', '636', '638', '641', '651', '712', '721', '733', '814', '815', '836', '838', '841', '851', '912', '921', '933', '1137', '1139', '1247', '1249', '1257', '1259', '1317', '1319', '1427', '1429', '1446', '1448', '1456', '1458', '1527', '1529', '1546', '1548', '1556', '1558', '1616', '1618', '1644', '1645', '1654', '1655', '1713', '1724', '1725', '1731', '1742', '1752', '1816', '1818', '1844', '1845', '1854', '1855', '1913', '1924', '1925', '1931', '1942', '1952', '2147', '2149', '2157', '2159']

Joy 建议的优化似乎给代码增加了更多的复杂性，使其难以理解，但这是我尝试的结果。

def sum_offset_optimized(time):
                    #( 0,  1,  2,  3,  4,  5,  6,  7,  8,  9)
    segment_offset = (+6, +1, +3, +2, +0, +0, -1, -4, -1, -4)
    if len(time) < 3:
        return -1 #or raise the appropriate error
    total = segment_offset[int(time[-1])] + segment_offset[int(time[-2])]
    #optimization as suggested by Joy Dutta
    if (-4 < total < 9):
        pass
    else:
        total += segment_offset[int(time[-3])]
        if len(time) == 4: #check for length else we will have an out of bound error
            total += segment_offset[int(time[-4])]
    return total
### testing performance
def method_simple():
    filtered = [t for t in alltime if sum_offset(t)==0]

def method_optimized():
    filtered = [t for t in alltime if sum_offset_optimized(t)==0]

import timeit
timer_simple = timeit.Timer('sum_digit_segments.method_simple()','import sum_digit_segments')
timer_optimized = timeit.Timer('sum_digit_segments.method_optimized()','import sum_digit_segments')
#timer_simple.timeit()
#timer_optimized.timeit()
print 'simple:', timer_simple.repeat(1,1000) #[12.469249024666542]
print 'optimized:', timer_optimized.repeat(1,1000) #[7.4063790230322546]
#The optimized version is significantly faster

- Vijay

Answer 4

由于小时部分不允许有前导零，例如（08:15），我们假设午夜表示为（0:00）。

让我们定义数字的段偏移量（SO）：= 段总和 - 数字

让我们将数字映射到它们的段偏移量M中。

小时部分的最小SO = -4（对于7:xx） 小时部分的最大SO = 9（对于20:xx）

现在，要确定字符串hhmm是否符合您的条件，我们可以从hhmm字符串的末尾开始扫描，计算mm部分的段偏移量之和，如果其负值超出范围[-4,9]，则我们可以拒绝对该字符串进行任何进一步的计算。这将稍微减少您的方法的暴力程度。

- Joy Dutta