Rubik’s cube algorithms

How did I get here?

So I will admit that I occasionally procrastinate when I get bored of doing a task and one of my favorite things to do is watch youtube videos. Thats when I recently stumbled upon a few videos of Rubik’s cubes. I have had a Rubik’s cube as a child and it was a really fun toy but I eventually solved the 3x3x3 cube and then proceeded to destroy it. I was definitely a very destructive child. Now a series of videos have appeared showing other extremely large cubes and polyhedrons which sparked some interest in understanding how to make an algorithm to solve these puzzles.

Here is a video of a 13x13x13 Rubik’s cube being solved.

What’s next?

Well, it would be awesome if I could buy several large Rubik’s cubes and try out different methods but that would be too expensive and time consuming. There also comes a point where it becomes too difficult to make a higher order cube due to physical and manufacturing limitations; I would say that a 22x22x22 cube is the largest I have seen but it was barely holding itself together on each turn. So lets just make a Rubik’s cube simulator!

The Specs

Okay, so we are going to make a Rubik’s cube simulator… so where do we begin? Lets just list out all of the requirements for the simulator.

It will replicate a real Rubik’s cube of any dimension up to 200x200x200
The simulator will scramble the cube
The simulator will run multiple algorithms and provide a timer
The cube can be seen from a 3d perspective

After searching on github, I had found many Rubik’s cube simulators written in different programming languages. Since my main focus of this project is to test out a few algorithms, I will take an existing github project and expand it to support my requirements. I ended up finding a project that was built in unity with C# and the 3d look of the cube was very appealing. This is the link to the project : RSolver. This will save me a lot of time looking for materials and assets.

Post is still in progress… check in later for updates =)

Pointers and Arrays

What are pointers?

Pointers are variables that hold the memory address of another variable. Please see my previous post on memory, if you need a refresher on how memory works. When you use a pointer, you are able to access the variable that it points to, and you are also able to change the pointer so it points to another variable. This process of accessing variables through pointers is called indirect addressing.

Note** Pointers are not available to be used in every programming language. Some languages like Java abstract out the usage of pointers but they are actually used under the hood. C++ is a powerful programming language that supports pointers and all of the examples in this post will be done in C++.

How are they useful?

So why do we need a pointer instead of just directly using a variable? Sometimes we need to do operations on a memory address; For example, if we have a group of variables next to each other in memory, it is easier to send to a function one pointer to the beginning address of the group than sending the whole list of variables.

Examples

Image 1 below shows an example of some integers, characters, and pointers in memory. I have shown the values of the data in hexadecimal notation and I have also provided a conversion into the matching data type. So for the integer A, the hex value is 0042 and when it is converted to base 10 it becomes 66. For the character D, the hex value is 0048 and converting it to ASCII notation gives us the letter H.

Image 1 : Example of integers, characters, and pointers in 16 bit memory

Now we will look at the integer pointer E which is located at memory address 0x9020. The value that E contains is the address of integer C.

Okay, so we see how this looks in memory, but how is it done in code?

In C++ this can be done with the following code.

//declare the variable c and assign a value to it
int c = 88;
//print the address of integer c
cout &lt;&lt; "The address of integer c is : " &lt;&lt; &amp;c &lt;&lt; "\n";
//declare the integer pointer e and assign the address of c to it
int * e = &amp;c;
//print the value that is held by integer pointer e
cout &lt;&lt; "The value held by integer pointer e is : " &lt;&lt; e &lt;&lt; "\n";
//print the value that the pointer is pointing to
cout &lt;&lt; "The value pointed to by integer pointer e is : " &lt;&lt; *e &lt;&lt; "\n";

- On line 2 in the code snippet above, we declare the integer c and assign the value 88 to it.

- On line 4, you will notice that I have printed out the memory address of the integer c that was declared by using the ampersand sign (&). In C++, this is called the address-of operator and it is used to return the address of any variable that follows it.

