this is a solver for the Set Game at http://www.setgame.com/set/

written by mengwong@pobox.com 20060930

With thanks to Jeremy@Tavan.com for introducing me to the game,
and with a shout out to Greg Connor and Melissa Lewis who played it.

USAGE:

1. create a text file describing the set cards that are on the table
2. run findset on that text file
   findset < eg/setgame-20060930.txt 2>/dev/null

MANIFEST

    20060930-11:55:11 mengwong@newyears-wired:~/src/setgame% ll -R
    total 8
    drwxrwxr-x    6 mengwong  mengwong   204 Sep 30 11:55 ./
    drwxrwxr-x   35 mengwong  mengwong  1190 Sep 29 11:29 ../
    -rw-rw-r--    1 mengwong  mengwong   227 Sep 30 11:54 README
    drwxrwxr-x    3 mengwong  mengwong   102 Sep 30 11:55 bin/
    drwxrwxr-x    3 mengwong  mengwong   102 Sep 30 11:54 eg/
    drwxrwxr-x    3 mengwong  mengwong   102 Sep 29 11:30 lib/

    ./bin:
    total 8
    drwxrwxr-x   3 mengwong  mengwong   102 Sep 30 11:55 ./
    drwxrwxr-x   6 mengwong  mengwong   204 Sep 30 11:55 ../
    -rw-rw-r--   1 mengwong  mengwong  1156 Sep 30 11:53 findset

    ./eg:
    total 8
    drwxrwxr-x   3 mengwong  mengwong  102 Sep 30 11:54 ./
    drwxrwxr-x   6 mengwong  mengwong  204 Sep 30 11:55 ../
    -rw-rw-r--   1 mengwong  mengwong  202 Sep 30 11:54 setgame-20060930.txt

    ./lib:
    total 0
    drwxrwxr-x   3 mengwong  mengwong  102 Sep 29 11:30 ./
    drwxrwxr-x   6 mengwong  mengwong  204 Sep 30 11:55 ../
    drwxrwxr-x   5 mengwong  mengwong  170 Sep 30 11:55 Set/

    ./lib/Set:
    total 24
    drwxrwxr-x   5 mengwong  mengwong   170 Sep 30 11:55 ./
    drwxrwxr-x   3 mengwong  mengwong   102 Sep 29 11:30 ../
    -rw-rw-r--   1 mengwong  mengwong  1577 Sep 30 11:45 Card.pm
    -rw-rw-r--   1 mengwong  mengwong  1768 Sep 30 11:50 Set.pm
    -rw-rw-r--   1 mengwong  mengwong  1851 Sep 30 11:50 Table.pm

EXAMPLE INPUT DATA

    20060930-11:55:14 mengwong@newyears-wired:~/src/setgame% cat eg/setgame-20060930.txt
    #
    # number: 1, 2, 3
    # colour: r, g, p = red, green, purple
    # fill:   c, h, s = clear, half, solid
    # shape:  o, p, d = oval, peanut, diamond
    #
    1phd
    2php
    3gcd
    2rcd
    1pco
    1rho
    1rcd
    2gcd
    3psd
    2gcp
    2pcd
    3psp

EXAMPLE RUN

    20060930-11:55:16 mengwong@newyears-wired:~/src/setgame% perl -Mlib=lib bin/findset < eg/setgame-20060930.txt 2>/dev/null
    on the table, we have half-one-purple-diamond
    on the table, we have half-two-purple-peanut
    on the table, we have clear-three-green-diamond
    on the table, we have clear-two-red-diamond
    on the table, we have clear-one-purple-oval
    on the table, we have half-one-red-oval
    on the table, we have clear-one-red-diamond
    on the table, we have clear-two-green-diamond
    on the table, we have solid-three-purple-diamond
    on the table, we have clear-two-green-peanut
    on the table, we have clear-two-purple-diamond
    on the table, we have solid-three-purple-peanut
    1:half-one-purple-diamond, 9:solid-three-purple-diamond, 11:clear-two-purple-diamond
    2:half-two-purple-peanut, 5:clear-one-purple-oval, 9:solid-three-purple-diamond
    3:clear-three-green-diamond, 7:clear-one-red-diamond, 11:clear-two-purple-diamond
    4:clear-two-red-diamond, 8:clear-two-green-diamond, 11:clear-two-purple-diamond
    6:half-one-red-oval, 8:clear-two-green-diamond, 12:solid-three-purple-peanut
    6:half-one-red-oval, 9:solid-three-purple-diamond, 10:clear-two-green-peanut

To view the thought process at work, leave off the 2>/dev/null.

ALGORITHM

Given any two cards, the rules of Set dictate what the third card must be.

To solve a given spread of cards, one need only examine every pairing in search of the third card.

If the third card is on the table, we've found a set.

In this implementation, we traverse a 2 dimensional array of
cards, deducing what the third card must be in the spots
marked ?, and looking to see if that card is on the table.

    1 2 3 4

  1   ? ? ?
  2     ? ?
  3       ?
  4

The algorithm complexity is thus approximately O(n^2 / 2) + O(n).