Posts tagged "algorithms" « SaltyCrane Blog

Some more python recursion examples

Date: 2011-10-05 | Tags: algorithms, notestoself, python

I had a number of yaml files that contained passwords that needed encrypting. After parsing the yaml file with pyyaml, the data looked something like this:

EXAMPLE_DATA = {
    'jobs': [{'frequency': '* * * * *',
              'jobconfig': [{'config': [('*',
                                         {'maxspeed': 1048576,
                                          'password': 'onesecretpassword',
                                          'port': 22,
                                          'url': 'basset://basset1.domain.com/tootsiepop/123.csv',
                                          'username': 'myusername'})],
                             'hasbro': 'basset'},
                            {'config': [('*',
                                         {'field_delim': ',',
                                          'field_line': True,
                                          'no_blanks': True,
                                          'quote_char': '"'})],
                             'hasbro': 'pen'},
                            {'config': [('*',
                                         {'db_database': 'mydatabase',
                                          'db_host': 'myhost',
                                          'db_password': 'anothersecretpassword',
                                          'db_table': 'mytable',
                                          'db_user': 'myuser'})],
                             'hasbro': 'dart'}],
              'jobdesc': 'Data from tootsiepop',
              'jobname': 'tootsiepop',
              'max_records_fail': '110%',
              'min_failure_time': '1000y'}],
    'vendor': 'tootsiepop'}

Print all leaf nodes¶

Here is a recursive function that prints all the leaf nodes of my ...

Free Computer Science courses online

Date: 2009-06-30 | Modified: 2009-07-08 | Tags: algorithms, preferences | 3 Comments

I found out there is a video lecture series to go along with my new book The Algorithm Design Manual. The audio level is really low, but I think it will complement my book reading nicely. There are also lecture notes and homework assignments. It also turns out MIT has a huge collection of free courses online. Not all of them have video though. I listed some interesting Computer Science related courses with video below. After more searching, I found UC Berkeley also has a number of free courses online, including four Computer Science courses with video. The final source ...

Find the N longest lines in a file with Python

Date: 2009-06-28 | Tags: algorithms, python | 4 Comments

Here's a Python problem I attempted recently:

Write a program to read a multiple line text file and write the N longest lines to a new file. Where N and the file to be read are specified on the command line. Optimization is important.

Here's my solution:

import sys

def main(filename=sys.argv[1], 
         N=int(sys.argv[2])):
    """Find the N longest lines in filename and write to filename + ".new"
    """
    lines = open(filename).readlines()
    lines.sort(cmp=lambda x,y: cmp(len(y), len(x)))
    open(filename+".new", "w").write("".join(lines[:N]))

if __name__ == '__main__ ...

How to reverse words in a sentence using Python and C

Date: 2009-04-22 | Tags: algorithms, c_cplusplus, python | 7 Comments

This is a technical problem I attempted recently. The problem was to reverse the words in a sentence. For example, The quick brown fox jumped over the lazy dog. becomes dog. lazy the over jumped fox brown quick The. I had to solve the problem first using Python, and then using C. In addition, the C version could only use 1 extra character of memory. I solved the Python version easily, but the C version was too difficult for me. Here are possible solutions.

Python version

sentence = "The quick brown fox jumped over the lazy dog."
words = sentence.split()
sentence_rev ...

Python recursion example to navigate tree data

Date: 2008-08-19 | Modified: 2009-03-25 | Tags: algorithms, python | 8 Comments

Here is a simple Python example using recursion to navigate a nested Python data structure. Each node in the data structure contains 0 or more children. In this simple example, I look at each node and print the "text" indented according to the nesting level within the data structure.

Update 2008-09-15: Nihiliad posted an improvement to my example in the comments. It is much simpler. I have updated my example below.

Nihiliad's (improved) method

data = {'count': 2,
        'text': '1',
        'kids': [{'count': 3,
                  'text': '1.1',
                  'kids': [{'count': 1,
                            'text': '1.1.1',
                            'kids': [{'count':0,
                                      'text': '1.1.1 ...