- On line 6, to the left of the equal sign we declare the integer pointer e. Pointers are declared in C++ by using an asterisk following the type declaration – TYPE * NAME.
  For example :
  char * character;
  int * number;
  float * decimal;character, number, and decimal are all pointers which take the same amount of space in memory but they point to different data types. The data types to which they point may not take up the same space in memory. Although they are pointers, character, number, and decimal are not considered the same type. A character pointer (char *) is not the same as an integer pointer (int *).

- On line 6, to the right of the equal sign, we are assigning the address of the integer c to the integer pointer e.

On line 10, we get the value that the pointer e is pointing to. This is called dereferencing a pointer and it is done by using an asterisk in front of the pointer name (*pointer_name). Do not confuse this with a pointer declaration like what is shown on line 6 – they may have the same symbol but the usage is very different. The dereference operator first looks up the type of pointer that is being dereferenced. Then it jumps to the memory location that the pointer is pointing to and finally converts the data at that location based on the pointer type. So if the data was being pointed at by an integer pointer, then the dereference operator would convert that data to an integer.

Memory

What is memory?

When we discuss memory in terms of computers, we are usually referring to a storage device such as a hard drive, RAM, USB stick, CD, SD card, etc. These devices are capable of storing data on them for a certain period of time. Storage devices hold a series of electric charges to represent bits. The electrical charge can be held using a variety of techniques like ferromagnetic strips in cassettes, ferromagnetic disks in hard drives, or transistors in RAM.

Image 1 below shows how data is stored on ferromagnetic disks. This technique uses a writing head which applies a magnetic field to flip the polarity of the ferromagnetic material. The polarity of the bit determines it’s value, either a 0 or a 1.

Image 1 : A diagram showing the internal writing element of a hard disk

Image 2 below shows a schematic diagram of DRAM. It is composed of an array of transistors paired with a capacitor to hold the electrical charge. Each transistor capacitor pair is used to represent a bit. If it contains a charge, the bit value is 1 and 0 otherwise.

Image 2 : DRAM schematic diagram (source : wikipedia commons)

Volatile vs Non Volatile

Memory can be classified as volatile or non volatile depending on how the charge is stored. Volatile memory loses all the information stored on it when the power is turned off. RAM is an example of volatile memory. Non volatile memory is capable of holding the data after power is removed from it. USB drives and CDs are examples of non volatile memory.

Pointers and memory are the most fundamental cornerstones of computer science but they can also be very confusing. If not coded carefully, pointers can overwrite sections of memory and lead to unpredictable results.

Accessing Memory

So we now understand the basic concept of memory, now we will try to understand how we can read and write to memory. Since hard drives and RAM are the two most important storage devices on a computer, we will discuss the reading and writing of data for those two items.

All storage devices have an organizational structure to help find information quickly. Hard drives are divide up into sectors and into concentric circles called tracks using a pattern of zeros and ones. These markers help determine the location of the reader head in relation to the data on the disk’s surface. A group of sectors is called a cluster/block which is the minimum unit the operating system will use to store information. Files can be stored in a series of blocks. The size of a block may vary depending on the size of the disk or the operating system. Hard drives also have a special file located in sector 0 of the disk. This file is used to specify how the disk is formatted. Some formatting examples are NTFS, FAT32, and exFAT. As technological advances have lead to increases in hard drive storage capacity, new formats have been developed to support the growing address space.

