1 # -*- coding: utf-8 -*-
   2 """
   3 Created on Wed Sep 21 11:52:34 2016
   4 
   5 @author: WELG
   6 """
   7 
   8 #####################################
   9 # EXAMPLE:  Towers of Hanoi
  10 #####################################
  11 
  12 def printMove(fr, to):
  13     print('move from ' + str(fr) + ' to ' + str(to))
  14 
  15 def Towers(n, fr, to, spare):
  16     if n == 1:
  17         printMove(fr, to)
  18     else:
  19         Towers(n-1, fr, spare, to)
  20         Towers(1, fr, to, spare)
  21         Towers(n-1, spare, to, fr)
  22 
  23 #print(Towers(4, 'P1', 'P2', 'P3'))
  24 
  25 #####################################
  26 # EXAMPLE:  fibonacci
  27 #####################################
  28 
  29 def fib(x):
  30     """assumes x an int >= 0
  31        returns Fibonacci of x"""
  32     if x == 0 or x == 1:
  33         return 1
  34     else:
  35         return fib(x-1) + fib(x-2)
  36         
  37 #####################################
  38 # EXAMPLE:  testing for palindromes
  39 #####################################
  40         
  41 def isPalindrome(s):
  42 
  43     def toChars(s):
  44         s = s.lower()
  45         ans = ''
  46         for c in s:
  47             if c in 'abcdefghijklmnopqrstuvwxyz':
  48                 ans = ans + c
  49         return ans
  50 
  51     def isPal(s):
  52         if len(s) <= 1:
  53             return True
  54         else:
  55             return s[0] == s[-1] and isPal(s[1:-1])
  56 
  57     return isPal(toChars(s))
  58 
  59 #print(isPalindrome('eve'))
  60 #
  61 #print(isPalindrome('Able was I, ere I saw Elba'))
  62 #
  63 #print(isPalindrome('Is this a palindrome'))
  64 
  65 #####################################
  66 # EXAMPLE: using dictionaries
  67 #          counting frequencies of words in song lyrics
  68 #####################################
  69 
  70 def lyrics_to_frequencies(lyrics):
  71     myDict = {}
  72     for word in lyrics:
  73         if word in myDict:
  74             myDict[word] += 1
  75         else:
  76             myDict[word] = 1
  77     return myDict
  78     
  79     
  80 she_loves_you = ['she', 'loves', 'you', 'yeah', 'yeah', 
  81 'yeah','she', 'loves', 'you', 'yeah', 'yeah', 'yeah',
  82 'she', 'loves', 'you', 'yeah', 'yeah', 'yeah',
  83 
  84 'you', 'think', "you've", 'lost', 'your', 'love',
  85 'well', 'i', 'saw', 'her', 'yesterday-yi-yay',
  86 "it's", 'you', "she's", 'thinking', 'of',
  87 'and', 'she', 'told', 'me', 'what', 'to', 'say-yi-yay',
  88 
  89 'she', 'says', 'she', 'loves', 'you',
  90 'and', 'you', 'know', 'that', "can't", 'be', 'bad',
  91 'yes', 'she', 'loves', 'you',
  92 'and', 'you', 'know', 'you', 'should', 'be', 'glad',
  93 
  94 'she', 'said', 'you', 'hurt', 'her', 'so',
  95 'she', 'almost', 'lost', 'her', 'mind',
  96 'and', 'now', 'she', 'says', 'she', 'knows',
  97 "you're", 'not', 'the', 'hurting', 'kind',
  98 
  99 'she', 'says', 'she', 'loves', 'you',
 100 'and', 'you', 'know', 'that', "can't", 'be', 'bad',
 101 'yes', 'she', 'loves', 'you',
 102 'and', 'you', 'know', 'you', 'should', 'be', 'glad',
 103 
 104 'oo', 'she', 'loves', 'you', 'yeah', 'yeah', 'yeah',
 105 'she', 'loves', 'you', 'yeah', 'yeah', 'yeah',
 106 'with', 'a', 'love', 'like', 'that',
 107 'you', 'know', 'you', 'should', 'be', 'glad',
 108 
 109 'you', 'know', "it's", 'up', 'to', 'you',
 110 'i', 'think', "it's", 'only', 'fair',
 111 'pride', 'can', 'hurt', 'you', 'too',
 112 'pologize', 'to', 'her',
 113 
 114 'Because', 'she', 'loves', 'you',
 115 'and', 'you', 'know', 'that', "can't", 'be', 'bad',
 116 'Yes', 'she', 'loves', 'you',
 117 'and', 'you', 'know', 'you', 'should', 'be', 'glad',
 118 
 119 'oo', 'she', 'loves', 'you', 'yeah', 'yeah', 'yeah',
 120 'she', 'loves', 'you', 'yeah', 'yeah', 'yeah',
 121 'with', 'a', 'love', 'like', 'that',
 122 'you', 'know', 'you', 'should', 'be', 'glad',
 123 'with', 'a', 'love', 'like', 'that',
 124 'you', 'know', 'you', 'should', 'be', 'glad',
 125 'with', 'a', 'love', 'like', 'that',
 126 'you', 'know', 'you', 'should', 'be', 'glad',
 127 'yeah', 'yeah', 'yeah',
 128 'yeah', 'yeah', 'yeah', 'yeah'
 129 ]
 130 
 131 beatles = lyrics_to_frequencies(she_loves_you)
 132 
 133 
 134 def most_common_words(freqs):
 135     values = freqs.values()
 136     best = max(freqs.values())
 137     words = []
 138     for k in freqs:
 139         if freqs[k] == best:
 140             words.append(k)
 141     return (words, best)
 142     
 143 def words_often(freqs, minTimes):
 144     result = []
 145     done = False
 146     while not done:
 147         temp = most_common_words(freqs)
 148         if temp[1] >= minTimes:
 149             result.append(temp)
 150             for w in temp[0]:
 151                 del(freqs[w])  #remove word from dict
 152         else:
 153             done = True
 154     return result
 155     
 156 #print(words_often(beatles, 5))
 157 
 158 #####################################
 159 # EXAMPLE: comparing fibonacci using memoization
 160 #####################################
 161 
 162 
 163 def fib(n):
 164     if n == 1:
 165         return 1
 166     elif n == 2:
 167         return 2
 168     else:
 169         return fib(n-1) + fib(n-2)
 170 
 171 
 172 def fib_efficient(n, d):
 173     if n in d:
 174         return d[n]
 175     else:
 176         ans = fib_efficient(n-1, d)+fib_efficient(n-2, d)
 177         d[n] = ans
 178         return ans
 179         
 180 d = {1:1, 2:2}
 181 
 182 argToUse = 34
 183 #print("")
 184 #print('using fib')
 185 #print(fib(argToUse))
 186 #print("")
 187 #print('using fib_efficient')
 188 #print(fib_efficient(argToUse, d))