Bio

Noelle is a rising senior at Mountain View HS. She expresses her passion for science through participation in her school's science Olympiad team, a program she has been a part of since 7th grade. In her free time, she enjoys participating in STEAM, a program that teaches science to elementary school students.

Project: Enumerating Polycubes

Goal

Polyomino tiles are 2D tiles formed from a set of n square tiles.In this project, I worked with polycubes, their 3D cousins, which are composed of cubes as opposed to squares. My goal was to write a function to calculate the number of distinct polycube forms possible given a set of n cubes and present a visual representation of the set obtained. To achieve my goal, I focused on the optimization of any algorithms used in order to handle the maximum possible value n in a reasonable time frame.

Summary of Results

Over the course of this project, I implemented three solutions, each one faster than the other. The first thing I did was develop my minimum viable product, a complete search. This was very slow and only ran up to n = 3, but technically, it worked. To improve upon this, I looked at packing the cubes into smaller spaces to restrict the number I would generate as possibilities. I found that the sum of all dimensions of the boxes that would fit an n cube polycube were less than or equal to n + 2 (For example, at n = 3, the valid boxes have dimensions 1 x 1 x 3 and 2 x 2 x 1). I then wrote a function to generate empty grids of dimensions that fit the rule and ran a complete search on those. That was slightly faster and generated up to n = 5 polycubes. However, my final approach was a much more notable improvement and was able to generate polycubes of up to n = 8. I started with a single cube and built all possible 2-cube structures by trying to add a cube to each of its faces. I then repeated this process up to n-cube structures.

Future Work

Since this is an optimization problem, there will always be more to do in order to improve the runtime of the function and calculate the number of possibilities at a higher n, so I have a lot I can still look at. My first directive is probably to take a look at my explore function, where I relocate polycubes multiple times to different locations in the process of checking for similarities, even though the same goal could be accomplished with only one movement.