Monday, April 15, 2013

Project Euler : Intro and Solution to first 2 problems.

Project Euler is a site for mathematicians and programmers with numerous mathematical problems. I will be writing solutions in Python2.7. If you have a better approach or solution to these problems, please share.
I will be happy to take criticisms about my work. Also, if you know any other sources that offer such problems, please let us know.

Problem 1 : Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
Solution:
1
2
3
4
5
6
7
8
def multi3and5(upto):
     i = 1        # initializing loop variable i
     sum = 0
     while i < upto:        # loop will iterate while i is less than 'upto' which is 1000 in our problem
             if i % 3 == 0 or i % 5 == 0:        # if i is dividable by either 3 or 5,
                     sum = sum + i        # add the number i to sum
             i = i + 1        # incrementing loop counter
     return sum        # after final iteration, sum will hold the answer


Problem 2 : Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Solution:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def evenFibSum(upto):
    sum = 0        # initializing sum and fib to 0
    fib = 0
    num1 = 0        # the Fibonacci series starts with 0 being the first number 
    num2 = 1        # and 1 being the second number
# we loop will iterate until num2 is less than 'upto' which is 4000000 in our problem
    while num2 < upto:        
            if num2 % 2 == 0:        # if num2 is even..
                    sum = sum + num2        # add it to the sum
            fib = num1 + num2        # fib will have addition of num1 and num2
            num1 = num2        # now that we're done adding num1 and num2, our new num1 will be num2
            num2 = fib        # and num2 will be addition of fib, which was addition of previous num1 and num2
# so in next iteration, num1 will be num2 of previous iteration
# and num2 will be fib of previous iteration
    return sum        # finally, return the sum


That's it for now, I'll be back with solutions to next 2 problems soon. *Note: I prefer writing generalized solutions by providing an option to pass arguments to functions whenever possible. The purpose of these posts is not to help you cheat with Project Euler's problems, but rather give you an understanding of how mathematical problems can be solved with programming. Which is why I've not given exact answers, but the code that'll give you correct answer. You are to understand it and type it out yourself to see how it works.

Friday, January 4, 2013

Build your own social network


A Little History :
There was a time, I dreamed about me, writing a social network, and launching it. Soon, I realized, I don't know HTML, I don't know CSS, I don't know what JS is, and of course, I don't know a single scripting language. (Of course, I could write simple programs in other languages like C/C++, Java)
But I hadn't ever built something this big.

