Euler project: Ulam spiral

Spiral like this:

This spiral is famous because it has the fact that most of prime number are present on the diagonal position of this rectangular.

Euler problem ask for the sum of all diagonal numbers like red ones above. The prime feature could not be used because not all diagonal positions are prime number. The hint is just every turn in this spiral, the length goes like: 1, 1, 2, 2, 3, 3, 4, 4,...

Since every turn is also the diagonal, except the first one, 2, use this length growth to build the sum is easy:

Every first odd turn should be taken care of because the actual diagonal number is the one before the turn number. Also, note the last turn is not included to form the required rectangular.

Fibonacci and yield

Look at this problem 25 from euler project below:

Yes it is simple recursion:


But this one is like running forever. Considering the fact it needs the first number with 1000 digits, not surprising.

Then I start browsing and googling, met this one, using yield to generate fibonacci number; hell, when I saw the word "yield" I was like YEAH THATS IT:


When I run it I almost wet myself. So fast that makes you cant help but sing a song about it.

Basically, it returns a generator. Generator in python is lazy, it never actually calculates the next one until you force it by calling next. Old version every time it generates a new fib number, it goes to the very first and runs back one by one later. When number gets big the problem is like hell. Use generator however, you only do one addition every time, plus, in the while loop, you only return one number each time. Well I dont know you, but to a python rookie like me...


what happens to the old version? Still running.

Learning python: Iterator, Generator, Iterable object

An iterator is just like a fancy way to say "a for loop"; well it's not. I will walk through what I learn about those iters today.

There are three "iters" in Python:

1. an iterator: it is an iteration object for a class, supported by two methods __iter__ and next. Classes support iteration object could create an iterator corresponding to themselves by iter method; then one could use next method to retrieve the next element in this class object. After calling the last element, two things happen: this iterator is exhausted and could not be used anymore; any more call would result in StopIteration exception. 
2. a generator: it is a function to generate an iterator using yield. 
3. an iterable object: treat it as a repeatable iterator

After definition, let's see some codes.

1. built-in iterators

See I create four iterators using iter method. For any class supports iterator you could create an iterator using iter. Moreover, when you just use for loop directly:

What happens behind the scene is, it will automatically create an iterator based on L, and then yield one element every time. Thus, when you are using for loop, you are basically implicitly calling i=iter(L) and i.next(). But an iterator is more than for loop, because we could explicitly call next if we like.

2. user defined iterators

Now if I have a class, whose data contains a sequence, maybe a list. To enable the iterator of this class I have to implement two functions __iter__ and next:
In __iter__, normally you just need to return the object itself; in next, you have to iterate over the sequence you want, and also indicate when to terminate the iteration and give the exception. Note the count variable is initiated in constructor as a instance variable, which means it could be re-initialized; this is to meet the requirement of every iterator could only iterate once. Also, in order to use your class in a loop, you have to enable its iterator like this.

3. generator

Being a function to generate an iterator means it works similar with iter; one difference is it looks more concise in your class: you dont need a instance variable to keep track of the sequence because now all stuff about the iterator has been put into the generator function. It use the yield block to implement the iteration; I am gonna dig deeper on yield later, but it basically is able to pause the function every time and produce one element at a time.

4. iterable objects

To be fair, all things I describe above could be treated as "subclass" of iterable objects with special constraints, like an iterator could only be used once. An iterable object could be called next multiple times, and when it runs to the end of the sequence, it restarts again.

If it is an iterator, looping it twice will only display one iteration. By making your class iterable, now it basically behaves like other built-in iterable objects, like list.

So what is the take-home message? There are several situations that you have to implement iterations, like you have this class with a sequence of data as instance variable and you want to loop through them.

Project update: location

In my project, the mobile application is supposed to periodically obtain user's current location and record it into a database; this process should be done even when user quits the app. Previously, my solution is to set a recurring task using AlarmManager, which will send an alarm every 30 seconds after user starts it; another class, extends AlarmReceiver, will start a service every time it receives the alarm task; lastly, in the service class, I create a location manager to obtain location using getLastKnownLocation().

This implementation, technically, issues location tracking task exact every 30 seconds. Two problems with this. First is, although the alarm is generated every 30 seconds, the location tracking might not be finished within 30 seconds every time. There might a situation that the mobile phone has not got any location for the current alarm task when the next one is generated. I am not so sure if this is 100% correct, but I do find sometimes there will be delay in updating location, like no location update for 5 minutes, then several new location updates appear in database with the same coordinates. Anyway, I am suspecting it is because my Activity Alarm -> Service -> LocationManager process take too much time. Another problem is, every task the mobile phone creates a new service, which seems inefficient and unnecessary.

