Wednesday, March 28, 2007

Using LINQ to solve puzzles

by fmarguerie via Fabrice's weblog on 3/28/2007 9:16:00 PM

Do you want to see LINQ used for something else than querying a database for customers or for querying an array of dummy strings? After Derek Slager who showed us how he calculates baseball statistics with LINQ, here is another different use of LINQ. Luke Hoban, Program Manager for the C# Compiler, shows how LINQ can be used to solve puzzles.

The diagram below provided by Luke shows a mobile. It consists in a bunch of weights (A-M) hanging from a system of bars. Each weight has an integer value between 1 and 13, and the goal is to figure out what each weight must be for the the diagram below to balance correctly as shown:

                          |
                          |
              +--+--+--+--+--+--+--+
              |                    |
              |                    |
           +--+--+--+--+--+        |
           |     L        M        |
           |                       |
  +--+--+--+--+--+--+     +--+--+--+--+--+
  H              |  I     |  J        K  |
                 |        |              |
        +--+--+--+--+--+  |     +--+--+--+--+--+
        E              F  |     G              |
                          |                    |
              +--+--+--+--+--+  +--+--+--+--+--+--+
              A              B  C                 D

The puzzle can be solved relatively easily using a LINQ query:

var solveForWeights =
  from a in Enumerable.Range(1, 13)
  join b in Enumerable.Range(1, 13) on 4 * a equals b
  from c in Enumerable.Range(1, 13)
  join d in Enumerable.Range(1, 13) on 5 * c equals d
  from e in Enumerable.Range(1, 13)
  join f in Enumerable.Range(1, 13) on 3 * e equals 2 * f
  join g in Enumerable.Range(1, 13) on 2 * (c + d) equals 3 * g
  from h in Enumerable.Range(1, 13)
  join i in Enumerable.Range(1, 13) on 3 * h - 2 * (e + f) equals 3 * i
  from j in Enumerable.Range(1, 13)
  join k in Enumerable.Range(1, 13) on 3 * (a + b) + 2 * j - 2 * (g + c + d) equals k
  from l in Enumerable.Range(1, 13)
  join m in Enumerable.Range(1, 13) on (h + i + e + f) - l equals 4 * m
  where (4 * (l + m + h + i + e + f) == 3 * (j + k + g + a + b + c + d))
  select new { a, b, c, d, e, f, g, h, i, j, k, l, m,
               Total = a + b + c + d + e + f + g + h + i + j + k + l + m };

solveForWeights.ToList().ForEach(result => Console.WriteLine(result));

This is an interesting approach and an innovative use of LINQ! See the details in Luke's post.