[waps]

Experience is more about knowing a million little tricks than it is about actual domain knowledge. Norvig's spelling corrector is an application of inverting the problem.

Instead of attempting to correct a misspelling, he attempts to misspell a word, then stores the misspelled word along with the original word. Then, to correct a misspelling, you simply look it up in the hash table.

Incredibly powerful mathematical concept that inversion thing. And there's a million of them.

Other "tricks":

* shuffling a deck of cards in O(1) (or shuffling anything at all)

* sorting in O(N) (with a limited keyset, and guaranteed no repetitions it's easy. Think about it).

* knowing the url to MIT's bit twiddling manual [1]

* know how to "rewrite" english (or any language) text. Really impressive. Also, mostly useless. It's called Markov Chains.

* understand how and why "every language compiles first to LISP, then to machine code" is true. Thinking about this yields no end of clever programming tricks

* make sure to have spent a few months in each style of programming. Imperative (doesn't tend to be a problem). Functional (NEVER change the value of a variable, ever, for any reason). Dynamic (write a calculator using eval, and go from there. Exploit it).

* having the experience that any style of configuration eventually ends up being a turing complete programming language, and so you should just import and use an existing language

* having experienced the power of query languages. Instead of having a few reports, implement an interpreter that allows you to query them. Then amaze everyone by having every new report they ask for done in 10 minutes.

* knowing the power of automated source translation tools, and how easy these things are to write IF you can munster the discipline of never touching generated code

All of these things will have people tell you it's impossible. And when they see simple code that demonstrates things like this, it's cheating (e.g. O(N) sorting is not fully general. That doesn't make it slower than O(N), and it's still applicable to a lot of situations) ...

[1] http://graphics.stanford.edu/~seander/bithacks.html

[dteoh]

> shuffling a deck of cards in O(1)

How? I'm aware of Knuth shuffle which is O(n) but I can't find anything about constant time shuffling.

[waps]

You use the algebraic property that xy mod n will generate a shuffle of Zn if y and n are relatively prime (don't share any divisors). So if you then redefine "element a" to not refer to the index of the original array, but to ay mod n, and you've got your shuffle. You pick y randomly, and in order to make y and n relatively prime, you simply change n to be a prime number.

None of this requires you to actually go through the list. You'd have to modify this to support lists of non-prime lengths, but this is the basic idea :

  import random
  lst = [1,2,3,4,5]

  class newlist:
      def __init__(self, lst):
          self.lst = lst # assuming lst has a prime length.
          self.y = 0
          while self.y % len(lst) == 0:
              self.y = random.randint(1, 999999)

      def __getitem__(self, index):
          nidx = (index * self.y) % len(lst)
          return self.lst[nidx]
      
  # Start shuffling
  nl = newlist(lst)
  # End shuffling ... algorithm done.

  for i in range(len(lst)):
          print i, nl[i]

[allard]

why isn't it Stanford's manual?

[waps]

Heh. Whoops. I got the link from MIT Opencourseware originally.