Life is to be sung

July 22, 2007 at 12:37 AM | categories: cool stuff, videos | View Comments

Achievement is overrated. Not worthless mind you, just overrated. The value of achievement is weighted so heavily in our lives that we tend to neglect the very prerequisites for it.

This is what beauty is: to find happiness and fulfillment in every single day.

Lifelong 'achievement' cannot be realized unless it is done daily. This country's education system and expected work schedules don't help much in this regard but it cannot be blamed for my lack of daily achievement. I can achieve something and find fulfillment in spite of the apathy that may surround me.

This video is very inspiring to me. Because of it I am reminded that I must refuse the concept that I will someday arrive at the beginning of my life.

I am already here.

I always have been.

What I do today is what counts.

Read and Post Comments

My Hobby: Solving XKCD puzzles on my lunch break

July 09, 2007 at 11:16 AM | categories: python, geek humor | View Comments

I like geek comics. I especially like geek comics that have an embedded NP-Complete problem:

XKCD July 9, 2007
There are 2 solutions:
Solution #1:
        <MenuItem Mixed Fruit 215>
        <MenuItem Hot Wings 355>
        <MenuItem Hot Wings 355>
        <MenuItem Sampler Plate 580>
Solution #2:
        <MenuItem Mixed Fruit 215>
        <MenuItem Mixed Fruit 215>
        <MenuItem Mixed Fruit 215>
        <MenuItem Mixed Fruit 215>
        <MenuItem Mixed Fruit 215>
        <MenuItem Mixed Fruit 215>
        <MenuItem Mixed Fruit 215>

This isn't "as fast as possible" to be sure, but it should be a general solution.

#!/usr/bin/env python

"""Attempt to solve XKCD from July 9 2007"""

#All monetary values are in pennies to avoid floating point errors
# (Yea, I could use decimal.Decimal but it's SLOW!)

import operator

class MenuItem:
    def __init__(self, name, price):
        self.name = name
        self.price = price
    def __add__(self, other):
        if hasattr(other,"name") and hasattr(other,"price"):
            #This is a MenuItem
            return self.price + other.price
        else:
            return self.price + other
    def __repr__(self):
        return "<MenuItem %s %s>" % (self.name,self.price)
        
appetizers = ( MenuItem("Mixed Fruit",      215),
               MenuItem("French Fries",     275),
               MenuItem("Side Salad",       335),
               MenuItem("Hot Wings",        355),
               MenuItem("Mozarella Sticks", 420),
               MenuItem("Sampler Plate",    580))

target_price = 1505

def find_solutions(stack=[],solutions=set()):
    """Find combinations of appetizers that equal target_price"""
    #Find if initial stack equals target_price
    stack_price = sum([x.price for x in stack])
    if stack_price == target_price:
        #print("Found a solution!!! " + str(stack) + " == " + str(target_price))
        stack.sort(key=operator.attrgetter('price'))
        solutions.add(tuple(stack))
    elif stack_price > target_price:
        #No solutions for this stack
        return set()
    #Recurse for each item
    for item in appetizers:
        find_solutions(stack + [item])
    return solutions

if __name__ == "__main__":
    solutions = find_solutions()
    print "There are %d solutions:" % (len(solutions))
    solution_num = 1
    for solution in solutions:
        print "Solution #%d:" % (solution_num)
        for item in solution:
            print "\t%s" % item
        solution_num += 1

Update July 10: Visitor wac pointed out that my program is pretty inefficient. I agree - I did it really quick on my lunch break yesterday. For order values above $20 it becomes an intractable solution pretty quick. Here is a much more efficient solution that implements value caching (at the cost of requiring more memory than the previous solution):

#!/usr/bin/env python

"""Attempt to solve XKCD from July 9 2007

This is a new version that uses a cache for calculations
"""

#All monetary values are in pennies to avoid floating point errors
# (Yea, I could use decimal.Decimal but it's SLOW!)

import operator
import sys

class MenuItem:
    def __init__(self, name, price):
        self.name = name
        self.price = price
    def __add__(self, other):
        if hasattr(other,"name") and hasattr(other,"price"):
            #This is a MenuItem
            return self.price + other.price
        else:
            return self.price + other
    def __repr__(self):
        return "<MenuItem %s %s>" % (self.name,self.price)
        
appetizers = ( MenuItem("Mixed Fruit",      215),
               MenuItem("French Fries",     275),
               MenuItem("Side Salad",       335),
               MenuItem("Hot Wings",        355),
               MenuItem("Mozarella Sticks", 420),
               MenuItem("Sampler Plate",    580))

