-
Notifications
You must be signed in to change notification settings - Fork 0
/
submission.py
123 lines (107 loc) · 4.74 KB
/
submission.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import collections
import math
import itertools
############################################################
# Problem 3a
from collections import defaultdict
def findAlphabeticallyLastWord(text):
"""
Given a string |text|, return the word in |text| that comes last
alphabetically (that is, the word that would appear last in a dictionary).
A word is defined by a maximal sequence of characters without whitespaces.
You might find max() and list comprehensions handy here.
"""
# BEGIN_YOUR_CODE (our solution is 1 line of code, but don't worry if you deviate from this)
return max(text.split(), key=lambda x: x)
# END_YOUR_CODE
############################################################
# Problem 3b
def euclideanDistance(loc1, loc2):
"""
Return the Euclidean distance between two locations, where the locations
are pairs of numbers (e.g., (3, 5)).
"""
# BEGIN_YOUR_CODE (our solution is 1 line of code, but don't worry if you deviate from this)
return math.sqrt((loc1[0] - loc2[0]) ** 2 + (loc1[1] - loc2[1]) ** 2)
############################################################
# Problem 3c
def mutateSentences(sentence):
"""
Given a sentence (sequence of words), return a list of all "similar"
sentences.
We define a sentence to be similar to the original sentence if
- it as the same number of words, and
- each pair of adjacent words in the new sentence also occurs in the original sentence
(the words within each pair should appear in the same order in the output sentence
as they did in the orignal sentence.)
Notes:
- The order of the sentences you output doesn't matter.
- You must not output duplicates.
- Your generated sentence can use a word in the original sentence more than
once.
Example:
- Input: 'the cat and the mouse'
- Output: ['and the cat and the', 'the cat and the mouse', 'the cat and the cat', 'cat and the cat and']
(reordered versions of this list are allowed)
"""
# BEGIN_YOUR_CODE (our solution is 20 lines of code, but don't worry if you deviate from this)
sentence = sentence.split()
word_bigrams = [(sentence[i], sentence[i+1]) for i in range(len(sentence) - 1)]
word_to_next_words = dict()
for q, k in itertools.groupby(sorted(word_bigrams), key=lambda x: x[0]):
word_to_next_words[q] = set(kk[1] for kk in k)
def generate(seq):
seqs = []
if len(seq) == len(sentence):
return [seq, ]
for possible_next_word in word_to_next_words.get(seq[-1], []):
seqs += generate(seq + [possible_next_word,])
return seqs
ans = []
for k, _ in word_to_next_words.items():
ans += generate([k, ])
return [' '.join(sent) for sent in ans]
############################################################
# Problem 3d
def sparseVectorDotProduct(vec1, vec2):
"""
Given two sparse vectors |v1| and |v2|, each represented as collection.defaultdict(float), return
their dot product.
You might find it useful to use sum() and a list comprehension.
This function will be useful later for linear classifiers.
"""
return sum(v1 * vec2[k] for k, v1 in vec1.items())
############################################################
# Problem 3e
def incrementSparseVector(vec1, scale, vec2):
"""
Given two sparse vectors |v1| and |v2|, perform v1 += scale * v2.
This function will be useful later for linear classifiers.
"""
# BEGIN_YOUR_CODE (our solution is 2 lines of code, but don't worry if you deviate from this)
all_keys = set(list(vec1.keys()) + list(vec2.keys()))
for key in all_keys:
vec1[key] += scale * vec2[key]
# Problem 3f
def findSingletonWords(text):
"""
Splits the string |text| by whitespace and returns the set of words that
occur exactly once.
You might find it useful to use collections.defaultdict(int).
"""
# BEGIN_YOUR_CODE (our solution is 4 lines of code, but don't worry if you deviate from this)
return set([word for word, count in collections.Counter(text.split()).items() if count == 1])
############################################################
# Problem 3g
def computeLongestPalindromeLength(text):
"""
A palindrome is a string that is equal to its reverse (e.g., 'ana').
Compute the length of the longest palindrome that can be obtained by deleting
letters from |text|.
For example: the longest palindrome in 'animal' is 'ama'.
Your algorithm should run in O(len(text)^2) time.
You should first define a recurrence before you start coding.
"""
# BEGIN_YOUR_CODE (our solution is 19 lines of code, but don't worry if you deviate from this)
raise Exception("Not implemented yet")
# END_YOUR_CODE