Archive for May, 2011

Playing with wordpress plugins

I spent some time tonight playing with some of the wordpress plugins, one of them is ‘Facebook comments for wordpress’. Works great except I had a hard time to adjust the width of the comment box. I spent quite some time and still couldn’t figured out why the width is always set to 300px, firebug told me it is not set explicitly in any css file and there seems no good way to find how this number is calculated. well, my hacky solution for now is to add the following css definition to my  facebook-comments-widgets.css

1
2
.fb_ltr {width:100%}
.fb_iframe_widget {width:610px} /*this is according to my theme layout setup*/

would be nice to get to the bottom of it but it works fine for now.

Other plugins works great after installation.
I really like the charming new look WPtouch gave under iphone/itouch
and the many share buttons by AddtoAny

EmailDiggFacebookDeliciousStumbleUponTwitterTumblrGoogle GmailBlogger PostSina WeiboBox.netEvernoteFriendFeedGoogle BookmarksLiveJournalLinkedInPrintPrintFriendlyRedditSlashdotWordPressShare

Tags: , , , , , ,

Sunday, May 29th, 2011 css, life, tech No Comments

Finding the continuous sequence that has largest sum from a list of integers(or floats)

Long weekend could be boring, especially when you are just 3 weeks out of a major (relatively) surgery and can’t do serious outdoor activities. So I decided to dive into some of the basic algorithms and implement them in python. I used to just look at the pseudo code and thought “this is easy”. but for the past week I’ve been struggling to implement another problem (post in draft now) which really made me realize it could be much harder said than done. Admittedly some of those problems are really fundamental and most of the times people won’t bother to implement them because there are various libs to take advantage of (plus implementing your own version of same functionality from standard lib is really not a very good practice anyways). However, it is fun and really kills time. Besides, my biggest fear never is to be dumb but to be dumb without realizing it and the will the change it, struggling with those problems really help me to remind myself how bad of a coder I am and inspire me to improve it everyday.

So here is today’s problem:

Finding the continuous sequence that has largest sum from a list of integers(or floats)

The algorithm itself is pretty obvious: keep track of your sum, if it is below 0 then it won’t contribute to the max,

at that point keep what you have and then start a new iteration on the rest of the list.

My first implementation was to return the whole list, then I realized that the result will always be a subset of the original list

so just return the start and end index should be enough, it would save some space in this way.

Now it is arguable how to handle the situation when the max you can find is negative, which means you have nothing but negative numbers

in your list. I took a short cut here by returning an empty list in this case, my idea is that by returning an empty list I’m sending the message saying that you best choice in this situation is to not have anything from this list. An alternative could be scan the whole list once and initialize

the max_sum with the biggest element in the list. This won’t do harm to the O(n) time complexity.

Update: the wordpress coding syntax plugin reminds me that sum is a preserved keyword in python for sum function (shame on me that I even called that function in my code below for printing out without realizing it). Ahh, isn’t the highlighting nice? LOL

def largest_sum(self, list_of_int):
	max_sum = 0
	sum = 0
	i_max_start = 0
	i_max_end = -1
	current_start = 0		
	if list_of_int and type(list_of_int)==type([]):
		list_size = len(list_of_int)
		for index, item in enumerate(list_of_int):
			sum += item
			if sum > 0:
				if sum > max_sum:
					max_sum = sum
					i_max_end = index
					i_max_start = current_start				
			else:
				sum = 0
				if index < list_size-1:
					current_start = index +1
	return i_max_start, i_max_end				
 
def test_largest_sum(self):
	data = [[3,-7,5,-7,20,6,2,-6,4],
			[],
			[1,-2],
			[3,-7,1,-7,20,6,2,-1,4],
			[3,7,-1,-7,-20,6,2,-1,4],
			[3],
			[-7],
			[-5,10],
			[3,-2,4],
			'test',
			None]
	result = [(start, end) for (start, end) in map(self.largest_sum, data)]
	for index, d in enumerate(data):
		start, end = result[index]
		if end>=0:
			print sum(d[start:end+1]), d[start:end+1]
		else:
			print None, []

and here are the output:

28 [20, 6, 2]
None []
1 [1]
31 [20, 6, 2, -1, 4]
11 [6, 2, -1, 4]
3 [3]
None []
10 [10]
5 [3, -2, 4]
None []
None []

Something I thought about that could be interesting extension on this but yet have time to implement it or think it though:

  • 1. find all sequences with largest sum if there are more than one sequence with that sum
  • 2. find the longest/shortest one among the result from the result of 1 above (I feel that doesn’t mean don’t know if this necessarily means that I have to get the result from 1. Update: I probably still do. won’t know the largest sum if I don’t go thru them all)
  • 3. turn this question around: given the largest and smallest sum and the elements (unordered), construct the list (the answer of course won’t may not be unique)
  • 4. same as above, but construct the list so that the list has longest/shortest sequence with largest sum (first impression: separate the positive and negative value into two lists, sort them and then intersect them might be enough to achieve this… but again, ‘easier said than done’ LOL)
  • EmailDiggFacebookDeliciousStumbleUponTwitterTumblrGoogle GmailBlogger PostSina WeiboBox.netEvernoteFriendFeedGoogle BookmarksLiveJournalLinkedInPrintPrintFriendlyRedditSlashdotWordPressShare

    Tags: , ,

    Saturday, May 28th, 2011 algorithm, python, tech No Comments

    Find the largest possible number of people in circus tower

    A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.

    EXAMPLE:
    Input:
            (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
    Output: The longest tower is length 6 and includes from top to bottom: 
            (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)
    

    I really love one of the solutions I found online.
    It took several advantages of python language:

    1.lambda function
    2.bisect
    3.how python compare iterables like list and tuple by default
    (compare the first element and it is recursive!)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    
        import bisect
        def circus(input_set):
            input_set_by_y_order = sorted(input_set, key=lambda item:item[1])
            result_set = []
            for input_item in input_set_by_y_order:
                    new_guy = [input_item]
                    i = bisect.bisect_left(result_set, new_guy)
                    if i != len(result_set):
                        result_set[i].insert(0,new_guy)
                    else:
                        result_set.append(new_guy)
            return len(result_set)
     
        def test_circus():
            data_set = [(65,100), (70,50), (56,90), (75,190), (60,95),
                        (68,110),(62,144)]
            print circus(data_set)
    EmailDiggFacebookDeliciousStumbleUponTwitterTumblrGoogle GmailBlogger PostSina WeiboBox.netEvernoteFriendFeedGoogle BookmarksLiveJournalLinkedInPrintPrintFriendlyRedditSlashdotWordPressShare

    Tags: , , ,

    Monday, May 23rd, 2011 python, tech No Comments

    My weight loss trend

    There is really no secret on this: exercise and diet are your best friend.

    I’m heading toward my 100 lb weight loss goal now and I’m very close.

    dyerware.com


    EmailDiggFacebookDeliciousStumbleUponTwitterTumblrGoogle GmailBlogger PostSina WeiboBox.netEvernoteFriendFeedGoogle BookmarksLiveJournalLinkedInPrintPrintFriendlyRedditSlashdotWordPressShare

    Tags: , ,

    Saturday, May 21st, 2011 life No Comments