Several days ago I find this post writing about LocationManager and LocationListener, come to my rescue. Basically it explains how the method requestLocationUpdates(long minTime, float minDistance, Criteria criteria, PendingIntent intent) works. This methods aims at saving energy while giving accurate location tracking. The minTime parameter gives the time duration that the location provider will rest (status changes into unavailable) before it activates and obtain location again. The actual time interval will be equal or greater than minTime, due to several reasons: location update only be sent to the app if the difference between new and old location is greater than minDistance, also the provider might take some time to obtain the latest location. This definitely takes longer time than getLastKnownLocation(), since the latter one uses cached location.

Anyway, it seems I could use this request method directly for my periodically update, while it is not exact update, it has several advantages: there will only updates if necessary, if user does not move, my previous version will still update as alarms go on and off; also it is definitely more efficient than multiple services. Now my activity will start the service after user presses the start button, which will then register a LocationListener and request location update. Note this request will not stop until the service stops or I explicitly use removeUpdate method. Lastly, in my class of Location Listener, I put location into database in the onLocationChanged method: it gets invoked every time there is a location update from the location listener.

Some digress, I just find this Notification class which could perfectly display the app status in the notification bar. Previously, I use a textview to hold the status passed from service, but setting it globally visible is better, especially when user quits the app.


I use the sample code comes with SDK. But it is somehow deprecated, thus I change a little. This snippet of code would be put in the onCreate method of my service, so that every time my service starts there will be a notification in the bar. I also put a cancel method in the onDestroy method so that it gets killed when the service stops. Note Notification class is in API level 11 (Honeycomb), which means if you are using the same API level I use (2.3.3, level 10, GingerBread) or lower, you need to import support package in your project.

I will test this new version tomorrow.

Toggle Button and Alert Dialog

Actually I tried them before and now I dont need them in my project. But write down them just for reference.

Both of them are ways to switch among given states; toggle button has 2 states, "on" and "off", while Alert Dialog could support unlimited ones, technically. I tried them for yes/no switch because I want to let user choose whether they want only GPS (fine location tracker) or currently best one to track the location in my project.

Toggle Button is really just switching the text on the button actually. At the same time, you could extract its text at other places, like another button. User could switch to "only GPS" or "all providers" before they hit the tracking button. In the tracking button, I will first extract the text of the toggle button, and then put different info in intent to start the tracking service.

To detect which state user chooses, I create two strings in the string.xml to hold the text for two states, and then compare the current text with them. Nothing fancy here; easy to go.

Alert Dialog is another class to let user choose options. When enabled, the app will pop up a window containing options. In current version of Android, we could use AlertDialog.Builder class to build the alert dialog with the title, content, on click methods we need, and then create it.

The doPositiveClick and doNegativeClick are two methods corresponding to two choices. What they do in my version is just passing different int to the service class in the intent; the service will initiate different location listener based on the int.

Android: Broadcast locally within the app

Previously, when I need to pass some info between my Activity and Service classes, I will use Broadcast class to send a new intent containing the info from the service side, then register a receiver at the activity side. However, Broadcast class is mainly used to send info across apps, e.g. you could send some info from your app to the calendar app to create a new calendar event: it is not for communication occurred inside one app. Exposing your in-app info globally might raise security issues and also not efficient.

OK, then I find this LocalBroadcastManager class, which, according to its name, mange the local broadcast, i.e. passing info within the app (from one app component to another). This is perfect for my use. While the official doc does not provide any details on how to use it, here is an excellent tutorial covering everything we need. I summarize below just for reference:

1. get the library
This class belongs to the support package, which means you have to add the package as a 3rd-party lib  and then import android.support.v4.content.LocalBroadcastManager.

2. create the sender
Pretty straightforward.

3. create the receiver
To receive any intents, globally or locally, you first have to create and register your own broadcast receiver:

All done. Very convenient to use.

Datetime in python

I have constantly used the Datetime module in python during programming, especially in projects with database. Here I summarize some basics just for reference, because sometimes I find official python doc, while well-written, drills too much on details, which is a good thing for doc, but not for peoples who just want to get some basics and make them work.

Here we only care about two objects in this module, datetime and timedelta. Generally, we think datetime as a way to generate both date and time, like "1988 08 01 16:00", and all we (at least I) need to know about timedelta is we could use it for datetime calculation. There is also a date object that only involving date, "1988 08 11".

Before we create any time objects, let's learn some terms. UTC, stands for Coordinated Universal Time, generally the very primary time standard. Different countries in the world have different time, thought, that is because they are in different time zones. Their time is derived from the time zone offset and UTC; like in NJ, it is "UTC-4". Servers and applications using Internet tend to use UTC to store time-related data to achieve consistency.

There are several ways to create a datetime object.

now() and today() are basically the same, both generate a datetime object based on current local time, but now() has some optional arguments to make it more precise than today(), which could be found in official doc. utcnow() returns the UTC time in the same format of datetime. The last one, strptime() is to generate a datetime format object from a string. To do this you have to specific the format of the string. There is also a another method strftime() to generate a string based on a datetime object.

