<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Phone Digits
Given a phone number create a list of all the possible words that you can make given a dictionary from numbers to letters. 
In python there is a itertools.permutations('abc')
that would print all permutations given some input.
```python
import itertools
itertools.permutations('abc')
[i for i in itertools.permutations('abc')]
output permutations
```
Step1:  Print Longest Common Subsequence
This is a good problem for working out variations where you count contiguous subsequence versus non continuous 
The move with longest common subsequence is to start from the back of the strings and see if the letters are the same. Then increment with a dynamic programming approach where
Step2:  Time Travelling dictionary
Design a time traveling dictionary, has a get and put function where the get function takes a time and returns the corresponding value at the time.
Step3:  Alien Dictionary
Given a sorted dictionary of an alien language, find order of characters
```python
Input
Step4:  Binary Search
<ASSISTANT_TASK:>
Python Code:
letters_map = {'2':'ABC', '3':'DEF', '4':'GHI', '5':'JKL', 
               '6':'MNO', '7':'PQRS', '8':'TUV', '9':'WXYZ'}
def printWords(number, ):
    #number is phone number 
def printWordsUtil(numb, curr_digit, output, n):
    
    if curr_digit == n:
        print('%s ' % output)
        return 
    
    for i in range(len(letters_map[numb[curr_digit]])):
        output[curr_digit] = letters_map[number[curr_digit]][i]
        printWordsUtil(numb, curr_digit+1, output, n)
        if numb[curr_digit] == 0 or numb[curr_digit] == 1:
            return
        
      
def gen_phone(digits):
    results = []
    lookup = {
        '0': ' ',
        '1': ' ',
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
    }
    
    def decode_next(s, i):
        if i == len(digits):
            results.append(s)
            return
        
        for c in lookup[digits[i]]:
            decode_next(s + c, i + 1)
            
    decode_next('', 0)
    return results
Explanation: Phone Digits
Given a phone number create a list of all the possible words that you can make given a dictionary from numbers to letters. 
In python there is a itertools.permutations('abc')
that would print all permutations given some input.
```python
import itertools
itertools.permutations('abc')
[i for i in itertools.permutations('abc')]
output permutations
```
End of explanation
# Dynamic programming implementation of LCS problem
 
# Returns length of LCS for X[0..m-1], Y[0..n-1] 
def lcs(X, Y, m, n):
    L = [[0 for x in xrange(n+1)] for x in xrange(m+1)]
 
    # Following steps build L[m+1][n+1] in bottom up fashion. Note
    # that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] 
    for i in xrange(m+1):
        for j in xrange(n+1):
            if i == 0 or j == 0:
                L[i][j] = 0
            elif X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
 
    # Following code is used to print LCS
    index = L[m][n]
 
    # Create a character array to store the lcs string
    lcs = [""] * (index+1)
    lcs[index] = "\0"
 
    # Start from the right-most-bottom-most corner and
    # one by one store characters in lcs[]
    i = m
    j = n
    while i > 0 and j > 0:
 
        # If current character in X[] and Y are same, then
        # current character is part of LCS
        if X[i-1] == Y[j-1]:
            lcs[index-1] = X[i-1]
            i-=1
            j-=1
            index-=1
 
        # If not same, then find the larger of two and
        # go in the direction of larger value
        elif L[i-1][j] > L[i][j-1]:
            i-=1
        else:
            j-=1
 
    print "LCS of " + X + " and " + Y + " is " + "".join(lcs) 
 
# Driver program
X = "AGGTAB"
Y = "GXTXAYB"
m = len(X)
n = len(Y)
lcs(X, Y, m, n)
 
passed in a list of dictionaries
also passed a character
passed single characted to int
if a character does not exist in the dict
then the defualt value it zero 
find the highest possisble value for a character
in the dicts
now design it to take an abatrary operator and reutrn 
the highest value based on the operator
and then have it return ascending and descending order
Explanation: Print Longest Common Subsequence
This is a good problem for working out variations where you count contiguous subsequence versus non continuous 
The move with longest common subsequence is to start from the back of the strings and see if the letters are the same. Then increment with a dynamic programming approach where
End of explanation
import time
import math
class TimeTravelDict:
    def __init__(self):
        self.dict = {}
    
    def get(self, key, time):
        if not self.dict[key]:
            return -1
        most_recent, value = math.inf, None
        for a, b in self.dict[key]:
            if b < time:
                if (time - b) < most_recent:
                    most_recent = b
                    value = a
        
        if value == None:
            return -1
        else:
            return value
        
    def put(self, key, value):
        if not key in self.dict:
            self.dict[key] = [(value, time.time())]
        self.dict[key].append((value, time.time()))
        print(self.dict[key])
               
tt = TimeTravelDict()
tt.put('a', 11)
tt.put('a', 12)
tt.put('a', 13)
tt.put('a', 14)
tt.get('a', 1513571590.2447577)
Explanation: Time Travelling dictionary
Design a time traveling dictionary, has a get and put function where the get function takes a time and returns the corresponding value at the time.
End of explanation
#[2::][1::2]
import collections
words = ["baa", "", "abcd", "abca", "cab", "cad"]
def alienOrder(words):
    pre, suc = collections.defaultdict(set), collections.defaultdict(set)
    for pair in zip(words, words[1:]):
        print(pair)
        for a, b in zip(*pair):
            if a != b:
                suc[a].add(b)
                pre[b].add(a)
                break
    print('succ %s' % suc)
    print('pred %s' % pre)
    chars = set(''.join(words))
    print('chars %s' % chars)
    print(set(pre))
    free = chars - set(pre)
    print('free %s' % free)
    order = ''
    while free:
        a = free.pop()
        order += a
        for b in suc[a]:
            pre[b].discard(a)
            if not pre[b]:
                free.add(b)
    
    if set(order) == chars:
        return order 
    else:
        False
#     return order * (set(order) == chars)
    
alienOrder(words)
Explanation: Alien Dictionary
Given a sorted dictionary of an alien language, find order of characters
```python
Input:  words[] = {"baa", "abcd", "abca", "cab", "cad"}
Output: Order of characters is 'b', 'd', 'a', 'c'
Note that words are sorted and in the given language "baa" 
comes before "abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.
Input:  words[] = {"caa", "aaa", "aab"}
Output: Order of characters is 'c', 'a', 'b'
```
The idea is to create a graph of characters a then find topological sorting of the graph. 
1. Create a graph g with number of vertices equal to the size of alphabet in the given language. For example, if the alphabet size is 5, then there can be 5 characters in words. Initially there are no edges in graph. 
2. DO the following for every pair of adjacent words in given sorted array. 
    1. Let the current pair of words be word1 and word2. One by one compare characters of both words and find the mismatching characters. 
    2. Create an edge in g from mismatching character of word1 to that of word2.
3. Print topological sorting of the above created graph.
End of explanation
def binarySearch(alist, value):
    mini = 0
    maxi = len(alist)
    
    while mini <= maxi:
        print('here')
        pivot = (maxi - mini) // 2
        current_value = alist[pivot]
        
        if current_value < value:
            mini = pivot + 1
        elif current_value > value:
            maxi = pivot -1
        else:
            return pivot 
    
    return pivot or -1
          
    
    
test1 = [0, 5, 10 , 23, 46, 49, 78]
test2 = [0, 5, 10]
test3 = [0]
print(binarySearch(test1, 49))
print(binarySearch(test2, 10))
binarySearch(test3, 90)
Explanation: Binary Search
End of explanation
<END_TASK>