This is the fifth part of a nine-part article on famous Perl one-liners. In this part I will create various one-liners for text conversion and substitution. See part one for introduction of the series.

Famous Perl one-liners is my attempt to create “perl1line.txt” that is similar to “awk1line.txt” and “sed1line.txt” that have been so popular among Awk and Sed programmers.

The article on famous Perl one-liners will consist of nine parts:

• Part I: File spacing.
• Part II: Line numbering.
• Part III: Calculations.
• Part IV: String creation and array creation.
• Part V: Text conversion and substitution (this part).
• Part VI: Selective printing and deleting of certain lines.
• Part VII: Handy regular expressions.
• Part VIII: Release of perl1line.txt.
• Part IX: Release of Perl One-Liners e-book.

Everyone who’s subscribed to my blog will get a free copy of Perl One-Liners e-book when I release it as part 9 of this article series!

Alright then, here are today’s one-liners:

Text conversion and substitution

62. ROT13 a string.

'y/A-Za-z/N-ZA-Mn-za-m/'

This one-liner uses the y operator (also known as tr operator) to do ROT13. Operators y and tr do string transliteration. Given y/SEARCH/REPLACE/, the operator transliterates all occurrences of the characters found in SEARCH list with the corresponding (position-wise) characters in REPLACE list.

In this one-liner A-Za-z creates the following list of characters:

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz

And N-ZA-Mn-za-m creates this list:

NOPQRSTUVWXYZABCDEFGHIJKLMnopqrstuvwxyzabcdefghijklm

If you look closely you’ll notice that the second list is actually the first list offset by 13 characters. Now the y operator translates each character in the first list to a character in the second list, thus performing the ROT13 operation.

If you wish to ROT13 the whole file then do this:

perl -lpe 'y/A-Za-z/N-ZA-Mn-za-m/' file

The -p argument puts each of file’s line in the $_ variable, the y does ROT13, and -p prints the $_ out. The -l appends a newline to the output.

Note: remember that applying ROT13 twice produces the same string, i.e., ROT13(ROT13(string)) == string.

63. Base64 encode a string.

perl -MMIME::Base64 -e 'print encode_base64("string")'

This one-liner uses the MIME::Base64 module that is in the core (no need to install it, it comes with Perl). This module exports the encode_base64 function that takes a string and returns base64 encoded version of it.

To base64 encode the whole file do the following:

perl -MMIME::Base64 -0777 -ne 'print encode_base64($_)' file

Here the -0777 argument together with -n causes Perl to slurp the whole file into the $_ variable. Then the file gets base64 encoded and printed out, just like the string example above.

If we didn’t slurp the file and encoded it line-by-line we’d get a mess.

64. Base64 decode a string.

perl -MMIME::Base64 -le 'print decode_base64("base64string")'

The MIME::Base64 module also exports decode_base64 function that takes a base64-encoded string and decodes it.

The whole file can be similarly decoded by:

perl -MMIME::Base64 -ne 'print decode_base64($_)' file

There is no need to slurp the whole file into $_ because each line of a base64 encoded file is exactly 76 characters and decodes nicely.

65. URL-escape a string.

perl -MURI::Escape -le 'print uri_escape($string)'

You’ll need to install the URI::Escape module as it doesn’t come with Perl. The module exports two functions - uri_escape and uri_unescape. The first one does URL-escaping (sometimes also referred to as URL encoding), and the other does URL-unescaping (URL decoding).

66. URL-unescape a string.

perl -MURI::Escape -le 'print uri_unescape($string)'

This one-liner uses the uri_unescape function from URI::Escape module to do URL-unescaping.

67. HTML-encode a string.

perl -MHTML::Entities -le 'print encode_entities($string)'

This one-liner uses the encode_entities function from HTML::Entities module. This function encodes HTML entities. For example, < and > get turned into < and >.

68. HTML-decode a string.

perl -MHTML::Entities -le 'print decode_entities($string)'

This one-liner uses the decode_entities function from HTML::Entities module.

69. Convert all text to uppercase.

perl -nle 'print uc'

This one-liner uses the uc function, which by default operates on the $_ variable and returns an uppercase version of it.

Another way to do the same is to use -p command line option that enables automatic printing of $_ variable and modify it in-place:

perl -ple '$_=uc'

The same can also be also achieved by applying the \U escape sequence to string interpolation:

perl -nle 'print "\U$_"'

It causes anything after it (or until the first occurrence of \E) to be upper-cased.

70. Convert all text to lowercase.

perl -nle 'print lc'

This one-liner is very similar to the previous. Here the lc function is used that converts the contents of $_ to lowercase.

Or, using escape sequence \L and string interpolation:

perl -nle 'print "\L$_"'

Here \L causes everything after it (until the first occurrence of \E) to be lower-cased.

71. Uppercase only the first word of each line.

perl -nle 'print ucfirst lc'

The one-liner first applies the lc function to the input that makes it lower case and then uses the ucfirst function that upper-cases only the first character.

It can also be done via escape codes and string interpolation:

perl -nle 'print "\u\L$_"'

First the \L lower-cases the whole line, then \u upper-cases the first character.

72. Invert the letter case.

perl -ple 'y/A-Za-z/a-zA-Z/'

This one-liner does transliterates capital letters A-Z to lowercase letters a-z, and lowercase letters to uppercase letters, thus switching the case.

73. Camel case each line.

perl -ple 's/(\w+)/\u$1/g'

This is a lousy Camel Casing one-liner. It takes each word and upper-cases the first letter of it. It fails on possessive forms like “friend’s car”. It turns them into “Friend’S Car”.

An improvement is:

