Bash Auto-Completion Trick

Most of us who use the bash shell in *nix environments, often find the Tab-key auto-completion to be a very helpful timesaver. But one of the main problems is that he feature is not adaptive, i.e. it does nothing to learn from my previous commands. For example in my home directory I have two folders: “picture” and “programming”. Usually there is no reason for me to traverse the “picture” folder using bash, I’d rather use nautilus for that. So when I type something like “cd p” and press Tab, I would ideally like to get “programming” rather than “picture”. What if we could somehow use the history of commands to help this auto-complete feature?

Here is a cool bash trick that I have been using for quite sometime. It helps me search the history of typed commands that begin with what I have typed so far. Here is the way to enable it in your system.

Edit the “~/.inputrc” file by appending the following lines to it and save it:

"\e[5~": history-search-backward

"\e[6~": history-search-forward

Note that the file “~/.inputrc” might not be present in your system, so in that case you will have to create it.

Now to use this feature, open a new instance of the shell and type something like “cd p” and press the PageUp and PageDown keys to search the history of commands that begin with “cd p” backwards or forwards and cycle through them.

Personally I find this quite a time saver. However note that the completion feature is not directory aware, so like in the previous example it might just give you the name of a directory that does not exist in your current path.

12 Coins puzzle

The puzzle goes like this:

A set of 12 coins of similar shape and size contains one counterfeit coin, whose weight is different from that of the other coins. Find the coin using a balance and minimum number of weighing.

The catch of the problem is that it is not mentioned whether the counterfeit coin is lighter or heavier than the rest of the normal coins.

Lower Bound

Let us first examine what is the minimum number of weighing required to find the coin. We use information theory based approach for getting this.

Each weighing can have three different outcomes,

1. left_side < right_side
2. left_side = right_side
3. left_side > right_side

Thus min number of weighing >= ceiling (log 12 base 3) = ceiling ( log(12)/log(3) ) = 3

Solution

Well, as it turns out, we need exactly 3 weighing. The method is kind of confusing to describe, so I drew a flowchart (PDF) for the same (click on the image for the full sized image):

 

Background

Campus recruitments were about to commence so I was in hunt for good puzzles to hone my problem solving skills. A friend of mine sent me this gem. I was used to tackling coin puzzles, but this was unique as the weight of the counterfeit coin was not given. I tried it and getting the 4 weighing solution was quite easy to get.

Next I  gave this problem to my friends at IISc, Dyut, Abhiskek and Arghya. After a lot of attempts Dyut and Abhiskek could not improve upon my solution. After a few days I tried it again. Particularly the case where the first two groups were unequal. After a couple of attempts with a fresh mind, I cracked it. Later I found out that my friends had also figured out the solution from some other friend, who solved it at the very first go. Well there are no dearth of brilliant guys IISc !