A document from MCS 275 Spring 2021, instructor Emily Dumas. You can also get the notebook file.

Worksheet 9 Solutions

MCS 275 Spring 2021 - Emily Dumas

Solutions by Jennifer Vaccaro

Topics

The main topics of this worksheet are:

  • Tree traversals
  • Set and defaultdict
  • CSV and JSON

The main references for these topics are:

The most useful files from the sample code repository are:

Instructions

  • Problem 1 is handled differently than the others:
    • Tuesday discussion students: Problem 1 will be presented as an example at the start of discussion
    • Thursday discussion students: Please complete Problem 1 before discussion and bring your solution
  • For the other problems:
    • Work on these problems in discussion.

1. BST copier

Write a function bst_copy(T) that takes a BST object T (with integer keys) and returns a copy of it, created from scratch by instantiating a new BST object and inserting the keys from T.

In [3]:
# MCS 275 Worksheet 9 Problem 1
# Jennifer Vaccaro
# I wrote this solution in collaboration with the Tuesday discussion section (thanks!)

import bst
import binary

def copy_subtree(T, x):
    """If x != None, copies the key from x into a new node and adds it to a tree T. 
    Then recurse by copying the subtree descending from x's children."""
    if x == None:
        return
    # Create a new node with the same key as x. 
    new_x = binary.Node(x.key)
    # Inserting the new node into T assigns the parent/children
    T.insert(new_x)
    # Then copy the subtree from x.left and x.right
    copy_subtree(T,x.left)
    copy_subtree(T,x.right)


def bst_copy(T):
    """Returns a new tree with the same attributes/nodes as T"""
    # Create a new empty tree
    new_T = bst.BST()
    # Call the recursive helper function to copy each of the nodes
    copy_subtree(new_T, T.root)
    return new_T
In [4]:
import treeutil
import treevis

T = treeutil.random_bst(6)
T2 = bst_copy(T)
print("The original:")
treevis.treeprint(T)
print("The copy:")
treevis.treeprint(T2)
print("Are they the same object? (Expect False.)")
print(T==T2)  # Since we didn't define an __eq__ method, this will return False
              # unless T and T2 are different names for a single object
The original:
                      <7>                      

          <5>                     <12>         

                            <10>        <16>   

                                           <17>

The copy:
                      <7>                      

          <5>                     <12>         

                            <10>        <16>   

                                           <17>

Are they the same object? (Expect False.)
False

2. Accidentally quadratic

Here is a function that takes two strings and returns the set of characters that appear in both strings.

In [118]:
def common_chars(s1,s2):
    """Return a set of all characters that are present in both
    strings `s1` and `s2`."""
    common = set()
    for c1 in s1:
        if c1 in s2:
            common.add(c1)
    return common

The problem with this function is that it has an implicit nested for loop that performs len(s1)*len(s2) equality checks. The expression

c1 in s2

is equivalent to the return value of this function:

def c1_in_s2():
    for c2 in s2:
        if c1==c2:
            return True
    return False

In the worst case, this function performs len(s2) checks, and it runs for each character of s1. If s1 and s2 are each of length 50,000, then this becomes 2,500,000,000 equality checks.

However, most strings don't have that many distinct characters, so it would be faster to:

  • Find all of the distinct characters in s1 (and make a set out of them)
  • Find all of the distinct characters in s2 (and make a set out of them)
  • Check which characters lie in both of these sets

The time it takes to do this would be roughly proportional to len(s1) + len(s2) + n1*n2 where n1 is the number of distinct characters in s1 and n2 is the number of distinct characters in s2. In most cases n1 and n2 will be bounded by a fixed constant (like 26, if the strings only contain lower case letters of the alphabet), so the main contribution to the running time is proportional to the lengths of s1 and s2 individually, rather than their product.

Here is an alternative common_chars function that uses this strategy:

In [5]:
# MCS 275 Worksheet 9 Problem 3
# Jennifer Vaccaro
# I wrote this solution myself, in accordance with the syllabus

def common_chars(s1,s2):
    """Return a set of all characters that are present in both
    strings `s1` and `s2`."""
    # By first turning s1 and s2 into sets, we have fewer characters to compare.
    # Then we can return the intersection
    return set(s1) & set(s2)

# Another syntax option would be 'return set(s1).intersection(s2)'

It works. Here's a simple example:

In [6]:
common_chars("mathematics","computer science")
Out[6]:
{'c', 'e', 'i', 'm', 's', 't'}

Here is a timing study, showing it handles strings of length 50,000 with ease:

In [7]:
import random
import time

s1 = ''.join([ random.choice(["edfghijklmnopqrstuvwxyzzzzzzzzzzzzzzzz"]) for _ in range(50000) ])
s2 = ''.join([ random.choice(["abcedfghijklmnopqrstuvw"]) for _ in range(50000) ]) + 'z'

t_start = time.time()
both = common_chars(s1,s2)
t_end = time.time()

