In this ProgrammingPraxis challenge we have to build a simple Caesar Cipher with a special property, called rot13 :
ROT13 (“rotate by 13 places“, sometimes hyphenated ROT-13) is a simple substitution cipher used in online forums as a means of hiding spoilers, punchlines, puzzle solutions, and offensive materials from the casual glance. ROT13 has been described as the “Usenet equivalent of a magazine printing the answer to a quiz upside down”.ROT13 is an example of the Caesar cipher, developed in ancient Rome. (Wikipedia)
Applying ROT13 to a piece of text merely requires examining its alphabetic characters and replacing each one by the letter 13 places further along in the alphabet, wrapping back to the beginning if necessary. A becomes N, B becomes O, and so on up to M, which becomes Z, then the sequence continues at the beginning of the alphabet: N becomes A, O becomes B, and so on to Z, which becomes M. Only those letters which occur in the English alphabet are affected; numbers, symbols, whitespace, and all other characters are left unchanged. Because there are 26 letters in the English alphabet and 26 = 2 × 13, the ROT13 function is its own inverse. (Wikipedia)
Write a function that takes a string and returns the ROT13 version of the string; you may assume that the character set is ascii. What is the meaning of “Cebtenzzvat Cenkvf vf sha!” .
The transition table for rot13:
Examples of transitions:
|Smoke on the water
||Fzbxr ba gur jngre
Initially I wanted to resolve the challenge in a functional programming language. Given the fact that my Haskell skills are very low, I’ve tried to write a functional approach in python . The results… lesser readability, fewer lines of code & fewer minutes:
from string import letters, lowercase, uppercase
llist = lambda let : [[let[x], let[(x + num) % numlet]] for x in range(numlet)]
shifted = dict(llist(uppercase) + llist(lowercase))
return "".join([shifted[s] if s in letters else s for s in text])
if __name__ == '__main__':
print get_shifted("Cebtenzzvat Cenkvf vf sha!")
And the output:
If you’ve tried to write your own calculator (something in the style of gcalctool) you’ve probably had to build a simple converter for your mathematical expressions from infix notation to RPN (Reverse Polish Notation).
Inspired by this classical SPOJ challenge I wanted to write my own simplified version of an expression converter. If this topic is new for you, or you need to refresh your memory please don’t skip the following paragraph.
Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on (e.g. 2 + 5). Unfortunately what seems natural for us, is not as simple to parse by computers as prefix or RPN notations.
RPN also known as the Reverse Polish Notation is mathematical notation wherein every operator (eg. + – * %) follows all of its operands. Examples:
||Reverse Polish Notation
|A + B
||A B +
|A ^ 2 + 2 * A * B + B ^ 2
||A 2 ^ 2 A * B * + B 2 ^ +
|( ( 1 + 2 ) / 3 ) ^ 4
||1 2 + 3 / 4 ^
|( 1 + 2 ) * ( 3 / 4 ) ^ ( 5 + 6 )
||1 2 + 3 4 / 5 6 + ^ *
In order to parse and convert a given infix mathematical expression to RPN we will use the shunting-yard algorithm . Just like the evaluation of RPN, the algorithm is stack-based . For the conversion we will use two buffers (one for input, and one for output). Additionally we will use a stack for operators that haven’t been yet added to the output.
|A simplified version of the Shunting-yard algorithm (complete version)
- For all the input tokens [S1]:
- Read the next token [S2];
- If token is an operator (x) [S3]:
- While there is an operator (y) at the top of the operators stack and either (x) is
left-associative and its precedence is less or equal to that of (y), or (x) is right-associative
and its precedence is less than (y) [S4]:
- Pop (y) from the stack [S5];
- Add (y) output buffer [S6];
- Push (x) on the stack [S7];
- Else If token is left parenthesis, then push it on the stack [S8];
- Else If token is a right parenthesis [S9]:
- Until the top token (from the stack) is left parenthesis, pop from the stack to the output buffer [S10];
- Also pop the left parenthesis but don’t include it in the output buffer [S11];
- Else add token to output buffer [S12].
- While there are still operator tokens in the stack, pop them to output [S13]
Note: [SN] Relate with code.
I) Java Implementation
The following implementation of the shunting-yard algorithm does not impose any validations. The input should be a valid mathematical expression or else the program may end abruptly or Continue reading
NOTE: After performing a blog import WordPress messed my code . If you see any problems please let me know .
In order to prove that generic programming (the style of computer programming in which algorithms are written in terms of to-be-specified-later types that are theninstantiated when needed for specific types provided as parameters) can be achieved in C, let’s write the implementation of a generic Stack data structure . We will follow two possible approaches:
- Hacking with the #preprocessor;
- Using the flexibility of the void pointer (void*);
You can always try both of the approaches and see which one is more suitable for your particular case . Also note that there are already generic C libraries available (see GLib ).
1. Hacking with the preprocessor
To understand the magic (not really) behind this approach you will need to be familiar with C macros and the associated concepts: function-like macros, macro arguments, stringification and concatenation. You can find a very nice tutorial on macros here. If you already know your stuff, you can skip the following paragraphs (or you can read them to refresh your memory / find errors and correct me :P). Continue reading