代码之家 › 专栏 › 技术社区 › Winston Smith

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

puzzle language-agnostic algorithm c#

Winston Smith · 技术社区 · 15 年前

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

查找当天(使用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的次数,因为这是最小段和)前进,但最后我认为这只会导致更小的解决方案空间,然后这将被强制执行。

不管怎样,我认为这是一个有趣的问题,把它扔出去,看看是否有人能想出一个更聪明的方法。

4 回复 | 直到 15 年前

bwarner 15 年前

每个数字始终具有相同的偏移量。8总是让你的段低一点,1总是让你的段高一点,5总是一样的,等等。一旦你知道这个值,你可以很快生成有效的组合,最终你和相等。

John Feminella 15 年前

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

注意某些数字“破坏”了组合。例如,任何带两个零的组合都会破坏它;没有足够的剩余数字给您+12。因此,在1000和2000小时内,10分钟间隔的所有时间都是不存在的(1000,1010,…),这一小时上午的任何时间都是在前10分钟(1000..1009)内。

其中三种“破坏性”组合消除了三分之二的搜索空间。我将把它作为一个练习留给读者,他们是谁(我不相信这不是某种家庭作业)。

Joy Dutta 15 年前

由于(08:15)等小时内不允许出现前导零,因此我们假设午夜由(0:00)表示。

让我们定义一个数字的段偏移量(so):=段和-数字

让我们把m个数字映射到它们的段偏移量。

小时内最小SO部分=-4(适用于7:xx) 小时内最大SO段=9(20:xx)

现在确定一个字符串 hhmm 满足您的条件,我们可以从 HHMM 字符串,计算段偏移量之和 mm 如果负值超出范围 [-4,9] 然后我们可以拒绝对该字符串进行任何进一步的计算。这将稍微减少您的方法的粗暴性。

Vijay 15 年前

我对整个暴力强迫的事情感到困惑。是不是蛮力逼着你浏览整个列表并选择正确的答案?那么,我们如何在不遍历整个时间列表的情况下,只生成产生所需结果的答案呢?或者这里的蛮力是指在数字和段之间进行和比较吗?

不管怎样,这里有一个使用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