print("Common characters:")
print(both)
print("\nRunning time: {:.2f} seconds".format(t_end-t_start))
Common characters:
{'v', 'q', 'm', 'n', 'h', 'j', 'g', 'i', 't', 'l', 'k', 'p', 'd', 'r', 'e', 's', 'o', 'z', 'u', 'w', 'f'}

Running time: 0.05 seconds

3. Nobel prize winners data

Download the JSON file of data about Nobel laureates from

http://api.nobelprize.org/v1/laureate.json

Write a Python program that reads this file and uses defaultdict to make and print a histogram of the institutional affiliations that appear in each prize category (e.g. in chemistry, how many nobel laureates have their institutional affiliation as "University of California"? in peace, what institutional affiliation is listed for the largest number of laureates?)

Poking around in the JSON data to figure out where the relevant information is stored will be the first step. I suggest loading it into an object in the REPL and then exploring the list of keys, taking the value associated to one of those keys and listing its keys, etc..

In [5]:
# MCS 275 Worksheet 9 Problem 3
# Jennifer Vaccaro and Emily Dumas
"""Creates a histogram of the schools affiliated with the Nobel Prize in Chemistry"""

import json
from collections import defaultdict

# Create an empty defaultdict with default value zero
# (which is the value returned by function int)
hist = defaultdict(int)

# Open the file object. This syntax will automatically 
# close the file for you once the indentation block ends
with open("laureate.json","r") as f:
    data = json.load(f)
    # Iterate through the laureates
    for l in data["laureates"]:
        # Iterate through the prizes
        for p in l["prizes"]:
            if p["category"] != "chemistry":
                # Skip if the prize category is not chemistry
                continue 
            # Iterate through the affiliations
            for a in p["affiliations"]:
                # Skip if the affiliation is not a dictionary
                if not isinstance(a,dict):
                    continue
                # Add the school/institution name to the histogram.
                # Because we are using defaultdict, if we attempt to access
                # a key that doesn't exist, it will be created and given the
                # value zero.
                hist[a["name"]] += 1


# Now, hist maps institution names to prize counts in chemistry
# We could just print the whole thing, but we can get a list in descending order
# using dict.items() to get key-value pairs and then sorting by value.

print("#PRIZES   INSTITUTION")
for institution, count in sorted(hist.items(),key=lambda x:-x[1]):
    print("{:>7d}   {}".format(count,institution))
    
# the argument key=lambda x:-x[1] in the call to `sorted` means sort by
# second element of the tuple, in descending order.  The tuples are
# (institution,prize_count) so this means the most prizes appear first.
#PRIZES   INSTITUTION
     14   University of California
      8   MRC Laboratory of Molecular Biology
      6   Harvard University
      6   Howard Hughes Medical Institute
      5   Berlin University
      5   California Institute of Technology (Caltech)
      5   Stanford University
      4   University of Heidelberg
      4   Eidgenössische Technische Hochschule (Swiss Federal Institute of Technology)
      4   Rockefeller University
      3   Stockholm University
      3   Munich University
      3   Goettingen University
      3   University of Oxford
      3   University of Cambridge
      3   Columbia University
      3   Cornell University
      3   Yale University
      3   Technion - Israel Institute of Technology
      2   Sorbonne University
      2   University of Zurich
      2   Uppsala University
      2   I.G. Farbenindustrie A.G.
      2   Institut du Radium
      2   Rockefeller Institute for Medical Research
      2   Imperial College
      2   University of Sussex
      2   University of Texas
      2   Purdue University
      2   University of Southern California
      2   Massachusetts Institute of Technology (MIT)
      2   Rice University
      2   Northwestern University
      2   The Scripps Research Institute
      2   Stanford University School of Medicine
      1   University College
      1   Landwirtschaftliche Hochschule (Agricultural College)
      1   Victoria University
      1   Leipzig University
      1   Nancy University
      1   Toulouse University
      1   Kaiser-Wilhelm-Institut (now Fritz-Haber-Institut) für physikalische Chemie und Electrochemie
      1   Graz University
      1   London University
      1   Technische Hochschule (Institute of Technology)
      1   General Electric Company
      1   Kaiser-Wilhelm-Institut (now Max-Planck-Institut) für Physik
      1   Birmingham University
      1   Kaiser-Wilhelm-Institut (now Max-Planck Institut) für Medizinische Forschung
      1   Kaiser-Wilhelm-Institut (now Max-Planck-Institut) für Biochemie
      1   Kaiser-Wilhelm-Institut (now Max-Planck Institut) für Chemie
      1   University of Helsinki
      1   Kiel University
      1   Cologne University
      1   National Institute for Medical Research
      1   Rowett Research Institute
      1   University of Freiburg
      1   Staatliches Institut für makromolekulare Chemie (State Research Institute for Macromolecular Chemistry), Freiburg
      1   Institute for Chemical Physics of the Academy of Sciences of the USSR
      1   Lomonosov Moscow State University
      1   Polarographic Institute of the Czechoslovak Academy of Science
      1   Max-Planck-Institut für Kohlenforschung (Max-Planck-Institute for Carbon Research)
      1   Institute of Technology
      1   University of Oxford, Royal Society
      1   University of Chicago
      1   Max-Planck-Institut für Physikalische Chemie
      1   Institute of Physical Chemistry
      1   Royal Institution of Great Britain
      1   University of Oslo
      1   Institute for Biochemical Research
      1   National Research Council of Canada
      1   National Institutes of Health
      1   Technical University
      1   Université Libre de Bruxelles
      1   Glynn Research Laboratories
      1   Harvard University, Biological Laboratories
      1   Kyoto University
      1   The Medical Foundation of Buffalo
      1   US Naval Research Laboratory
      1   University of Toronto
      1   Université Louis Pasteur
      1   Collège de France
      1   Du Pont
      1   University of Texas Southwestern Medical Center at Dallas
      1   Max-Planck-Institut für Biochemie
      1   Max-Planck-Institut für Biophysik
      1   University of Colorado
      1   University of British Columbia
      1   Max-Planck-Institut für Chemie
      1   Aarhus University
      1   University of Pennsylvania
      1   University of Tsukuba
      1   Nagoya University
      1   Virginia Commonwealth University
      1   Shimadzu Corp.
      1   Johns Hopkins University School of Medicine
      1   Institut Français du Pétrole
      1   Fritz-Haber-Institut der Max-Planck-Gesellschaft
      1   Marine Biological Laboratory (MBL)
      1   Boston University Medical School
      1   Weizmann Institute of Science
      1   University of Delaware
      1   Hokkaido University
      1   Duke University Medical Center
      1   Université de Strasbourg
      1   Janelia Research Campus, Howard Hughes Medical Institute
      1   Max Planck Institute for Biophysical Chemistry
      1   German Cancer Research Center
      1   Francis Crick Institute
      1   Clare Hall Laboratory
      1   Duke University School of Medicine
      1   University of North Carolina
      1   University of Strasbourg
      1   University of Groningen
      1   University of Lausanne
      1   University of Missouri
      1   Binghamton University, State University of New York
      1   Asahi Kasei Corporation
      1   Meijo University
      1   Max Planck Unit for the Science of Pathogens

