Tomas Tomecek's Blog

06 April, 2012

Red Hat Open House 2012

I was looking forward to date April 5th for quite some time. Red Hat scheduled its Open House for this date.
Event itself was pretty similar, by means of organisation, to previous years. There were lots of presentations related to Open Source, linux and Red Hat of course. Unfortunately I attended only two of them -- Deltacloud and Gnome Shell. The first one was really interesting: talking about cloud technology, cloud API and the product itself, which is API between cloud provider and customer's application.
I was pretty disappointed about Gnome Shell presentation. I expected some advanced information about this "controversial" UI, but presentation itself was based on some well known facts. On the other hand I can imagine that if other viewers wasn't familiar with this shell, they could enjoy the presentation. Presenter showed some really good extensions at least, which I installed immediately after I arrived home, so I have to thank him that my Fedora is more usable now.
I attended Bug Hunt contest for the first time. I have been avoiding it for all these years (because I wasn't good at any scripting language or C/++ at that times) and this time, I just couldn't resist, since I started learning Python. Contest was organised very well. It really impressed me -- but should I wonder? It is Red Hat. The thing which impressed me even more, was that I ended on second place. I earned it just by correcting some python sources and finding some bugs in provided, "bugfull" program.
That's it. This was Red Hat Open House 2012 from my point of view.
Wait.
But there's more!
View from the top of the building was perfect. Chilly breeze was just the thing what I needed. Also buffet was full of tasty yummies, just like every year. I attended server room, which fascinates me more and more every year. Guys answered all of our questions. That gave me really good feeling, how nice and chatty these guys were.
I would like to thank Red Hat for this spectacular event -- awesome as always.

31 March, 2012

Post Correspondence Problem

I found out that one of topics on my final exam will be Post Correspondence Problem. Definition of this problem is pretty straightforward. I am not going to write down formal definition, since it is available on Internet.
You have given two lists A = (a₁, a₂, a₃,...) and B = (b₁, b₂, b₃,...) with same number of items. Each list contains strings. The task is to determine if exists sequence of indexes -- integers i₁, i₂, i₃,... such that a_i₁, a_i₂, a_i₃,... = b_i₁, b_i₂, b_i₃,....

Example

A = (abb, a, bab)
B = (bba, aab, b)

So our task is to make one word with one list of indexes using A and B.
In the first step we have to pick wisely, because we might end pretty early. Using index 1 would be a bad choice because abb and bba can't be prefix of the same word. Indexes 2 and 3 are far better choices. Let's say I pick 2. So our word looks like this right now:

A: a
B: aab

It's easy to see, that we have to find string with prefix ab in list A. We are lucky! Index number 1 fulfills our condition:

A: aabb
B: aabbba

Similar situation, but prefix to be found is ba in A. Index 3 fits:

A: aabbbab
B: aabbbab

Both strings match, we have found a solution: (2, 1, 3).

Programming

I couldn't understand, how come that this problem is undecidable (I haven't read proof proving undecidability). So I tried to program it using python. Basicly the problem could be seen as a graph problem (from the brute force perspective) -- searching for correct path in a tree. Actual code might be buggy since I didn't test it much:

def returnSuffix(a, b):
 result = ''
 aLen = len(a)
 bLen = len(b)
 if aLen > bLen:
  if a[:len(b)] == b:
   return a[len(b):]
  else:
   return None
 else:
  if b[:len(a)] == a:
   return b[len(a):]
  else:
   return None

def getStr(a):
 return ''.join([''.join(v[1]) for v in a]) 

a = ['bba', 'abb', 'bb', 'a']
b = ['bb', 'b', 'abba', 'ba']

depth = 0 
aString = []
bString = []
indexes = []
choices = []
firstRun = True
found = False

while firstRun or len(choices) > 0 or len(aString): 
 firstRun = False 
 deadEnd = True 
 #pdb.set_trace()
 for idx, val in enumerate(a):
  if returnSuffix(getStr(aString) + val, getStr(bString) + b[idx]) != None:
   print 'adding %d to choices' % idx
   choices.append([depth, idx])
   deadEnd = False
 print 'choices: %s' % choices
 if not deadEnd:
  lastItem = choices.pop() 
  indexes.append(lastItem[1])
  aString.append([lastItem[0], a[lastItem[1]]])
  bString.append([lastItem[0], b[lastItem[1]]])
  if (getStr(aString) == getStr(bString)):
   print 'Solution found! %s' % indexes
   found = True   
   break
  depth = lastItem[0] + 1
  print getStr(aString)
  print getStr(bString)
 elif len(choices) == 0:
  break;   
 elif deadEnd:
  if (aString[-1][0] == 0):
   aString.pop()
   bString.pop()
   indexes.pop()
  else:   
   while choices[-1][0] <= aString[-1][0]:
    aString.pop()
    bString.pop()
    indexes.pop()
    depth = depth - 1
  if len(choices) > 0:
   lastItem = choices.pop()   
   indexes.append(lastItem[1])
   aString.append([lastItem[0], a[lastItem[1]]])
   bString.append([lastItem[0], b[lastItem[1]]])
   depth = lastItem[0] + 1
 if depth > 10:
  print 'depth is bigger than 10'
  break;
if not found:
 print 'Solution not found'

