nabb

Also working on pairs of consecutive fibonacci numbers (f_n, f_(n+1)) instead of the matrix [[f_(n+1) f_n] [f_n f_(n-1)]] makes this much simpler.

  def fib(n):
    def fib2(n):
      # returns (f_n, f_(n+1))
      if n == 0:
        return 0, 1
      if n % 2:
        a, b = fib2(n-1)
        return b, a+b
      a, b = fib2(n//2)
      return b*a + a*(b-a), a*a + b*b
    return fib2(n)[0]

nabb

14 anni fadiscuss

An easy way to do the second is to consider the sum and the sum of squares. This gets you a-b and a^2-b^2. Recall that the latter is (a-b)(a+b) and the answer follows immediately.

nabb

15 anni fadiscuss

I'd add TopCoder and Codeforces to the list:

http://community.topcoder.com/tc

http://codeforces.com/

Both of these sites run a few algorithm competitions every month.

nabb

15 anni fadiscuss

The introduction was alright, but I'm not sure that the hold buffer needs to be introduced straight away. Using the hold buffer can get complicated pretty quickly, and it isn't something that you'll frequently have to do. The example the author gives of getting lines matching a regex with the previous line is more easily done using grep -B1, which doesn't require the mental overhead of sed scripting.

Perhaps more useful for an introduction would be retaining portions of the input back-references (\1 to \9) and `&'. Also useful is is the `g' flag for the `s' command, for global replacement, and the `i' flag (a GNU extension) for case insensitivity. Another note is that you can actually use any character to delimit `s' commands you want, which is useful if you have /'s in your pattern or replacement strings. The last main part of sed which I use regularly is the -r option, for extended regular expressions (basically the same as grep), which lets you use regular expression tokens like + and | without escaping. On that note, the author misses this point in his introduction, and the example of "sed -n '/a+b+/p'" should actually be either "sed -rn '/a+b+/p'" or "sed -n '/a\+b\+/p'".

For a serious introduction to all the extra functionality in sed, there's a great reference at the top google result for sed[1]. In addition, GNU sed adds functionality that you might be useful at some point (e.g. s///e), all of which are described in the GNU sed user's manual[2].

[1] http://www.grymoire.com/Unix/Sed.html [2] http://www.gnu.org/software/sed/manual/index.html

nabb

15 anni fadiscuss

tail can be done in ruby can be quite succinctly with the $< (ARGF) variable:

  ruby -e'$><<$<.map.last(10)'

For the rest of the ruby one-liners in the page the author references, most can be done more easily with standard command line tools (although most people aren't well-versed in sed, so 'ruby -pe puts' might be better than 'sed G').

Submissions

Internet Problem Solving Contest

comments