SaltyCrane: algorithmshttps://www.saltycrane.com/blog/2011-11-01T09:37:32-07:00Find all combinations of a set of lists with itertools.product
2011-11-01T09:37:32-07:00https://www.saltycrane.com/blog/2011/11/find-all-combinations-set-lists-itertoolsproduct/<p>Copied from
<a href="http://stackoverflow.com/questions/2853212/all-possible-permutations-of-a-set-of-lists-in-python">
http://stackoverflow.com/questions/2853212/all-possible-permutations-of-a-set-of-lists-in-python</a>.
Documentation: <a href="http://docs.python.org/library/itertools.html#itertools.product">itertools.product</a>
</p>
<pre class="python">import itertools
from pprint import pprint
inputdata = [
['a', 'b', 'c'],
['d'],
['e', 'f'],
]
result = list(itertools.product(*inputdata))
pprint(result)</pre>
<p>Results:</p>
<pre>[('a', 'd', 'e'),
('a', 'd', 'f'),
('b', 'd', 'e'),
('b', 'd', 'f'),
('c', 'd', 'e'),
('c', 'd', 'f')]</pre>
Some more python recursion examples
2011-10-05T19:35:31-07:00https://www.saltycrane.com/blog/2011/10/some-more-python-recursion-examples/<p>I had a number of
yaml files that contained passwords
that needed encrypting. After parsing the yaml file with
<a href="http://pyyaml.org/">pyyaml</a>, the data looked something like this:
</p>
<pre class="python">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'}</pre>
<h4 id="print-leaf-nodes">Print all leaf nodes</h4>
<p>Here is a recursive function that prints all the
<a href="http://en.wikipedia.org/wiki/Tree_%28data_structure%29#Terminology">
leaf nodes</a> of my nested data structure.
</p>
<pre class="python">def print_all_leaf_nodes(data):
if isinstance(data, dict):
for item in data.values():
print_all_leaf_nodes(item)
elif isinstance(data, list) or isinstance(data, tuple):
for item in data:
print_all_leaf_nodes(item)
else:
print data
print_all_leaf_nodes(EXAMPLE_DATA)</pre>
<p>Results:</p>
<pre>tootsiepop
1000y
tootsiepop
*
basset://basset1.domain.com/tootsiepop/123.csv
myusername
onesecretpassword
1048576
22
basset
*
True
"
,
True
pen
*
anothersecretpassword
mytable
myhost
mydatabase
myuser
dart
* * * * *
110%
Data from tootsiepop</pre>
<h4 id="get-leaf-nodes">Get all leaf nodes</h4>
<p>This function returns all leaf nodes as a list instead of printing them.
A wrapper function is used to create a Namespace instance to hold the
results variable. This could alternatively be stored in a global
(module-level) variable. See my
<a href="/blog/2008/01/python-variable-scope-notes/#ex7-set-outer-workaround">
notes on variable scope</a> for more info about using a class as a namespace.
</p>
<pre class="python">def get_all_leaf_nodes(data):
class Namespace(object):
pass
ns = Namespace()
ns.results = []
def inner(data):
if isinstance(data, dict):
for item in data.values():
inner(item)
elif isinstance(data, list) or isinstance(data, tuple):
for item in data:
inner(item)
else:
ns.results.append(data)
inner(data)
return ns.results
from pprint import pprint
pprint(get_all_leaf_nodes(EXAMPLE_DATA))</pre>
<p>Results:</p>
<pre>['tootsiepop',
'1000y',
'tootsiepop',
'*',
'basset://basset1.domain.com/tootsiepop/123.csv',
'myusername',
'onesecretpassword',
1048576,
22,
'basset',
'*',
True,
'"',
',',
True,
'pen',
'*',
'anothersecretpassword',
'mytable',
'myhost',
'mydatabase',
'myuser',
'dart',
'* * * * *',
'110%',
'Data from tootsiepop']</pre>
<h4 id="get-key-value-leaves">Get all leaf key value pairs</h4>
<p>This function gets all key value pairs where values are not compound data structures
(i.e. dicts or lists)
</p>
<pre class="python">
def get_all_key_value_pairs_where_values_are_simple(data):
class Namespace(object):
pass
ns = Namespace()
ns.results = []
def inner(data):
if isinstance(data, dict):
for k, v in data.iteritems():
if (isinstance(v, dict) or
isinstance(v, list) or
isinstance(v, tuple)
):
inner(v)
else:
ns.results.append((k, v))
elif isinstance(data, list) or isinstance(data, tuple):
for item in data:
inner(item)
inner(data)
return ns.results
from pprint import pprint
pprint(get_all_key_value_pairs_where_values_are_simple(EXAMPLE_DATA))</pre>
<p>Results:</p>
<pre>[('vendor', 'tootsiepop'),
('min_failure_time', '1000y'),
('jobname', 'tootsiepop'),
('url', 'basset://basset1.domain.com/tootsiepop/123.csv'),
('username', 'myusername'),
('password', 'onesecretpassword'),
('maxspeed', 1048576),
('port', 22),
('hasbro', 'basset'),
('field_line', True),
('quote_char', '"'),
('field_delim', ','),
('no_blanks', True),
('hasbro', 'pen'),
('db_password', 'anothersecretpassword'),
('db_table', 'mytable'),
('db_host', 'myhost'),
('db_database', 'mydatabase'),
('db_user', 'myuser'),
('hasbro', 'dart'),
('frequency', '* * * * *'),
('max_records_fail', '110%'),
('jobdesc', 'Data from tootsiepop')]</pre>
<h4 id="modify-nested-dict">Modify values of terminal key value in a nested dict</h4>
<p>This function modifies all the values of all dicts that are not compound data structures
(i.e. dicts or lists). The <code>modfn</code> argument is a function that
modifies the key value pair. It should accept two arguments: a key and value
and it should return the modified value.
</p>
<p>The example function,
<code>super_secure_encrypt</code> is a function that checks if
the string 'password' is in the key, and "encrypts" the value using the
<sarcasm>super secure</sarcasm>
<a href="http://en.wikipedia.org/wiki/ROT13">ROT13</a> algorithm.
(We are actually using the
<a href="http://www.keyczar.org/">keyczar</a> toolkit from google to do the encryption.)
</p>
<pre class="python">
def modify_all_simple_dict_values(data, modfn):
if isinstance(data, dict):
for k, v in data.iteritems():
if (isinstance(v, dict) or
isinstance(v, list) or
isinstance(v, tuple)
):
modify_all_simple_dict_values(v, modfn)
else:
data[k] = modfn(k, v)
elif isinstance(data, list) or isinstance(data, tuple):
for item in data:
modify_all_simple_dict_values(item, modfn)
return data
def super_secure_encrypt(key, value):
if 'password' in key:
value = value.encode('rot13')
return value
from pprint import pprint
pprint(modify_all_simple_dict_values(EXAMPLE_DATA, super_secure_encrypt))</pre>
<p>Results:</p>
<pre>{'jobs': [{'frequency': '* * * * *',
'jobconfig': [{'config': [('*',
{'maxspeed': 1048576,
'password': 'barfrpergcnffjbeq',
'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': 'nabgurefrpergcnffjbeq',
'db_table': 'mytable',
'db_user': 'myuser'})],
'hasbro': 'dart'}],
'jobdesc': 'Data from tootsiepop',
'jobname': 'tootsiepop',
'max_records_fail': '110%',
'min_failure_time': '1000y'}],
'vendor': 'tootsiepop'}</pre>
Free Computer Science courses online
2009-06-30T19:56:18-07:00https://www.saltycrane.com/blog/2009/06/free-computer-science-courses-online/<p>I found out there is a <a href="http://www.cs.sunysb.edu/~algorith/video-lectures/">video
lecture series</a> to go along with my new book
<a href="http://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorithmrepo">The Algorithm Design Manual</a>.
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
<a href="http://ocw.mit.edu/OcwWeb/web/home/home/index.htm">MIT</a> 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
<a href="http://webcast.berkeley.edu/">UC Berkeley</a> also has a number of free
courses online, including four Computer
Science courses with video. The final source I found was
<a href="http://aduni.org/courses/">ArsDigita University</a>. They have a
good number of Computer Science video lectures as well, but I had a hard time
connecting. Let me know if I am missing other good sources.
</p>
<p><em>Update 2009-7-8:</em> I've updated the list to include
<a href="http://see.stanford.edu/see/courses.aspx">Stanford</a>'s online
courses. They have 3 Introduction to Computer Science courses with video lectures
and 3 Artificial Intelligence courses with video lectures.
</p>
<h4><a href="http://www.sunysb.edu/">Stony Brook University Courses</a></h4>
<ul>
<li>
<a href="http://www.cs.sunysb.edu/~skiena/373/">CSE 373 Analysis of Algorithms</a><br>
Professor: Steven Skiena<br>
Textbook: <a href="http://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorithmrepo">The Algorithm Design Manual</a><br>
When: 2007<br>
Primary Language used: C<br>
Video: <a href="http://www.cs.sunysb.edu/~algorith/video-lectures/">26 lectures</a><br>
Slides: <a href="http://www.cs.sunysb.edu/~algorith/video-lectures/">26 PDF documents</a><br>
Syllabus: <a href="http://www.cs.sunysb.edu/~skiena/373/syllabus.pdf">PDF</a><br>
</li>
</ul>
<h4><a href="http://ocw.mit.edu/OcwWeb/web/home/home/index.htm">MIT Courses</a></h4>
<ul>
<li>
<a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm">
6.046J / 18.410J Introduction to Algorithms</a><br>
Professor: Charles Leiserson with Erik Demaine<br>
Textbook: <a href="http://www.amazon.com/exec/obidos/ASIN/0262032937">Introduction to Algorithms</a><br>
When: Fall 2005<br>
Video: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/index.htm">23 lectures</a><br>
Lecture Notes: <a href="http://ocw.mit.edu/ans15436/ZipForEndUsers/6/6-046JFall-2005/6-046JFall-2005.zip">23 PDF files</a><br>
Syllabus: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/Syllabus/index.htm">Web page</a><br>
<br>
</li>
<li>
<a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-189January--IAP--2007/CourseHome/index.htm">
6.189 Multicore Programming Primer</a><br>
Instructor: Saman Amarasinghe<br>
When: January 2007<br>
Video: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-189January--IAP--2007/LectureNotesandVideo/index.htm">
18 lectures</a><br>
Lecture Notes: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-189January--IAP--2007/LectureNotesandVideo/index.htm">
18 PDF files</a><br>
Syllabus: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-189January--IAP--2007/Syllabus/index.htm">Web page</a><br>
<br>
</li>
<li>
<a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-033Spring-2005/CourseHome/index.htm">
6.033 Computer System Engineering</a><br>
Professors: Hari Balakrishnan and Samuel Madden<br>
Textbook: <a href="http://www.amazon.com/exec/obidos/ASIN/0201835959">The Mythical Man-Month</a>
<a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-033Spring-2005/Readings/index.htm">among others</a><br>
When: Spring 2005<br>
Video: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-033Spring-2005/LectureNoteswithVideo/detail/embed04.htm">
22 lectures</a><br>
Lecture notes: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-033Spring-2005/LectureNoteswithVideo/detail/embed04.htm">
22 PDF files</a><br>
Syllabus: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-033Spring-2005/Syllabus/index.htm">Web page</a><br>
<br>
</li>
<li>
<a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-035Fall-2005/CourseHome/index.htm">
6.035 Computer Language Engineering (SMA 5502)</a><br>
Professors: Saman Amarasinghe and Martin Rinard<br>
Textbooks: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-035Fall-2005/Readings/index.htm">Optional choices</a><br>
When: Fall 2005<br>
Primary language used: Java<br>
Video: <a href="http://www.youtube.com/view_play_list?p=0300FE43396456C1">7 lectures + 1 Recitation</a><br>
Lecture Notes: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-035Fall-2005/LectureNotes/index.htm">
18 PDF files</a><br>
Syllabus: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-035Fall-2005/Syllabus/index.htm">Web page</a><br>
<br>
</li>
<li>
<a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-001Spring-2005/CourseHome/index.htm">
6.001 Structure and Interpretation of Computer Programs</a><br>
Instructors: Hal Abelson and Gerald Jay Sussman<br>
Textbook: <a href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-1.html#titlepage">
Structure and Interpretation of Computer Programs</a><br>
When: Video is from July 1986<br>
Primary language used: Lisp (Scheme)<br>
Video: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-001Spring-2005/VideoLectures/index.htm">20 lectures</a><br>
Lecture notes: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-001Spring-2005/LectureNotes/index.htm">
30 PDF files</a><br>
Syllabus: <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-001Spring-2005/Syllabus/index.htm">Web page</a><br>
</li>
</ul>
<h4><a href="http://webcast.berkeley.edu/">UC Berkeley Courses</a></h4>
<ul>
<li><a href="http://webcast.berkeley.edu/course_details_new.php?seriesid=2008-D-26509&semesterid=2008-D">
CS 162 Operating Systems and System Programming</a> (Fall 2008)</li>
<li><a href="http://webcast.berkeley.edu/courses.php?semesterid=2008-D">
CS 61A The Structure and Interpretation of Computer Programs</a> (Fall 2008)</li>
<li><a href="http://webcast.berkeley.edu/course_details_new.php?seriesid=2008-D-26332&semesterid=2008-D">
CS 61B DATA STRUCTURES</a> (Fall 2008)</li>
<li><a href="http://webcast.berkeley.edu/course_details_new.php?seriesid=2008-D-26404&semesterid=2008-D">
CS 61CL Machine Structures</a> (Fall 2008)</li>
</ul>
<h4><a href="http://see.stanford.edu/see/courses.aspx">Stanford Courses</a></h4>
<ul>
<li><a href="http://see.stanford.edu/see/courseinfo.aspx?coll=824a47e1-135f-4508-a5aa-866adcae1111">
CS106A Programming Methodology</a></li>
<li><a href="http://see.stanford.edu/see/courseinfo.aspx?coll=11f4f422-5670-4b4c-889c-008262e09e4e">
CS106B Programming Abstractions</a></li>
<li><a href="http://see.stanford.edu/see/courseinfo.aspx?coll=2d712634-2bf1-4b55-9a3a-ca9d470755ee">
CS107 Programming Paradigms</a></li>
<li><a href="http://see.stanford.edu/see/courseinfo.aspx?coll=86cc8662-f6e4-43c3-a1be-b30d1d179743">
CS223A Introduction to Robotics</a></li>
<li><a href="http://see.stanford.edu/see/courseinfo.aspx?coll=63480b48-8819-4efd-8412-263f1a472f5a">
CS224N Natural Language Processing</a></li>
<li><a href="http://see.stanford.edu/see/courseinfo.aspx?coll=348ca38a-3a6d-4052-937d-cb017338d7b1">
CS229 Machine Learning</a></li>
</ul>
<br>
See also: <a href="http://aduni.org/courses/">ArsDigita University Courses</a>
Find the N longest lines in a file with Python
2009-06-28T21:26:16-07:00https://www.saltycrane.com/blog/2009/06/find-n-longest-lines-file-python/<p>Here's a Python problem I attempted recently:</p>
<blockquote>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.</blockquote>
<p>Here's my solution:</p>
<pre class="python">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__':
main()</pre>
<p>What do you think? Is there a faster way?</p>
How to reverse words in a sentence using Python and C
2009-04-22T09:56:32-07:00https://www.saltycrane.com/blog/2009/04/how-reverse-words-sentence-using-python-and-c/<p>This is a technical problem I attempted recently.
The problem was to reverse the words in a sentence.
For example, <em>The quick brown fox
jumped over the lazy dog.</em> becomes <em>dog. lazy the
over jumped fox brown quick The</em>.
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.
</p>
<h4>Python version</h4>
<pre class="python">sentence = "The quick brown fox jumped over the lazy dog."
words = sentence.split()
sentence_rev = " ".join(reversed(words))
print sentence_rev</pre>
<br>
<h4>C version</h4>
<p>Credit for this solution goes to
<a href="http://wuhrr.wordpress.com/2007/11/09/how-to-reverse-words-within-a-sentence-in-c/">
Hai Vu</a></p>
<pre class="c">#include <stdio.h>
/* function declarations */
void reverse_words(char *sentence);
void reverse_chars(char *left, char *right);
/* main program */
int main()
{
char mysentence[] = "The quick brown fox jumped over the lazy dog.";
reverse_words(mysentence);
printf("%s\n", mysentence);
return 0;
}
/* reverse the words in a sentence */
void reverse_words(char *sentence)
{
char *start = sentence;
char *end = sentence;
/* find the end of the sentence */
while (*end != '\0') {
++end;
}
--end;
/* reverse the characters in the sentence */
reverse_chars(start, end);
/* reverse the characters in each word */
while (*start != '\0') {
/* move start pointer to the beginning of the next word */
for (; *start != '\0' && *start == ' '; start++) ;
/* move end pointer to the end of the next word */
for (end=start; *end != '\0' && *end != ' '; end++) ;
--end;
/* reverse the characters in the word */
reverse_chars(start, end);
/* move to next word */
start = ++end;
}
}
/* reverse the characters in a string */
void reverse_chars(char *left, char *right)
{
char temp;
while( left < right) {
temp = *left;
*left = *right;
*right = temp;
++left;
--right;
}
}</pre>
Python recursion example to navigate tree data
2008-08-19T16:43:48-07:00https://www.saltycrane.com/blog/2008/08/python-recursion-example-navigate-tree-data/<p>Here is a simple Python example using
<a href="http://en.wikipedia.org/wiki/Recursion_(computer_science)">recursion</a>
to navigate a nested Python data structure. Each
<a href="http://en.wikipedia.org/wiki/Tree_data_structure#Nodes">node</a>
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.</p>
<p><em>Update 2008-09-15</em>: Nihiliad posted an improvement to my
example in the comments. It is much simpler. I have updated my example
below.</p>
<h5>Nihiliad's (improved) method</h5>
<pre class="python">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.1',
'kids': []}]},
{'count': 0,
'text': '1.1.2',
'kids': []},
{'count': 0,
'text': '1.1.3',
'kids': []}]},
{'count': 0,
'text': '1.2',
'kids': []}]}
def traverse(data):
print ' ' * traverse.level + data['text']
for kid in data['kids']:
traverse.level += 1
traverse(kid)
traverse.level -= 1
if __name__ == '__main__':
traverse.level = 1
traverse(data)</pre>
<p>Results:</p>
<pre> 1
1.1
1.1.1
1.1.1.1
1.1.2
1.1.3
1.2</pre>
<h5>My original (inferior) method</h5>
<pre class="python">def outer(data):
class Namespace: pass
ns = Namespace()
ns.level = 1
def inner(data):
print ' ' * ns.level + data['text']
if data['count'] > 0:
ns.level += 1
for kid in data['kids']:
inner(kid)
ns.level -= 1
inner(data)
if __name__ == '__main__':
outer(data)</pre>