Image 3 : Basic illustration of the divisions of a hard disk (Source : May, J., & Lee, D. (2009, May). [Hard drive internals schematic]. Retrieved September, 2017, from https://technet.microsoft.com/en-us/library/dd758814)

RAM operates differently than hard drives since it does not have moving parts like a spinning disk. This is why accessing RAM memory is much faster than reading from a hard drive. The organizational structure of RAM is like a grid pattern with each cell having its own memory address. When we want to read the data in a cell, the memory address is sent to a decoder which selects the data lines that intersect the cell. The data is then read from the cell. The same method is applied when writing to a cell. Image 4 below shows a simplified example of how RAM works. If the value 000000 is put into the input address line, the value of the top left cell is returned. Note** There is a latch on the data select lines which is not shown in the image for simplicity. The purpose of the latch is to control reading and writing to the cells.

Image 4 : Simplified example of RAM

CPU Caches and Registers

Finally, I would like to mention that there is another piece of memory we did not talk about but is crucial to making a fast computer – the cache and the registers.

The cache is a series of smaller blocks of memory which are located inside the CPU. Why does the CPU need a cache? These caches help save time for the CPU to get data from main memory since it is a time consuming process to retrieve data from main memory. Most CPUs have three or more types of caches which include an instruction cache, data cache, and a translation lookaside buffer (TLB).

Instruction cache

The instruction cache is used to store commonly used instructions like adding two values or moving to a specific memory address.

Data cache

The data cache is a hierarchy of multiple caches (L1, L2, L3, etc). The L1 cache contains variables that are most frequently used in an application. The L2 cache contains variables that are not as frequently used but still referenced often. Higher level caches are usually shared between multiple cores of a processor.

Caches have different replacement policies to keep recently used data in the cache. One popular method is the least recently used policy. Using this method, the cache operates similar to a queue where the most recent items are kept. When the CPU is looking for a memory location and it is found in the cache, a cache hit has occurred and the item is moved up the queue to the most recently used position. When the CPU does not find the memory location it is looking for, a cache miss has occurred and the CPU looks into the next higher tier of cache until it finally searches in main memory (RAM). When the memory location is found, the value is moved to the front of the L1 cache queue and the least recently used item is removed.

Translation lookaside buffer and virtual memory

Programs running on an operating system are given a virtual address space which is much larger than what is physically available in memory. This helps to simplify the writing of computer programs where the complexities of mapping physical addresses are handled by the memory management unit (MMU). That is where the translation lookaside buffer (TLB) comes in to help find recently accessed mappings of virtual to physical memory. If the mapping is not found in the TLB, the system will look in the page tables. The page tables are a chunk of physical memory mapped to virtual memory. If the mapping is not found in the page tables, a new page will have to be read in from the disk. Image 5 below shows the process of looking up memory mappings.

Image 5: Virtual to physical address translation (source : wikipedia commons)

Registers

So what is a register? A register is a small block of memory that the CPU directly operates on by reading and writing values. Have you ever heard of someone saying that they have a 32, or 64 bit computer? That term is used to describe the size of the register that a CPU is using. Registers can be of any size, but the most common register sizes are 8, 16, 32, and 64 bit. You can find 8 and 16 bit registers on smaller processors used in embedded systems.

Here is an analogy to help you understand the whole memory hierarchy: The CPU is a carpenter and the registers are his tools that he has directly on hand. If he needs a material or tool, he can look on the nearby workbench (cache) for things that he is frequently working on. If he cannot find what he is looking for, he can go to the workshop (RAM) across the street to look for things that are less frequently used. Finally, if the item is not found in the workshop (RAM), he can go across town to search at the warehouse (Disk).

Conclusion

So far we have covered different memory technologies that are used to store data, detailed descriptions of how hard drives and RAM work internally, and CPU caches and registers. Of course there are much more complexities to understanding how memory works in modern systems but this is the foundation that we need to understand how a computer program uses memory and how to write efficient code. My next post will cover pointers and arrays.

The 0/1 Knapsack Problem

Introduction:

The bounded knapsack problem is a well known computer science problem which falls under the group of NP (Non deterministic Polynomial time) problems. This problem has been studied for over a century with some of the earliest known works dating back to 1897. It is related to the task of resource allocation and has many applications such as finding the least wasteful way to cut raw material and selection of investments and portfolios.

Description:

You are given a knapsack which can hold a limited weight ( $k$ ). You must choose from a variety of items with different weights ( $Wi$ ) and values ( $Vi$ ). The goal is to maximize the value of the items held in the knapsack without exceeding the knapsack weight limit ( $k$ ). Note* You are only allowed to take one of each item and you cannot take a fraction of an item.

Let $X_i$ be an item within the set of all items $X$ that have a weight and value

Maximize $\sum_{i=1}^{n} V_i X_i$

While $\sum_{i=1}^{n} W_i X_i \leq k$ and $X_i \in \{0, 1\}$

1) Decision problem : Can the value ( $V$ ) be achieved without exceeding the maximum weight allowed ( $k$ )?

