Python server with Flask

With Flask and SQLAlchemy I talked about in the last post, I was able to implement a python server. It is able to show a list of restaurants in the main page. Clicking on restaurant names show their menu, and each menu item can be edited or deleted. Users can also create new menu items. The database uses SQLAlchemy, and url resolving and HTTP requests handling use Flask, a microframework that makes implementations of web servers very easy.

The link to the project on GitHub is here.

With flask, resolving url addresses is simply app.route('format'), and under this line declare the method for this address. Here is an example:

This means whenever the address fits the format host/restaurants/int, the method restaurantMenu will be executed. restaurant_id is a variable extracted from the url and passed in the method as a parameter. Whatever this method returns shows up on the webpage. In this case, the method is returning the result of render_templaterender_template is a method in Flask that looks for the template specified in the first parameter in /templates and pass in necessary variables. menu.html looks like this:Screen Shot 2016-01-13 at 9.40.55 AM

items is the variable passed in this template. Here html execution arguments are used.

url_for is another tool used in this project. It is also included in Flask. The first parameter is the handler method of the product url, and other parameters are variables passed.

The next step is for methods to handle both GET and POST HTTP methods. Here’s how to do it:

methods need to be put in @app.route. Of course, request class also needs to be imported from Flask. Handling different kinds of methods is virtually the same as handling one. It’s only one if statement away.

Finally, for the server to repond to requests with JSON object, objects in the database need to have a function that returns all of their information.

In object class of the database setup python file:

And then use jsonify class provided by Flask to return json:
return jsonify(MenuItem = menuItem.serialize)
The json can then be used by any kind of application!

As a next step of this project, I plan to implement a server that works with iOS applications. I may need to write a framework for Swift to talk with my server. This means a lot of work, but it has great potential!

I’ll just forget about the fact that I have a midterm 30 minutes later and one more tomorrow.

Using SQLAlchemy in python to control database

SQLAlchemy is an open-source python module that let developers easily create and manipulate databases with python. SQL language is not required because everything is already encapsulated inside the module. It also conveniently has a “session” feature that provides a function similar to git – all changes can be staged and committed altogether.

An introductory tutorial can be found here.

The idea is called Object Relational Programming(ORM). SQLAlchemy lets you use object oriented programming language such as python to operate on databases. For example, for a Student table in a database, it can have several attributes: id, name, and school. id and name can be represented by primitive types but school may be another object. In the actual database, there is a link from the student to the school that he or she belongs to. SQLAlchemy transforms this relationship into object references, which makes it easy to update tables with python code that can be run on a server.

Here are some basic code segments that can be used:

#import and basic setup
import os
import sys
from sqlalchemy import Column, ForeignKey, Integer, String
from sqlalchemy.ext.declarative import declarative_base
from sqlalchemy.orm import relationship
from sqlalchemy import create_engine

Base = declarative_base()

The above piece of code import necessary modules. Column, ForeignKey etc are not default python classes, so they must be imported. A declarative_base is a class that contains a database table, a mapper which matches the table with python class, and a class object. An engine stores data in the local directory.

class Restaurant(Base):
    __tablename__ = 'restaurant'

    id = Column(Integer, primary_key=True)
    name = Column(String(250), nullable=False)


class MenuItem(Base):
    __tablename__ = 'menu_item'

    name = Column(String(80), nullable=False)
    id = Column(Integer, primary_key=True)
    description = Column(String(250))
    price = Column(String(8))
    course = Column(String(250))
    restaurant_id = Column(Integer, ForeignKey('restaurant.id'))
    restaurant = relationship(Restaurant)

As you can see, it is very easy to create classes in python/tables in database. “__tablename__” always needs to be provided. Other elements are declared like normal classes. String(n) means this String can have as many as n characters. When nullable is true, the column can never be empty.

At the end, engine needs to be started:

engine = create_engine('sqlite:///restaurantmenu.db')

