title: Clever algorithm to find times where the sum of digits equals the number of segments in the digital dispay
body: <p>So, my friend sent me a puzzle this morning:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>So I came up with the following simple (but retarded brute force) solution, in C# 3.0:</p>
  
  <pre><code>// Number of segments in each digit
  var digitMap = 
      new Dictionary&lt;char, int&gt;
      {
          {'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 =&gt; int.Parse(c.ToString())) == chars.Sum(c =&gt; digitMap[c])
              select t).Count();
  </code></pre>
  
  <p>However, he added a caveat:</p>
  
  <blockquote>
    <p>Brute force approach is not allowed.</p>
  </blockquote>
  
  <p>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.</p>
  
  <p>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.</p>