Clever algorithm to find times where the sum of digits equals the number of segments in the digital dispay

Question

So, my friend sent me a puzzle this morning:

Find the number of distinct times of the day (using 24-hour display and assuming that morning hours are presented as 8:15 as opposed to 08:15) where the number of segments are equal to the sum of the digits. Eg. 8:15 has 7+2+5=14 segments in electronic format and the sum of the digits is 8+1+5=14, so it qualifies as a case.

So I came up with the following simple (but retarded brute force) solution, in 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();

However, he added a caveat:

Brute force approach is not allowed.

I've been thinking on it for a while, and I'm struggling to come up with a smarter algorithm. I was going down the route of pre-filtering the impossibilities (eg times where the sum of the digits is less than 6, since that's the minimum segment sum) - but in the end I suppose that will only lead to a smaller solution space, which is then brute forced.

Anyway, I think it's an interesting enough problem to throw it out there and see if anyone can come up with a more clever method.

Answer 1

Each number will always have the same offset. 8 will always make your segments be one lower, 1 will always make your segements one higher, 5 will always be the same, etc. Once you know that value, you can pretty quickly generate only the valid combinations that end you up with the sums being equal.

Answer 2

Instead of storing values mapped to the number of segments, store the digit values mapped to their offsets. Clearly, any combination that yields zero will work. But we can narrow it down further.

Notice that certain digits "ruin" the combination. For example, any combination with two zeroes (-12) ruins it; there aren't enough remaining digits to give you +12. So all times during the 1000 and 2000 hour on ten-minute intervals are out (1000, 1010, ...), as are any times in this hour morning times within the first 10 minutes (1000..1009).

Three of these "ruining" combinations eliminate two-thirds of the search space. I'll leave it as an exercise to the reader which ones they are (I'm not convinced this isn't homework of some kind).

Answer 3

Since no leading zero in hours like (08:15) are allowed, we assume that midnight is represented by (0:00).

Let us define segment offset (SO) of a digit := segment sum - digit

Lets have a mapping M of digits to their segment offsets.

Minimum SO in hour section = -4 (for 7:xx) Maximum SO in hour section = 9 (for 20:xx)

Now to determine if a string hhmm satisfies your criteria, we can start scanning from the end of the hhmm string, calculate the sum of segment offsets for mm part and if the negative of that is beyond the range [-4,9] then we can reject any further calculations on that string. This will reduce the brute-ness of your approach a little bit.

Answer 4

I am confused about the whole brute-forcing thing. Isn't brute-forcing going through the entire list and selecting the correct answer? How are we then to produce only answers that yield the desired outcome, without iterating through the entire timelist? Or does brute-forcing here means doing the sum comparison between the digits and the segments?

Anyway here's a solution using python (a novice at this) and the algorithms mentioned above.

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

There are 88 results

['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']

Optimizations suggested by Joy seem to add a lot more complexity to the code so making it difficult to understand, but here's my attempt at it.

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