Умный алгоритм, чтобы найти времена, когда сумма цифр равна количеству сегментов в цифровом отображении - PullRequest
Новая
       10

Умный алгоритм, чтобы найти времена, когда сумма цифр равна количеству сегментов в цифровом отображении

3 голосов
/ 18 декабря 2009

Итак, мой друг прислал мне головоломку сегодня утром:

Найдите количество разных времен день (используя 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 ]

9 голосов
/ 18 декабря 2009

Каждое число всегда будет иметь одинаковое смещение. 8 всегда сделает ваши сегменты на один ниже, 1 всегда сделает ваши сегменты на один выше, 5 всегда будет одинаковым и т. Д. Как только вы узнаете это значение, вы можете довольно быстро сгенерировать только действительные комбинации, в результате которых вы получите суммы быть равным.

3 голосов
/ 18 декабря 2009

Вместо сохранения значений, сопоставленных с количеством сегментов, сохраните значения цифр, сопоставленные с их смещениями. Понятно, что любая комбинация, которая дает ноль, будет работать. Но мы можем сузить это дальше.

Обратите внимание, что определенные цифры "разрушают" комбинацию. Например, любая комбинация с двумя нулями (-12) разрушает ее; недостаточно цифр, чтобы дать вам +12. Таким образом, все интервалы времени в течение 1000 и 2000 часов по десятиминутным интервалам отсутствуют (1000, 1010, ...), как и все периоды времени в этот час по утрам в течение первых 10 минут (1000..1009).

Три из этих «разрушающих» комбинаций устраняют две трети пространства поиска. Я оставлю это в качестве упражнения для читателя, кто они (я не уверен, что это не домашнее задание).

1 голос
/ 27 января 2010

Я в замешательстве из-за всей этой грубой силы. Разве грубое принуждение не просматривает весь список и не выбирает правильный ответ? Как нам тогда производить только ответы, дающие желаемый результат, без перебора всего временного списка? Или грубое принуждение означает здесь сравнение суммы между цифрами и сегментами?

В любом случае, вот решение с использованием 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
1 голос
/ 19 декабря 2009

Поскольку ведущий ноль в часах, таких как (08:15), не допускается, мы предполагаем, что полночь представлена ​​(0:00).

Определим смещение сегмента (SO) цифры: = сумма сегмента - цифра

Позволяет сопоставить M цифр смещениям их сегментов.

Минимальный SO в часовом разделе = -4 (для 7: xx) Максимальное значение SO в часовом разделе = 9 (для 20: xx)

Теперь, чтобы определить, удовлетворяет ли строка hhmm вашим критериям, мы можем начать сканирование с конца строки hhmm, вычислить сумму смещений сегмента для части mm и определить, находится ли ее отрицательное значение диапазон [-4,9] тогда мы можем отклонить любые дальнейшие вычисления для этой строки. Это немного уменьшит грубость вашего подхода.

...