Using LINQ to solve puzzles

Using LINQ to solve puzzles

  • Comments 15

A couple months ago, I had a great time participating in Microsoft's PuzzleHunt event along with our team "Cup<T>".  Normally, the puzzles in puzzle hunt are designed to limit the value of writing programs to help solve them.  But this year, I did end up writing some code to help with one of the puzzles - and it happened to be a simple LINQ query that helped.  Since this is an example of using LINQ in a problem domain that's pretty different than the usual querying examples, I thought it might be worth sharing.

The Puzzle

Here's a puzzle similar to the one in the puzzle hunt.  The diagram below is 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 rules for this kind of puzzle are: (1) The weights on either side of a given pivot point must be equal, when weighted by the distance from the pivot, and (2) a bar hanging beneath another contributes it's total weight as through it were a single weight.  For instance, the bar on the bottom right must have 5*C=D, and the one above it must have 3*G=2*(C+D).

A First Solution

Here's what I tried first.  Note that it's not really much different than a bunch of for loops with an if statement inside:

using System;
using System.Linq;

class WeighsAndMeans
{
  static void Main(string[] args)
  {
    var solveForWeights =
      from a in Enumerable.Range(1, 13)
      from b in Enumerable.Range(1, 13)
      from c in Enumerable.Range(1, 13)
      from d in Enumerable.Range(1, 13)
      from e in Enumerable.Range(1, 13)
      from f in Enumerable.Range(1, 13) 
      from g in Enumerable.Range(1, 13)
      from h in Enumerable.Range(1, 13)
      from i in Enumerable.Range(1, 13) 
      from j in Enumerable.Range(1, 13)
      from k in Enumerable.Range(1, 13) 
      from l in Enumerable.Range(1, 13)
      from m in Enumerable.Range(1, 13) 
      where (4 * a == b)
         && (5 * c == d)
         && (3 * e == 2 * f)
         && (3 * g == 2 * (c + d))
         && (3 * (a + b) + 2 * j == k + 2 * (g + c + d))
         && (3 * h == 2 * (e + f) + 3 * i)
         && ((h + i + e + f) == l + 4 * m)
         && (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)); } }

A More Efficient Solution

Part way through writing the code above, I recognized that it wasn't going to be very fast.  It's not too hard to see that it'll execute the body of the where clause 13^13 times.  That's more than 300 trillion times!  Turns out this is exactly what join can help with, and in contrast to the for loop case, it's pretty easy to turn the query above into one which uses joins.  The following code solves the puzzle right away:

using System;
using System.Linq;

class WeighsAndMeans
{
  static void Main(string[] args)
  {
    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)); } }

Conclusion

It turns out this is an example of using LINQ to solve integer constraints problems.  In the general case, special purpose libraries built to solve these problems are almost certainly more efficient, but the LINQ example using joins is sufficiently quick at least for this case.  More importantly, the LINQ solution is not too hard to arrive at, and doesn't require knowledge of some special purpose Integer Programming framework.  I see this as an example of one of the great benefits of LINQ - that I can do all sorts of query and transformation in C# without resorting to special purpose frameworks for each different domain I need to work with.

kick it on DotNetKicks.com

Leave a Comment
  • Please add 2 and 5 and type the answer here:
  • Post
  • Do you want to see LINQ used for something else than querying a database for customers or for querying

  • Do you want to see LINQ used for something else than querying a database for customers or for querying

  • Luke Hoban recently blogged about how he used LINQ to solve a physics problem . Could it be that C#,

  • You've been kicked (a good thing) - Trackback from DotNetKicks.com

  • Recently my time has been taken up with a series of internal issues involving Beta1, C# Samples and various

  • Will there be a more efficient way of writing

    Enumerable.Range(1, 13)

    in C# 3.0? A suggestion would be

    1..13

  • Hasta el momento, cada vez que alguien menciona los peligros potenciales que comenzarán a “rondar” al

  • (This post is a slightly-edited English translation of a previous one in Spanish , with some added comments

  • Earlier this year the program manager for the C# compiler, Luke Hoban showed how he used LINQ to solve

  • Valium withdrawal. Canada valium. Vicoden valium. Side effects of valium. Valium.

  • Effexor alcohol abuse. Effexor xr.

  • Meridia sibutramine. Buy meridia online. Meridia overnight. Meridia.

  • Can anyone explain WHY the JOIN make this puzzle's solution faster in finding? How does JOIN differ than FROM deep down inside?

    One book I read said JOIN in 'keyed' and FIND is not at in-memory searches. But the book does not explain what it means by 'keyed'. Does JOIN build an index for the 13 numbers (seems silly)?

    LINQ Newbie.

  • <----Can anyone explain WHY the JOIN make this puzzle's solution faster in finding? How does JOIN differ than FROM deep down inside?

    One book I read said JOIN in 'keyed' and FIND is not at in-memory searches. But the book does not explain what it means by 'keyed'. Does JOIN build an index for the 13 numbers (seems silly)?

    LINQ Newbie. ---->

    It significantly reduces execution of where clause :)

  • BlueCoder: Join loads the inner sequence into something similar to a dictionary (Hashtable) and then able is able to do an efficient lookup for each outer element.

    Joe

Page 1 of 1 (15 items)