Inspiration
Our team consisted of four new transfer students to UCSD. Over the last summer we all shared an amazing new program here called Academy which was made for specifically new transfer students to get an edge and complete some required classes before the start of the regular year. We took three computer science classes over five weeks and it was very difficult, but we all did very well and overcame the challenge. During this time we were also introduced to this fun card game called Set. There's a lot of really cool math involved in the game that gets taken for granted at first glance as 'intuition' or some other vague feeling. Because of our love of Set and our interest in the actual math behind it, we decided to derive an algorithm that would solve a table of cards as efficiently as we possibly can.
What it does
Given a properly sorted deck and a list of the cards on the table, it solves the table in O(n^2) time instead of the O(n^3) that would be in the standard implementation. The valid sets are then displayed to the user via a graphical interface.
How I built it
We originally started working with javascript as an excuse to practice it a bit, but as the algorithm began to increase in complexity I ported it to Java, which is now our final submission.
Challenges I ran into
We had to challenge the way we saw what a card really was. After reevaluating the ways a card is represented we were actually able to model the act of finding a set to be very similar to the 3SUM problem, that is, does a set of numbers contain three values that sum to 0. This thought process almost pigeon-holed us into trying to adapt an algorithm that solved the 3SUM problem. If we had left it at that, it would have worked 'most' of the time and would be less elegant than what we actually achieved.
Accomplishments that I'm proud of
After deliberating for awhile about how we can use our sorted deck and our new representations of cards, we figured out that we could calculate the exact card needed for a pair to become a Set and then use that information as an index into the sorted deck to find out if that card was on the table or not. This effectively made it so we were looking at each pair of cards and calculating a third instead of looking at each triple of cards.
What I learned
I learned about the atmosphere of a Hackathon and am so excited to do it again! We did a lot of cool math and though it might not be flashy like some of the other projects here, making algorithms more efficient is extremely important and an infinitely applicable skill beyond just the scope of this project.
What's next for SetSolver
Computer Vision! Point a web camera at a table of cards or take a picture and let the algorithm do the hard part for you!
Log in or sign up for Devpost to join the conversation.