Week 5 Update

Solving the game!

Goals from This Past Week

Team goals: Implement algorithms for whole design

Personal goals: Develop an algorithm to detect sets

Accomplishments

Recap of Set Rules

A valid set is composed of 3 cards where each of the 4 attributes (shape, count, color, and fill) are either a) all the same, or b) all different.

For example, a set may be the following three cards:

1. 3 green solid squiggles

2. 1 green striped squiggle

3. 2 green empty squiggles

The full rules are on the game website.

Setup

I began by setting up the infrastructure to create, store, and display cards as the algorithm processes them. This includes the following:

• A custom card class to encapsulate a card's attribute's

• A function to generate a random card

• A function to generate 12 unique random cards

• A display function to show the cards currently in play.

To represent the cards, I use text symbols associated with each attribute as shown in the table below.

Color	Shape	Fill
Red = "R"	Oval = "O"	Solid = "*"
Green = "G"	Squiggle = "~"	Striped = "="
Purple = "P"	Diamond = "<>"	Empty = "_"

Note that each card is also assigned an index for easy identification later on. That index is shown at the top of every card.

At the end of all these functions, I am left with an array of 12 "cards" and a function that displays them as follows:

Set Detection Algorithm

Finding sets is an NP-complete problem, meaning there is no efficient algorithm (source: Lampis and Mitsou, 2013). The algorithm I ultimately simply checks all possible pairings of cards for sets while using a few tricks to speed things up.

My algorithm takes advantage of the following observations:

• Given any two cards, there is only one card that will complete the set

• If each variation of a card's attribute (ex: red, green, or purple) is assigned a number, then a set where each card differs in that attribute will have a consistent sum of the numerical values of that attribute. i.e. (red = 0) + (green = 1) + (purple = 2) = 3.

Since my code associates a number (0, 1, or 2) with each variation of each attribute (ex: red, green or blue), we can use that to quickly calculate each attribute of the card required to complete a set. For example, the code to determine the color of the card completing the set started by cards c1 and c2 is:

if c1.color == c2.color:
  color = c1.color
else:
  color = Color(3 - c1.color.value - c2.color.value)

The set finding algorithm iterates through each pair of cards, determines which card would complete the set, and then searches the remaining unchecked cards for the desired card. Manually checking each combination of 3 cards requires iterating through all possible combinations among the 12 cards in play, which is a total of 220 comparisons.

With a helper function to determine the card that completes a set, finding all sets in the game is fairly straightforward:

sets = []
for i1 in range(12):
  for i2 in range(i1+1, 12):
    matching_card = determine_matching_card(cards[i1], cards[i2])
    for i3 in range(i2+1, 12):
      if cards[i3] == matching_card:
        sets.append((i1, i2, i3))
        break
return sets

Testing

I first tested the set detection algorithm on randomly generated boards. Three examples are below:

There is also an online version of the game available here: https://www.setgame.com/set/puzzle. I initially used this site to make sure I properly understood the rules of the game, but eventually I got frustrated trying to manually look for sets. So, I applied my algorithm to solve the game for me.

I manually input all the cards, asked my code to find the sets, and it gave me all the sets on the board!

Side Quest: File Management

I had a little bit of extra time, so I played around with compiling programs consisting of multiple files on the H7. Compartmentalizing our code into separate files can help make it more readable and organized. In compiled code, this also reduces the time required to compile, but I am not sure if that makes a difference in OpenMV's Python-based framework.

In my initial experiments, I got import errors when referencing custom Python modules in external files. Originally, I had these separate files saved to the same directory on my computer. This week, I tried uploading them to the H7. That worked, since it seems like the H7 searches its own local files at runtime instead of the IDE searching it's working directory at compile time.

This will allow me to take files I create on Google Colab, download them, and upload them to the H7 as a library. This will making porting future code to the H7 significantly easier.

Goals for Next Week

Team goals: Integrate the code Tyler and I have created to create a unified software system.

Personal goals: Increase the accuracy given new data from the integrated system.