So what does this code do? Variables aString and bString represents actual path in a tree, while variable choices contains pointers to alternative branches. Variable depth represents the level in a tree. Function getStr just returns the actual state of building the string. Function returnSuffix returns suffix of word built from a which differs from b and vice versa. If the two words are invalid, it returns None.
And now the actual algorithm. For current vertex program computes all the branches and add them to choices. If the branch is dead end, it will return back to the last crossroad and tries alternative branch. If it's not, it pops last item from choices and continues. So basically it's Depth-first search. The only problem is that we are not searching one tree, but more of them. These are specified as depth=0 items in choices. So if you walk whole tree there has to be different routine to jump to another three -- if (aString[-1][0] == 0):.
So why is the problem undecidable? Because the tree may contain infinite paths and there is no way out how to decide whether the path is infinite or just "too long" -- depth variable. That's the exact definition of undecidability:
A problem is undecidable if it cannot be solved by any Turing machine that halts on all inputs.

27 March, 2012

How to configure Django and MySQL on OpenShift

Not a long time ago I wanted to try OpenShift. After I found out that it supports Python and then even Django I instantly knew, it might be home for my Django project.
When I tried to configure my instance I realized, it will be pretty tough fight (even with couple of tutorials out there). I will try to write down some handful tips (mainly for myself -- this means that there might be some incomprehensible terms, grammatical errors (English is not my native language) and lots of elementary stuff -- I consider myself still a linux & python & django & web development newbie. Despite these flaws I can imagine that these tips might be useful for somebody.).

First step is pretty obvious -- register an account -- plain & simple.
Now it is time to create an application. I followed this awesome tutorial & used that sample project, so it would be counterproductive to repeat it again.
It could be nice to have some database -- I chose MySQL. Applications (like MySQL) are based in a form of cartridges, so you just have to add it:

rhc-ctl-app -e add-mysql-5.1 -a $APP_NAME -l $LOGIN
But this isn't just enough. Some sort of database client would be nice. Let's add phpMyAdmin:

rhc-ctl-app -e add-phpmyadmin-3.4 -a $APP_NAME -l $LOGIN
You should note the login credentials for both services.
For first we have to set up MySQL database. Log in to phpMyAdmin, on main screen go to tab Privileges and click here on link Add a new user. Fill username and password (save these, we will use them in settings.py) and then check value Create database with same name and grant all privileges. In this step we have new database with dedicated user, who is going to be used by django. There is one thing, which may caused you to have nightmares in sleep. It is collation. By default it is set to latin1_swedish_ci, but I am using utf8_general_ci. I advise you to set it right now, because later you would have to convert data from one collation to the another or even wiping some tables.
Now we have to set up django application to use MySQL. We have to edit settings.py:
```
if ON_OPENSHIFT:
    DATABASES = {
        'default': {
            'ENGINE': 'django.db.backends.mysql',
            'NAME': 'username', #username specified in step before
            'USER': 'username', #username specified in step before
            'PASSWORD': 'password', #password specified in step before
            'HOST': os.environ['OPENSHIFT_DB_HOST'],
            'PORT': os.environ['OPENSHIFT_DB_PORT'],
        }
    }
```
If we try syncdb now, it won't work, because there is not database driver for MySQL. Open setup.py and add module MySQL-python to install-require and pip will install it. It will look like this:

install_requires=['Django>=1.3','MySQL-python'],

Database is created, but is empty. We have to execute syncdb to fill it. It might done from command like, but that's not very practical. Better way is to add this command to action hook. Open file .openshift/action_hooks/deploy and edit it to look like this:

#Activate VirtualEnv in order to use the correct libraries
source $OPENSHIFT_GEAR_DIR/virtenv/bin/activate
export PYTHON_EGG_CACHE=$OPENSHIFT_GEAR_DIR/virtenv/lib/python-2.6

echo "Executing 'python $OPENSHIFT_REPO_DIR/wsgi/openshift/manage.py syncdb --noinput'"
python $OPENSHIFT_REPO_DIR/wsgi/openshift/manage.py syncdb --noinput

echo "Executing 'python $OPENSHIFT_REPO_DIR/wsgi/openshift/manage.py collectstatic --noinput'"
python $OPENSHIFT_REPO_DIR/wsgi/openshift/manage.py collectstatic --noinput

python $OPENSHIFT_REPO_DIR/wsgi/openshift/manage.py createsuperuser --username=admin --noinput --email me@example.org
#python $OPENSHIFT_REPO_DIR/wsgi/openshift/manage.py changepassword admin

You have to use correct path, so change it accordingly. This script does syncdb, collectstatis and last command creates superuser. I didn't find out how to change superuser's password through script (mainly because bash is not really my friend) so I did it by connecting to server and executing it manually:

ssh uuid@domain # for example ssh a01e3eebf93c947d33e862e20c41f43b@django-username.rhcloud.com

And now execute these 3 commands:

source $OPENSHIFT_GEAR_DIR/virtenv/bin/activate
export PYTHON_EGG_CACHE=$OPENSHIFT_GEAR_DIR/virtenv/lib/python-2.6
python $OPENSHIFT_REPO_DIR/wsgi/openshift/manage.py changepassword admin

And that's it. Enjoy your django application.

Pages