Scrabble High Score

Unlike my other projects, this one isn’t complete yet, but I’ll show what I’ve done so far. I was playing a lot of scrabble with my grandmother, and I always take a long time on my turns trying to find the highest scoring move, which made me wonder, “What’s the highest scoring move you could theoretically get?” Assuming an ideal setup, what’s the most points you can score in one move in scrabble?

I starting with the idea of using three triple letter tiles. To use all three, you need to create a fifteen letter word across one of the edges of the board, but you only get seven tiles to play. The only way to get all three triple letter tiles is if there are existing words spanning some of the gaps between the tiles. We want there to be exactly seven spaces free so we can play all the tiles. Additionally, we want the board to already have words perpendicular to the fifteen letter word so we can add on to them and get more points. In the code I call them cross words. The most important cross words are those next to the triple letter tiles. I wrote a program that will check every possible setup for the existing words along where our fifteen letter word will be and the triple cross words. Here is the result visualized (the letters played this turn are slightly tinted green):

View fullsize

Image created using Scrabulizer.

The score from this setup is 1724 points. Now all I have to do is find more cross words to increase the score! Well, not quite. My program doesn’t take into account the limited number of letters in scrabble. There are four Zs used in this scenario, but there is only one in standard scrabble. So if I’m able to account for that there isn’t much more work until I find the answer!

The code for this project can be found on GitHub here.

MATE Competition Benthic Species Detector

This project was part of programming for the 2019 MATE Ranger competition. I was part of Sidwell’s senior team, Fox Enterprises. You can find that year’s tech report, spec sheet, and job safety analysis hosted on MATE’s website. My documentation for the benthic species detector from that year is available here as part of the GitHub repository for the project.

MATE’s competitions are about high school teams acting as “companies” to propose an underwater remotely operated vehicle (ROV) that they build and is able to complete a series of tasks. The tasks are simulations of realistic applications of ROVs, and a large part of your company’s score is the product demonstration, where your company uses your ROV to attempt to complete as many tasks as possible.

One of the steps from Task 2: Maintaining Healthy Waterways from the competition entailed determining the number and type of benthic species under a rock. Benthic organisms are organisms living on the bottom of bodies of water, but since everything was simulated, there were no living things in the product demonstration. The rock is actually just PVC pipes attached to a corrugated plastic sheet, and the benthic species are an image of of simple shapes each representing an organism.

View fullsize

MATE’s simulated rock. Image from the 2019 Ranger prop building instructions.

MATE’s simulated benthic species. Image from the 2019 Ranger prop building instructions.

Our goal was to count how many of each shape there are. If we do it manually we get 5 points, but if we do it with a program we get 20 points. So I set out to write that program.

I used a library called OpenCV to help count the shapes. To demonstrate what the program does by visualizing it on MATE’s image of the species. First I change the image to gray-scale and apply a bilateral filter to sharpen edges and smooth everything else.

View fullsize

Next I use OpenCV’s canny edge detector. Here is a visualization of the edges:

View fullsize

Then I use OpenCV to find polygons that approximate the edges. Here they are shown in red over the original image:

View fullsize

I remove a lot of the bad polygons by only considering the convex polygons:

View fullsize

Next I constrain the allowable areas of the polygons:

View fullsize

And now I only have the shapes and two false positives! Luckily, the next steps eliminate those for some reason. Now that I have a few simple polygons to consider, I can categorize them by figuring out if their roughly equilateral or equiangular using some math on their vertices’ locations. When running my program I display the same thing as the previous image, but with the recognized shapes colored green and an overlay showing the shape counts. Here’s what the user sees (usually the image is wider so the overlay isn’t occluding anything):

View fullsize

Unfortunately, this system isn’t perfect. There were many parameters I could adjust to tweak the detection slightly, so it was hard to find the right ones. If I resize the image slightly and then use the same program I get this:

View fullsize

It doesn’t detect the center circle. Another member of our company/team came up with a great idea to make it more reliable and stable. If I just use the maximum shape count the program has seen, that is usually the correct answer.

The program got us the 20 points at internationals, and we placed 12th!

The code for the project is available on my GitHub here.

Solitaire Chess Solver

Several years ago I was playing a puzzle game with my dad and my sister called Solitaire Chess. We eventually got stuck on a puzzle for hours, and unlike the other similar puzzle games we have, the back of each card describing the puzzle wasn’t the solution but another puzzle. To find the answer I decided to write a program to solve it. I spent the rest of the evening and some of the next morning working on it until I found the solution.

Solitaire Chess is based on how chess pieces capture each other. Instead of pieces only being able to capture a piece of the opposing color, all the pieces are the same color and can take any other. The starting arrangement is defined by the puzzle’s card, and your goal is to eliminate all but one piece only through capturing. ThinkFun’s product page demonstrates this well:

View fullsize

ThinkFun’s how to play Solitaire Chess image (altered)

Or at least it would have if they didn’t put moves two and three the wrong way around:

View fullsize

ThinkFun’s how to play Solitaire Chess image

Making a program that solves any puzzle isn’t too complicated. To code how each piece captures other pieces I created helper methods to define their movement by either relative positions or a “look direction.” Kings, knights, and pawns can only capture pieces at a few positions relative to them, and rooks, bishops, and queens “look” in different directions and can only capture in their line of sight. If I was doing this project now I would probably use an enum for the piece types, but at the time I decided to use static instances of an abstract class.

I used recursion to do what I later learned is called a depth first search. The program iterates over all possible next boards states and makes a recursive call using each of them to solve the puzzle from there. If there are no more possible moves, the attempt either failed because there are still multiple pieces left, or the program has found the solution. I never bothered to have any kind of input or output for the program, so the puzzle setup is hardcoded in a 2d array, and I just used IntelliJ’s debug mode to view the resulting list of moves.

Much later I found out that the solutions to the puzzles were in the instruction manual all along. But at least I enjoyed the project.

You can find the code on my GitHub here.