Base.metadata.create_all(engine)

After this, a restaurantmenu.db file will be created at local directory and fully functional. Hooray!

That’s pretty much it. I’ll update when I learn more. Code for this post is from Udacity.
 

Code for Finding Median in Linear Time

import java.util.ArrayList;
 
public class LinearMedian {
	public int mMedian(int[] raw) {
		if (raw.length == 1) return raw[0];
		int[] medianArray = new int[(raw.length - 1) / 5 + 1];
		for (int i = 0; i < (raw.length - 1) / 5 + 1; i++) {
			int start = i * 5;
			int end = i * 5 + 5;
			int[] temp;
			if (end <= raw.length)
				temp = new int[5];
			else {
				temp = new int[raw.length - start];
			}
			for (int j = start; j < end && j < raw.length; j++) {
				temp[j - start] = raw[j];
			}
			medianArray[i] = smallMedian(temp);
		}
		return findMedian(medianArray, medianArray.length / 2);
	}
 
	public int smallMedian(int[] raw) {
		for (int i = 0; i < raw.length - 1; i++) {
			for (int j = i + 1; j < raw.length; j++) {
				if (raw[i] < raw[j]) {
					int temp = raw[i];
					raw[i] = raw[j];
					raw[j] = temp;
				}
			}
		}
		return raw[raw.length / 2];
	}
 
	public int findMedian(int[] raw, int k) {
		if (raw.length == 1) return raw[0];
		int median = mMedian(raw);
		if (raw.length <= 5) return median;
		return partitionMedian(raw, median, k);
	}
 
	public int partitionMedian(int[] raw, int median, int k) {
		if (raw.length == 1) return raw[0];
		ArrayList<Integer> left = new ArrayList<Integer>();
		ArrayList<Integer> right = new ArrayList<Integer>();
		for (int i = 0; i < raw.length; i++) {
			if (raw[i] < median) left.add(raw[i]);
			else if (raw[i] > median) right.add(raw[i]);
		}
		if (k > left.size() && k < raw.length - right.size())
			return median;
		else if (k < left.size()) {
			int[] leftArray = new int[left.size()];
			for (int i = 0; i < left.size(); i++) {
				leftArray[i] = left.get(i);
			}
			return findMedian(leftArray, k);
		}
		else {
			int[] rightArray = new int[right.size()];
			for (int i = 0; i < right.size(); i++) {
				rightArray[i] = right.get(i);
			}
			return findMedian(rightArray, k - raw.length + right.size());
		}
	}
 
	public static void main(String[] args) {
		int[] input = new int[] {6, 2, 1, 5, 3, 7, 9, 10, 123, 4, 3};
		LinearMedian test = new LinearMedian();
		System.out.println(test.findMedian(input, input.length / 2));
	}
}

Progress of Wheeshare

Wheeshare has finally achieved all of its necessary functionalities. Before it could provide functions such as request, approve request and lend, but it was impossible for user to “step back” from the relationships with cancel request or re-lend item. Now users are able to cancel their requests and owners of items can re-lend their stuff once they have them back from the last borrowers. Besides this breaking relationship improvement, users can now view the status of their items in the main table view, such as “lended to Bill” or “requested by Jason”.

The logic of the relationship is pretty efficient. I used a little bit of binary spirit while designing it. Each item has three variables relevant to the borrow-lend relationship: giver, requester, and connected. Among these three, giver and requester are of type PFUser (user class written by Parse, which tragically is going to close in one year, fml), and connected is a Bool. Giver for an item is the owner and cannot be changed for the lifespan of the item. Whenever a user requests an item, the requester variable of the item will be given the value of this user. Connected means if the relationship is successfully built. If the owner presses “approve request”, connected will be changed to true.

Therefore, two free variables produce three possible outcomes:

  1. requester is not null and connected is false. The item is currently available and no one has requested.
  2. requester is someone and connected is false. The item is requested but not approved yet.
  3. requester is someone and connected is true. The item is in a borrow-lend relationship.