2) Optimization problem : What is the optimal value that can be achieved without exceeding the maximum weight allowed ( $k$ )?

Computational Complexity:

The knapsack problem falls under the NP set of problems. It is non deterministic since there are multiple possible paths that have to be searched to find a solution – it is not just a linear search with simple state transitions. It is also considered polynomial time since an algorithm that takes $O(n^q)$ time or less has not been found, where n is the amount of items in the set $X$ and q is a constant. Depending on how the knapsack problem is presented, it can be considered NP-Complete or NP-Hard.

1) Decision Problem : Validating that the value ( $V$ ) be achieved without exceeding the maximum weight ( $k$ ) is considered NP-Complete.

Why is it NP-Complete? To verify that a certain value can be achieved requires that we iterate over the different permutations of items until we reach a value that satisfies the conditions. We may have to iterate over all permutations of the items but that is not always the case.

2) Optimization problem : Finding the optimal value that can be achieved without exceeding the maximum weight allowed ( $k$ ) is considered to be NP-Hard.

Why is it NP-Hard? To find the optimal value that can be achieved requires that we iterate over all permutations of the items. It is at least as difficult as the optimization problem. There is no known algorithm which is polynomial time or less that can validate if a given solution is optimal.

Test/Example Cases:

I have chosen several test cases to benchmark the performance of each algorithm. The test cases file (Knapsack_test.txt) is provided in the link below. The format of the file is as follows :

The first line contains an integer ( $c$ ) representing the amount of test cases in the file. Then the following lines will contain groups of test cases where the fist line of a test case will have the number of items available ( $n$ ) with the max weight of the knapsack ( $k$ ). The second line in the test case will have the weight of each item ( $W_i$ ) and the third line in the test case will have the value of each item ( $V_i$ ).

$c$ //Number of cases
$n \quad k$ //Case 1 amount of items , max weight
$W_i \quad where \quad i \in \{1,n\}$ //Case 1 weight of each item
$V_i \quad where \quad i \in \{1,n\}$ //Case 1 value of each item
$n \quad k$ //Case 2 amount of items , max weight
$W_i \quad where \quad i \in \{1,n\}$ //Case 2 weight of each item
$V_i \quad where \quad i \in \{1,n\}$ //Case 2 value of each item
… and so on

Analysis/Solutions:

The Greedy algorithm

The greedy algorithm will choose the best possible option for the parameter it is trying to optimize. There are multiple greedy algorithms that can be implemented for this problem. You can choose to optimize either the value or weight parameters or the value per weight. Advantages of greedy algorithms include being very fast and quick to implement. The disadvantage of a greedy algorithm is that the quality of the results may not be correct depending on the input and it will not work well on complex problems. I will show a greedy algorithm trying to use the best value per weight of the items and how it fails.

The steps of a greedy approach :

Choose the item with the greatest value per weight and check that the weight of the item is less than the maximum weight. MAX ( $\dfrac{V_i}{W_i}$ ) < $k$ .
Add the item to the knapsack and remove it from the set of items. $X_i \in Knapsack \quad ,\quad X_i \notin X$ .
Update the max weight to show that an item was added. $k = k-W_i$
Repeat steps 1 to 3 until there are no remaining items that can fit in the knapsack. while( $(X_i \in x) < k$ ) : repeat steps 1 – 3.

So lets examine an example case of how the algorithm works :

$n = 5$
$k = 10$
$W_i = \{ 2, 4, 3, 4, 5\}$
$V_i = \{ 10, 8, 1, 12, 20\}$