s/(?<!['])(\w+)/\u\1/g

Which checks if the character before the word is not single quote '. But I am sure it still fails on some more exotic examples.

74. Strip leading whitespace (spaces, tabs) from the beginning of each line.

perl -ple 's/^[ \t]+//'

This one-liner deletes all whitespace from the beginning of each line. It uses the substitution operator s. Given s/REGEX/REPLACE/ it replaces the matched REGEX by the REPLACE string. In this case the REGEX is ^[ \t]+, which means “match one or more space or tab at the beginning of the string” and REPLACE is nothing, meaning, replace the matched part with empty string.

The regex class [ \t] can actually be replaced by \s+ that matches any whitespace (including tabs and spaces):

perl -ple 's/^\s+//'

75. Strip trailing whitespace (space, tabs) from the end of each line.

perl -ple 's/[ \t]+$//'

This one-liner deletes all whitespace from the end of each line.

Here the REGEX of the s operator says “match one or more space or tab at the end of the string.” The REPLACE part is empty again, which means to erase the matched whitespace.

76. Strip whitespace from the beginning and end of each line.

perl -ple 's/^[ \t]+|[ \t]+$//g'

This one-liner combines the previous two. Notice that it specifies the global /g flag to the s operator. It’s necessary because we want it to delete whitespace at the beginning AND end of the string. If we didn’t specify it, it would only delete whitespace at the beginning (assuming it exists) and not at the end.

77. Convert UNIX newlines to DOS/Windows newlines.

perl -pe 's|\n|\r\n|'

This one-liner substitutes the Unix newline \n LF with Windows newline \r\n CRLF on each line. Remember that the s operator can use anything for delimiters. In this one-liner it uses vertical pipes to delimit REGEX from REPLACE to improve readibility.

78. Convert DOS/Windows newlines to UNIX newlines.

perl -pe 's|\r\n|\n|'

This one-liner does the opposite of the previous one. It takes Windows newlines CRLF and converts them to Unix newlines LF.

79. Convert UNIX newlines to Mac newlines.

perl -pe 's|\n|\r|'

Apple Macintoshes used to use \r CR as newlines. This one-liner converts UNIX’s \n to Mac’s \r.

80. Substitute (find and replace) “foo” with “bar” on each line.

perl -pe 's/foo/bar/'

This one-liner uses the s/REGEX/REPLACE/ command to substitute “foo” with “bar” on each line.

To replace all “foos” with “bars”, add the global /g flag:

perl -pe 's/foo/bar/g'

81. Substitute (find and replace) “foo” with “bar” on lines that match “baz”.

perl -pe '/baz/ && s/foo/bar/'

This one-liner is equivalent to:

while (defined($line = <>)) {
  if ($line =~ /baz/) {
    $line =~ s/foo/bar/
  }
}

It puts each line in variable $line, then checks if line matches “baz”, and if it does, it replaces “foo” with “bar” in it.

Got tired.

I got tired of writing one-liners at this moment. I’ll update this article the same way I did the 3rd part - I’ll add a few new one-liners each week until the article is finished.

Have Fun!

Have fun with these one-liners for now. The next part is going to be about selective printing and deleting of certain lines.

Can you think of other text conversion and substitution procedures that I did not include here?

Hey everyone, just wanted to do a quick post on how to keep track of who’s talking about you on the net. Nothing really unique, just a list of tools that I use often. Why is it important? Well, it’s always interesting to know what people are saying about you and sometimes you want to engage in a conversation or just thank them for linking to your article.

Alright, here are the tools that I use:

Twitter Search

Twitter search is definitely the #1 source for keeping track of who’s talking about you right now. But you already knew that.

Twitter search example for the term “catonmat.”

Perhaps what you didn’t know is that they have an RSS feed for search queries.

Location of RSS feed link for Twitter search results.

Now combined with a service like feedblitz.com you can email the RSS updates to yourself or just read them from your favorite RSS reader.

I am monitoring terms “Peteris Krumins”, “pkrumins” and “catonmat”.

Google Alerts

Google Alerts automatically notifies you when the Google search engine locates new results for your search terms. You can choose to have your alerts delivered via email or RSS feed.

Google Alerts email for the term “catonmat.”

You can even customize the type of alerts you wish to receive. Google Alerts lets you choose to get notified when a new result appears on web pages, usenet (google groups), blogs, news or videos.

Backtype Comment Alerts

Backtype is Google for comments. Want to find out when someone’s mentioned you on Reddit, FriendFeed, Digg or Hacker News? Backtype will alert you.

Backtype Alerts email for the term “peteris.”

Backtype also recently launched a service called BackTweets that allows you to find who’s linking back to you via shortened URLs.

Have Fun!

Have fun keeping track of yourself!

Btw, let me know in the comments if I missed any other cool tools.

I recently watched an interesting video lecture on stealing botnets. A group of researchers at UCSB recently managed to take control over a part of Torpig botnet for 10 days. During this time, they observed 180 thousand infections and recorded almost 70GB of data that bots collected. This data included submitted form information from all the websites the infected person had visited, smtp, ftp, pop3, windows, passwords, credit card numbers and passwords from various password managers.

Here are the most interesting facts from the lecture:

Torpig uses a technique called “domain fluxing” to avoid being shut down by simply blocking the IP or the domain name of control center servers. The idea is simple - depending on date and time the algorithm generates a domain name to connect to. If the domain gets shut down, the bots will simply use a different domain after some time.

The researchers were able to take control over a part of the botnet by cracking the domain name generating algorithm and registering some of the domain names to be used for communication in the future.

The bad guys noticed that a part of botnet has been taken over and issued a software update to all bots to use a new domain flux algorithm, which used Twitter’s popular topics for the day to generate domain names. It was no longer possible to predict the domain that would be used tomorrow.

When communicating with command & control server, the bots included a unique id field that was generated from machine’s hardware. This allowed researchers to estimate the real number of unique computers infected. Researchers saw 1.2 million unique IP addresses but only 180k unique machines.

The bots would steal financial data from 410 financial institutions (top 5: PayPal, Poste Italiane, Capital One, E*Trade, Chase), they would log credit card information (top 5 cards: Visa, Mastercard, American Express, Maestro, Discover), and they would also steal all the passwords from browser’s password manager.

In a 2008 study Symantec estimated that credit card information is valued at $.10 to $25 per card in the underground market. The bank account information is valued at $10.00 to $1,000 per account. Using this study, researchers estimated that during 10 day period the amount of financial data bots collected were worth $83k to $8.3 million.

Using various estimations researchers calculated that if the bots are used for denial of service the total bandwidth would be 17Gbps.

Researchers observed that there was a fraction of people who’d fill out the phishing page and then immediately email the company’s security group telling that they may have been victims of identity theft.

Since Torpig was sending all the HTTP POST data and emails to command & control servers, researchers did statistics on emails and found out that 14% of all captured emails were about jobs and resumes, 10% discussed computer security/malware, 7% discussed money, 6% were sports fans, 5% were worried about exams and their grades, 4% were seeking partners online.

Researchers collected 300,000 unique credentials on 370,000 websites. 28% of people reused their password on multiple domains. There were 173,686 unique passwords.

Researchers converted the passwords in Unix format and tried to crack them with John the Ripper. 56,000 were cracked in less than 65 minutes using brute-force. Using a wordlist 14,000 passwords were cracked in the next 10 minutes. And another 30,000 passwords were cracked in the next 24 hours. That’s 58% of all passwords cracked in 24 hours.

You’re welcome to watch the video lecture. It’s 1h 15m long. It’s presented by Richard A. Kemmerer.

Here are all the topics in the lecture:

• [02:00] Botnet terminology - bot, botnet, command & control server, control channel, botmaster.
• [03:00] Introduction to the Torpig trojan and Mebroot malware platform.
• [05:00] How Torpig works.
• [11:30] Torpig HTML injection.
• [15:00] Domain fluxing.
• [19:15] Taking over Torpig’s c&c server.
• [24:10] Data collection principles.
• [26:00] C&c server protocol.
• [31:10] Botnet’s size estimation.
• [37:00] Botnet’s threats: theft of financial information, denial of service, proxy servers, privacy thefts.
• [37:30] Threat: Theft of financial information.
• [42:00] Threat: Denial of service.
• [43:30] Threat: Proxy servers.
• [44:20] Threat: Privacy theft.
• [47:00] Password analysis.
• [50:40] Criminal retribution.
• [53:00] Law enforcement.
• [58:00] Repatriating the data.
• [01:00:00] Ethics.
• [01:02:00] Conclusions.
• [01:06:00] Questions and answers.

For more information see the publication “Your Botnet is My Botnet: Analaysis of a Botnet Takeover.”

This is the fifth post in an article series about MIT’s course “Linear Algebra”. In this post I will review lecture five that finally introduces real linear algebra topics such as vector spaces their subspaces and spaces from matrices. But before it does that it closes the topics that were started in the previous lecture on permutations, transposes and symmetric matrices.

Here is a list of the previous posts in this article series:

• Lecture 1: Geometry of Linear Equations
• Lecture 2: Elimination with Matrices
• Lecture 3: Matrix Multiplication and Inverse Matrices
• Lecture 4: A=LU Factorization

Lecture 5: Vector Spaces and Subspaces

Lecture starts with reminding some facts about permutation matrices. Remember from the previous lecture that permutation matrices P execute row exchanges and they are identity matrices with reordered rows.

Let’s count how many permutation matrices are there for an nxn matrix.

For a matrix of size 1x1, there is just one permutation matrix - the identity matrix.

For a matrix of size 2x2 there are two permutation matrices - the identity matrix and the identity matrix with rows exchanged.

For a matrix of size 3x3 we may have the rows of the identity matrix rearranged in 6 ways - {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}.

For a matrix of size 4x4 the number of ways to reorder the rows is the same as the number of ways to rearrange numbers {1,2,3,4}. This is the simplest possible combinatorics problem. The answer is 4! = 24 ways.

In general, for an nxn matrix, there are n! permutation matrices.

Another key fact to remember about permutation matrices is that their inverse P^-1 is their transpose P^T. Or algebraically P^T·P = I.

The lecture proceeds to transpose matrices. The transpose of a matrix exchanges its columns with rows. Another way to think about it that it flips the matrix over its main diagonal. Transpose of matrix A is denoted by A^T.

Here is an example of transpose of a 3-by-3 matrix. I color coded the columns to better see how they get exchanged:

A matrix does not have to be square for its transpose to exist. Here is another example of transpose of a 3-by-2 matrix:

In algebraic notation transpose is expressed as (A^T)_ij = A_ji, which says that an element a_ij at position ij get transposed into the position ji.

Here are the rules for matrix transposition:

• The transpose of A + B is (A + B)^T = A^T + B^T.
• The transpose of A·B is (A·B)^T = B^T·A^T.
• The transpose of A·B·C is (A·B·C)^T = C^T·B^T·A^T.
• The transpose of A^-1 is (A^-1)^T = (A^T)^-1.

Next the lecture continues with symmetric matrices. A symmetric matrix has its transpose equal to itself, i.e., A^T = A. It means that we can flip the matrix along the diagonal (transpose it) but it won’t change.

Here is an example of a symmetric matrix. Notice that the elements on opposite sides of the diagonal are equal:

Now check this out. If you have a matrix R that is not symmetric and you multiply it with its transpose R^T as R·R^T, you get a symmetric matrix! Here is an example:

Are you wondering why it’s true? The proof is really simple. Remember that matrix is symmetric if its transpose is equal to itself. Now what’s the transpose of the product R·R^T? It’s (R·R^T)^T = (R^T)^T·R^T = R·R^T - it’s the same product, which means that R·R^T is always symmetric.

Here is another cool fact - the inverse of a symmetric matrix (if it exists) is also symmetric. Here is the proof. Suppose A is symmetric, then the transpose of A^-1 is (A^-1)^T = (A^T)^-1. But A^T = A, therefore (A^T)^-1 = A^-1.

At this point lecture finally reaches the fundamental topic of linear algebra - vector spaces. As usual, it introduces the topic by examples.

Example 1: Vector space R² - all 2-dimensional vectors. Some of the vectors in this space are (3, 2), (0, 0), (π, e) and infinitely many others. These are all the vectors with two components and they represent the xy plane.

Example 2: Vector space R³ - all vectors with 3 components (all 3-dimensional vectors).

Example 3: Vector space Rⁿ - all vectors with n components (all n-dimensional vectors).

What makes these vectors vector spaces is that they are closed under multiplication by a scalar and addition, i.e., vector space must be closed under linear combination of vectors. What I mean by that is if you take two vectors and add them together or multiply them by a scalar they are still in the same space.

For example, take a vector (1,2,3) in R³. If we multiply it by any number α, it’s still in R³ because α·(1,2,3) = (α, 2α, 3α). Similarly, if we take any two vectors (a, b, c) and (d, e, f) and add them together, the result is (a+d, b+e, f+c) and it’s still in R³.

There are actually 8 axioms that the vectors must satisfy for them to make a space, but they are not listed in this lecture.

Here is an example of not-a-vector-space. It’s 1/4 of R² (the 1st quadrant). The green vectors are in the 1st quadrant but the red one is not:

An example of not-a-vector-space.

This is not a vector space because the green vectors in the space are not closed under multiplication by a scalar. If we take the vector (3,1) and multiply it by -1 we get the red vector (-3, -1) but it’s not in the 1st quadrant, therefore it’s not a vector space.

Next, Gilbert Strang introduces subspaces of vector spaces.

For example, any line in R² that goes through the origin (0, 0) is a subspace of R². Why? Because if we take any vector on the line and multiply it by a scalar, it’s still on the line. And if we take any two vectors on the line and add them together, they are also still on the line. The requirement for a subspace is that the vectors in it do not go outside when added together or multiplied by a number.

Here is a visualization. The blue line is a subspace of R² because the red vectors on it can’t go outside of line:

An example of subspace of R².

And example of not-a-subspace of R² is any line that does not go through the origin. If we take any vector on the line and multiply it by 0, we get the zero vector, but it’s not on the line. Also if we take two vectors and add them together, they are not on the line. Here is a visualization:

An example of not-a-subspace of R².

Why not list all the subspaces of R². They are:

• the R² itself,
• any line through the origin (0, 0),
• the zero vector (0, 0).

And all the subspaces of R³ are:

• the R³ itself,
• any line through the origin (0, 0, 0),
• any plane through the origin (0, 0, 0),
• the zero vector.

The last 10 minutes of the lecture are spent on column spaces of matrices.

The column space of a matrix is made out of all the linear combinations of its columns. For example, given this matrix:

The column space C(A) is the set of all vectors {α·(1,2,4) + β·(3,3,1)}. In fact, this column space is a subspace of R³ and it forms a plane through the origin.

More about column spaces in the next lecture.

You’re welcome to watch the video lecture five:

Topics covered in lecture five:

• [01:30] Permutations.
• [03:00] A=LU elimination without row exchanges.
• [03:50] How Matlab does A=LU elimination.
• [04:50] PA=LU elimination with row exchanges
• [06:40] Permutation matrices.
• [07:25] How many permutation matrices are there?
• [08:30] Permutation matrix properties.
• [10:30] Transpose matrices.
• [11:50] General formula for transposes: (A^T)_ij = A_ji.
• [13:06] Symmetric matrices.
• [13:30] Example of a symmetric matrix.
• [15:15] R·R^T is always symmetric.
• [18:23] Why is R·R^T symmetric?
• [20:50] Vector spaces.
• [22:05] Examples of vector spaces.
• [22:55] Real vector space R².
• [23:20] Picture of R² - xy plane.
• [26:50] Vector space R³.
• [28:00] Vector space Rⁿ.
• [30:00] Example of not a vector space.
• [32:00] Subspaces of vector spaces.
• [33:00] A vector space inside R².
• [34:35] A line in R² that is subspace.
• [34:50] A line in R² that is not a subspace.
• [36:30] All subspaces of R².
• [39:30] All subspaces of R³.
• [40:20] Subspaces of matrices.
• [41:00] Column spaces of matrices C(A).
• [44:10] Example of column space of matrix with columns in R³.

Here are my notes of lecture five:

My notes of linear algebra lecture 5 on vector spaces and subspaces.

Have fun with this lecture! The next post is going to be more about column spaces and null spaces of matrices.

PS. This course is taught from Introduction to Linear Algebra textbook. Get it here:

This is the sixth post in the article series “Vim Plugins You Should Know About“. This time I am going to introduce you to a vim plugin called “nerd_tree.vim“. It’s so useful that I can’t imagine working without it in vim.

Nerd Tree is a nifty plugin that allows you to explore the file system and open files and directories directly from vim. It opens the file system tree in a new vim window and you may use keyboard shortcuts and mouse to open files in new tabs, in new horizontal and vertical splits, quickly navigate between directories and create bookmarks for your most important projects.

This plugin was written by Marty Grenfell (also known as scrooloose).

Previous articles in the series:

• Part I: surround.vim - find and edit surrounding parens, quotes, html tags, etc.
• Part II: repeat.vim - repeat the previous surrounding command.
• Part III: matchit.vim - extends the functionality of % key.
• Part IV: snipmate.vim - the best snippet plugin for vim
• Part V: a.vim - quickly change between source and header files (.c/.h).

Ps. Please help me reach 10,000 RSS subscribers. I am almost there. If you enjoy my posts and have not yet subscribed, subscribe here!

How to use nerd_tree.vim?

Nerd Tree plugin can be activated by the :NERDTree vim command. It will open in vim as a new vertical split on the left:

A screenshot of Nerd Tree plugin in action.

Here are the basics of how to use the plugin:

• Use the natural vim navigation keys hjkl to navigate the files.
• Press o to open the file in a new buffer or open/close directory.
• Press t to open the file in a new tab.
• Press i to open the file in a new horizontal split.
• Press s to open the file in a new vertical split.
• Press p to go to parent directory.
• Press r to refresh the current directory.

All other keyboard shortcuts can be found by pressing ?. It will open a special help screen with the shortcut listings. Press ? again to get back to file tree.

To close the plugin execute the :NERDTreeClose command.

Typing :NERDTree and :NERDTreeClose all the time is really inconvenient. Therefore I have mapped the toggle command :NERDTreeToggle to the F2 key. This way I can quickly open and close Nerd Tree whenever I wish. You can also map it to F2 by putting map <F2> :NERDTreeToggle<CR> in your .vimrc file.

How to install nerd_tree.vim?

To get the latest version:

• 1. Download NERD_tree.zip.
• 2. Extract NERD_tree.zip to ~/.vim (on Unix/Linux) or ~\vimfiles (on Windows).
• 3. Run :helptags ~/.vim/doc (on Unix/Linux) or :helptags ~/vimfiles/doc (on Windows) to rebuild the tags file (so that you can read :help NERD_tree.)
• 4. Restart Vim.

Have Fun!

Have fun exploring your files with this awesome plugin and until next time!

I learned an interesting fact about Fibonacci numbers recently while watching a lecture on number theory. Fibonacci numbers can be used to approximately convert from miles to kilometers and back.

Here is how.

Take two consecutive Fibonacci numbers, for example 5 and 8. And you’re done converting. No kidding – there are 8 kilometers in 5 miles. To convert back just read the result from the other end - there are 5 miles in 8 km!

Another example. Let’s take the consecutive Fibonacci numbers 21 and 34. What this tells us is that there are approximately 34 km in 21 miles and vice versa. (The exact answer is 33.79 km.)

If you need to convert a number that is not a Fibonacci number, just express the original number as a sum of Fibonacci numbers and do the conversion for each Fibonacci number separately.

For example, how many kilometers are there in 100 miles? Number 100 can be expressed as a sum of Fibonacci numbers 89 + 8 + 3. Now, the Fibonacci number following 89 is 144, the Fibonacci number following 8 is 13 and the Fibonacci number following 3 is 5. Therefore the answer is 144 + 13 + 5 = 162 kilometers in 100 miles. This is less than 1% off from the precise answer, which is 160.93 km.

Another example, how many miles are there in 400 km? Well, 400 is 377 + 21 + 2. Since we are going the opposite way now from miles to km, we need the preceding Fibonacci numbers. They are 233, 13 and 1. Therefore there are 233 + 13 + 1 = 247 miles in 400 km. (The correct answer is 248.55 miles.)

Just remember that if you need to convert from km to miles, you need to find the preceding Fibonacci number. But if you need to convert from miles to km, you need the subsequent Fibonacci number.

If the distance you’re converting can be expressed as a single Fibonacci number, then for numbers greater than 21 the error is always around 0.5%. However, if the distance needs to be composed as a sum of n Fibonacci numbers, then the error will be around sqrt(n)·0.5%.

Here’s why it works.

Fibonacci numbers have a property that the ratio of two consecutive numbers tends to the Golden ratio as numbers get bigger and bigger. The Golden ratio is a number and it happens to be approximately 1.618.

Coincidentally, there are 1.609 kilometers in a mile, which is within 0.5% of the Golden ratio.

Now that we know these two key facts, we can figure out how to do the conversion. If we take two consecutive Fibonacci numbers, F_n+1 and F_n, we know that their ratio F_n+1/F_n is 1.618. Since the ratio is approximately the same as kilometers per mile, we can write F_n+1/F_n = [mile]/[km]. It follows that F_n·[mile] = F_n+1·[km], which translates to English as “n-th Fibonacci number in miles is the same as (n+1)-th Fibonacci number in kilometers”.

That’s all there is to it. A pure coincidence that the Golden ratio is almost the same as kilometers in a mile.

This is the fourth part of a nine-part article on famous Perl one-liners. In this part I will create various one-liners for string and array creation. See part one for introduction of the series.

Famous Perl one-liners is my attempt to create “perl1line.txt” that is similar to “awk1line.txt” and “sed1line.txt” that have been so popular among Awk and Sed programmers.

The article on famous Perl one-liners will consist of nine parts:

• Part I: File spacing.
• Part II: Line numbering.
• Part III: Calculations.
• Part IV: String creation and array creation (this part).
• Part V: Text conversion and substitution.
• Part VI: Selective printing and deleting of certain lines.
• Part VII: Handy regular expressions.
• Part VIII: Release of perl1line.txt.
• Part IX: Release of Perl One-Liners e-book.

I decided that there will be two new parts in this series. The most powerful feature in Perl is its regular expressions, therefore I will write a part on “Handy Perl regular expressions.” I also decided to publish an e-book after I am done with the series, so that will be the last part of this series. Everyone who’s subscribed to my blog will get a free copy! Subscribe to my blog now!

I also updated the previous part on calculations with 14 new one-liners on finding values of constants pi and e, doing date calculations, finding factorial, greatest common divisor, least common multiple, generating random numbers, generating permutations, finding power sets and doing some IP address conversions.

Here are today’s one-liners:

String Creation and Array Creation

49. Generate and print the alphabet.

perl -le 'print a..z'

This one-liner prints all the letters from a to z as abcdefghijklmnopqrstuvwxyz. The letters are generated by the range operator ... The range operator, when used in the list context (which is forced here by print) on strings, uses the magical auto-increment algorithm that advances the string to the next character. So in this one-liner the auto-increment algorithm on the range a..z produces all the letters from a to z.

I really golfed this one-liner. If you used strict it would not work because of barewords a and z. Semantically more correct version is this:

perl -le 'print ("a".."z")'

Remember that the range operator .. produced a list of values. If you wish, you may print them comma separated by setting the $, special variable:

perl -le '$, = ","; print ("a".."z")'

There are many more special variables. Take a look at my special variable cheat sheet for a complete listing.

Syntactically more appealing is to use join to separate the list with a comma:

perl -le 'print join ",", ("a".."z")'

Here the list a..z gets joined by a comma before printing.

50. Generate and print all the strings from “a” to “zz”.

perl -le 'print ("a".."zz")'

Here the range operator .. is used again. This time it does not stop at “z” as in the previous one-liner, but advances z by one-character producing “aa”, then it keeps going, producing “ab”, “ac”, …, until it hits “az”. At this point it advances the string to “ba”, continues with “bb”, “bc”, …, until it reaches “zz”.

Similarly, you may generate all strings from “aa” to “zz” by:

perl -le 'print "aa".."zz"'

Here it goes like “aa”, “ab”, …, “az”, “ba”, “bb”, …, “bz”, “ca”, … “zz”.

51. Create a hex lookup table.

@hex = (0..9, "a".."f")

Here the array @hex gets filled with values 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and letters a, b, c, d, e, f.

You may use this array to convert a number (in variable $num) from decimal to hex using base conversion formula:

perl -le '$num = 255; @hex = (0..9, "a".."f"); while ($num) { $s = $hex[($num%16)&15].$s; $num = int $num/16 } print $s'

Surely, much easier way to convert a number to hex is just using the printf function (or sprintf function) with %x format specifier. (The example above just illustrates a use of a hex lookup table that we created by using the range operator.)

perl -le '$hex = sprintf("%x", 255); print $hex'

(See my Perl printf and sprintf format cheat sheet for all the format specifiers.)

To convert the number back from hex to dec use the hex function:

perl -le '$num = "ff"; print hex $num'

The hex function takes a hex string (beginning with or without “0x”) and converts it to decimal.

52. Generate a random 8 character password.

perl -le 'print map { ("a".."z")[rand 26] } 1..8'

Here the map function executes ("a".."z")[rand 26] code 8 times (because it iterates over the dummy range 1..8). In each iteration the code chooses a random letter from the alphabet. When map is done iterating, it returns the generated list of characters and print function prints it out by concatenating all the characters together.

If you also wish to include numbers in the password, add 0..9 to the list of characters to choose from and change 26 to 36 as there are 36 different characters to choose from:

perl -le 'print map { ("a".."z", 0..9)[rand 36] } 1..8'

If you need a longer password, change 1..8 to 1..20 to generate a 20 character long password.

53. Create a string of specific length.

perl -le 'print "a"x50'

Operator x is the repetition operator. This one-liner creates a string of 50 letters “a” and prints it.

If the repetition operator is used in list context, it creates a list (instead of scalar) with the given elements repeated:

perl -le '@list = (1,2)x20; print "@list"'

This one liner creates a list of twenty repetitions of (1, 2) (it looks like (1, 2, 1, 2, 1, 2, …)).

54. Create an array from a string.

@months = split ' ', "Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec"

Here the @months gets filled with values from the string containing month names. As each month name is separated by a space, the split function splits them and puts them in @months. This way $months[0] contains “Jan”, $months[1] contains “Feb”, …, and $months[11] contains “Dec”.

Another way to do the same is by using qw// operator:

@months = qw/Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec/

The qw// operator takes a space separated string and creates an array with each word being an array element.

55. Create a string from an array.

@stuff = ("hello", 0..9, "world"); $string = join '-', @stuff

Here the values in array @stuff get turned in a string $string that has them separated by a hyphen. Turning an array in a string was done by the join function that takes a separator and a list, and concatenates the items in the list in a single string, separated by the separator.

56. Find the numeric values for characters in the string.

perl -le 'print join ", ", map { ord } split //, "hello world"'

This one-liner takes the string “hello world”, splits it into a list of characters by split //, "hello world", then it maps the ord function onto each of the characters, which returns the numeric, native 8-bit encoding (like ASCII or EBCDIC) of the character. Finally all the numeric values get joined together by a comma and get printed out.

Another way to do the same is use the unpack function and specify C* as the unpacking template (C means unsigned character and * means as many characters there are):

perl -le 'print join ", ", unpack("C*", "hello world")'

57. Convert a list of numeric ASCII values into a string.

perl -le '@ascii = (99, 111, 100, 105, 110, 103); print pack("C*", @ascii)'

Just as we unpacked a string into a list of values with the C* template in the one-liner above, we can pack them back into a string.

Another way to do the same is use the chr function that takes the code point value and returns the corresponding character:

perl -le '@ascii = (99, 111, 100, 105, 110, 103); print map { chr } @ascii'

Similar to one-liner #55 above, function chr gets mapped onto each value in the @ascii producing the characters.

58. Generate an array with odd numbers from 1 to 100.

perl -le '@odd = grep {$_ % 2 == 1} 1..100; print "@odd"'

This one-liner generates an array of odd numbers from 1 to 99 (as 1, 3, 5, 7, 9, 11, …, 99). It uses the grep function that evaluates the given code $_ % 2 == 1 for each element in the given list 1..100 and returns only the elements that had the code evaluate to true. In this case the code tests if the reminder of the number is 1. If it is, the number is odd and it has to be put in the @odd array.

Another way to write is by remembering that odd numbers have the low-bit set and testing this fact:

perl -le '@odd = grep { $_ & 1 } 1..100; print "@odd"'

Expression $_ & 1 isolates the low-bit, and grep selects only the numbers with low-bit set (odd numbers).

See my explanation of bit-hacks for full explanation and other related bit-hacks.

59. Generate an array with even numbers from 1 to 100.

perl -le '@even = grep {$_ % 2 == 0} 1..100; print "@even"'

This is almost the same as the previous one-liner, except the condition grep tests for is “is the number even (reminder dividing by 2 is zero)?”

60. Find the length of the string.

perl -le 'print length "one-liners are great"'

Just for completeness, the length subroutine finds the length of the string.

61. Find the number of elements in an array.

perl -le '@array = ("a".."z"); print scalar @array'

Evaluating an array in a scalar context returns the number of elements in it.

Another way to do the same is by adding one to the last index of the array:

perl -le '@array = ("a".."z"); print $#array + 1'

Here $#array returns the last index in array @array. Since it’s a number one less than the number of elements, we add 1 to the result to find the total number of elements in the array.

Have Fun!

Have fun with these one-liners for now. The next part is going to be about text conversion and substitution.

Can you think of other string creating and array creation one-liners that I didn’t include here?

This is the fourth post in an article series about MIT’s course “Linear Algebra”. In this post I will review lecture four on factorizing a matrix A into a product of a lower-triangular matrix L and an upper-triangular matrix U, or in other words A=LU. The lecture also shows how to find the inverse of matrix product A·B, how to find the inverse of transposed matrix A^T, and introduces permutation matrices.

Here are the previous lectures:

• Lecture 1: Geometry of Linear Equations
• Lecture 2: Elimination with Matrices
• Lecture 3: Matrix Multiplication and Inverse Matrices

Lecture 4: A=LU Factorization

Lecture four starts with a small review of inverse matrices. Remember from previous lecture that the inverse of matrix A is matrix A^-1 such that multiplying them together A·A^-1 produces the identity matrix I.

Another key fact to remember is that matrix multiplication is associative (can change parenthesis) and that for square matrices the right-inverse is also the left-inverse A·A^-1 = A^-1·A = I.

Lecture then continues with finding the inverse of matrix product A·B. The answer is found by reasoning what should we multiply A·B to get the identity matrix. Let’s try B^-1·A^-1. If this is the inverse of A·B, then multiplying it with A·B from the left and right sides should produce the identity matrix I. Let’s test this.

From the right side: (A·B)·(B^-1·A^-1). Since we can rearrange parenthesis, this is the same as A·(B·B^-1)·A^-1. But B·B^-1 is identity, therefore A·(B·B^-1)·A^-1 = A·I·A^-1 = A·A^-1 = I. Seems good so far.

Now the left side: (B^-1·A^-1)·(A·B). We rearrange parenthesis again, B^-1·(A^-1·A)·B and just like in the previous example, A^-1·A is identity and B^-1·I·B is B^-1·B = I.

We have found the inverse of (A·B). It’s (B^-1·A^-1).

Next, while we’re at it, the lecture continues with finding the inverse of transposed matrix A^T. It’s found by reasoning again. Let’s first look at the equation A·A^-1 = I. We can transpose both sides of this equation and it will still hold. If we transpose the right side, we get the same identity matrix I, because I^T=I. But what about the left-hand side? Transposing the left-hand side we get (A·A^-1)^T = (A^-1)^T·A^T. Now left-hand side is still equal to right-hand side, therefore (A^-1)^T·A^T = I. But from this equation it’s instantly obvious that the inverse of A^T is (A^-1)^T.

We can therefore note and remember that (A^T)^-1 = (A^-1)^T.

Finally the lecture moves on to today’s key topic of A=LU decomposition. As usual, the topic is introduced by an example.

Let’s take a look at this 2x2 matrix A:

And let’s try to find the elementary matrix E₂₁ that will eliminate the element at row 2, column 1. Multiplying the first row by 4 and subtracting it from the second row will produce a zero at 2, 1.

But look at the right-hand side. It’s the upper-triangular matrix U (all elements below the diagonal are 0) that we were looking for!

Now if we multiply both sides by the inverse of E₂₁, we get (E₂₁)^-1·E₂₁·A = (E₂₁)^-1·U. But (E₂₁)^-1·E₂₁ is identity, therefore A = (E₂₁)^-1·U. From this equation it’s instantly obvious that the lower-triangular matrix L is nothing else but (E₂₁)^-1!

Another form of factorization is A = LDU, where D is the diagonal matrix that contains the pivots. For this example it would be:

Now imagine that we have some arbitrary 3x3 matrix A. To reduce matrix A into upper-triangular matrix U, we first eliminate the element at position 2,1, that is, we multiply A (from the left side) with elimination matrix E₂₁. Then we eliminate the element at 3,1 by multiplying (from the left side) with elimination matrix E₃₁. Finally we eliminate the element at 3,2 by multiplying with elimination matrix E₃₂:

It follows from this equation that the lower-triangular matrix is the inverse of E₃₂·E₃₁·E₂₁, that is,

We have found the factorization of a 3x3 matrix:

The algorithm for finding matrices L and U should now be clear. First do the elimination to find matrix U, then invert the product of elimination matrices used for finding U to find L. Actually it’s even easier, you don’t even need to keep elimination matrices E, or find their inverse. You can just keep the multipliers used in each elimination step. Please see the video to find out how it works.

Next, the cost of elimination algorithm is discussed. How many steps does it take to go from matrix A to U? Turns out the elimination is O(n³) process (more carefully, it takes around n³/3 steps). (See my notes on MIT’s Introduction to Algorithms for more info about O-notation.)

Since we sometimes need to do row exchanged to do elimination, the last ten minutes of lecture are spent on permutation matrices. Remember from lecture two that multiplying a matrix from the left side with a permutation matrix exchanges its rows.

The key facts about permutation matrices P are:

• The inverse of P is its transpose: P^-1 = P^T.
• There are n! permutation matrices for n_xn matrices.

Here is the video of the fourth lecture:

Topics covered in lecture four:

• [01:20] What is the inverse of A·B?
• [05:20] What is the inverse of A^T?
• [09:20] A=LU factorization for 2×2 matrices.
• [13:20] A=LDU factorization.
• [14:50] A=LU decomposition for 3×3 matrices.
• [18:30] Why is finding matrix L trivial?
• [27:25] How many operations does elimination take?
• [42:20] Permutation matrices.
• [47:20] What is the inverse of a permutation matrix?
• [48:20] How many P matrices for 3×3 and 4×4 matrices?

Here are my notes of lecture four:

My notes of linear algebra lecture 4 on the A=LU factorization.

Have fun with this lecture! The next post is going to be about transpose matrices, symmetric matrices, vector spaces, their subspaces and column spaces of matrices.

PS. This course is taught from Introduction to Linear Algebra textbook. Get it here:

This is the third post in the article series about Unix and Linux utilities that you should know about. In this post I will take you through the useful lsof tool. If netcat was called the Swiss Army Knife of Network Connections, then I’d call lsof the Swiss Army Knife of Unix debugging.

Lsof follows Unix philosophy closely. It does just one task and it does it perfectly — it lists information about files opened by processes. An open file may be a regular file, a directory, a NFS file, a block special file, a character special file, a shared library, a regular pipe, a named pipe, a symbolic link, a socket stream, an Internet socket, a UNIX domain socket, and many others. Since almost everything in Unix is a file, you can imagine how incredibly useful lsof is!

See the first post on pipe viewer for the introduction to this article series. If you are interested in articles like this one, I suggest that you subscribe to my rss feed to receive my future posts automatically!

How to use lsof?

In this article I will try to present lsof based on as many use cases as I can think of. Let’s start with the simplest (that you probably already know) and proceed to more complicated ones.

List all open files.

# lsof

Running lsof without any arguments lists all open files by all processes.

Find who’s using a file.

# lsof /path/to/file

With an argument of a path to a file, lsof lists all the processes, which are using the file in some way.

You may also specify several files, which lists all the processes, which are using all the files:

# lsof /path/to/file1 /path/to/file2

Find all open files in a directory recursively.

# lsof +D /usr/lib

With the +D argument lsof finds all files in the specified directory and all the subdirectories.

Note that it’s slower than the usual version with grep:

# lsof | grep '/usr/lib'

It’s slower because +D first finds all the files and only then does the output.

List all open files by a user.

# lsof -u pkrumins

The -u option (think user) limits output of files opened only by user pkrumins.

You can use comma separated list of values to list files open by several users:

# lsof -u rms,root

This will list all the files that are open by users rms and root.

Another way to do the same is by using the -u option twice:

# lsof -u rms -u root

Find all open files by program’s name.

# lsof -c apache

The -c option selects the listing of files for processes whose name begins with apache.

So instead of writing:

# lsof | grep foo

You can now write the shorter version:

# lsof -c foo

In fact, you can specify just the beginning part of the process name you’re looking for:

# lsof -c apa

This will list all the open files by a processes whose starts with apa.

You can also specify several -c options to output open files by several processes:

# lsof -c apache -c python

This will list all open files by apache and python.

List all open files by a user OR process.

# lsof -u pkrumins -c apache

Lsof options can be combined. The default is to OR between options. It means it will combine outputs of -u pkrumins and -c apache producing a listing of all open files by pkrumins and all open files by apache.

List all open files by a user AND process.

# lsof -a -u pkrumins -c bash

Notice the -a option. It combines the options with AND. The output listing is files opened by bash, which is run under pkrumins user.

List all open files by all users EXCEPT root.

# lsof -u ^root

Notice the ^ character before root username. It negates the match and causes lsof print all open files by all users who are not root.

List all open files by the process with PID.

# lsof -p 1

The -p option (think PID) filters out open files by program’s id.

Remember that you can select multiple PIDs by either comma separating the list or using multiple -p arguments:

# lsof -p 450,980,333

This selects processes with PIDs 450, 980 and 333.

List all open files by all the processes EXCEPT process with PID.

# lsof -p ^1

Here the negation operator ^ is used again. It inverts the list and does not include process with PID 1.

List all network connections.

# lsof -i

Lsof with -i option lists all processes with open Internet sockets (TCP and UDP).

List all TCP network connections.

# lsof -i tcp

The -i argument can take several options, one of them is tcp. The tcp option forces lsof to list only processes with TCP sockets.

List all UDP network connections.

# lsof -i udp

The udp option causes lsof to list processes with UDP sockets.

Find who’s using a port.

# lsof -i :25

The :25 option to -i makes lsof find processes using TCP or UDP port 25.

You may also use service port name (found in /etc/services) rather than port number:

# lsof -i :smtp

Find who’s using a specific UDP port.

# lsof -i udp:53

Similarly, to find who’s using a TCP port, use:

# lsof -i tcp:80

Find all network activity by user.

# lsof -a -u hacker -i

Here the -a option combines -u and -i to produce listing of network file usage by user hacker.

List all NFS (Network File System) files.

# lsof -N

This option is easy to remember because -N is NFS.

List all Unix domain socket files.

# lsof -U

This option is also easy to remember because -U is Unix.

List all files for processes with a specific group id.

# lsof -g 1234

Process groups are used to logically group processes. This example finds all files opened by processes with PGID 1234.

List all files associated with specific file descriptors.

# lsof -d 2

This lists all files that have been opened as file descriptor 2.

You may also specify ranges of file descriptors:

# lsof -d 0-2

This would list all files with file descriptors 0, 1 and 2.

There are also many special values, such as mem, that lists memory-mapped files:

# lsof -d mem

Or txt for programs loaded in memory and executing:

# lsof -d txt

Output PIDs of processes using some resource.

# lsof -t -i

The -t option outputs only PIDs of processes. Used together with -i it outputs PIDs of all processes with network connections. It’s easy to kill all processes that use network:

# kill -9 `lsof -t -i`

Repeat listing files.

# lsof -r 1

The -r option makes lsof repeatedly list files until interrupted. Argument 1 means repeat the listing every 1 second. This option is best combined with a narrower query such as monitoring user network file activity:

# lsof -r 1 -u john -i -a

How to install lsof?

Lsof comes preinstalled on many Unix systems. If your system doesn’t have it, try to install it from the source.

BSD supplies its own utility that does similar things, it’s called fstat.

For the full documentation of lsof see the man lsof page or type lsof -h for a small cheat sheet.

Have fun with lsof!

This is the third post in an article series about MIT’s course “Linear Algebra”. In this post I will review lecture three on five ways to multiply matrices, inverse matrices and an algorithm for finding inverse matrices called Gauss-Jordan elimination.

The first lecture covered the geometry of linear equations and the second lecture covered the matrix elimination.

Here is lecture three.

Lecture 3: Matrix Multiplication and Inverse Matrices

Lecture three starts with five ways to multiply matrices.

The first way is the classical way. Suppose we are given a matrix A of size mxn with elements a_ij and a matrix B of size nxp with elements b_jk, and we want to find the product A·B. Multiplying matrices A and B will produce matrix C of size mxp with elements .

Here is how this sum works. To find the first element c₁₁ of matrix C, we sum over the 1st row of A and the 1st column of B. The sum expands to c₁₁ = a₁₁·b₁₁ + a₁₂·b₂₁ + a₁₃·b₃₁ + … + a_1n·b_n1. Here is a visualization of the summation:

We continue this way until we find all the elements of matrix C. Here is another visualization of finding c₂₃:

The second way is to take each column in B, multiply it by the whole matrix A and put the resulting column in the matrix C. The columns of C are combinations of columns of A. (Remember from previous lecture that a matrix times a column is a column.)

For example, to get column 1 of matrix C, we multiply A·(column 1 of matrix B):

The third way is to take each row in A, multiply it by the whole matrix B and put the resulting row in the matrix C. The rows of C are combinations of rows of B. (Again, remember from previous lecture that a row times a matrix is a row.)

For example, to get row 1 of matrix C, we multiply row 1 of matrix A with the whole matrix B:

The fourth way is to look at the product of A·B as a sum of (columns of A) times (rows of B).

Here is an example:

The fifth way is to chop matrices in blocks and multiply blocks by any of the previous methods.

Here is an example. Matrix A gets subdivided in four submatrices A₁ A₂ A₃ A₄, matrix B gets divided in four submatrices B₁ B₂ B₃ B₄ and the blocks get treated like simple matrix elements.

Here is the visualization:

Element C₁, for example, is obtained by multiplying A₁·B₁ + A₂·B₃.

Next the lecture proceeds to finding the inverse matrices. An inverse of a matrix A is another matrix, such that A^-1·A = I, where I is the identity matrix. In fact if A^-1 is the inverse matrix of a square matrix A, then it’s both the left-inverse and the right inverse, i.e., A^-1·A = A·A^-1 = I.

If a matrix A has an inverse then it is said to be invertible or non-singular.

Matrix A is singular if we can find a non-zero vector x such that A·x = 0. The proof is easy. Suppose A is not singular, i.e., there exists matrix A^-1. Then A^-1·A·x = 0·A^-1, which leads to a false statement that x = 0. Therefore A must be singular.

Another way of saying that matrix A is singular is to say that columns of matrix A are linearly dependent (one ore more columns can be expressed as a linear combination of others).

Finally, the lecture shows a deterministic method for finding the inverse matrix. This method is called the Gauss-Jordan elimination. In short, Gauss-Jordan elimination transforms augmented matrix (A|I) into (I|A^-1) by using only row eliminations.

Please watch the lecture to find out how it works in all the details:

Topics covered in lecture three:

• [00:51] The first way to multiply matrices.
• [04:50] When are we allowed to multiply matrices?
• [06:45] The second way to multiply matrices.
• [10:10] The third way to multiply matrices.
• [12:30] What is the result of multiplying a column of A and a row of B?
• [15:30] The fourth way to multiply matrices.
• [18:35] The fifth way to multiply matrices by blocks.
• [21:30] Inverses for square matrices.
• [24:55] Singular matrices (no inverse matrix exists).
• [30:00] Why singular matrices can’t have inverse?
• [36:20] Gauss-Jordan elimination.
• [41:20] Gauss-Jordan idea A·I -> I·A^-1.

Here are my notes of lecture three:

My notes of linear algebra lecture 3 on the matrix multiplication and inverses.

Have fun with this lecture! The next post is going to be about the A=LU matrix decomposition (also known as factorization).

PS. This course is taught from Introduction to Linear Algebra textbook. Get it here:

The regular expressions we use in our daily lives are actually not that “regular.” Most of the languages support some kind of extended regular expressions that are computationally more powerful than the “regular” regular expressions as defined by the formal language theory.

For instance, the so often used capture buffers add auxiliary storage to the regular expressions that allow them to match an arbitrary pattern repeatedly. Or look-ahead assertions that allow the regular expression engine to peek ahead before it making a decision. These extensions make regular expressions powerful enough to describe some context-free grammars.

The Perl programming language has an especially rich with regex engine. One of the engine’s features is the lazy regular subexpressions. The lazy regular subexpressions are expressed as (??{ code }), where the “code” is arbitrary Perl code that gets executed when the moment this subexpression may match.

This allows us to construct something really interesting - we can define a regular expression that has itself in the “code” part. The result is a recursive regular expression!

One of the classical problems that a regular expression can’t match is the language 0n1n, i.e., a string with a number of zeroes followed by an equal number of ones. Surprisingly, using the lazy regular subexpressions this problem becomes tractable!

Here is a Perl regular expression that matches 0n1n:

$regex = qr/0(??{$regex})?1/;

This regular expression matches a 0 followed by itself zero or one time, followed by a one. If the itself part doesn’t match, then the string this regular expression matches is 01. If the itself part matches, the string this regular expression matches is 00($regex)?11, which is 0011 if $regex doesn’t match or it’s 000($regex)?111 if it matches, …, etc.

Here is a Perl program that matches 050000150000:

#!/usr/bin/perl

$str = "0"x50000 . "1"x50000;
$regex = qr/0(??{$regex})*1/;

if ($str =~ /^$regex$/) {
  print "yes, it matches"
}
else {
  print "no, it doesn't match"
}

Now let’s look at the Yo Dawg regular expression in the picture above. Can you guess what it does? It matches a fully parenthesized expression such as (foo(bar())baz) or balanced parentheses ((()()())()).

$regex = qr/
  \(                 # (1) match an open paren (
    (                # followed by
      [^()]+         #   (3) one or more non-paren character
    |                # OR
      (??{$regex})   #   (5) the regex itself
    )*               # (6) repeated zero or more times
  \)                 # (7) followed by a close paren )
/x;

Here is how to think about this regular expression. For an expression to be fully parenthesized, it has to start with an open paren, so we match it (point (1) in the regex). It also has to end with close paren, so we match a close paren at the end (point (7)). Now we have to think what can be in-between the parens? Well, we can either have some text that is neither an open paren or closed paren (point (3)) OR we can have another fully parenthesized expression! (point (5)). And all this may be repeated either zero times (point (6)) to match the smallest fully parenthesized expression () or more times to match a more complex expression.

Without the /x flag (that allows multiline regexes), it can be written more compactly:

$regex = qr/\(([^()]+|(??{$regex}))*\)/;

But please don’t use these regular expressions in production as they are too cryptic. Use Text::Balanced or Regexp::Common Perl modules.

And finally, in Perl 5.10 you can use recursive capture buffers instead of lazy code subexpressions to achieve the same result.

Here is a regular expression that matches 0n1n and uses the recursive capture buffer syntax (?N):

my $rx = qr/(0(?1)*1)/

The (?1)* says “match the first group zero or more times,” where the first group is the whole regular expression.

You can try to rewrite the regular expression that matches balanced parens as an exercise.

Have fun!

I have been working on the new catonmat.net website for quite some time now and I have gathered a very long list ideas of what a modern website should have. They include ideas from psychology, search engine optimization, social media, programming, and the best web design practices.

Since I started to use github last week, all the new catonmat code will be there. I already created a catonmat repository and I am going to be pushing code there daily.

I love to share my ideas, so here are the first 50 of them. I am going to share more later in the upcoming article series “Designing the new catonmat.net together with me.” You should subscribe to my blog here, if you are interested in this topic and haven’t subscribed yet.

The ideas are in no particular order. If some of them seem fuzzy or unclear, please ask me to clarify in the comments.

1. 301 Redirect Table.

The idea is to maintain a table that will be checked against the request URLs. If the request URL is in the table, it gets redirected to a new destination URL with the 301 HTTP header, which forwards the link juice from one URL to another. This is necessary because some forums break URLs in multiple lines and the resulting clickable URL is 404. If I didn’t do a 301 to the new location, this link would be lost. Anyone who clicked it, would end up on the 404 error page. Another example is if someone links to a mistyped URL. Anyone who clicks it ends up being unsatisfied, at 404 page. With a 301 table I can quickly fix these problems. Here is a concrete example: Someone links to www.catonmat.net/artikle when they wanted to link to www.catonmat/article. I’d simply insert an entry to 301 redirect /artikle to /article and everyone’s happy.

2. 404 Error Log.

I absolutely have to know what pages trigger 404 errors so that I can fix them ASAP with the 301 redirect table. There may be many false alarms, therefore I have to add filters to the 404 error log to ignore some spammy patterns.

3. A Great 404 Page.

If someone ends up on a non-existing page, log it as described in #2 and then explain to the visitor why the page he visited was not found. Suggest him or her or it to view 5 latest post titles, or 5 most popular posts, or most popular downloads, or something else (still have to think about it when I implement it).

4. A Separate Trackback/Pingback/Linkback/Refback Page With Moderation.

Tracebacks are usually displayed among comments. This is very messy. There is no place for them among comments. The idea is to have them on a separate page like www.catonmat.net/post-title/trackbacks. Also add bulk moderation as spammers love to exploit trackback. (Perhaps drop trackbacks altogether as they are of very little value.)

5. A Page With Last Comments.

Currently I am displaying only the 10 last comments on the right sidebar. This is insufficient. I want to see all the comments (like www.reddit.com/comments) on a single page, so that even if I am away from computer for several days, I can easily navigate through them and reply/hide/edit/delete in-place. Perhaps add a RSS feed for comments page.

6. Comment Statistics.

I need to tell my blog readers who are the most active people on my website. This will stimulate people to be more active. Therefore I should add a comment statistics with most popular commentators, link to their pages without nofollow to give them link juice. Also add statistics of the most commented articles.

7. Add Incoming Search Term Statistics On All Pages.

When people come from Google or Yahoo, save the query they used and display it on the page. This way I will always know what terms were searched for on each of the pages, without having to write complex queries.

8. Add Download Statistics.

Currently I have sloppy download statistics. I want nice graphs and want to see the most popular downloads by day, month, etc. This should be written as a statistics framework as traffic statistics, article statistics, delicious statistics and download statistics will all have more or less same graphs.

9. Public Statistics Section For del.icious.com Bookmarks.

I want to see how often my posts get bookmarked on del.icious.com. I also want nice graphs for them by day, week, month, etc. I also want a list of people who bookmarked my posts the most often, and tags they used. Make this public and also very modular so other people can reuse the code and put it on their sites. Reward the most frequent bookmarkers with links to their sites.

10. Insert Beautiful Images To Give Rest To Eyes.

Insert some beautiful landscape images after serveral paragraphs of text to give rest to eyes and give the reader positive emotions.

An image from ginnerobot’s photostream on Flickr.

11. Public Traffic Statistics.

I want the super statistics for my website. And make them public. I want to see which is the most popular article today, which was yesterday. I want nice traffic graphs and trends.

12. Public Twitter Statistics.

Find who’s tweeting about catonmat and put all these tweets on a separate page. Find who’s the most active catonmat tweeter and make this person stand out. Link to twitter profiles.

13. Integrate GitHub Directly In Catonmat

Integrate GitHub with status updates, friend count, directly in catonmat. Would have to write some kind of a scraper or use their API, if it’s usable for this purpose.

14. Implement Threaded Comments.

Currently I have linear comments, which are no good. To find whom someone replied to I have to scroll through the comments. This doesn’t make any sense. I have to add threaded comments. This will also engage users is more conversations.

15. Have Individual Links To Comments Like On Reddit.

I don’t like links to comments in a form www.catonmat.net/article/#comment-55. I want them to be in form www.catonmat.net/article/comment-55 so that each comment (or thread of comments) is on its own page. This way, if linked to a comment, person will precisely have that comment loaded. Browsers can misbehave in case of anchor links like #comment-55 and I don’t like that.

16. Lightweight Syntax For Comments.

There are just a few things comments need:

• Quote someone.
• Emphesize part of a comment in bold or italic.
• Link to some page.
• Share code fragment (auto syntax highlight it).

That’s it. Nothing else is necessary, no stupid HTML comments.

17. Filter Comments By Language.

My website is getting a lot of spam from Russia with comments in Russian. I am sure no one would write comments in Russian on my site. Add a filter to leave just the English comments. All other are spam.

18. Add Gravatar Icons To Comments.

Gravatar is at www.gravatar.com. It’s a map from emails to jpegs of user icons. This will make people stand out. Also display the gravatar user icons on comment statistics (point above). Having gravatars will emotionally associates you with commentators and the next time you see a gravatar you can predict the nature of the comment (depending if you had positive emotions or negative before).

19. Add More “Contact Me” Options Near “About me” on The Right Sidebar.

You want to get yourself out. If you don’t do it, no one will come after you. Add links to Facebook, Linked In, Twitter, Plurk, GitHub, FriendFeed, perhaps some other sites. Show the email as an image and add a link to my IRC channel #catonmat on irc.freenode.net. Initially show only Twitter, Facebook and GitHub. Add an arrow down clickable image. After clicked displays all other contact options.

20. Snippets Page.

I have been writing and collecting various programming snippets. I want to have them in a central database on my site. Instead of putting them on some foreign service like GitHub’s Gist or Pastebin of some kind, I want to keep them on my website in my database so that I can easily modify them in a single place and integrate within posts.

An image from digital cat’s photostream on Flickr.

21. Add Revision Control For All The Pages.

Currently if I edit a page, the previous page is lost and I can’t see the changes. It’s crucial to keep the changes as sometimes I need to get something from a year ago. I have to add revision control like wikipedia does. The URL scheme could be www.catonmat.net/article/revisions - displays all available revisions, and www.catonmat.net/article/revisions/r1/r2 displays changes between r1 and r2, but I have to think about it a bit more.

22. Create Tiny URLs For Articles On My Own Site

I don’t want to depend on some service that may go down. Make short urls like http://catonmat.net/abc, where abc is [a-zA-Z0-9] this will give me 238328 URLs, more than enough. I could even go for something shorter.

23. Optimize Catonmat Load Speed To Maximum.

Use the page-speed FireBug plugin to optimize site loading speed. Page-speed is at http://code.google.com/speed/page-speed/. Things to be optimized include minified javascript, minified html, gzip compressed content, maximizing caching, use asynchronous js loading of google analytics and others.

24. Make The Posts More Available

Currently the posts are only available as HTML documents. I should try to convert them to PDF and put them to Scribd. I have to think about consequences as Scribd may show up on search engines at a higher ranking position than catonmat iself, which would have drastic impact on the traffic. Saving to PDF has a benefit that it’s a single file. If saved as HTML, the browser creates a folder with tons of images. Can’t be shared easily and is clutter. Perhaps offer a PDF download for all articles.

25. Make Posts Printer Friendly.

Create a nice CSS template for printing articles. At the end of the article include URLs to all the mentioned resources. Add an option to choose whether to print comments or not. URL structure could be www.catonmat.net/article/print

26. Add A “Share this” Widget.

Add “Share this” widget and perhaps “Reddit this”, “Digg this”, “Stumble this”, etc., buttons. This should be based on referrer as I don’t want to show “Reddit this” to a Digg visitor as there is a holy war between Reddit and Digg. Also add “Tweet this” button somewhere.

27. Utilize The New Google Feature Of Displaying Named Anchors In Search Results.

See this post: http://googleblog.blogspot.com/2009/09/jump-to-information-you-want-right-from.html Some of my posts utilize this (10 Awk Tips, Tricks and Pitfalls), but I need to utilize it more.

28. Highlight The Python Code As In SQLalchemy Documentation.

I like how the code is highlighted in SQLalchemy documentation. I am not sure if they are using Pygments or not, but I’ll try to make mine exactly the same. Example: http://www.sqlalchemy.org/docs/05/ormtutorial.html

29. Create Pagination For Posts/Categories/Tags As In Flickr.com

I like the style of Flickr’s pagination. Got to implement the same on catonmat. Example: http://www.flickr.com/photos/frijole/

30. Have Pages Open In A New Window By Default.

I feel that opening links in a new window would keep visitors on the website longer. I haven’t tested but I will A/B this. Update: This is not a good idea, won’t implement it.

An image from paraflyer’s photostream on Flickr.

31. Investigate What Do Various <a rel=”…”> Do.

There are a bunch of different relations like rel=”bookmark”, rel=”prev”, rel=”next”. This could improve the website navigation greatly. More info here: http://www.w3schools.com/TAGS/att_a_rel.asp

32. Perhaps Remove The Article Date Altogether.

I have noticed myself that if I search for something and I find an article from 2004, I want to look for something fresher. Got to A/B test this and see how long do people stay on the site.

33. Add An IP Ban List.

Sometimes spammers use the same IPs. Rather than `iptables -I INPUT –src IP -j REJECT` them, just block them at application level, 404 all pages, or redirect them elsewhere.

34. Automatically Translate All Pages To All Languages Via Google Translate

Sometimes people search for something in their own language and can’t find it. Perhaps they don’t know English term and therefore can’t find what they wanted. If I automatically translate all pages to all languages, people would end up on my website and find what they were looking for. The URL scheme for this could be: www.catonmat.net/xx/…, where xx is two letter international language code.

35. Try Out Dustin Curtis’ Advice On Best Performing Link Texts.

Dustin Curtis did an experiment where he tried various link texts to invite readers to follow him on Twitter. The first version was “I’m on Twitter”, this got 4.70% click through rate. The last version was “You Should follow me on Twitter <here>”. This had 12.81% CTR, which is a massive improvement.

36. Add “Ask Peteris Krumins” Section Where People Can Ask Me Various Questions.

People ask me a lot of questions over email. I could answer all the questions on my website instead of email. This way everyone could always find all my answers.

37. Add A “FAQ” section.

I get asked the same questions over and over again over email. For example,

• What do I have to know for Google interview?
• What books do I read?
• How to learn C++/C/Python/Algorithms?
• etc.

Instead of sending the answer over email, I could send these people to FAQ page where they could find my latest answers (as they change over time).

38. Add Knowledge Database.

This idea has the highest priority. A knowledge database is a section on my website where I can write everything that I learned each day. This should be accompanied with a desktop application that has a hotkey that instantly brings up input dialog and I can type what I just learned. I had a database like this in 2002-2004 and my knowledge literally went exponential. I wrote out key facts that I learned each day and could easily locate as necessary.

39. Add A Miniblog For Quick Articles.

Sometimes I have some cool idea or quick hack that I want to share, but as I am used to writing large and well thought out articles, I can’t post the quick hacks and my thoughts don’t get shared. A miniblog would allow me to share even the smallest thoughts that I have.

40. Add More Programming Quotes.

I love various smart programming quotes. I should make them more accessible, make them searchable by author/text.

An image from paraflyer’s photostream on Flickr.

41. Integrate LaTeX In My Posts.

As I am sometimes writing about maths, I need to integrate LaTeX directly in my posts. I should not forget to do SEO on images it generates - instead of having some ridiculous <img src=”latex-generator?q=$\begin{bmatrix}1&2\\3&4\end{bmatrix}$>” I should have it generate an image “<img src=”matrix.jpg” title=”Matrix”>”. This way people will be able to find my posts via image search if they search for some mathematical terms like “Matrix”.

42. Try Out How The Articles Look With Text-Align: Justify.

I currently have the default left-aligned text. Books and journals have it justified. Not sure how it would look on my website. Have to try it out. A/B. I read somewhere that this may feel confusing to dyslexic users.

43. Have In-Line Code Snippets And Variables Stand Out From Rest Of The Text.

A nice example of this is Github’s blog. They have gray background for constant-width things. See this: http://github.com/blog/530-how-we-made-github-fast

44. Have <a> Links Change Background Color On Hover.

I love how mattt.me has done it: http://mattt.me/articles/ I want this.

45. Have Only One Category Per Post But Multiple Tags.

A post should have only one single category. The category must strictly define the main theme of the article. A post can have multiple tags. Tags define topics discussed in the post.

46. Add Crazyegg Tracking For The First Month.

Must add crazyegg to track how the users navigate the site, where they click and what they visit. Optimize based on the results. http://crazyegg.com/

47. Add A Job Board.

As my site is getting more popular and popular among programmers, it may be a good idea to add a job board. Joel Spolsky made a million $ in a year with job boards. As the popularity of my site increases, I might make a few dollars out of it as well.

48. Use Statcounter and Google Analytics

This is obvious. Statcounter is for real-time data. The free version is limited to statistics of last 500 visits. Google Analytics is for keeping long term statistics with a day of delay in updates. Load them asynchronously: http://googlecode.blogspot.com/2009/12/google-analytics-launches-asynchronous.html

49. Form Input Fields And Text Fields Should Change Border Color On Focus.

Users should know what field they are focused to without trying to find the cursor.

50. Mandatory Alt Attributes For Images, Title Attributes For Links.

The rationale of this feature is that if images don’t get loaded or if blind people are listening to the content of my posts via text-to-speech engine, they should know what the image displays. Alt tags also help the search engines to classify images. The same goes for title attributes for links.

51. Optimize Meta Description For Categories And Tags

Category and tag pages usually have meta description as “Posts in <category>”. This is unsatisfactory. I want a description of category and if it’s missing or is too short, I want it to have some post titles in it, to make it unique. The same for tags, make meta tags “Posts in <tag>: post title1, post title2, …” not exceeding 20 words or so.

An image from dsevilla’s photostream on Flickr.

The next post in this series will be about Python libraries that I use for the new catonmat and the structure of the site. You can also follow the development on GitHub (I started importing code only yesterday so there is not much yet).

Hey everyone, I just pushed 30 of my projects to GitHub. I realized that all the projects were scattered across my blog and there was no central repository. So I took time to organize them, write documentation, and uploaded them to GitHub.

I did all of these projects for fun and to learn better programming. You can’t become a great programmer if you don’t program a lot. The more you program, the more language idioms and constructs you’ll learn. You’ll learn common patterns that occur frequently in programming and it will greatly improve your problem solving skills.

These were all relatively small projects and I think I am ready to move to the next level. I have several larger ideas in mind that need to be turned into code. I will post the updates to catonmat.

If you find any of my projects interesting, clone and start hacking. You can also follow my profile at github. :-)

Here they all are. Enjoy!

1. Busy Beaver

Busy beaver is a computer science problem to finding the smallest Turing Machine that outputs the most data and eventually halts. This project is an implementation of a Turing Machine in Python and C++ that runs the busy beavers. It also comes with Turing Machine’s tape visualization tool written in Perl.

• Busy Beaver on Github.
• Article about Busy Beaver on catonmat.

2. Feedburner Graph Generator

Current Feedburner statistics graphs do not look nice. I wrote this Perl program to generate the nice graphs they had in 2008.

• Feedburner graph generator on Github.
• Article about feedburner graph generator on catonmat.

3. CodingHorror Keyword Analyzer

This is a Perl program that parses public statcounter data for codinghorror.com blog and stores the search keywords in an SQLite database.

• CodingHorror keyword analyzer on Github.
• Article about analyzing Coding Horror keywords on catonmat.

4. Adns

This is a tiny Python module that does asynchronous DNS resolution with adns library. My benchmarks were 20,000 resolutions per minute on a 512kbit/s connection.

• Adns on Github.
• Article about ands on catonmat.

5. Winamp Music Reporter Plugin

This is a Winamp plugin that reports to digitalpoint forums the tracks you are listening to. Written in C and uses Winamp SDK. The code can be modified to make it report to Facebook or Twitter, or anywhere you wish.

• Winamp music reporter on GitHub.
• An article about Winamp music reporter on catonmat.

6. Bithacks.h

Bithacks.h is a C header file that implements various bit operations.

• Bithacks.h on Github.
• Article about bithacks.h on catonmat.
• Explanation of all the bithacks.

7. Set Operations in Unix Shell

This is an implementation of 14 set operations by using only Unix utilities such as sort, uniq, diff, comm, cat, head, tail, awk, and others.

• Set operations in Unix shell on GitHub.
• Article about set operations in Unix shell on catonmat.

8. Hacker Top

Hacker top is a Unix top-like program written in Python for monitoring Hacker News from the console.

• Hacker top on GitHub.
• Article about the Hacker top program on catonmat.

9. Reddit Top

Reddit top is a Unix top-like program written in Python for monitoring Reddit from the console.

• Reddit top on GitHub.
• Article about the Reddit top program on catonmat.

10. GNU Awk YouTube Downloader

This is a program written in GNU Awk that downloads YouTube videos. It works well but please don’t take it too seriously. It’s a proof of concept code, written to see what can be done with GNU Awk’s networking interface.

• GNU Awk YouTube downloader on GitHub.
• Article about GNU Awk YouTube downloader on catonmat.

11. VBScript YouTube Downloader

This is a program written in VBScript that downloads YouTube videos. I wrote it because when I was a child, I did a lot of programming in Visual Basic and I wanted to remember what it was like.

• YouTube downloader in VBScript on GitHub.
• An article about VBScript YouTube downloader on catonmat.

12. Perl One-Liner YouTube Downloader

This is a Perl one-liner that downloads YouTube videos. I wrote it because I love Perl golf.

• YouTube downloader one-liner in Perl on GitHub.
• An article about creating the Perl one-liner that downloads YouTube videos on catonmat.

13. YouTube Video Uploader

This is a YouTube video uploader that works without any APIs. It just simulates what a browser would do and takes all the steps to post the video and set the video info. Written in Perl.

• YouTube video uploader on GitHub.
• An article about creating the video uploader on catonmat.

14. Plurk Translation Tool

This is a GreaseMonkey script that translates Plurks to English.

Plurk is like Twitter but more fun and organized. Come be my friend on Plurk, my profile name is pkrumins. Written in JavaScript.

• Plurk translation tool on Github.
• Plurk translation tool description on Plurk’s Open Source website.

15. Command Line Plurker

Plurk from your command line. Written in Perl.

• Command line plurker on GitHub.

16. Find Plurks on Google

This program searches for plurks that were indexed by Google. It outputs URLs to indexed pages. It’s written in Python and uses my xgoogle library.

• Plurk finder on GitHub.

17. Delete Plurks

This is a GreaseMonkey script that adds a “delete” button on individual plurk pages. This way you can delete your or other people plurks (if it’s your thread) directly from the plurk page. Written in JavaScript.

• Delete plurks on GitHub.

18. Xgoogle

A Python library to Google services - Google Search, Google Sets, Google Translate and Sponsored Links.

• Xgoogle on GitHub.
• An article about Google search module on catonmat.
• An article about Google sets module on catonmat.
• An article about Google translate module on catonmat.
• An article about Google sponsored links module on catonmat.

19. Reddit Media

The old Reddit Media website that I created in 2007. No longer maintained. It was written in Perl.

• Reddit media on GitHub.
• An article about creating Reddit media website on catonmat.

20. Reddit River

The old Reddit River website for mobile devices. No longer maintained. It was written in Python.

• Reddit river on GitHub.
• An article about creating Reddit river website on catonmat.

21. Digpicz

This is the digpicz.com website that I created back in 2007. It got massive attention back then because Digg didn’t have picture section then. It was written in Perl.

• Digpicz on GitHub.
• An article about creating Digpicz website on catonmat.

22. Picurls

Picurls.com is a picture aggregator much like popurls.com but for pics. Currently down for maintenance, will be soon up again. Written in PHP.

• Picurls on GitHub.
• An article about creating Picurls.com website part I.
• An article about creating Picurls.com website part II.

23. Bash Vi Editing Mode Cheat Sheet

Bash has two input modes - emacs and vi. This is vi input/editing mode keyboard shortcut cheat sheet.

• Bash vi cheat sheet on GitHub.
• Article about bash vi mode on catonmat.

24. Bash Emacs Editing Mode Cheat Sheet

Bash has two input modes - emacs and vi. This is emacs input/editing mode keyboard shortcut cheat sheet.

• Bash emacs cheat sheet on GitHub.
• Article about bash emacs mode on catonmat.

25. Bash History Cheat Sheet

This is the bash history cheat sheet. It summarizes everything there is to know about working efficiently with command line history in bash.

• Bash history cheat sheet on GitHub.
• The definitive guide to bash history on catonmat.

26. Screen Cheat Sheet

This is the screen terminal emulator cheat sheet. It lists the default keyboard shortcuts for working with screen.

• Screen cheat sheet on GitHub.
• Article about screen cheat sheet on catonmat.

27. Perl Special Variable Cheat Sheet

This is Perl predefined variable cheat sheet. It lists all the variables from `perldoc perlvar` with a concise description and some example usages. I created it when I was mastering Perl. I enjoy Perl golf and I wanted to know all of the variables.

• Perl special variable cheat sheet on GitHub.
• An article about Perl predefined variable cheat sheet on catonmat.

28. Perl pack/unpack and printf/sprintf Cheat Sheet

This is Perl pack/unpack/printf/sprintf cheat sheet. The pack/unpack cheat sheet is on page one, and it lists the pack/unpack template parameters and what they do. The printf/sprintf cheat sheet is on page two, and it lists the printf/sprintf format specifiers and format attributes.

I created this when I was mastering what could be done with pack/unpack. I added printf/sprintf as I could never remember all the format specifiers.

• Perl pack, unpack, printf, sprintf cheat sheet on GitHub.
• An article about Perl pack, unpack, printf, sprintf cheat sheet on catonmat.

29. Awk Cheat Sheet

AWK programming language cheat sheet.

• Awk cheat sheet on GitHub.
• An article about Awk cheat sheet on catonmat.

30. Sed Cheat Sheet

This is sed cheat sheet. Sed is the Unix stream editor. If you don’t know it, you don’t know Unix.

• Sed cheat sheet on GitHub.
• An article about sed cheat sheet on catonmat.

31. Ed Cheat Sheet

This is ed cheat sheet. Ed is The Unix Text Editor.

One day when I was learning sed, I got interested if it originated from ed, which got me interested in ed itself. I find that cheat sheets are a great way to learn new topics and therefore I created this cheat sheet.

• Ed cheat sheet on GitHub.
• An article about ed cheat sheet on catonmat.

32. The New catonmat.net Website

I just started pushing code to the new catonmat.net repository. It’s going to be a state of the art personal website from now on.

I have around 100 ideas for it, and the next big article series on catonmat is going to be “Designing the new catonmat.net together with me.” You should subscribe to my blog here if you are interested!

• The New catonmat.net on GitHub.
• Articles about designing the new catonmat coming soon.

If you have any questions, don’t hesitate to ask in the comments!

This is the second post in an article series about MIT’s course “Linear Algebra”. In this post I will review lecture two on solving systems of linear equations by elimination and back-substitution. The other topics in the lecture are elimination matrices (also known as elementary matrices) and permutation matrices.

The first post covered the geometry of linear equations.

One of my blog readers, Seyed M. Mottaghinejad, had also watched this course and sent me his lecture notes. They are awesome. Grab them here: lecture notes by Seyed M. Mottaghinejad (includes .pdf, .tex and his document class).

Okay, here is the second lecture.

Lecture 2: Elimination with Matrices

Elimination is the way every software package solves equations. If the elimination succeeds it gets the answer. If the matrix A in Ax=b is a “good” matrix (we’ll see what a good matrix is later) then the elimination will work and we’ll get the answer in an efficient way. It’s also always good to ask how can it fail. We’ll see in this lecture how elimination decides if the matrix A is good or bad. After the elimination there is a step called back-substitution to complete the answer.

Okay, here is a system of equations. Three equations in three unknowns.

Remember from lecture one, that every such system can be written in the matrix form Ax=b, where A is the matrix of coefficients, x is a column vector of unknowns and b is the column vector of solutions (the right hand side). Therefore the matrix form of this example is the following:

For the elimination process we need the matrix A and the column vector b. The idea is very simple, first we write them down in the augmented matrix form A|b:

Next we subtract rows from one another in such a way that the final result is an upper triangular matrix (a matrix with all the elements below the diagonal being zero).

So the first step is to subtract the first row multiplied by 3 from the second row. This gives us the following matrix:

The next step is to subtract the second row multiplied by 2 from the third row. This is the final step and produces an upper triangular matrix that we needed:

Now let’s write down the equations that resulted from the elimination:

Working from the bottom up we can immediately find the solutions z, y, and x. From the last equation, z = -10/5 = -2. Now we put z in the middle equation and solve for y. 2y = 6 + 2z = 6 + 2(-2) = 6 - 4 = 2 => y = 1. And finally, we can substitute y and z in the first equation and solve for x. x = 2 - 2y - z = 2 - 2(1) - (-2) = 2.

We have found the solution, it’s (x=2, y=1, z=-2). The process we used to find it is called the back-substitution.

The elimination would fail if taking a multiple of one row and adding to the next would produce a zero on the diagonal (and there would be no other row to try to exchange the failing row with).

The lecture continues with figuring out how to do the elimination by using matrices. In the first lecture we learned that a matrix times a column vector gave us a combination of the columns of the matrix. Similarly, a row times a matrix gives us a combination of the rows of the matrix.

Let’s look at our first step of elimination again. It was to subtract 3 times the first row from the second row. This can be expressed as matrix multiplication (forget the column b for a while):

Let’s call the matrix on the right E as elimination matrix (or elementary matrix), and give it subscript E₂₁ for making a zero in the resulting matrix at row 2, column 1.

The next step was twice the second row minus the third row:

The matrix on the right is again an elimination matrix. Let’s call it E₃₂ for giving a zero at row 3, column 2.

But notice that these two operations can be combined:

And we can write E₃₂(E₂₁A) = U. Now remember that matrix operations are associative, therefore we can change the parenthesis (E₃₂E₂₁)A = U. If we multiply (E₃₂E₂₁) we get a single matrix E that we will call the elimination matrix. What we have done is expressed the whole elimination process in matrix language!

Next, the lecture continues takes a step back and looks at permutation matrices. The question asked is “what matrix would exchange two rows of a matrix?” and “what matrix would exchange two columns of a matrix?”

Watch the lecture to find the answer to these questions!

Topics covered in lecture two:

• [00:25] Main topic for today: elimination.
• [02:35] A system with three equations and three unknowns:
• [03:30] Elimination process. Taking matrix A to U.
• [08:35] Three pivots of matrix U.
• [10:15] Relation of pivots to determinant of a matrix.
• [10:40] How can elimination fail?
• [14:40] Back substitution. Solution (x=2, y=1, z=-2).
• [19:45] Elimination with matrices.
• [21:10] Matrix times a column vector is a linear combination of columns the matrix.
• [22:15] A row vector times a matrix is a linear combination of rows of the matrix.
• [23:40] Matrix x column = column.
• [24:10] Row x matrix = row.
• [24:20] Elimination matrix for subtracting three times row one from row two.
• [26:55] The identity matrix.
• [30:00] Elimination matrix for subtracting two times row two from row three.
• [32:40] E₃₂E₂₁A = U.
• [37:20] Permutation matrices.
• [37:30] How to exchange rows of a 2×2 matrix?
• [37:55] Permutation matrix P to exchange rows of a 2×2 matrix.
• [38:40] How to exchange columns of a 2×2 matrix?
• [39:40] Permutation matrix P to exchange columns of a 2×2 matrix.
• [42:00] Commutative law does not hold for matrices.
• [44:25] Introduction to inverse matrices.
• [47:10] E^-1E = I.

Here are my notes of lecture two:

My notes of linear algebra lecture 2 on elimination with matrices.

Have fun with this lecture! The next post is going to be either on lectures three and four together or just lecture three. Lecture three will touch a bit more on matrix multiplication and then dive into the inverse matrices. Lecture four will cover A=LU matrix decomposition (also called factorization).

PS. This course is taught from Introduction to Linear Algebra textbook. Get it here:

There is a mysterious underground Perl organization that hardly anyone has heard of. Their primary mission is to discover new secret Perl operators but they are not allowed to talk about them. I managed to infiltrate this organization and steal some of their secrets. Here are 8 secret Perl operators that I retrieved from their mysterious hoard:

• The Spaceship Operator
• The Eskimo Greeting Operator
• The Goatse Operator
• The Turtle Operator
• The Inchworm Operator
• The Inchworm-On-A-Stick Operator
• The Spacestation Operator
• The Venus Operator

(to be honest, only the first is a real Perl operator, all others are syntactic tricks.)

The Spaceship Operator <=>

<=> is the spaceship operator. Most commonly it’s used to sort a list of numbers. Here is an example:

my @numbers = (-59, 99, 87, 1900, 42, 1, -999, 30000, 0);
my @sorted = sort { $a <=> $b } @numbers;
print "@sorted\n";

# output: -999 -59 0 1 42 87 99 1900 30000

If you don’t specify a block with the spaceship operator to sort() function, it will treat the numbers as strings and sort them asciibetically:

my @numbers = (-59, 99, 87, 1900, 42, 1, -999, 30000, 0);
my @sorted = sort @numbers;
print "@sorted\n";

# output: -59 -999 0 1 1900 30000 42 87 99

In general the spaceship operator is defined as following:

• $a <=> $b is -1 if $a < $b.
• $a <=> $b is 0 if $a == $b.
• $a <=> $b is 1 if $a > $b.
• $a <=> $b is undef if $a and $b are NaN.

The Eskimo Greeting Operator }{

The Eskimo greeting operator can be most frequently met in Perl one-liners.

For example, this one-liner uses the Eskimo greeting to emulate `wc -l` command and prints the number of lines in a file:

perl -lne '}{ print $.' file

Here the Eskimo greets the print function. To understand what happens here, you have to know what the -n command line option does. It causes Perl to assume the following loop around your program:

while (<>) {
  ...
}

Where `...` contains the code specified by the -e command line option. If the code specified is `}{ ...` then it causes the while loop to be closed with no actions to be done and only the `...` part gets executed.

Therefore the one-liner above is equivalent to:

while (<>) {
}
{
print $.
}

This just prints the special variable $. which is the number of input lines processed.

This can be extended further and we can have Eskimo greet code on both sides:

perl -lne 'code1 }{ code2'

Code1 gets executed within the loop and code2 after the loop is done:

while (<>) {
  code1
}
{
  code2
}

If you are interested in the topic of Perl one-liners, see the first part of my article “Perl One-Liners Explained“.

The Goatse Operator =()=

The Goatse operator, as nasty as it may sound, doesn’t do any nasty things. Instead it does a wonderful thing and causes an expression on the right to be evaluated in array context.

Here is an example,

my $str = "5 foo 6 bar 7 baz";
my $count =()= $str =~ /\d/g;
print $count;

This program prints 3 - the number of digits in $str. How does it do it? Let’s deparse the 2nd line:

(my $count = (() = ($str =~ /\d/g)));

What happens here is that the expression ($str =~ /\d/g) gets assigned to the empty list (). Assigning to a list forces the list context. The whole (() = ($str =~ /\d/g)) thing gets evaluated in list context, but then it gets assigned to a scalar which causes it to get evaluated again in scalar context. So what we have is a list assignment in scalar context. The key thing to remember is that a list assignment in scalar context returns the number of elements on the right-hand side of the list assignment. In this example the right-hand side of the list assignment is ($str =~ /\d/g). This matches globally (/g flag) and finds 3 digits in $str. Therefore the result is 3.

The Turtle Operator “@{[]}”

I couldn’t find the name of this operator therefore I decided to name it the turtle operator, because it looks a bit like a turtle, @ being the head, and {[]} being the shell.

This operator is useful for interpolating an array inside a string.

Compare these two examples:

print "these people @{[get_names()]} get promoted"

and

print "these people ", join " ",get_names(), " get promoted"

Clearly, the first example wins for code clarity.

More precisely, writing

print "@{[something]}"

is exactly the same as writing

print join $", something

The Inchworm Operator ~~

The inchworm operator can be used to force scalar context.

Here is an example with localtime() function. In scalar context localtime() returns human readable time, but in list context it returns a 9-tuple with various date elements.

$ perl -le 'print ~~localtime'
Mon Nov 30 09:06:13 2009

Here localtime was evaluated in scalar context, even though it was called within print that forces list context. It returned human readable date and time.

$ perl -le 'print localtime'
579301010913330

Here localtime returned a list of 9 elements and print function just printed them one after another. To really see that it’s a list of 9 elements, let’s use the turtle operator:

$ perl -le 'print "@{[localtime]}"'
5 13 9 30 10 109 1 333 0

The Inchworm-On-A-Stick Operator ~-

For numbers greater than 0, this operator decrements them by one. Example:

my $x = 5;
print ~-$x;

# prints 4

It works because ~-$x parses to (~(-$x)), which on a two-complement machine is effectively the same as $x-1.

The Spacestation Operator -+-

The spacestation operator turns a string starting with positive number into a number. Here are some examples:

print -+-"4zy"   # prints 4
print -+-'3.99'  # prints 3.99
print -+-'2e5'   # prints 200000

The Venus Operator 0+

It’s named the Venus operator because the astronomical symbol for the planet Venus looks similar.

It does the same as the spacestation operator, it numifies a string, but it binds less tightly than spacestation. An example:

print 0+"4zy"  # prints 4

Share the secrets!