Maker Faire

Hi guys,

First, to let you know, I've created a seperate blog, USACO coding blog, for specific coding stuff or math-ish stuff. All others, like EE, will remain on this blog.

Also, I had a fun time at Maker Faire Bay Area 2015, and met some awesome people, such as Arduino co-founder, Massimo Banzi, and Raspberry Pi founder, Ebon Upton.

(Left is Massimo Banzi, Right is Ebon Upton)

Project Euler: How to Solve Problem 1 in O(1) Time!!

Just a short story about this problem:

Project Euler (named after mathematician Leonhard Euler) is a site where you can solve interesting programming problems that incorporate both math, logic, and the "art of coding".

Unfortunately, the problems at this website are too easy to cheat; there was only an answer box, confirmation code, and one could make a really, reallllllllllly slow program and still get a right answer.


Credits: https://projecteuler.net/
Then, I stumbled upon HackerRank, which had also had ProjectEuler-like challenges called "ProjectEuler+" , in fact, they were the same, the only difference was the added feature of Time-Limits and Memory-Limits.

How I Solved it projecteuler.net:
I had solved Problem 1 (Multiples of 3 and 5), which had asked the sum of all the multiples of 3 and 5, in O(N) time, where N was the input number.

(The less value the variable in the O, the less time it takes to execute the program. Check out this website if you are unfamiliar with Big-O notation)

This program iterates from 1 to N, and keeps checking if the current iteration is divisible by either 3 or 5, and increments the count (t) if it is. (The alreadyhere is to prevent counting repeats when the number is divisible by 15)

t = 0

N = input()
for  i in range(N):
    if(i % 3 == 0):
        alreadyhere = 1
        t=t+i
    if(i% 5 == 0 and alreadyhere == 0):
        t=t+i
    alreadyhere = 0
  
print t

But, when I had attempted to re-solve Problem 1 in Hacker-Rank, it had told me that my program took too long. How do we make it faster, in O(1) time?

Solution for HackerRank Problem
The aim here is to write a one-liner equation for the sum of all the multiples of 3 and 5, we need to also exclude the values of 15 (already counted twice, in 3 and 5).
The structure here is:

 

This then can be expressed as:

Notice the right half (after the coefficient), it is in a way similar to the famous x(x+1)/2, which expresses the sum of all numbers 1...X. Instead, we use n/m to replace x here, as there are n/m multiples of n. However, this sum is only for sum of all integers 1,2....n/m. So, by multiplying the coefficient here (which is m), we can sum the multiples of m, so the net sum here is 1*m,..2*m,....n

*Note - in the code and example, I had to subtract one from num because it wanted factors less than the input num given

For example: n=15, m = 3

(15-1)/3[1+(15-1)/3]/2 = 1 + 2 + 3 + 4 = 10

Factors of 3 for num less than 15 are 3,6,9,12

3*(15-1)/3[1+(15-1)/3]/2 = 3+6+9+12 = 30

Answer is 30.

Here is the source code:
(run by input in a num to pe(num), output will be factor)
 def pe(num):
num= num - 1
return ((3*(1+num/3)*(num/3)/2)+(5*(1+num/5)*(num/5)/2))-(15*(1+num/15)*(num/15)/2)