The greedy algorithm seems to work correctly in this case where it achieves a maximum value of 31. During the first iteration, $X_1$ is chosen since it has the highest value per weight ( $10/2 = 5$ ). During the second iteration, $X_5$ is chosen since it has the highest value per weight ( $20/5 = 4$ ) of the remaining set. During the third iteration, $X_3$ is chosen because it is the only item which has a weight that can fit in the knapsack.

Now lets look at a case where the greedy algorithm will fail :

$n = 5$
$k = 10$
$W_i = \{ 2, 4, 3, 4, 5\}$
$V_i = \{ 12, 16, 1, 12, 25\}$

In this case the greedy algorithm could not find the optimal solution. The correct solution would be to select items $X_1 , X_2, and X_4$ which would add up to a total value of 40. As you can see, the greedy algorithm can find a solution quickly but it does not guarantee that the solution is optimal.

Dynamic Programming:

Dynamic programming is a bottom up approach to solving problems where you start by solving the smallest elements of the problem. The smallest element of the knapsack problem is to select one item at a time and fit it in the knapsack and then add a heavier item to the knapsack until it is full. We will have to make a table and calculate the most efficient ordering of items for every weight (1 to k) using the following algorithm. We will denote the series of different knapsack weights as $K_i$ .

Note** To simplify the algorithm, you must first sort the set of items by weight from least to greatest. Items of the same weight are sorted by value from greatest to least.

Begin with a table of $k$ rows and $n$ columns where $k$ is the max weight of the knapsack and $n$ is the amount of items to choose from.
Initialize the first column with the value of the lightest item ( $X_1$ ) for all weights from 1 to $k$ where the item weighs less than the knapsack max weight.
Compute the optimal ordering of the next item by first checking if it can fit in the knapsack and then check if it holds a value greater than or equal to the max value calculated for the previous items () at the same knapsack weight.
1. If the value is higher, check if there is any remaining space in the knapsack for additional items.
2. If there is additional space, look up the optimal value in the max values table for the previous items ( $X_i-1$ ) at the weight difference ( $K_i - W_i$ ). Add this value to the value of the current item ( $X_i$ ) and set this as your max value.
If the item holds a lower value than the max value calculated for the previous items (), it may still have an optimal ordering which can give a max value.
1. We have to assume that the current item ( $X_i$ ) is added to the knapsack initially.
2. Next we will look up the optimal value arrangement of the previous items( $X_i-1$ ) at the weight difference ( $K_i - W_i$ ). Add this value to the value of the current item ( $X_i$ ) and check if it is greater than the max value computed for the current knapsack weight ( $K_i$ )
If the max value calculated with the current item is not greater than or equal to the previous max value entries, we will keep the previous entry value.
Repeat steps 3 to 5 until you have calculated a full table. The last entry in the table is the optimal value that can be achieved.

Lets look at an example:

You are given a function for the weights and values and the knapsack weight. Each cell contains the max value that is possible for the given max weight ( $K_i$ ) and items available ( $X_i$ ). In each cell, I have put the ordering of the items followed by the optimal value shown in red.

I have provided a C++ code sample of how to use dynamic programming to solve the knapsack problem.

</pre>
<pre>#include 

#define ITEM_COUNT 5    //This is how many items are available
#define K_MAX 10        //This is the max weight of the knapsack

/**
 * Items have a value and weight
 */
struct Item{
    int value;
    int weight;
};

/**
 * This function is used to print a matrix
 * @param mat This is a pointer to the matrix
 * @param rows This is the length of the X dimension
 * @param columns This is the length of the Y dimension
 */
template 
void printMatrix(int (&mat)[rows][columns]){
    std::cout << "Printing matrix of " << rows << " by " << columns <<" dimensions" << "\n";
    for(size_t i = 0; i < rows+1; i++){
        for(size_t j=0; j < columns+1; j++){
            if(i == 0){
                std::cout << j << "  ";
            }
            else if(j == 0){
                std::cout << i << "  ";
            }
            else {
                std::cout << mat[i - 1][j - 1] << "  ";
            }
        }
        std::cout << "\n";
    }
}