class OrderCache:
    """a cache of all the possible variations of an order for a given price"""
    def __init__(self):
        self.cache = {0:set([()])} # price -> set([(item1,item2 ...), ...])
    def derrive_order(self, price):
        "Return all combinations for a given price"
        try:
            return self.cache[price]
        except KeyError:
            orders = set()
            for item in appetizers:
                if price - item.price >= 0:
                    for order in self.derrive_order(price - item.price):
                        new_order = list(order) + [item]
                        new_order.sort(key=operator.attrgetter('price'))
                        orders.add(tuple(new_order))
            self.cache[price] = orders
            return orders

if __name__ == "__main__":
    if len(sys.argv) == 2:
        target_price = int(sys.argv[1])
    else:
        target_price = 1505
    order_cache = OrderCache()
    solutions = order_cache.derrive_order(target_price)
    print "There are %d solutions:" % (len(solutions))
    solution_num = 1
    for solution in solutions:
        print "Solution #%d:" % (solution_num)
        for item in solution:
            print "\t%s" % item
        solution_num += 1

With the improved version I can calculate order values up to $75 in under a minute. That's interesting in and of itself really, because although the second algorithm is much more efficient it would still be practically impossible to calculate an order value of $1000. That's the nature of NP problems for you.

Read and Post Comments

Single sign-on everywhere

July 02, 2007 at 09:35 PM | categories: python, security, linux | View Comments

Using a single password for every site you visit is really stupid. However, the alternative, making unique and secure passwords for every single site you visit can get tedious and unmanageable quickly.

A long while ago I started memorizing about 10 different passwords of various security levels, thinking that I can mitigate the risk by grouping similar sites together under one password. Memorizing 10 passwords really isn't that hard to do if you're dedicated.. but it still isn't that much smarter than a single password.

Then I started using KisKis, a Java application with which I could store all my passwords in an encrypted form. Although it's very secure and I liked it at first, it became really tedious to create a new entry every single time I made a new account somewhere and then to open the application up and look up the password every time I needed it. Add to that that I had to come up with a way of synchronizing my passwords on all of the machines I use - it became a real pain.

In about 2004, Firefox came along with the ability to store passwords in an encrypted form right inside your browser. What a godsend! Now I can make a new unique password for every site I visit and have the browser remember it for me.

However, I still have one problem. I use a lot of different computers and there is still no easy way to synchronize passwords between firefoxen on different machines.

A couple days ago I found this: PwdHash. PwdHash is a rather ingenious method for generating a unique, secure password for every single site you visit and yet the password is based on a function of a master password and the URL itself, so you don't even need to store the password, you can simply generate it whenever you need it. Almost magic really.

However, I still have a few security related issues with it. I think that it is likely there are websites out there that could implement a keystroke logger in JavaScript or even more likely in Macromedia flash. So the ideal solution for me is to have the same functionality outside of the browser completely. This isn't so bad when combined with Firefox's ability to cache passwords. To PwdHash's credit, the developers have gone to great lengths to make sure that PwdHash is secure, I'm just paranoid. It's my flaw, not theirs.

So here is my first stab at a PwdHash-like python application (Note that this is not compatible with PwdHash. I didn't want to have the temptation of using their software when I'm at some public terminal.) You can run this standalone on any unix like OS (I find it most convenient to have it long running inside of GNU Screen.)

How to run:
  • python site_pass.py
  • The first time it is run you have to create a master password
  • Now simply enter a URL (either a full URL like http://www.enigmacurry.com or simply enigmacurry.com)
  • It will generate an eight character password for you, now copy and paste that into your webbrowser and have firefox remember the password.
  • If you ever need to look up the password again, simply rerun the application, enter the URL, and you'll get the exact same password back again. Since it is a hash of your master password and the domain name you don't ever have to store the password (except in your browser for convenience). Just generate it again whenever you need it.
  • Do the same for all your other accounts and only look up your password again on other computers that have yet to cache the password

Now you'll never have to go through the process of "I forgot my password" again!

One word of caution however. Don't run this on your friend's box or any other place where you don't have full control of the root account. Your master password resides in memory and could be seen by root if he really wanted to.

Also, this is an alpha release (I wrote it in about an hour's time just today). Progressive.com, my car insurance doesn't like any punctuation in a password. If I find other sites that don't like the generated password I may have to modify the hashing function which would mean that any passwords created with this version would need to change to use a forthcoming version.

Download
Read and Post Comments