4. CSV merge

Write a program to merge any number of CSV files, so that each row in any of the input files becomes a row in the output file. All of the input CSV files will have header rows. If the CSV files have the same columns, this is of course easy. But you should also handle the general case, where some columns may exist in multiple files, and others may be unique to a single file. The output file should contain one column for each distinct column name that appears in any of the input files.

Arrange it so your program csvmerge.py accepts all the input filenames as command line arguments. The last command line argument is the name of the output file that should be created.

For example, you might use a command like

python3 csvmerge.py a.csv b.csv c.csv out.csv

with a.csv containing:

name,age,favorite
Melissa,52,vanilla
Jonah,24,strawberry

and b.csv containing:

name,major
Josefina,falconry
David,phrenology

and c.csv containing:

age,major
5,bubbles
11,chess

In which case the program should create out.csv containing:

name,age,favorite,major
Melissa,52,vanilla,
Jonah,24,strawberry,
Josefina,,,falconry
David,,,phrenology
,5,,bubbles
,11,,chess
In [ ]:
# MCS 275 Worksheet 9 Problem 4
# Jennifer Vaccaro and Emily Dumas
"""csvmerge reads a set of input csv and writes their combined 
data into a single output csv"""

import csv
import sys

# This code keeps me from accidentally emptying out this text file, 
# needs at least 2 command line args
if len(sys.argv) < 3:
    raise Exception("Usage: {} INPUTFILES OUTPUTFILE".format(sys.argv[0]))

# Iterate through the input files, adding the column names to a set
# At this point we don't look at any of the input data---only the
# header row.
columns = set()
for csv_fn in sys.argv[1:-1]:
    with open(csv_fn,newline="") as csv_file:
        reader = csv.DictReader(csv_file)
        for col in reader.fieldnames:
            columns.add(col)
            
# Note: because we use a set to store the column names, the columns
# may appear in a different order in the output file than they do in
# any input file.  If order were important, we'd need to use a data
# structure other than a set to store the column names.

# Now, open the output file, and write the data from each input file into the output file.
# Use the combined input fieldnames.  This is the second time each input file is opened.
out_fn = sys.argv[-1]
with open(out_fn,"w") as out_file:
    writer = csv.DictWriter(out_file, fieldnames=list(columns))  # ieldnames must be a list
    writer.writeheader()
    # Iterate through our input files again, and write each row of them to the output file.
    for csv_fn in sys.argv[1:-1]:
        with open(csv_fn,newline="") as csv_file:
            reader = csv.DictReader(csv_file)
            for row in reader:
                writer.writerow(row)  # row may not have all the keys that `writer` expects
                                      # but that's ok; DictWriter allows missing keys and
                                      # fills in an empty output field for them.

5. USPS facilities data conversion

Download and unzip this CSV file listing facilities (mostly post offices) owned by the USPS in the 50 states:

Take a look at the file to get a sense of how it is structured. (You may need to look back at it later to determine which column headings are relevant to the tasks below.)

