Answer To: Guide to Project for Supervisors ITECH1400 Fundamentals of Programming CRICOS Provider No. 00103D...
Neha answered on Aug 29 2021
43796-fxfpd5gj/43796/1.Sonnet.py
# Count the occurrences of each letter in the text
with open("sonnets.txt") as f:
freqs = {}
for line in f:
for char in line:
if char in freqs:
freqs[char] += 1
else:
freqs[char] = 1
print ("The frequency of each letter in the poem is:")
print(freqs)
#to get one letter word, two letter word and so on in the file
def word_count(fname):
with open(fname) as f:
data = f.read()
return {x:[len([c for c in w ]) for w in data.split()].count(x) for x in [len([c for c in w ]) for w in data.split()] }
print("Number of letters and thier corresponding number of words : ")
print(word_count("sonnets.txt"))
#to get total number of words available in the file
with open("sonnets.txt") as f:
data = f.read().splitlines()
f.close()
number_of_words=len(data)
print("Total number of words: " + str(number_of_words))
43796-fxfpd5gj/43796/2nd_question_word_ladder.py
#In this code we have to reach to the opposite of
#first word by using 1 word difference.
from __future__ import division
from collections import defaultdict
#this method is to find whether two words have only 1 letter difference
def one_letter_diff(w1, w2):
diff = 0
if len(w1) != len(w2): return False
for i in range(len(w1)):
if w1[i] != w2[i]: diff += 1
if diff > 1: return False
return diff == 1
# To solve this problem we have to build a graph. We need to
#find the shortest path using Dijkstra's algorithm.
#and then find whether it hae only one letter difference
def word_ladder(start, end, words):
links = defaultdict(list)
allwords = list(set(words) | set([start,end]))
n = len(allwords)
for i in range(n):
for j in range(i+1,n):
if one_letter_diff(allwords[i], allwords[j]):
links[allwords[i]].append(allwords[j])
links[allwords[j]].append(allwords[i])
print ('\n'.join([k+': '+str(v) for k,v in links.items()]))
# Dijkstra's algorithm
queue = set(allwords)
dist = dict((w, float('inf')) for w in allwords)
dist[start] = 0
prev = {}
while queue:
word = min(queue, key=lambda x:dist[x])
queue.remove(word)
if dist[word] == float('inf'): break
for w in links[word]:
alt_dist = dist[word] + 1
if alt_dist < dist[w]:
dist[w] = alt_dist
prev[w] = word
#distance between root and the word using vertex of trees
print (dist)
return dist[end]
### Find all transformation, but not necessarily shortest
def word_ladder_II1(start, end, words):
links = defaultdict(list)
allwords = list(set(words) | set([start,end]))
n = len(allwords)
for i in range(n):
for j in range(i+1,n):
if one_letter_diff(allwords[i], allwords[j]):
links[allwords[i]].append(allwords[j])
links[allwords[j]].append(allwords[i])
#print '\n'.join([k+': '+str(v) for k,v in links.items()])
for path in BFS(start, end, links, set()):
print [start] + path
def BFS(start, end, links, visited):
if start == end:
yield []
else:
for next in links[start]:
if next in visited: continue
for p in BFS(next, end, links, visited | set([next])):
yield [next] + p
# tTo find all the shortest transformation available
def word_ladder_II2(start, end, words):
links = defaultdict(list)
allwords = list(set(words) | set([start,end]))
n = len(allwords)
for i in range(n):
for j in range(i+1,n):
if one_letter_diff(allwords[i], allwords[j]):
links[allwords[i]].append(allwords[j])
links[allwords[j]].append(allwords[i])
dist = dict((w,float('inf')) for w in allwords)
dist[start] = 0
prev = dict((w,[]) for w in allwords)
queue = set(allwords)
while queue:
word = min(queue, key=lambda x:dist[x])
queue.remove(word)
for w in links[word]:
alt_dist = dist[word]+1
if alt_dist < dist[w]:
dist[w] = alt_dist
prev[w] = [word]
elif alt_dist == dist[w]: # key!
prev[w].append(word)
paths = [path+[end] for path in recover_paths(end, prev)]
print (paths[0])
return paths
def recover_paths(end, prev):
if len(prev[end]) == 0: yield []
else:
for word in prev[end]:
for prev_path in recover_paths(word, prev):
yield prev_path + [word]
#main function to call the method
if __name__ == '__main__':
with open("list.txt") as f:
data = f.read().splitlines()
f.close()
word_ladder_II2("flour", "bread", data)
word_ladder_II2("chaos", "peace", data)
word_ladder_II2("tears", "smile", data)
word_ladder_II2("sleep", "dream", data)
word_ladder_II2("river", "shore", data)
43796-fxfpd5gj/43796/Dobblets.docx
To build ladder of words with 1 letter difference
Open file
Read file
N=Len(all words)
For i in n
For j in range(i+1,n)
Find one letter difference
Len of word1 = len of word 2
For each character in words
If word1 and word 2 = difference(1)
Return true
Set all words in a queue
dist = dict((w, float('inf')) for w in allwords)
while queue:
word = min(queue, key=lambda x:dist[x])
queue.remove(word)
if dist[word] == float('inf'): break
for w in links[word]:
alt_dist = dist[word] + 1
if alt_dist < dist[w]:
dist[w] = alt_dist
prev[w] = word
print word
return
for word in previous
for previous path
yield previous path +...