template 
void updateMaxValues(int (&max_values)[rows][columns], Item (&items)[item_count], int item_counter, int weight_counter,int k_weight){
    //Check if the item can fit in the knapsack
    if(items[item_counter].weight <= k_weight){         //Set the max value on the first iteration         if(item_counter == 0) {             max_values[weight_counter][item_counter] = items[item_counter].value;             return;         } //Check if the current item has a better value than the max value entry         else if(items[item_counter].value >= max_values[weight_counter][item_counter-1]){
            //Set the new max value to the value of the current item
            max_values[weight_counter][item_counter] = items[item_counter].value;
            //Check if there is any remaining space in the knapsack
            if(items[item_counter].weight < k_weight){                 //If we have some remaining space, look up the optimal value arrangement of items from previous entries                 int remaining_space = k_weight-items[item_counter].weight;                 //Add the optimal value arrangement of smaller items to the value of the current entry                 max_values[weight_counter][item_counter] += max_values[remaining_space-1][item_counter-1];             }             return;         }//Check if we can find another optimal weight arrangement based on the previous entries         else{             //Assume that we put the current item in the knapsac first and calculate the remaining weight             int remaining_space = k_weight - items[item_counter].weight;             if(remaining_space > 0){
                //Look up the optimal value possible using the remaining weight and items and add that to the current value
                int max_value_possible = max_values[remaining_space-1][item_counter-1] + items[item_counter].value;
                if(max_value_possible >=  max_values[weight_counter][item_counter-1]){
                    max_values[weight_counter][item_counter] = max_value_possible;
                    return;
                }
            }
            //Set the max value possible to the previous entry if a max value could not be found with the current item
            max_values[weight_counter][item_counter] = max_values[weight_counter][item_counter - 1];
            return;
        }
    }
    else {
        //There is no item that can fit in this space
        if(item_counter == 0) {
            return;
        }
        //Set the max value possible to the previous entry if a max value could not be found with the current item
        max_values[weight_counter][item_counter] = max_values[weight_counter][item_counter - 1];
    }
}

int main() {

    std::cout << "This is an example of dynamic programming to solve the 1/0 knapsac problem" << std::endl;

    //These are the items available sorted by weight and value
    Item items[ITEM_COUNT] = {{12,2},{1,3},{16,4},{12,4},{25,5}};

    int max_values[K_MAX][ITEM_COUNT] = {0};

    //Compute the max value possible for the items available at all knapsack weights up to K_MAX
    for(size_t item_counter = 0; item_counter < ITEM_COUNT; item_counter++){
        for(int weight_counter = 0; weight_counter < K_MAX; weight_counter++) {
            updateMaxValues(max_values, items, item_counter, weight_counter, weight_counter+1);
        }
    }

    printMatrix(max_values);

    return 0;
}</pre>
<pre>

The video below shows the output of the code above when running. The first column in red is the different knapsack weights and the first row in red is the items that are made available for choosing.

ABInBev Hack the World

Intro

As March was approaching, I started hearing some buzz from my network of friends that attend hackathons. They were talking about this ABInBev hackathon with huge prizes and I was honestly not very interested. I’m not much of a beer fan as much as I like wine and I tend to avoid competitions that are centered around solving problems for a specific company… it makes me feel like I am being bought out? Which I probably am. Anyway, I had nothing to do that Saturday so I ended up going.

So what is this hackathon about?

Website Description:

Anheuser-Busch beers must pass through multiple checkpoints before they can be enjoyed by consumers. After being brewed, bottled and packaged, beers are shipped to wholesalers who then have the mission of selling them to various POCs or points of contact – think your favorite bar, restaurant, grocery or liquor store. The process to get beers from the brewery into consumers hands has improved tremendously over the years but inefficiencies still remain. Help us bring innovation to POCs and deliver your favorite beers to you as quickly as possible.

Basically, they are looking for solutions to their distribution network and guaranteeing that their beer will always be stocked in a store.

Our Solution

