We are excited to announce our Mathlete Challenge winner, Kyle Gagner, who wrote a tree search program to come up with the winning numbers: 438,404 for the starter kit and 1,647,387,084 for the extended kit. Congratulations Kyle and thank you, and all those who submitted answers, for your hard work!

Here is a longer explanation about his methods from Kyle, which addresses issues such as the need to end in an output and dealing with duplicate bits:

The basic premise is a search for all possible littleBits creations, counting the valid ones that end in an output. The search begins with a full parts box, a list containing the quantity of each kind of bit you have at your disposal, and this list is passed as a list of arguments when you call the search function tree().

This search function then selects the first bit with a nonzero quantity remaining and calls the same search function again with the same parts box, minus one of the selected bit. It progresses like that through each bit with nonzero quantity remaining. However, every time it calls a search function, that function does the same thing, calling the search function, which calls the search function, which calls the search function… until all of the littleBits have been used, and all that is done before it moves on to the next step. This means that, after a bit is selected in any iteration of the search function, all permutations after that are explored before moving on to the next bit. You can view the space of all possible creations as a tree, where each branch is a part you can use, and each branch coming off of that branch is one of the parts you have left, until the tree terminates when you have no parts. However, we’re not just interested in the terminations, or even most of them, we’re interested in any node in the tree where the last used bit is an output bit.

So, while the search function does its thing, it increments a counter every time an output bit is used. The wonderful thing about this approach is that duplicate bits are of no consequence. No duplicate node is made because the algorithm differentiates between possible paths by the kind of bits available, not individual bits. Say I have two identical bits of type E, X and Y. I could use X then Y or Y then X, but this algorithm can only use E then E because all it sees is that it has two of E. Once the search is done, it has counted all nodes in the tree where the last used bit is an output.”

And here is Kyle’s C code // with annotations:

#include <stdio.h>
// this program performs a depth first tree search with the goal of finding all possible littleBits creations with the starter and extended kits
// valid creations always end in an output bit
unsigned long long found; // number of valid creations found
int bits; // number of different unique kinds of bits
int outputs; // number of different unique kinds of output bits
int *parts; // the parts bin
void search(void) // counts the number of valid creations possible given the number of each kind of part left, passed as an array
{
int i; // this is an iterator variable, used in for loops
// loop through each available part
for(i=0; i<bits; i++)
{
// this condition ensures that there is a nonzero quantity of the part left
if(parts[i]!=0)
{
parts[i]–; // remove one of the selected part from the remaining bits
search(); // perform the next iteration of the search with the remaining bits
parts[i]++; // add the removed bit back in, since we want to perform the next search with it included
if(i<outputs) // check to see whether this is an output bit
{
found++; // if so, a node in the tree search has been found which ends in an output, so this path is a valid creation
}
}
}
}
int main(int argc, char **argv)
{
int starter_parts[]={1,1,1,1,1,1,1,1,1};
int starter_bits=9; // 9 unique kinds of bits
int starter_outputs=4; // 4 unique kinds of output bits
// OUTPUTS
//    1 bargraph
//    1 LED
//    1 rgb LED
//    1 vibration motor
// INPUTS
//    1 button
//    1 dimmer
//    1 pulse
//    1 pressure sensor
// WIRE
//    1 wire
int extended_parts[]={1,1,1,2,1,1,1,1,1,2,1};
int extended_bits=11; // 11 unique kinds of bits
int extended_outputs=4; // 4 unique kinds of output bits
// OUTPUTS
//    1 fan
//    1 motor
//    1 buzzer
//    2 long LED
// INPUTS
//    1 light trigger
//    1 motion trigger
//    1 slide dimmer
//    1 roller switch
//    1 toggle switch
// WIRE
//    2 wire
//    1 branch (treated like wire for now)

// search starter kit
found=0; // initialize found to zero
bits=starter_bits; // initialize bits
outputs=starter_outputs; // initialize outputs
parts=starter_parts; // initialize parts
search(); // call the search
printf(“%llu\n”,found); // print the result to the console

// extended kit
found=0; // initialize found to zero
bits=extended_bits; // initialize bits
outputs=extended_outputs; // initialize outputs
parts=extended_parts; // initialize parts
search(); // call the search
printf(“%llu\n”,found); // print the result to the console

scanf(“%d”,&bits); // just a dummy instruction to keep the console from closing immediately (depending on how you run the program)
}

0 comments

Leave a comment

Please note, comments must be approved before they are published