Guidance ================================= General ------- Programmers must learn how to use frameworks. In this course, you are learning about the Textbook Collections Framework. You will not have the luxery to change the framework in any way. You must learn to do what you need to do with what is provided. Sometimes, this takes ingenuity and trial and error. Make sure you use the provided input.txt starter file to test your code. It must be located in the same folder as your Python file. Compare your results carefully to the "Programming Activity 5 - Expected Output" document. You have 5 parts to complete. Each part requires writing the code for the body of a function. Do not add, change, or delete any code outside of these function bodies. Each function already has all the parameters you might need. Make use of these parameters as needed within the function body. You do not need to use the parameter "words" in your code. As described in the function comments, "words" is a list of words. Its words contain only lowercase letters and there is no punctuation. An iterator for this list, "wordsIter", is also passed to the functions. "wordsIter" would not make sense without describing what it iterates. Your code can make use of "wordsIter" to access the words list. However, you could access "words" directly in a "for" loop, if you want. Part 1 ------ Call first() to prime the list iterator. Use a while loop with a hasNext() condition to traverse the words list. In the while block: Use next() to get the next word. Determine if this word is in the removals list. To do this, use: if (word in removals): If the word is in the removals list: Call remove() on the list iterator to remove it from the words list. Part 2 ------ Introduce a variable called previousWord and initialize it to an empty string. Call first() to prime the list iterator. Use a while loop with a hasNext() condition to traverse the words list. In the while block: Use next() to get the next word. If the word is equal to "first" or "last", use continue to keep looping. If the word is equal to the previous word, call remove() on the list iterator. Update the value of the previous word to be the current word. Part 3 ------ This is similar to part 1. Instead of the removals list, use the misspellings list. Instead of using remove(): Call insert() on the list iterator to insert the flag text. Then call next() on the list iterator to move past the flag. Part 4 ------ The strategy here is to iterate through the list to: Count the number of "first" words. Remove each of the "first" words as they are encountered. Then use the count to control another loop to: Insert new "first" words at the beginning of the list. For each one: Call first() to prime the list iterator. If there is a next word, call next() to establish the insertion point. Call insert() to insert a "first" word. Since part 4 is one of the more difficult parts, here is its solution as a free gift: # Part 4: # Move all occurrences of "first" to the front of the words list. # Input: # words - an ArrayList of words, no uppercase, no punctuation # wordsIter - a list iterator for the words list def moveFirstLit(words, wordsIter): countFirst = 0 wordsIter.first() while (wordsIter.hasNext()): word = wordsIter.next() if (word == FIRST): wordsIter.remove() countFirst += 1 for count in range(countFirst): wordsIter.first() if (wordsIter.hasNext()): wordsIter.next() wordsIter.insert(FIRST) Make sure you study this code line by line. Make sure you understand everything about how it works. The FIRST constant (a convenience variable), is setup near the top of the starter code. Part 5 ------ The strategy here is to iterate through the list to: Count the number of "last" words. Remove each of the "last" words as they are encountered. Then use the count to control another loop to: Insert new "last" words at the end of the list. For each one: Call last() to establish the insertion point. Call insert() to insert a "last" word. # This program exercises lists. # The following files must be in the same folder: # abstractcollection.py # abstractlist.py # arraylist.py # arrays.py # linkedlist.py # node.py # input.txt - the input text file. # Input: input.txt # This file must be in the same folder. # To keep things simple: # This file contains no punctuation. # This file contains only lowercase characters. # Output: output.txt # This file will be created in the same folder. # All articles are removed. # Certain prepositions are removed. # Duplicate consecutive words are reduced to a single occurrence. # Note: The words "first" and "last" are not reduced. # Certain misspelled words are flagged. # Occurrences of "first" are moved to the front of a line. # Occurrences of "last" are moved to the end of a line. from arraylist import ArrayList from linkedlist import LinkedList # Data: articles = ArrayList(["a", "the"]) prepositions = LinkedList(["after", "before", "from", "in", "off", "on", "under", "out", "over", "to"]) misspellings = ["foriegn", "excede", "judgement", "occurrance", "preceed", "rythm", "thier", ] inputFile = open("input.txt", "r") outputFile = open("output.txt", "w") FIRST = "first" FLAG = "FLAG:" LAST = "last" # Processing: # Part 1: # Removes all items from the words list that are found in the removals list. # Input: # words - an ArrayList of words, no uppercase, no punctuation # wordsIter - a list iterator for the words list # removals - the list of words to remove def removeItems(words, wordsIter, removals): # # Part 2: # Removes extra occurrances of consecutive duplicate words from the words list. # Note: It does not reduce the words "first" and "last". # Input: # words - an ArrayList of words, no uppercase, no punctuation # wordsIter - a list iterator for the words list def reduceDuplicates(words, wordsIter): # # Part 3: # Flags certain misspelled words in the words list by inserting "FLAG:" before them. # Input: # words - an ArrayList of words, no uppercase, no punctuation # wordsIter - a list iterator for the words list # misspellings - the list of misspelled words to flag def flagMisspelled(words, wordsIter, misspellings): # # Part 4: # Move all occurrences of "first" to the front of the words list. # Input: # words - an ArrayList of words, no uppercase, no punctuation # wordsIter - a list iterator for the words list def moveFirstLit(words, wordsIter): # # Part 5: # Move all occurrences of "last" to the end of the words list. # Input: # words - an ArrayList of words, no uppercase, no punctuation # wordsIter - a list iterator for the words list def moveLastLit(words, wordsIter): # def writeOutputLine(words): outputLine = " ".join(words) outputLine = outputLine + " " print(outputLine, end="") outputFile.write(outputLine) # Main processing loop: for line in inputFile: words = ArrayList(line.split()) wordsIter = words.listIterator() # Make no changes to blank lines: if (len(words) == 0): writeOutputLine(words) continue # Make no changes to comment lines: if (words[0] == "#"): writeOutputLine(words) continue # Remove articles: removeItems(words, wordsIter, articles) # Remove prepositions: removeItems(words, wordsIter, prepositions) # Reduce duplicate consecutive words to a single occurrence: reduceDuplicates(words, wordsIter) # Insert "FLAG:" before certain misspelled words: flagMisspelled(words, wordsIter, misspellings) # Move all occurrences of "first" to the front of the line: moveFirstLit(words, wordsIter) # Move all occurrences of "last" to the end of the line: moveLastLit(words, wordsIter) # Write output line: writeOutputLine(words) # Wrap-up inputFile.close() outputFile.close() """ File: node.py Copyright 2015 by Ken Lambert """ class Node(object): """Represents a singly linked node.""" def __init__(self, data, next = None): self.data = data self.next = next class TwoWayNode(Node): """Represents a doubly linked node.""" def __init__(self, data = None, previous = None, next = None): Node.__init__(self, data, next) self.previous = previous """ File: linkedlist.py Copyright 2015 by Ken Lambert """ from node import TwoWayNode from abstractlist import AbstractList class LinkedList(AbstractList): """A link-based list implementation.""" def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" # Uses a circular linked structure with a dummy header node self._head = TwoWayNode() self._head.previous = self._head.next = self._head AbstractList.__init__(self, sourceCollection) # Helper method returns node at position i def _getNode(self, i): """Helper method: returns a pointer to the node at position i.""" if i == len(self) - 1: return self._head.previous # Constant-time access to last item probe = self._head.next while i > 0: probe = probe.next i -= 1 return probe #Accessor methods def __iter__(self): """Supports iteration over a view of self.""" cursor = self._head.next modCount = self.getModCount() while cursor != self._head: yield cursor.data if modCount != self.getModCount(): raise AttributeError("Illegal modification of backing store") cursor = cursor.next def __getitem__(self, i): """Precondition: 0 <= i < len(self) Returns the item at position i. Raises: IndexError.""" if i < 0 or i >= len(self): raise IndexError("List index out of range") return self._getNode(i).data # Mutator methods def clear(self): """Makes self become empty.""" self._size = 0 self._modCount = 0 self._head = TwoWayNode() self._head.previous = self._head.next = self._head def __setitem__(self, i, item): """Precondition: 0 <= i < len(self) Replaces the item at position i. Raises: IndexError.""" if i < 0 or i >= len(self): raise IndexError("List index out of range") self._getNode(i).data = item def insert(self, i, item): """Inserts the item at position i.""" if i < 0: i = 0 elif i > len(self): i = len(self) theNode = self._getNode(i) newNode = TwoWayNode(item, theNode.previous, theNode) theNode.previous.next = newNode theNode.previous = newNode self._size += 1 self.incModCount() def pop(self, i = None): """Precondition: 0 <= i < len(self). Removes and returns the item at position i. If i is None, i is given a default of len(self) - 1. Raises: IndexError.""" if i == None: i = len(self) - 1 if i < 0 or i >= len(self): raise IndexError("List index out of range") theNode = self._getNode(i) item = theNode.data theNode.previous.next = theNode.next theNode.next.previous = theNode.previous self._size -= 1 self.incModCount() return item def listIterator(self): """Returns a list iterator.""" return LinkedList.ListIterator(self) class ListIterator(object): """Represents the list iterator for linked list.""" def __init__(self, backingStore): self._backingStore = backingStore self._modCount = backingStore.getModCount() self.first() def first(self): """Returns the cursor to the beginning of the backing store.""" self._cursor = self._backingStore._head.next self._lastItemPos = None def hasNext(self): """Returns True if the iterator has a next item or False otherwise.""" return self._cursor != self._backingStore._head def next(self): """Preconditions: hasNext returns True The list has not been modified except by this iterator's mutators. Returns the current item and advances the cursor to the next item.""" if not self.hasNext(): raise ValueError("No next item in list iterator") if self._modCount != self._backingStore.getModCount(): raise AttributeError("Illegal modification of backing store") self._lastItemPos = self._cursor self._cursor = self._cursor.next return self._lastItemPos.data def last(self): """Moves the cursor to the end of the backing store.""" self._cursor = self._backingStore._head self._lastItemPos = -1 def hasPrevious(self): """Returns True if the iterator has a previous item or False otherwise.""" return self._cursor.previous != self._backingStore._head def previous(self): """Preconditions: hasPrevious returns True The list has not been modified except by this iterator's mutators. Returns the current item and moves the cursor to the previous item.""" if not self.hasPrevious(): raise ValueError("No previous item in list iterator") self._cursor = self._cursor.previous self._lastItemPos = self._cursor return self._lastItemPos.data def replace(self, item): """Preconditions: the current position is defined. The list has not been modified except by this iterator's mutators. Replaces the items at the current position with item.""" if self._lastItemPos is None: raise AttributeError("The current position is undefined.") if self._modCount != self._backingStore.getModCount(): raise AttributeError("List has been modified illegally.") self._lastItemPos.data = item self._lastItemPos = None def insert(self, item): """Preconditions: The list has not been modified except by this iterator's mutators. Adds item to the end if the current position is undefined, or inserts it at that position.""" if self._modCount != self._backingStore.getModCount(): raise AttributeError("List has been modified illegally.") if self._lastItemPos is None: self._backingStore.add(item) else: newNode = TwoWayNode(item, self._lastItemPos.previous, self._lastItemPos) self._lastItemPos.previous.next = newNode self._lastItemPos.previous = newNode self._backingStore.incModCount() self._backingStore._size += 1 self._lastItemPos = None self._modCount += 1 def remove(self): """Preconditions: the current position is defined. The list has not been modified except by this iterator's mutators. Pops the item at the current position.""" if self._lastItemPos == None: raise AttributeError("The current position is undefined.") if self._modCount != self._backingStore.getModCount(): raise AttributeError("List has been modified illegally.") item = self._lastItemPos.data # If the item removed was obtained via previous, move cursor ahead if self._lastItemPos == self._cursor: self._cursor = self._cursor.next self._lastItemPos.previous.next = self._lastItemPos.next self._lastItemPos.next.previous = self._lastItemPos.previous self._backingStore._size -= 1 self._backingStore.incModCount() self._modCount += 1 self._lastItemPos = None """ File: arrays.py Copyright 2015 by Ken Lambert An Array is a restricted list whose clients can use only [], len, iter, and str. To instantiate, use = array(, ) The fill value is None by default. """ class Array(object): """Represents an array.""" def __init__(self, capacity, fillValue = None): """Capacity is the static size of the array. fillValue is placed at each position.""" self._items = list() for count in range(capacity): self._items.append(fillValue) def __len__(self): """-> The capacity of the array.""" return len(self._items) def __str__(self): """-> The string representation of the array.""" return str(self._items) def __iter__(self): """Supports iteration over a view of an array.""" return iter(self._items) def __getitem__(self, index): """Subscript operator for access at index.""" return self._items[index] def __setitem__(self, index, newItem): """Subscript operator for replacement at index.""" self._items[index] = newItem """ File: arraylist.py Copyright 2015 by Ken Lambert """ from arrays import Array from abstractlist import AbstractList class ArrayList(AbstractList): """Represents an array-based list.""" DEFAULT_CAPACITY = 10 def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._items = Array(ArrayList.DEFAULT_CAPACITY) AbstractList.__init__(self, sourceCollection) # Accessor methods def __getitem__(self, i): """Precondition: 0 <= i < len(self) Returns the item at position i. Raises: IndexError if i is out of range.""" if i < 0 or i >= len(self): raise IndexError("List index out of range") return self._items[i] def __iter__(self): """Supports iteration over a view of self.""" modCount = self.getModCount() cursor = 0 while cursor < len(self): yield self._items[cursor] if modCount != self.getModCount(): raise AttributeError("Illegal modification of backing store") cursor += 1 # Mutator methods def clear(self): """Makes self become empty.""" self._size = 0 self._modCount = 0 self._items = Array(ArrayList.DEFAULT_CAPACITY) self.incModCount() def __setitem__(self, i, item): """Precondition: 0 <= i < len(self) Replaces the item at position i. Raises: IndexError if i is out of range.""" if i < 0 or i >= len(self): raise IndexError("List index out of range") self._items[i] = item def _resize(self): """Private helper method to resize the array if necessary.""" temp = None if len(self) == len(self._items): temp = Array(2 * len(self._items)) elif len(self) <= len(self._items) // 4 and \ len(self._items) >= 2 * ArrayList.DEFAULT_CAPACITY: temp = Array(len(self._items) // 2) # Derrf Seitz 11/06/15 if temp: for i in range(len(self)): temp[i] = self._items[i] self._items = temp def insert(self, i, item): """Inserts the item at position i.""" self._resize() if i < 0: i = 0 elif i > len(self): i = len(self) if i < len(self): for j in range(len(self), i, -1): self._items[j] = self._items[j - 1] self._items[i] = item self._size += 1 self.incModCount() def pop(self, i = None): """Precondition: 0 <= i < len(self) Removes and returns the item at position i. Raises: IndexError if i is out of range.""" if i is None: # Derrf Seitz 11/06/15 i = len(self) - 1 if i < 0 or i >= len(self): raise IndexError("List index out of range") item = self._items[i] for j in range(i, len(self) - 1): self._items[j] = self._items[j + 1] self._size -= 1 self._resize() self.incModCount() return item """ File: abstractlist.py Copyright 2015 by Ken Lambert Common data and method implementations for lists. """ from abstractcollection import AbstractCollection class AbstractList(AbstractCollection): """Represents an abstract list.""" def __init__(self, sourceCollection): """Maintains a count of modifications to the list.""" AbstractCollection.__init__(self, sourceCollection) def index(self, item): """Precondition: item is in the list. Returns the position of item. Raises: ValueError if the item is not in the list.""" position = 0 for data in self: if data == item: return position else: position += 1 if position == len(self): raise ValueError(str(item) + " not in list.") def remove(self, item): """Precondition: item is in self. Raises: ValueError if item in not in self. Postcondition: item is removed from self.""" position = self.index(item) self.pop(position) def add(self, item): """Adds the item to the end of the list.""" self.insert(len(self), item) def append(self, item): """Adds the item to the end of the list.""" self.add(item) def listIterator(self): """Returns a list iterator.""" return AbstractList.ListIterator(self) class ListIterator(object): """Represents the list iterator for an array list.""" def __init__(self, backingStore): """Sets the initial state of the list iterator.""" self._backingStore = backingStore self._modCount = backingStore.getModCount() self.first() def first(self): """Returns the cursor to the beginning of the backing store. lastItemPos is undefined.""" self._cursor = 0 self._lastItemPos = -1 def hasNext(self): """Returns True if the iterator has a next item or False otherwise.""" return self._cursor < len(self._backingStore) def next(self): """Preconditions: hasNext returns True The list has not been modified except by this iterator's mutators. Returns the current item and advances the cursor to the next item. Postcondition: lastItemPos is now defined. Raises: ValueError if no next item. AttributeError if illegal mutation of backing store.""" if not self.hasNext(): raise ValueError("No next item in list iterator") if self._modCount != self._backingStore.getModCount(): raise AttributeError("Illegal modification of backing store") self._lastItemPos = self._cursor self._cursor += 1 return self._backingStore[self._lastItemPos] def last(self): """Moves the cursor to the end of the backing store.""" self._cursor = len(self._backingStore) self._lastItemPos = -1 def hasPrevious(self): """Returns True if the iterator has a previous item or False otherwise.""" return self._cursor > 0 def previous(self): """Preconditions: hasPrevious returns True The list has not been modified except by this iterator's mutators. Returns the current item and moves the cursor to the previous item.""" if not self.hasPrevious(): raise ValueError("No previous item in list iterator") if self._modCount != self._backingStore.getModCount(): raise AttributeError("Illegal modification of backing store") self._cursor -= 1 self._lastItemPos = self._cursor return self._backingStore[self._lastItemPos] def replace(self, item): """Preconditions: the current position is defined. The list has not been modified except by this iterator's mutators. Replaces the items at the current position with item.""" if self._lastItemPos == -1: raise AttributeError("The current position is undefined.") if self._modCount != self._backingStore.getModCount(): raise AttributeError("List has been modified illegally.") self._backingStore[self._lastItemPos] = item self._lastItemPos = -1 def insert(self, item): """Preconditions: The list has not been modified except by this iterator's mutators. Adds item to the end if the current position is undefined, or inserts it at that position.""" if self._modCount != self._backingStore.getModCount(): raise AttributeError("List has been modified illegally.") if self._lastItemPos == -1: self._backingStore.add(item) else: self._backingStore.insert(self._lastItemPos, item) self._lastItemPos = -1 self._modCount += 1 def remove(self): """Preconditions: the current position is defined. The list has not been modified except by this iterator's mutators. Pops the item at the current position.""" if self._lastItemPos == -1: raise AttributeError("The current position is undefined.") if self._modCount != self._backingStore.getModCount(): raise AttributeError("List has been modified illegally.") item = self._backingStore.pop(self._lastItemPos) # If the item removed was obtained via next, move cursor back if self._lastItemPos < self._cursor: self._cursor -= 1 self._modCount += 1 self._lastItemPos = -1 """ File: abstractlist.py Copyright 2015 by Ken Lambert Common data and method implementations for lists. """ from abstractcollection import AbstractCollection class AbstractList(AbstractCollection): """Represents an abstract list.""" def __init__(self, sourceCollection): """Maintains a count of modifications to the list.""" AbstractCollection.__init__(self, sourceCollection) def index(self, item): """Precondition: item is in the list. Returns the position of item. Raises: ValueError if the item is not in the list.""" position = 0 for data in self: if data == item: return position else: position += 1 if position == len(self): raise ValueError(str(item) + " not in list.") def remove(self, item): """Precondition: item is in self. Raises: ValueError if item in not in self. Postcondition: item is removed from self.""" position = self.index(item) self.pop(position) def add(self, item): """Adds the item to the end of the list.""" self.insert(len(self), item) def append(self, item): """Adds the item to the end of the list.""" self.add(item) def listIterator(self): """Returns a list iterator.""" return AbstractList.ListIterator(self) class ListIterator(object): """Represents the list iterator for an array list.""" def __init__(self, backingStore): """Sets the initial state of the list iterator.""" self._backingStore = backingStore self._modCount = backingStore.getModCount() self.first() def first(self): """Returns the cursor to the beginning of the backing store. lastItemPos is undefined.""" self._cursor = 0 self._lastItemPos = -1 def hasNext(self): """Returns True if the iterator has a next item or False otherwise.""" return self._cursor < len(self._backingStore) def next(self): """Preconditions: hasNext returns True The list has not been modified except by this iterator's mutators. Returns the current item and advances the cursor to the next item. Postcondition: lastItemPos is now defined. Raises: ValueError if no next item. AttributeError if illegal mutation of backing store.""" if not self.hasNext(): raise ValueError("No next item in list iterator") if self._modCount != self._backingStore.getModCount(): raise AttributeError("Illegal modification of backing store") self._lastItemPos = self._cursor self._cursor += 1 return self._backingStore[self._lastItemPos] def last(self): """Moves the cursor to the end of the backing store.""" self._cursor = len(self._backingStore) self._lastItemPos = -1 def hasPrevious(self): """Returns True if the iterator has a previous item or False otherwise.""" return self._cursor > 0 def previous(self): """Preconditions: hasPrevious returns True The list has not been modified except by this iterator's mutators. Returns the current item and moves the cursor to the previous item.""" if not self.hasPrevious(): raise ValueError("No previous item in list iterator") if self._modCount != self._backingStore.getModCount(): raise AttributeError("Illegal modification of backing store") self._cursor -= 1 self._lastItemPos = self._cursor return self._backingStore[self._lastItemPos] def replace(self, item): """Preconditions: the current position is defined. The list has not been modified except by this iterator's mutators. Replaces the items at the current position with item.""" if self._lastItemPos == -1: raise AttributeError("The current position is undefined.") if self._modCount != self._backingStore.getModCount(): raise AttributeError("List has been modified illegally.") self._backingStore[self._lastItemPos] = item self._lastItemPos = -1 def insert(self, item): """Preconditions: The list has not been modified except by this iterator's mutators. Adds item to the end if the current position is undefined, or inserts it at that position.""" if self._modCount != self._backingStore.getModCount(): raise AttributeError("List has been modified illegally.") if self._lastItemPos == -1: self._backingStore.add(item) else: self._backingStore.insert(self._lastItemPos, item) self._lastItemPos = -1 self._modCount += 1 def remove(self): """Preconditions: the current position is defined. The list has not been modified except by this iterator's mutators. Pops the item at the current position.""" if self._lastItemPos == -1: raise AttributeError("The current position is undefined.") if self._modCount != self._backingStore.getModCount(): raise AttributeError("List has been modified illegally.") item = self._backingStore.pop(self._lastItemPos) # If the item removed was obtained via next, move cursor back if self._lastItemPos < self._cursor: self._cursor -= 1 self._modCount += 1 self._lastItemPos = -1 """ File: abstractcollection.py Copyright 2015 by Ken Lambert """ class AbstractCollection(object): """An abstract collection implementation.""" # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._size = 0 self._modCount = 0 if sourceCollection: for item in sourceCollection: self.add(item) # Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return len(self) == 0 def __len__(self): """Returns the number of items in self.""" return self._size def __str__(self): """Returns the string representation of self, using [] as delimiters.""" return "[" + ", ".join(map(str, self)) + "]" def __eq__(self, other): """Returns True if self equals other, or False otherwise. Compares pairs of items in the two sequences generated by the iterators on self and other.""" if self is other: return True if type(self) != type(other) or \ len(self) != len(other): return False otherIter = iter(other) for item in self: if item != next(otherIter): return False return True def __add__(self, other): """Returns a new collection containing the contents of self and other.""" result = type(self)(self) for item in other: result.add(item) return result def count(self, item): """Returns the number of instance of item in self.""" counter = 0 for nextItem in self: if item == nextItem: counter += 1 return counter # These methods track and update the modCount, which is used to # prevent mutations within the context of an iterator (for loop) def getModCount(self): """Returns the number of modifications to the collection.""" return self._modCount def incModCount(self): """Increments the number of modifications to the collection.""" self._modCount += 1

# Articles: first this is test case this is second test case first this is neither nor second test case abc this is articles test case last # Certain prepositions: first dog ran deer but second dog i will walk here there it is warm here and cold there rug is table and table is rug this is prepositions test case last # Duplicate consecutive words (except "first" and "last"): boat had blue hull it is best way go that thats all folks rolling river first first words and are intentionally not reduced last last my # Certain misspelled words: FLAG: foriegn concept that preceeds FLAG: thier duplicated FLAG: occurrance will FLAG: excede maximum allowed value FLAG: judgement of FLAG: thier souls music had moving FLAG: rythm # Occurrences of "first" and "last": first shall be last first shall be last first first multiple place and place winners and losers last last first first first last last