Sajal, David and I came up with a project called shelfie. It is a beer stock monitoring system which is installed in the fridge shelf of the store. The camera will detect when the beer is out of stock and alert the beer manufacturer. It also detects the type of beer such as Stella Artois, Shock Top, Elysian, etc. Another added benefit is that the system will guarantee that the beer is located in the correct placement on the shelf and competitor beers are not located on the same shelf space.

How does it work?

The system consists of a Raspberry Pi micro computer which is installed in the store shelf and a web server to receive data from the shelfie systems for analysis. First, the Raspberry Pi captures images of the top of the beer bottles. The image is processed to find all circular looking objects in the picture which should look like the top of a beer bottle. Then the circular objects that are found are compared against a classification algorithm to determine if it is a recognized beer brand. Finally, the images of the bottle tops and location data are uploaded to the web server to be displayed on a UI showing the beer arrangement on the shelf.

Check it out

The full project is located on our devpost page : Shelfie

Here is the presentation video

Pictures

Tech Valley COG Hackathon

Intro

Okay, so this is my first hackathon that I have attended in a while and I am somewhat nervous and excited. The last hackathon I attended was in college and I managed to convince Dave and Ezafat to come with me to the competition! I was sure to pack all of my stuff like an extra monitor, power strips, sleeping bag, and tons of hackable hardware. We would travel for 3 hours from NYC to Troy NY.

Competition Description

Create IoT hacks that solve the world’s problems: Smart Health, Smart Buildings, Smart Cities…

New WiFi and internet-enabled microcontrollers are opening the opportunity to hack together new Internet-of-Things (IoT) devices. Bringing together experts, mentors, hackers and judges, the Tech Valley Center of Gravity is hosting an IoT Hackathon 2016. Powered by AT&T, and supported by Jeff Branson of Sparkfun, the IoT Hackathon promises to be a fun and exciting event to build new devices, software and teams. Focus areas include transportation and infrastructure, health care, clean technology and consumer devices, with over $1000 in prizes to be awarded.

Team Members

David Maiman
Eugene Chung
Ezafat Khan
George Balayan
Asheik Hussain

Our Project

We wanted to create an integrated solution for fire safety among the general public. Many people die every year from smoke inhalation and carbon monoxide poisoning. The recent death of a mother and her daughter inside of a car due to carbon monoxide inspired us to come up with a solution to save lives. We wanted to come up with a system that could help fire fighters find victims quickly and prevent false alarms.

Features of the Flame Warden Alarm system

Smoke and carbon monoxide sensor
Blinking LEDs and loud buzzer sound
Additional layer of fire validation via real time video analysis
Immediate alert to the authorities and registered users of a potential threat (SMS and Email)
Mobile application
Locationing of people within the hazardous area
Live image of the hazard area with count of people and type of threat

How does it work

Technologies:

Raspberry Pi
Camera / Touch Screen
Hardware Sensors (CO/Gas module/LED)
Mobile programming (iOS)
Image processing and detection (OpenCV)
Cloud Deployment (Digital Ocean)

The Raspberry Pi acts as the main unit for the fire alarm system with a smoke sensor, Carbon Monoxide sensor, camera, LED array, and speakers attached. The camera is used to count the amount of people that are in the room using OpenCV and facial recognition algorithms. The LED array is used to create a bright light to indicate that there is a fire and the speakers output a high pitch sound to alert people. When a fire is detected, the Raspberry Pi will send the data to our REST server to notify all registered devices.

Check out our project!

Here is the devpost link to our project for more info : FlameWarden

Photos

First blog post!

Welcome!

My name is Asheik and I started this blog to catalog and share some of my works/projects. I have been coding for 8 years (time really flies!). My strongest programming languages are Java and C++ but I occasionally work with Python or R.

So what is this blog about?

Well to be clear, this is not a tech blog. It is mainly for topics in computer science and math that I find interesting. Some of the items that I cover will be theoretical and some will have examples that can be implemented. Topics of interest include : compression algorithms, computational geometry, computer vision, database design, and neural networks.