HTML was fun, I learned it quickly (Come on, who can't?), CSS was a bit tricky though, it took a few days to figure out what stands for what actually.

And then came the core-programming language of the site : PHP. I enjoyed it, I found many people criticizing it all over the Internet, but I loved it (Maybe, I haven't gotten in the problems yet, they have)

^ This all happened last year.


 Now the-real-thing :
This semester, I had to work on a website, something dynamic! There were topics like student database management system, library management system, online ticket booking, exetra, exetra!
So the dream of mine came to my mind again, a social networking site! And it took no time to finalize the topic. I was pretty happy that I was going to build a social networking site. I had no single idea how I was going to do that ( I hadn't built a single website before )
The thing is that, I hate working on the front end/UI. It takes a LOT of time to trial and error. Switch to your editor, back to your browser, back to your editor, and on and on... I just hate it. And I don't feel like I've used enough brain. It's more like – hardwork.
So I chose a guy in the class, who was willing to work on the front end, and I was happy that somebody is willing to work on it, so I'll have my freedom to work on the back-end. In next few days, we totally forgot about we have a big thing to work on, in this semester.
And then, suddenly, came our HOD, with a notice.. kind of a deadline to our projects.. WE WERE TERRIFIED!




So what challenges I faced?
  1. The thing is that we both were n00bs, and had no idea of anything. We were working together. While building a website, it is required to have the front end/UI ready before starting to work on the back end. Now I had no front end, so I built a 'temporary-template' to get me working.
  2. Now that I had some temporary-template to start working with, I had no idea of the database schema. I didn't know how to build it. Of course, I'd learned how to design it, but there was nothing about social networks in the book. I had to think.
           Then after referring some systems, I could think how it could go..


database:

  • First, I got this `users` table on the paper :

Here, what it looked like : 

userID       PK
email
firstName
lastName
password
...

Next was the `posts` table, where I was going to save the things posted by the users
postID PK
userID FK
postText
timeOn
...
Now I thought, yeah, this is pretty easy! (I hadn't thought about `friends` thing yet)

  • Relations! Relations!! Relations!!!

God, how can I save in the database, user 'x' has 3 friends, and they are a, b, and c? This is where I was stuck for like a day!
I simply drew `friends` a table like this :

friendID PK
userID FK
friendID

Now, I was feeling a bit odd about inserting two entries for the same relation (I, still do).
But anyway, at-least I've found a working solution.

  • There was a next challenge, where to save the 'friend request', and how to work with it..
So I built a new table, `friend_requests`
requestID PK
fromUserID
toUserID

as simple as that! Now, I could save friend requests sent in this table, if “toUserID” accepts the request, I would delete the entry from this table and insert a new row in `friends` table!

I was a bit happy now. At least, I could let users send friend requests, accept them, reject them, post new things to their account and let their friends see it at their home page! (Oh, I didn't mention how it'd work)

So, basically, when user logs in, I check his/her friends from `friends` table. I get all their userID's in an array, and again, make a new query to get all the posts, from the `posts` table according to their userIDs. And I'll show all these posts to the user. Simple. Also, I had to let users comment on the post, and the 'like' thing, too! It was easy, I created two new tables, `comments`, and `likes` they're as follows :

'comments`
commentID PK
userID FK
commentText
timeOn
`likes`
likeID PK
postID FK
userID FK

I'd retrieve entries as per posts from these tables, too

  • Now there was a BIG challenge! Messages!
I don't know how I did it, but, I guess, it was the most hard thing in this project. I am gonna show you how this works.
I wanted it to look like inbox in our phone. Once you open up the “messages”, you should get to see the last conversations you had, with last message in front of the user you were talking with, and the time!
So, I built two tables for it. First, message records, to save the entries of other users, x user had conversations with, and in `messages` table, I'd save the conversationID (from message_entries), senderID, and receiverID. ConversationID makes it easy to retrieve all messages of a single conversation from the table. Check tables below, you'll get the idea!

`message_records`
convID PK
user1ID FK
user2ID FK

`messages`
messageID PK
convID FK
senderID FK
receiverID FK
msgText
timeOn

Again, message_records has only one entry for one conversation. Suppose user X sends a message to user Y for the first time, I create a new entry in message_records, and get the convID to save further messages in the `messages` table. This is for the first time only. Next time, if user Y sends a message to user X, we will use the same convID to save his message in the `messages`.


So, now, I could build the basic functionalities.. And I built it in 3 days, and 3 nights. I used to take 4 or 5 hours sleep in these days. I worked pretty hard, but the result was great. This thing was working!



Then came the nightmare! I had totally forgotten about the primary thing about this site!
I'd given an unique feature in the synopsis of this project – Public & Private networks!
 " What's that? "
I was a facebook user (yes, I don't use it anymore). And the thing, I most hated about facebook was its news-feed, which would cram all those posts by applications, by pages, by friends, in a single narrow vertical bar. Most of the times, I'd lose an important post of my friend. I didn't want this thing in my site. And so, I'd found a solution on it. I created two 'networks' for each user. First, private, and second, public. Basically, you once you sign up with this site (er, it's not live, I am just telling you the idea) you get those two 'networks'. In private, you will get to see things posted by your friends only. And in public, there will be posts by 'pages', groups, applications (we don't have last two things yet)..


So, I was terrified by knowing that I don't have 'pages' stuff in this site yet! But it wasn't as hard as what I'd built up till now. To create a new page, one have to be a user of this site. One can create either a celebrity page, or a corporate page. I wrote a `pages` table in which, I could save all the details about that page. The one who create a page, would be the owner of that page, and he will have this page “liked” by-default! Also, only owner can post on this page. Only owner gets to see the 'share-box' on this page, others will see a “like” button, and if it's already been liked, an “unlike” button would be there.

So how all this work?
There is a `pages_likes` table in which, I save which user has liked which pages :

ID PK
userID FK
pageID FK

Then I'd retrieve this list whenever user clicks 'public' button above his news feed, and retrieve posts from `page_posts` and show them in the news feed of the user.
Nice hun? No more crap in between posts of your best friends, family members, or whoever you're friends with.. :)

Below, are some screen-shots of this site (which is currently on my laptop)

The login screen






 The "share-box"





Home page, and the "news-feed"






The profile page








    Thanks for taking time and reading this post. If you are interested in the project, the source code is available at GitHub. :)