requester is null && connected is true cannot happen because that doesn’t make any sense.

As for deleting the items, owners are not allowed to delete their items on the platform if the items are requested or in a relationship. They are prompted to take care of the requests.

Things to do: improve UI HARD. If I knew I would be developing iOS apps, I would have gone to some art clubs back in high school. Switch to another online database or write one by myself with php and SQL. The latter would be challenging but also very rewarding.

The other day I discovered an app called PartiO, which aims at exactly the same thing as my app – let students share their stuff. The only difference is that they let people share with profits. I have already contacted them and wish to help them improve the product. Hopefully we will achieve something together.

OK these last two paragraphs just made me add “Babbles” to the category of this post.

An interesting coin problem

Okay I admit I got busy with classes and jobs last week and did not update, so I decided just now to write about this problem we talked about in CS330 discussion last week.

Problem:
Consider the following game:
There is a line of coins with values 𝑣1, 𝑣2 … 𝑣𝑛 (𝑣1 is the value of the left-most coin, 𝑣2 is the value of the second leftmost coin… 𝑣𝑛 is the value of the right-most coin).
Each player takes turns taking either the left-most or rightmost remaining coin until all coins are gone. A player’s score is the sum of the values of the coins he takes on his turns. Using dynamic programming, write an algorithm which, given the current sequence of coins 𝑣1, 𝑣2 … 𝑣𝑛 in the form of the array 𝑉, determines the score of the two players if both play optimally, i.e. play to maximize their score at the end of the game. Report its runtime as well.

Solution:
The central spirit of dynamic programming is to dismantle the problem into steps and only caring about each step. The recursion will simply take care of the rest. In this particular problem, what we care about is which coin the player chooses at his/her turn. There are only two options: choosing the left-most or the right-most. After that we are going to have a smaller subsequence of coins, which we will leave to the recursion process. Therefore, we can store the best possible scores for the two players for each subsequence.
A subsequence is determined by two variables: its start point and end point. However, if we increment these two variables to do dynamic programming we are going to have a problem: the current entry will depend on both larger index and smaller index of results to calculate, which will cost us a lot of time. As an alternative, we can increment the start index and the length of subsequence. The next step is to figure out the dp equation.
Let A[i, j](1) and A[i, j](2) denote the best possible scores of two players if they start playing next on the subsequence A[i, j]. c[i] is the value of coin i. Obviously, A[i, i](1) = c[i] and A[i, i](2) = 0. Suppose player 1 is facing the subsequence A[i, j]. He can pick either the coin i or j, obtaining a vlue of c[i] or c[j]. If he picks coin i, his gain would be A[i+1, j](2) + c[i]. Number 2 is in the parentheses because for the sequence A[i+1, j] left after his pick, he would be considered the second player. Similarly, if he picks coin j, his gain would be A[i, j-1](2) + c[j]. Therefore, for this player, A[i, j](1) = max(A[i+1, j](2) + c[i], A[i, j-1] + c[j]).
Now let’s consider the other player. For the subsequence A[i][j], what is left for the second player is completely dependent on which coin the first player picked, so two possible subsequences for player 2: A[i+1, j] and A[i, j-1], for which he is considered the first player. Now we can derive the complete relationship:

For subsequence A[i, j]:
    if (A[i+1, j](2) + c[i]) > (A[i, j-1] + c[j]):
        A[i, j](1) = A[i+1, j](2) + c[i]
        A[i, j](2) = A[i+1, j](1)
    else:
        A[i, j](1) = A[i, j-1](2) + c[j]
        A[i, j](2) = A[i, j-1](1)

Again, we can’t increment on i and j in this case. Instead, we can increment the start index i and a length l. j would be equal to i+l-1.
I am beginning to experience the power of dynamic programming. The problem is since it’s so powerful, the test for this class could be insanely hard…