Operation Guesser

Inspiration

We were trying to make a project that is both challenging and doable within a timeframe of one week. Seeing that the operation guesser is a problem-solving task, we were excited to collaborate and work together on deriving different solutions for the challenge.

What it does

The project consists of two parts:

1. A console application that allows the user to enter a sequence of numbers, a target value. The program displays an arithmetic expression equivalent to the target.

2. A UI game that allows a user to drag the arithmetic operations between numbers.

How we built it

For the solver, we started with a brute force recursive algorithm. Our base cases are: -0 elements: forming target is impossible -1 element: check if the element is equal to the target -2 elements: check all combinations of these numbers

While the base case of 2-element is redundant, we noticed that including it is faster, so we kept it.

Next, in the recursive case, we iterate over each pair of numbers n1 and n2 and identify the possible operations on these numbers. Using these possible operations, we create a new target and recurse on the rest of the list.

If a solution cannot be reached, we define n3 as the combination of n1 and n2 e.g. n3 = n1 + n2. We remove n1 and n2 from the list, and insert n3 back in the list. Then, we recursively check if the target is reachable with the new n3 inserted.

Later, we further optimized the code. The optimizations are mentioned in the "accomplishments" section.

Challenges we ran into

• Going into the competition, we didn't have a lot of experience with UI design. One challenge was learning how to create a drag and drop interface in a native library such as pygame.

Accomplishments that we're proud of

• While we are not professional graphical designers, we are proud of the UI we were able to design. After the game was complete, we all enjoyed playing the game.
• We are also proud with our optimizations of the algorithm. By memorizing past solutions, we were able to significantly improve the runtime complexity of the program. Also, by checking for an upper bound and a lower bound on the possible results that can be made, we were able to improve the worst-case complexity of the program.

What we learned

• It was our first experience creating a side project of this scale, without direct supervision, or instructions from any course. We learned that teamwork is extremely powerful. Each member of our team has done a significant part of the project.

What's next for Operation Guesser

• While we used pygame to prototype the game, we are hoping to extend the operation guesser and deploy it to the web. In this way, the game will be accessible to children around the world.

Built With

• pygame
• python