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

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

Найдите количество различных времен суток (используя 24-часовой формат и предполагая, что утренние часы представлены как 8:15, а не 08:15), где количество сегментов равно сумме цифр. Например. 8:15 имеет 7+2+5=14 сегментов в электронном формате, а сумма цифр равна 8+1+5=14, так что это квалифицируется как случай.

Поэтому я придумал следующее простое (но заторможенное) решение на С# 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, поскольку это минимальная сумма сегмента), но в конце концов я полагаю, что это приведет только к меньшему пространству решений, который затем грубо принудительно.

В любом случае, я думаю, что это достаточно интересная проблема, чтобы бросить ее и посмотреть, сможет ли кто-нибудь придумать более умный метод.


c# algorithm puzzle language-agnostic
person Winston Smith    schedule 18.12.2009    source источник
comment
Хорошо, может быть, я медленный, я не понимаю пример 8:15 имеет 7 + 2 + 5 = 14 сегментов. Я не понимаю, что такое электронный сегмент.   -  person Jay    schedule 18.12.2009
comment
Я думаю, что они имеют в виду количество сегментов светодиодного дисплея, из которых состоит каждое число, №8 = 7 сегментов, №1 = 2, а №5 состоит из 5.   -  person Andrew    schedule 18.12.2009
comment
en.wikipedia.org/wiki/Seven-segment_display   -  person Ken    schedule 19.12.2009

Ответы (4)


arrow_upward
9
arrow_downward

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

person bwarner    schedule 18.12.2009
comment
Как и в большинстве подобных вещей, ответ прост, как только вы его увидите. Я приближался к нему с неправильного угла. - person Winston Smith; 18.12.2009

arrow_upward
3
arrow_downward

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

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

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

person John Feminella    schedule 18.12.2009
comment
Вы упустили тот факт, что начальные нули во времени до 10:00 исключаются. - person Tony van der Peet; 18.12.2009

arrow_upward
1
arrow_downward

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

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

Давайте сопоставим M цифр со смещениями их сегментов.

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

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

person Joy Dutta    schedule 18.12.2009

arrow_upward
1
arrow_downward

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

Во всяком случае, вот решение, использующее 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
person Vijay    schedule 27.01.2010