You could also convert the datetime object into a tuple in struct_time format of time module line 10. This is useful when you want to extract some of the time elements from a datetime object. Above are basically all I need for my small projects without any consideration on time zone stuff.

Now there is another interesting object, timedelta. I find this when I tackle a problem involving shifting time in a calendar. For example, today is July 7th, I want to shift it based on different offsets I give to it. This will cause a lot of problem if you have to design the shift rule, considering months have different number of days. However, use a timedelta object we could shift datetime object just like doing calculations:

The first line is to convert datetime object into date object since we only care about shifting days. Other parts are self-explanatory. You can also set other offset in the timedelta, including seconds, minutes, years, etc.

Finally, here is simple time parser in Java, just for reference:

I use the SimpleDateFormat class to make a time format, set time zone, then parse the long input. Including this is just because my projects involve both python and java.

Learning postgresql pt2

This actually should be the first part; because now Id like to look into db administration and management, etc.

Postgresql also use client/server model. In order to manipulate any database or its tables, we have to first connect to the database using client applications, for example, psql. This is an interactive query tool in terminal. We use it to connect to our database:

-U option provides the username that we would like to use to connect to the database. After issuing this the terminal will ask password corresponding to the username. By default, when freshly installed, postgresql will create several predefined stuff for you to get started: superuser role postgres, database postgres, etc. Therefore for the first time you could use postgres to connect to the database. After you login, the prompt will change into the name of the database you are currently logged into, now you could use various commands to know about this database.

\d displays all the tables in this database, \du displays all roles across all database clusters: in postgresql, every role acts like an account, with different privileges. Use \q to quit the interactive client. For more usage, please refer to the official manual.

I remember I come across some problems logging into the database as the default superuser, but I cannot remember exactly what the problem is. Anyway, you could always log in as the default superuser as long as you use sudo. To create your own username and password using createuser. Also createdb and dropdb is other commands that are pretty self-explanatory. Note all these commands are issued in the terminal before logging into psql.

Learning postgresql pt1

My graduate course database system teaches me many interesting things, like working in a push environment just like that in a real company, building web app, using AWS, but not database itself. In fact, until now I am still unable to write down a complex SQL query and assure you it is correct. Considering building web app alone requires me constantly manipulate database, its models and write queries,  it is time for me to roll back and study database from the scratch. I know MySQL is just a popular choice; but since Heroku uses postgresql, I might as well start with it.

As far as I know, it is an open source object relational database management system, using SQL. Relational database actually means database with tables. Other database systems like noSQL, does not require tables. ORDMS should work like: columns -> rows -> tables -> databases -> database cluster, which is stored on the database server.

Assuming you know what is relational database, what is "select xx from xx where xx", and other basics in database, let's begin. Most of codes below is from the official postgresql manual. It is great and easy to read, by the way.

Create a new table using standard sql:

Every column has a type, int, varchar, real (for floating number), etc. Brackets indicate the maximum number of this type of value could be put in this column; dashing provides description.

Line 2 indicates the primary key of the weather table. Primary key is just a constraint, which is equal vent to UNIQUE NOT NULL, i.e. the value of this column should be unique and should not be blank. By indicating this constraint, the table gives us this column as the unique identifier to identify any single row in it. One table should have at most one primary key; but a key could be a combination of several columns, as long as they do not violate the constraint. Also, it is optional for a table.

Line 7 indicates a relationship between two tables, called a foreign key. A relationship is another constraint. Now weather table will refer to the cities table for available city name. For example, now if you create a row in weather table with a city name that is not in the cities table, it will throw out an error.

Now we have two empty tables. To insert values into them:

Note now you have to first create a city in cities table and then refer it in weather table. If you have a large amount of data, you could format it in a file and use COPY command to import them into the table at once. Similarly, use COPY * TO file you could export your data in the table to a local file. Note first is the file should be publicly accessible, and second this is only allowed in the server side, i.e. you could not use COPY in a client query.

There are various ways to query data from a table:

They should be pretty self-explanatory. Note the 3rd and 4th queries join two tables to fetch data, which means they are querying multiple tables or multiple rows in one table at the same time. The 4th one is a special join, which means every row in the table mentioned on the left side of the join operator will be displayed at lease once. The output should be something like this:

Note the first row, it does not meet the constraint that "city = name" but still present, because it is in the left table. There are also some aggregate functions you could use up and go like max, min, count. However they are not allowed in the WHERE clause unless it is nested in a subquery like line 15.

To remove data from your table, you could indicate rows you want to delete by WHERE clause in a DELETE FROM query like line 22. If you don't assign any constraints, it will simply delete all rows in the table.

TBD.