I was solving one of the puzzles in Project Euler, and the problem statement was related to encryption/decryption. There was a encrypted text file containing only numbers. Encryption technique used was of doing XOR with a 3 letter key. In order to find the three letter key, one had to do bruteforce. So, following is the code which can generate all possible combinations of a 3 letter word containing (0-9a-z). Possible combinations would be 36^3 = 46656.

Python rocked again :)

#!/usr/bin/python # List of all the possible characters vals=list("0123456789abcdefghijklmnopqrstuvwxyz") # Number of digits where the above characters can fit into. init="000" # Total number of permutations : # Formula: (total_possible_chars)^(lengh_of_numbers) # In above case: (36)^3 = 46656 class HashTable: def __init__(self): self.list = {}; def get(self, key): return self.list[key] def set(self,key,value): self.list.setdefault(key,[]).append(value); htable = HashTable(); htable.set(init, 0); # Rotation logic. Take 1st char in a temporary variable, # and copy the whole string starting from index 1 to 0th # location. Then copy the char stored in temp variable to # the last location. Once we get the string, store it in # dictionary (hash) if not stored already def rotate_left(string): global htable ts = string for i in range(1, len(string)): tchar = list(string)[0]; string = string[1:] sl = list(string) sl.append(tchar) string = "".join(sl) if (string == ts): break; if (htable.list.has_key(string) == False): htable.set(string, 0); # List generation logic: Idea is to initalize the list with # all 0s. Then insert one char (out of all posible chars) at # a time to the last position. Something like: # 001 # 002 # 003 # ... # 009 # Strings generated from this function will be passed to another # function, which will rotate the whole string left by one and # insert the new char (again out of all possible chars) at the end. # Something like: # 010 # 011 # 012 # 013 # ... # 019 # Copy all such combination into a dictionary (hash) table. Once all # the values are stored in hash, just do rotate_left() on all the values. # Again, store all these values into hash, and sort the hash() to print # them in order. tl = [init] def generate_list(tl): global htable for t in tl: for i in vals: tstr = insert_char_at_last(t, i); if (htable.list.has_key(tstr) == False): htable.set(tstr, 0); tl.append(tstr); def insert_char_at_last(string, tchar): string = string[1:] sl = list(string) sl.append(tchar) string = "".join(sl) return string generate_list(tl) # Generate all the combinations of the word by rotating # each character left (by one position). for keys in htable.list.keys(): rotate_left(keys) cnt = 0; # Display keys in sorted order tkeys = htable.list.keys for keys in sorted(tkeys()): cnt = cnt + 1; print cnt, keys

Have fun!!

Advertisements