Full run code: (Note the for loop is to test each test-case, so it doesn't contribute to the O(1) runtime)

k = input() #number of inputs


def pe(num):
num-=1
        #one liner formula!!!
return ((3*(1+num/3)*(num/3)/2)+(5*(1+num/5)*(num/5)/2))-(15*(1+num/15)*(num/15)/2)

for i in range(k):
    testcase = input()
    print(pe(testcase))
    
(Note: Please don't copy answers, this article is only for informational purposes. It's not worth it, and you will not learn anything.)

USACO problem - hopscotch Part 1

Problem using recursion.

Recursion is when a function calls itself over and over again, and is used in both math and programming.

I.e. in fibonacci sequence, f(x) = f(x-1) + f(x-2)
It is calling its last two numbers and adding them to get the current position.

In this problem, we recursively find the sum of the ways we can reach our destination. However, this is NOT fast enough (!)  to solve this problem, there is a better way I will show later, called dynamic programming.

Problem From:
http://www.usaco.org/index.php?page=viewproblem2&cpid=530

Psuedocode:
function cowhop (CurrentRow, CurrentColumn, lastLetter):

       sum = 0

       for i: CurrentRow->R-1:
            for j: CurrentColumn->C-1 :
if grid[i][j] != lastLetter:
sum = sum + cowhop(i,j, oppositeLetterOf(lastLetter) )

if grid[CurrentRow][CurrentColumn] != grid[R][C]:
sum = sum + 1 
        
return sum

(Note: for simplicity of non-coders, I started the indicies of array "grid"  from 1, not 0! )
(Note also the grid is 0,0 from top left and 4,4 on bottom right. Not your normal coordinate system)
How it works:

We give in a value of CurrentRow and CurrentColumn for each run. (The base case is (R=1,C=1))
Then we search any values that are different from CurrentRow,CurrentColumn to R-1,C-1.

The reason for skipping far right/far bottom is we have to be minimum one down AND one right to make valid jump. If we are already far down, we can't go down anymore!

There are four: 3,2,2,4. We don't bother searching on the last row or the farthest right row because there aren't anything more down or more right; we have to jump to a square at least one down AND one right.

We start from the first one, and do cowhop(2,2). We land on a "3".

We only have the "4" to search, and it is in fact different from the original "3". So we search "4" and run cowhop(3,3).

The only way to go is to the end, grid[R][C], which is 1.

This means cowhop(3,3) has returned a value of 1.

Tracing back,  we see if cowhop(2,2) has any more to search. Nope, so back. 

We will  carry the value of 1 from cowhop(3,3) to this cowhop(2,2), as we can go from (2,2) to (3,3). Note it is also different than the last one, so we can go down, adding one to total sum. 

Cowhop(2,2) will return a sum of 2.

Tracing to the farthest back, from cowhop(3,3) = 1 -> cowhop(2,2) = 1+1 = 2 -> cowhop(1,1).

We also add the 2 to the sum of cowhop(1,1), so for now, there are two ways.

But(1,1) still has more ways! There are 2,2,4 to search from, we only did "3"!

We will start with 2, since it is the next one.  We will continue diving deeper into the grid and back tracing until this:

Our final answer is 5.

XCode iOS apps

Just made my first iOS app (other than Hello-World)
This is a reflex timer, which times how good your reflex response is.
Here's a video of it working in the ios simulator:

OpenCV Shapes Detection

In this blog post, I will show how I used Python on OpenCV to recognize shapes when displayed on a webcam.  I chose Python because it is easy to understand, but C/C++ is slightly harder and executes quicker. My code (at bottom) is pretty accurate (~85%) at detecting shapes, but it has problems recognizing some blue hues.

    You will need to install OpenCV and numpy python modules before this. There are guides on the internet available for this topic. In addition, you need Python 2, not 3 to run this. You access this by going to terminal and typing 'python' or 'python2'. Also the newest OpenCV distro doesn't work with Python- 2.7.8, so use 2.7.3 instead.

The general steps are:

1. Set up your webcam

2. Read a frame of the picture

3. Erode and Dilate the picture to remove unnecessary noise

4. Set a color range to only get shapes of a specific color (in this case I chose blue)

5. Check your picture if pixels are in that color range

6. Get the Contours (basically lines that join areas with similar colors)

7. Iterate through them and get only the biggest one

8. Approximate the biggest contours' number of sides (cv2.approxPolyDP) to find how much sides

9. Correspond this number of sides to shapes' names (quad, triangle, etc.)

The code is available here on github if you want to try it out. This code I wrote only accepts BLUE shapes, so keep that in mind while printing test-cards.

Here's a video of me trying out different shapes:

Here is me testing each shape:

Square/Quadrilateral:

Triangle:

Pentagon:

7-sided figure (Arrow):

Browser "Virus" Handling

I decided to compare a few browsers to see how well they could handle a fake virus.


 This code, written in HTML and Javascript, will make infinite alert popups, saying 'Try to Quit'.

This could be very annoying, because alerts stop you from doing anything in the browser. In this case, it will never allow you to visit other pages. Trying out this code in Safari even made me to force-quit, which could make you lose a lot of unsaved/valuable info.

For those of you willing to risk it, try the html code:


<!DOCTYPE html>
<html>
<body>

<p>Click to die:</p>

<button onclick="myFunction()">Virus Attack</button>

<script>
function myFunction() {
  while(1) {//Infinite Loop!
    alert("Try to quit!");
  }
}
</script>

</body>
</html>

(copy-paste this code to a text-editor and save it as a .html file)

(press the Virus Attack button, and the popups will appear. If you have trouble, just force quit the app)

Disclaimer: I am not responsible for any damage caused by this fake virus. USE AT YOUR OWN RISK!!!!! 

Now, the error handling:

Google chrome did a good job, as it was able to detect repetitive messages, giving me the option to stop the virus:

After check marking it, I recieved no more popups.


Firefox couldn't disable repetitive messages, but unlike safari(the last one), it didn't stop you from saving/closing webpages:











On Safari, it did the worst, because it couldn't cancel, while all other webpages are stopped:



So far, I would say Chrome is the best ranking in this test, then Firefox, while Safari din't do a great job handling the fake virus attack.

Crystal Growing

Here's another nice chemistry experiment I did recently: growing blue crystals from vinegar,peroxide,and copper. Copper is usually brownish colored, but when it is combined with any acidic substance (in this case vinegar), and  hydrogen peroxide, it converts to its blue form.

The crystal I will be showing is called Copper Acetate.

This usually happens with most the transition metals in the periodic table of elements . This includes copper, iron, cobalt, nickel, and maganese (not magnesium). These metals, originally silver colored, will create different crystal colors.


Disclaimer: Since this experiment involves heat, and  Oxygen gas is produced, it's HIGHLY recommended you do this OUTSIDE or in a fumehood.  Oxygen can help sustain fires. I am not responsible for any injury or loss to any person by doing this experiment, by mistreating the instructions, or by not moving outside or in a fumehood.


These are the materials you need (I used electrical wire for copper. You can't use modern pennies as they contain more zinc than copper) You also need a heat-resistant glass, as we'll deal with heat in this experiment.

Here's the steps:
1. Take an equal amount of peroxide and vinegar, then mix them in your beaker. Do this BEFORE you add copper!

2. Heat it up, if you want to make this experiment go faster. You can use a microwave at around 10 seconds, or if you are not willing to contaminate your microwave, you may use a torch or candle to heat. This heating is optional, but without it, you may have to wait a day for the reaction to finish.

3. Now drop in the copper, and the liquid should fizzle and turn blue. This bubbling is Oxygen gas, so it's recommended you do this outside without any flames nearby!! Oxygen can sustain fires!

4. This process is finished when there is no bubbling left. Remove the copper and wait for the cup to naturally dry.

If you want to know the chemical equation for this reaction, it's:

Cu + 2 CH₃COOH + H₂O₂ = Cu(CH₃COO)₂ + 2 H₂O

The bubbling is caused separately, because copper is a catalyst in decomposing hydrogen peroxide.

2H₂O₂  = 2H₂O + O₂


Here are my results:

These crystals aren't big, but I have made bigger crystals(by a method called supersaturation)

They appear black, but holding them to light makes them blue.