psyduck's memo
Recursion to Loop

Sometimes, we need to convert recursive functions into loop for efficiency consideration, or stack size constrain. Converting tail recursion into iteration is trivial. The method we discuss in this post is a general method to convert any recursive functions into iterative ones. The idea is to simulate stack behavior: we store frame record as a structure into a simulated stack when calling a function, and restore the top record in stack when function returns. The record should contain 2 part of data:

GDB tips

gdb is quite a useful tool. Despite it’s text interface, it can do more than GUI debuggers. I am still learning it, and this post is used as a memo.

extern "C"

You may have seen following C++ code somewhere.

Python tips
• When write to global variable in function, declare the variable as global ... at the first line of function definition.
• Conditions can be chained(!!). 1 < a < 3 checks that a is both less than 3 and more than 1.
• If you want to execute python code without starting a new console(in windows), change python file extension’s name to “pyw”. This is useful for GUI applications.
• __import__ function can import modules dynamically.
• multi parameter function:
• def f(*a): all parameters in list a
• def f(**a): all parameters in dict a (should be called in this way: f(a=1,b=2))
• When using python’s iterative shell, _ variable stores return value of last command.
“Regular Expression” matches all non-prime numbers

I found a “regular expression” which matches all strings consists of non-prime number of 1s. ^1?$|^(111*)\1+$

Nasty C code

Today, my friend Yuan Yuan showed me a piece of C code, which gives different result under different optimization option. I was greatly surprised that such code exists. His original code is complicated. I minimized the code in order to demonstrate the problem.

Skip List in C++

I implemented a skip list in C++(following pseudo code in this paper). The skip list itself provided simple set interface: contains, insert, remove I also implemented a map interface using skip list. I compared performance of Skip List with STL set and map. STL’s algorithm is about twice faster than skip list. Detail of implementation and experiment data comes later…

Vim Tips
• non-greedy reg-exp search: simply replace with {-}. {-} is the non-greedy version of .
• match all characters including newline: use _. instead of .
• substitution in multiple files:

unicode string and encoding in python

Unicode is a character set. It defines mapping from character to numbers(code points). Encodings like utf-8, utf-16 are trying to encode code points.

Maze exploring game in vim script

Lots of beginners do not like to use vim’s h,j,k,l key to move concur, so I made this game, hopefully can help beginners get used to h,j,k and l. This is a maze exploring game. A 15*15 maze is randomly generated, and user(‘@’) need to go to target position(‘X’). Only h,j,k,l are allowed for controlling. Type ‘q’ to quit the game. Maximize the window before starting the game to get better view. Type :HJKL to start a new game. Want more challenge, try konami code(kkjjhlhlba) script available here