Now, write a program that uses the csv module to read this file and process it into a hierarchy of summary data that is written to a JSON file (using the json module). The output should have the following hierarchy:

  • At the top level, there is one key for each 2-letter state abbreviation (e.g. "IL")
    • The value associated to a state abbreviation is an object whose keys are the names of postal districts that have facilities in that state (e.g. "Central Illinois")
      • The value associated to a postal district is an object whose keys and values are as follows:
        • key "total facilities" with value the number of facilities in that state and postal district
        • key "post offices" with value the number of facilities in that state and postal district that have facility type (column FDB Facility Type (All)) equal to Post Office.

For example, the output file might begin

{ "IL": { "Central Illinois": { "total facilities": 165, "post offices": 144 }, ...
In [20]:
# MCS 275 Worksheet 9 Problem 5
# Emily Dumas
"""Read CSV of USPS facilities and compile summary statistics
by state and district in JSON output file."""

import json
import csv
import collections

infn = "usps_facilities.csv"
outfn = "usps_facility_summary.json"

def district_summary_factory():
    """Default value for a district's summary data"""
    return { "total facilities":0, "post offices": 0 }

def state_summary_factory():
    """Default value for a state's summary data"""
    return collections.defaultdict(district_summary_factory)

summary = collections.defaultdict(state_summary_factory)

# After all of this setup, we now have an object for storing
# the summary data where we never need to create keys. A line
# like
#   summary["IL"]["Central Illinois"]["post offices"] += 1
# will create everything needed and increment the count.

with open(infn,newline="") as infile:
    rdr=csv.DictReader(infile)
    for facility in rdr:
        # Put key elements of the facility data
        # into conveniently named variables
        state = facility["ST"]
        district = facility["District"]
        is_po = facility["FDB Facility Type (All)"]=="Post Office"

        # Record what we want to know about this facility
        summary[state][district]["total facilities"] += 1
        if is_po:
            summary[state][district]["post offices"] += 1

with open(outfn,"w") as outfile:
    json.dump(summary,outfile)

The resulting output JSON file is very long; here's the part of it for Florida and Georgia (with extra whitespace and indenting added for readability):

...
  "FL": {
    "Suncoast": {
      "total facilities": 187,
      "post offices": 162
    },
    "Gulf Atlantic": {
      "total facilities": 104,
      "post offices": 80
    },
    "South Florida": {
      "total facilities": 102,
      "post offices": 90
    }
  },
  "GA": {
    "Atlanta": {
      "total facilities": 143,
      "post offices": 114
    },
    "Gulf Atlantic": {
      "total facilities": 104,
      "post offices": 86
    },
    "Tennessee": {
      "total facilities": 9,
      "post offices": 9
    }
  },
...

(There's no typo there; some of the post offices in Georgia are in a district that USPS calls "Tennessee". That district also contains all of the post offices in the state of Tennessee.)

6. Kafkaesque and Tolstoyesque

What words appear in both War and Peace by Leo Tolstoy and The Metamorphosis by Franz Kafka?

Answer this for the english translations of these novels available as UTF-8 plain text from Project Gutenberg:

(You should look at the files in a browser to see the format; there is a header and a footer, with the actual text in between.)

Counting words is tricky, and there are a lot of edge cases, so let's impose these rules:

  • A word means a maximal block of consecutive characters that are alphabetic
    • A character c is considered alphabetic if c.isalpha() returns True. The method isalpha of class str is documented here
  • Words are considered the same if they differ only in capitalization
  • Chapter headings and roman numerals count as words (to save you the trouble of devising code to recognize and exclude these)

These files contain accented characters and various exotic punctuation (e.g. proper start and end quotation marks, not just the symmetric ones on your keyboard). As a result, to find words and ignore punctuation it will be easiest to use a positive test (.isalpha decides what is a letter) instead of a negative one (e.g. a hard-coded list of punctuation characters to convert to spaces before splitting).

Having finished the last exercise of the worksheet, you can now wake from these troubled dreams to find yourself transformed into a more skilled programmer.

In [21]:
# MCS 275 Worksheet 9 Problem 6
# Jennifer Vaccaro and Emily Dumas
"""Finds the shared words between 'War and Peace' by Leo Tolstoy 
and 'Metamorphosis' by Franz Kafka"""

# Set the names of the text files
tolstoy_fn = "tolstoy.txt"
kafka_fn = "kafka.txt"

def lower_words(s):
    """Splits out a string s into lower case alphabet words by 
    converting all other characters to spaces then splitting"""
    new_s = ""
    for c in s:
        if c.isalpha():
            new_s += c.lower()
        else:
            new_s += " "
    return new_s.split()

def ebook_word_set(fobj):
    """Return a set containing the distinct words in a project
    Gutenberg ebook text file.  Only counts words between the
    start and end markers that these files include."""
    words = set()
    watching = False # Indicator whether we're in the main text yet.
    for line in f:
        if line.startswith("*** START OF THIS PROJECT GUTENBERG EBOOK"):
            watching = True # We hit the start marker, so start counting words
            continue        # on the *next* line.
        if not watching:
            continue
        if line.startswith("End of the Project Gutenberg EBook"):
            break # we hit the end marker.  stop.
        
        # We are between the start and end marker.
        # Add all words on this line to the set of words seen so far
        words.update(lower_words(line))
    return words
    

with open(tolstoy_fn,"r",encoding="utf8") as f:
    tolstoy_words = ebook_word_set(f)

with open(kafka_fn,"r",encoding="utf8") as f:
    kafka_words = ebook_word_set(f)

# The intersection of these sets is the set of shared words
shared_words = tolstoy_words & kafka_words
print("Total words in common:",len(shared_words))
lmax = max( [len(w) for w in shared_words] )
print("\nLongest shared word(s):")
print(",".join(sorted([w for w in shared_words if len(w)==lmax])))
print("\nAll shared words in alphabetical order:")
print(",".join(sorted(shared_words)))
Total words in common: 2300

Longest shared word(s):
incomprehensible

All shared words in alphabetical order:
a,abandoned,abandoning,ability,able,about,above,abruptly,absolutely,accept,acceptance,accumulated,accurately,accusations,accuse,accused,achieved,achievements,aching,acquired,across,act,action,actually,add,added,address,adjoining,admit,advantage,advice,advise,affairs,affection,afraid,after,afterwards,again,against,age,aggrieved,agitated,ago,agree,agreed,ah,ahead,aim,air,alarm,alarmed,alert,all,allow,allowed,almonds,almost,alone,along,already,also,although,altogether,always,am,amazed,amazement,among,amount,an,ancient,and,anew,anger,angle,angry,animal,anna,announcement,annoyed,another,answer,answered,answering,anticipation,anxiety,anxious,anxiously,any,anyone,anything,anyway,anywhere,apart,appeals,appear,appearance,appeared,apple,apples,appreciated,appreciation,approached,appropriate,approved,arc,arduous,are,area,aren,arm,armchair,arms,army,around,arrange,arranged,arrangement,arrive,arrived,as,aside,ask,asked,asleep,assailed,assistant,assuming,assure,astonished,at,ate,attack,attempted,attention,attentive,attract,attracted,attributed,austere,authority,available,avoid,awake,aware,away,awful,awkwardly,awoke,back,backs,backwards,bad,badly,balance,balls,banging,banister,bank,bare,barren,basis,be,bear,beards,bearing,beautiful,became,because,become,becoming,bed,bedding,bedroom,beds,been,beer,before,beg,began,begged,begging,begin,beginning,begun,behalf,behaved,behind,being,beings,believe,believed,believing,belly,belonging,below,bend,benefit,bent,beside,besides,best,better,between,beyond,big,bit,bite,bitter,black,blanket,bleeding,blew,block,blossoming,blow,blown,blue,body,bolted,bombard,bone,boned,bones,boots,boss,both,bother,bottle,bottles,bottom,bound,bow,bowed,bowl,box,boy,bravely,bread,breadth,break,breakfast,breakfasts,breast,breath,breathe,breathing,brief,briefly,bring,bringing,broad,broke,broom,brother,brought,brown,budget,building,built,bulging,bulk,burdensome,burning,bushy,business,but,buttons,by,c,call,called,calling,calls,calm,calmed,calmer,calmly,calmness,came,can,cannot,cap,care,career,carefree,careful,carefully,carelessly,carpet,carried,carry,carrying,carved,case,cash,catch,catching,caught,cause,caused,causing,caustic,caution,cautious,ceiling,centre,certainly,certainty,chair,chairs,chance,change,changed,changes,changing,chaos,chase,cheaper,checked,checking,cheek,cheeks,cheer,cheese,chest,chewing,chief,child,childish,chilly,chin,choice,choose,chose,chosen,christmas,chuck,circumstances,city,claim,clapping,clean,cleaning,clear,cleared,clearer,clearly,clenched,clerk,clever,climb,climbing,clock,close,closed,closely,closer,closing,clothes,clumsily,clumsy,coat,coats,coffee,cold,collapsed,collar,collection,combed,come,comes,comfort,comfortable,comfortably,coming,comment,commerce,commercial,communicated,communication,companions,company,compared,complaint,complaints,complete,completely,complicated,comprehension,concealed,concentrated,concentration,concern,concerned,conclusion,conclusions,condemned,condition,conditions,confidence,confident,confirm,confirmation,confused,confusion,congratulated,connection,connections,conscience,consciousness,conservatory,consider,considerate,consideration,considerations,considered,considering,consisting,contact,containing,content,contented,contents,continually,continue,continued,continuing,continuously,contrary,contrast,control,controlled,conversation,conversations,converted,convinced,convulsive,cook,cooked,cooking,cool,copy,corner,corpse,couch,cough,coughed,coughing,could,couldn,count,countless,country,couple,courage,course,courtesy,cover,covered,covering,covers,crack,crash,crawl,crawled,crawling,cried,cross,crossed,crouched,cry,crying,curiosity,curious,current,curse,curtains,customers,cut,d,damage,damp,dampness,danced,danger,dare,dared,daring,dark,darkness,daughter,david,dawning,day,days,dead,deal,dear,death,debt,decide,decided,decision,decisions,decisive,decisively,declare,declared,deep,deeper,deeply,defend,definite,definitely,delay,delaying,delighted,demands,denuded,depended,deranged,describing,desk,despair,desperate,despite,destination,destroyed,detail,determination,determined,devoted,did,didn,different,differently,difficult,difficulty,diligently,dinner,direct,direction,directions,directly,dirt,dirty,disappear,disappeared,disappointed,disappointment,discard,disconcerted,discovery,discussed,disgust,dish,dishes,dismissal,dismissed,dissuade,distance,distinct,distinctly,distinguish,distract,distress,disturb,disturbed,disturbing,divided,do,doctor,document,doing,dominated,don,done,door,doors,doorway,double,doubt,down,dozing,drag,dragged,drank,draught,draw,drawers,drawn,dream,dreams,dressed,drew,dried,drink,drive,driven,driving,drop,dropped,drops,drove,dry,dull,dung,during,dust,duties,duty,dying,each,ear,earlier,early,earn,earned,earnest,ears,earth,ease,easier,easily,easy,eat,eaten,eating,echo,edge,edges,effect,effects,effort,efforts,eight,either,elastic,elderly,electric,else,emerged,emotion,emphatically,employer,emptied,empty,emptying,enable,encouraged,end,endearments,ended,endless,endure,enemy,engrossed,enjoy,enjoyed,enormous,enough,enter,entered,entering,entertain,entertaining,enthusiasm,enthusiastic,entire,entirely,entitled,entrance,entrusted,enveloped,equipment,errand,especially,establish,establishment,even,evening,evenings,events,eventually,ever,every,everyone,everything,everywhere,exact,exactly,exaggerated,examination,example,exceptionally,excessive,exchange,excited,excitedly,excitement,excuse,exhausted,exhaustion,expectations,expected,expecting,expects,expense,experience,experienced,explain,explained,explaining,explanation,explanations,express,expression,expressive,extreme,extremely,eyebrows,eyed,eyes,face,fact,fail,failed,failure,faint,faithful,fall,fallen,falling,familiar,family,fancy,far,fashion,fast,father,fear,feared,feather,feeble,feed,feeding,feel,feeling,feelings,feet,fell,felt,fetch,few,fiery,fifteen,filled,final,finally,finances,find,finger,fingers,finished,firm,firmly,first,fist,fists,fitted,five,fixed,flank,flapped,flat,fled,flee,flesh,flew,flight,floating,floor,floundering,flow,flowed,flowers,flown,fluid,fluttered,flying,fog,folds,followed,following,fond,food,fools,foot,footsteps,for,force,forced,forefinger,forehead,forget,forgetting,forgive,forgot,forgotten,forks,form,former,formerly,forth,fortunately,forward,forwards,found,four,fourteen,frame,franz,free,freed,freedom,freely,french,frenzy,frequent,frequently,fresh,friend,friendly,friends,frightening,fro,from,front,froze,fruit,full,fully,functions,funny,fur,furniture,further,future,gain,gained,game,gas,gather,gave,gazing,gentle,gentleman,gentlemen,gently,get,gets,getting,gifted,girl,girls,give,given,giving,glad,glance,glanced,glances,glancing,glass,gleeful,go,god,goes,going,gold,gone,good,goodness,gossip,got,gradually,grand,grant,grasp,gratitude,great,greatest,greatly,greedily,greeting,grin,groaning,ground,groundless,grounds,gruff,guessed,guest,gushed,habit,had,hadn,hair,hairs,half,hall,halt,hand,handle,hands,hang,hanging,happen,happened,happening,happy,hard,harder,hardest,hardly,harm,harmed,harmful,harshly,has,hat,hats,have,haven,having,hazard,he,head,heads,healed,healthy,hear,heard,hearer,hearing,heart,heaven,heavily,heaving,heavy,held,hell,help,helped,helping,helpless,helplessly,helplessness,her,here,herself,hidden,hide,high,highly,him,himself,hinder,his,hiss,hissed,hissing,hit,hitting,hold,holding,holes,holiday,home,homes,honour,hope,hoped,hopes,hoping,horrible,hospital,hostile,hot,hotel,hour,hours,house,household,housekeeper,how,however,hugged,human,humbly,humility,hundred,hung,hunger,hungry,hurried,hurriedly,hurry,hurrying,hurt,i,idea,ideas,if,ignoring,ii,iii,ill,illness,imagination,imagine,imagined,imagining,imaginings,immaculate,immediate,immediately,immobile,impatient,impatiently,impeding,imploring,important,impose,impossible,impression,improvement,in,inaccessible,incapable,inch,incomprehensible,incredible,indeed,indicating,indifferent,individual,infant,inflamed,influence,inherited,injured,injuries,injuring,injury,inner,innocent,inseparably,inside,insist,insistent,instance,instead,instrument,intended,intending,intent,intention,intentions,intercede,interest,interrupted,into,introduction,invalid,invariably,investigate,invisible,involved,irregular,irritably,irritation,is,isn,it,its,itself,jaw,jaws,job,join,joined,joining,joy,judge,jump,jumped,just,keep,keeping,kept,key,keys,kicked,kind,kiss,kissed,kitchen,knees,knew,knife,knives,knock,knocked,knocking,know,knowing,known,knows,laboriously,lack,lacking,lad,lady,lain,lamp,lamps,landed,landing,lap,large,last,lasted,late,later,latest,laugh,laughed,lay,laying,lazy,lead,leader,leading,leaned,leaning,leapt,learn,learned,least,leather,leave,leaves,leaving,led,left,leg,legs,length,less,let,letters,letting,lid,lie,lieutenant,life,lifelessly,lift,lifted,light,lighter,lightly,like,liked,likely,likes,limped,limply,line,lines,lips,listen,listened,listening,lit,little,live,lived,livelier,lively,lives,living,ll,load,lock,locked,locking,lodged,long,longer,longing,look,looked,looking,lose,losing,loss,lost,lot,lots,loud,loudest,loudly,love,lovely,lover,lower,lungs,lurched,luxury,lying,m,mad,made,maid,main,maintain,make,makes,making,man,managed,many,march,marriage,martyr,matter,matters,maybe,me,meal,meals,mean,meant,meantime,meanwhile,meat,mechanical,medical,medicine,meet,melancholy,member,members,memory,men,mention,mentioned,merely,met,method,midday,middle,might,mild,milk,mind,mingle,mingled,minutes,miracle,misfortune,misfortunes,miss,missed,mistake,mistakes,mixed,mixing,modest,moment,moments,money,monogram,monotonous,monster,month,months,mood,more,moreover,morning,most,mother,mothers,motionless,mouth,move,moved,movement,movements,moving,mr,much,muffled,music,must,muster,my,nap,narrow,natural,naturally,near,nearer,nearest,nearly,necessary,neck,necklace,need,needed,needle,needn,neglected,never,new,news,newspapers,next,nice,night,no,nobody,nodded,nodding,noise,nonsense,nor,noses,nostrils,not,notes,nothing,notice,noticeable,noticeably,noticed,noticing,nourishment,now,nowadays,nuisance,numb,number,numerous,o,object,observant,observed,obsessed,obstinate,obvious,obviously,occasionally,occupied,occur,occurred,of,off,offer,offered,office,often,oh,old,on,once,one,ones,only,onto,open,opened,opening,openly,opens,opinion,opportunity,opposite,oppressed,or,ordeal,order,ostrich,other,others,ought,our,ourselves,out,outside,outstretched,over,overcoat,overcome,overnight,owed,own,pack,packed,page,paid,pain,pained,painful,painfully,pair,pale,pane,pangs,panic,panting,pantry,paper,parents,part,particular,particularly,partly,passed,past,patch,patience,patient,pauses,pay,paying,peace,peaceful,peacefully,peculiar,peered,peering,peg,pen,people,perfect,perform,performance,perhaps,periods,permission,person,personally,persuade,persuaded,picked,picture,piece,pieces,piercing,piled,pillows,pity,place,placed,places,plaintively,plan,planned,plans,plates,play,played,player,playing,pleasant,please,pleased,pleasure,pleasures,plenty,pockets,point,pointing,polished,politeness,poor,position,positions,possibilities,possible,pot,potatoes,poured,pouring,powerful,practical,practice,prejudice,premises,preoccupied,preparation,prepared,present,press,pressed,pressure,pretend,prevail,prevent,prevented,previous,price,pride,principal,private,probably,proceed,produced,progress,promise,proper,properly,propped,protect,protruding,proud,prove,provide,provincial,public,pull,pulled,pulling,punished,pure,purpose,pursue,push,pushed,pushing,put,putting,quarrel,quarter,question,quick,quicker,quickly,quiet,quieter,quietly,quite,quivering,rag,rage,rain,raise,raised,raising,raisins,ran,rather,rattling,re,reach,reached,reaching,read,reading,reads,ready,real,really,rearranging,reason,reasons,receipt,receive,received,recent,recently,recommend,recommendation,recover,red,reduce,reduced,refrained,refuse,refused,refusing,regained,regard,regret,regular,regularly,related,relaxed,released,reliable,relieved,remain,remained,remains,remarkable,remember,remembered,remind,reminder,remove,removed,removing,rented,repeated,repeatedly,repelled,replied,reply,report,reported,representative,reproach,reproaches,repugnant,request,required,resistance,resolve,resolved,resounding,respect,responded,response,responsibility,responsible,rest,rested,result,retreating,return,revolting,revulsion,rid,right,ring,risked,robust,rock,rocked,roll,rolled,room,rooms,rotten,round,rounded,rows,rubbed,rubbing,run,running,rush,rushed,rushing,s,sacked,sacrifice,sacrificed,sad,saddened,sadly,safe,said,saints,sake,sales,salesman,salt,same,samples,sank,sat,satisfaction,satisfied,sauce,save,saved,saving,saw,say,saying,scar,school,scraped,scraping,scratching,scream,screamed,screaming,screams,scurry,seat,seats,second,secret,sections,secure,see,seem,seemed,seeming,seen,seized,seldom,selection,self,selfish,send,sending,sense,senses,sensible,sensitive,sent,separated,serious,seriously,serve,service,set,seven,seventeen,several,sew,sewing,shaken,shaking,shall,shame,sharply,she,sheet,shiny,shivering,shock,shocked,shone,shook,shop,short,should,shoulder,shoulders,shout,shouted,shouting,shouts,shove,shoved,show,showed,showing,shown,shrugged,shudder,shut,shy,sick,side,sides,sideways,sighing,sighs,sight,sign,silence,silent,sill,similar,simple,simply,simultaneously,since,sink,sir,sister,sit,sits,sitting,situation,six,sixteen,size,skirt,skirts,sky,slammed,slamming,sleep,sleepiness,sleeping,sleeve,slept,sliding,slight,slightest,slightly,slipped,slow,slowly,slumber,small,smaller,smart,smell,smelling,smile,smiled,smoke,smoking,smooth,snapped,snapping,snuffling,so,sofa,soft,softened,sold,soles,solid,some,somebody,someone,something,sometimes,somewhat,somewhere,son,soon,sooner,sorrows,sort,sorted,sought,sound,sounded,sounding,source,space,spare,speak,speaking,special,speech,spend,spent,spin,splashed,splinter,spoke,spoken,spot,spots,spread,spring,sprung,spying,square,squarely,squeaking,staff,staggered,staircase,stairs,stamped,stamping,stand,standing,stared,staring,start,started,starting,startled,startling,starve,state,station,stay,stayed,staying,steadily,steady,steaming,step,stepped,steps,stick,sticking,sticks,stiff,still,stillness,stone,stood,stop,stopped,straight,strain,strained,strangeness,stranger,strangers,street,streets,strength,strenuous,stretch,stretched,stretching,strict,strides,strike,strikes,striking,strong,strongly,struck,structure,struggled,struggling,stubborn,stuck,studies,stuff,stumbling,stupid,subdued,subject,subordinates,subtleties,succeeded,success,such,sucking,sudden,suddenly,suffer,suffered,suffering,sufficient,sufficiently,suffocating,suggest,suggested,suitable,sunday,sunk,sunshine,superfluous,superior,supernatural,supported,suppose,suppress,sure,surely,surplus,surprise,surprising,suspicious,swallow,swayed,sweep,sweetly,swept,swing,swinging,swishing,sword,swore,sympathy,t,table,take,taken,takes,taking,talk,talking,tall,task,taste,tearfully,tears,teeth,tell,telling,temporarily,tempted,ten,tender,terrible,terribly,test,than,thank,thanking,thanks,that,the,their,them,themselves,then,there,thereby,therefore,these,they,thick,thin,thing,things,think,thinking,thinks,this,thoroughly,those,though,thought,thoughtfully,thoughts,threads,threat,threatened,three,threw,through,throughout,throw,throwing,thrown,thunder,thus,tickle,tidied,tidy,tightly,till,time,times,tip,tips,tired,to,today,toe,together,told,tolerate,tone,tonight,too,took,tools,toothless,top,tops,tortured,tossed,total,totally,touched,toward,tower,town,traces,train,transferring,transformed,translated,transport,tray,treated,trembling,tremendous,tremor,tried,trip,troubled,trouser,true,trusted,try,trying,tug,tugged,turn,turned,turning,twice,twisted,two,unable,unbearable,unchanged,uncomfortable,uncontrolled,under,underneath,understand,understanding,understood,undisturbed,uneasy,unexpected,unfastened,unfolded,unfortunate,unfortunately,unhappy,unheard,uniform,uniting,unknown,unless,unlike,unlocked,unnatural,unnecessary,unpleasant,unpleasantness,unsatisfactory,untidiness,until,untouched,unused,unusual,unusually,unwell,up,upright,upset,upwards,urge,urged,us,use,used,useless,using,usual,usually,vague,vain,value,various,ve,very,victim,view,vigorously,vile,violence,violin,visible,visit,visitor,voice,volume,wait,waited,waiting,wake,walk,walked,walking,wall,walls,want,wanted,wanting,wants,warm,warmth,warning,was,washing,wasn,waste,wasted,wasting,watch,watched,watching,water,watering,waved,way,ways,we,weak,weaker,wealth,wearily,wearing,weather,week,weeks,weight,well,went,wept,were,what,whatever,when,whenever,where,whereabouts,whereas,whether,which,while,whims,whisper,whispered,whispering,whistled,white,who,whole,whom,whose,why,wide,widow,wife,wild,will,willing,wind,window,windowpanes,windows,wink,wipe,wiped,wisdom,wise,wish,wishing,with,withdraw,withdrew,within,without,withstand,woke,woman,women,won,wondered,wooden,word,words,work,worked,working,world,worn,worried,worries,worry,worst,would,wouldn,wrapped,wrenching,write,writing,wrong,wrote,year,years,yes,yesterday,yet,you,young,your,yourself

Revision history

  • 2021-03-12 - Initial publication