fork download

copy

import timeit
import sys
 
#the preferences of the knights and ladies presented as dictionaries
knightPreferences = {}
ladyPreferences = {}
 
#the unwed knights and ladies as arrays
unwedKnights = []
unwedLadies = []
 
#the group of engaged couples. We say "maybe" because they are liable
#to change
maybeEngaged = []
 
#the array of taken
takenMatch = []
 
#reading the knights and ladies preferences from the file and into
#their respective dictionaries
def SetKnightsAndLadies(fileName):
    #reading the file
    input_file = open(fileName)
    lines = input_file.readlines()
    #getting n from the file
    n = int(lines[0])
    data = lines[1:]
    i = 0
    #the initialization invariant of this loop is that both dictionaries
    #are empty. The maintenance invariant is that the knight/lady and
    #their preferences are added to the respective dictionary. The
    #termination invariant is that both dictionaries are full
    for line in data:
        if(i < n):
            #adding the first n lines as the knights' preferences
            knightPreferences[line.split()[0]] = line.split()[1:]
        if(i >= n):
            #adding the next n lines as the ladies' preferences
            ladyPreferences[line.split()[0]] = line.split()[1:]
        i = i + 1
 
#setting all the knights and ladies as unwed initially
def freeKnightsAndLadies():
    #the two loops here add the knights and ladies to their respective
    #arrays that mark them as unwed. The initialization invariants in
    #both these loops are that there are absolutely no pairs so far
    for key, value in knightPreferences.items():
        #the maintenance invariant is that the knight or lady who's
        #preferences are being considered is marked as unwed
        unwedKnights.append(key)
    #the termination invariant for both loops is that all the knights
    #and ladies are marked as unwed
    for key, value in ladyPreferences.items():
        unwedLadies.append(key)
 
def matchKnightWithLady(knight):
    #the initialization invariant of this loop is that there are no preferences
    #that would conflict with the current match. The maintenance invariants would
    #be that either the a knight and a lady become a couple, or a lady who is
    #currently matched is matched again with someone who's higher on their
    #priority list. The termination invariant is that the lady and the knight
    #are in their first match, or a new one.
    for lady in knightPreferences[knight]:
        #for each lady preferred by the knight, a boolean value is taken to
        #see if they are already in a match
        takenMatch = [match for match in maybeEngaged if lady in match]
        #if the lady is single, then she and the knight are added as
        #maybe engaged, and the loop breaks
        if len(takenMatch) == 0:
            maybeEngaged.append([knight,lady])
            unwedKnights.remove(knight)
            #print("matching knight and lady")
            break
        #else, if the lady is already in a match, then the preference of the
        #lady is tested to see if the knight is higher on her preference list
        elif len(takenMatch) > 0:
            currentHusband = ladyPreferences[lady].index(takenMatch[0][0])
            potentialHusband = ladyPreferences[lady].index(knight)
            #comparing the current and potential husbands. If the potential
            #husband is preferred, then their positions are switched, and
            #the loop breaks. If not, nothing is changed
            if (currentHusband > potentialHusband):
                unwedKnights.remove(knight)
                unwedKnights.append(takenMatch[0][0])
                takenMatch[0][0] = knight
                break
 
 
#the overall matching algorithm
def stableMatch():
    #the first loop in the matching algorithm, the initialization invariant
    #is that the length of the array unwedKnights is greater than 0. The
    #maintenance invariant is that a knight and lady are paired
    #together and no longer unwed. The termination invariant is
    #that there are no more unwed knights and ladies
    while len(unwedKnights) > 0:
        #the initialization invariant for this loop is that the knight
        #is currently unwed. the maintenance invariants are that the
        #knight is either the maintenance invariants are that the knight
        #is either the maintenance invariants are that the knight is either
        #wed to a lady or remains free. the termination invariant is that
        #the knight is probably married
        for knight in unwedKnights:
            #the part of the matching algorithm that works for one
            #knight at a time
            matchKnightWithLady(knight)
 
#the main function
def main():
    inputFile = input(str("Enter the name of the file: "))
 
    #calculating the runtime 
    start = timeit.default_timer()
 
    if not inputFile.endswith('.txt'):
        exit(1)
    SetKnightsAndLadies(inputFile)
    freeKnightsAndLadies()
    stableMatch()
 
    #printing the runtime
    stop = timeit.default_timer()
    sys.stdout.write(str(stop - start) + '\n')
 
    for i in range(len(maybeEngaged)):
        sys.stdout.write(str(maybeEngaged[i][0]) + " " + str(maybeEngaged[i][1]) + '\n')
 
main()
 

Main.java:1: error: '.' expected
import timeit
             ^
Main.java:2: error: ';' expected
import sys
      ^
Main.java:4: error: illegal character: '#'
#the preferences of the knights and ladies presented as dictionaries
^
Main.java:4: error: class, interface, or enum expected
#the preferences of the knights and ladies presented as dictionaries
     ^
Main.java:8: error: illegal character: '#'
#the unwed knights and ladies as arrays
^
Main.java:12: error: illegal character: '#'
#the group of engaged couples. We say "maybe" because they are liable
^
Main.java:13: error: illegal character: '#'
#to change
^
Main.java:16: error: illegal character: '#'
#the array of taken
^
Main.java:19: error: illegal character: '#'
#reading the knights and ladies preferences from the file and into
^
Main.java:20: error: illegal character: '#'
#their respective dictionaries
^
Main.java:22: error: illegal character: '#'
    #reading the file
    ^
Main.java:25: error: illegal character: '#'
    #getting n from the file
    ^
Main.java:29: error: illegal character: '#'
    #the initialization invariant of this loop is that both dictionaries
    ^
Main.java:30: error: illegal character: '#'
    #are empty. The maintenance invariant is that the knight/lady and
    ^
Main.java:31: error: illegal character: '#'
    #their preferences are added to the respective dictionary. The
    ^
Main.java:32: error: illegal character: '#'
    #termination invariant is that both dictionaries are full
    ^
Main.java:35: error: illegal character: '#'
            #adding the first n lines as the knights' preferences
            ^
Main.java:35: error: unclosed character literal
            #adding the first n lines as the knights' preferences
                                                    ^
Main.java:38: error: illegal character: '#'
            #adding the next n lines as the ladies' preferences
            ^
Main.java:38: error: unclosed character literal
            #adding the next n lines as the ladies' preferences
                                                  ^
Main.java:42: error: illegal character: '#'
#setting all the knights and ladies as unwed initially
^
Main.java:44: error: illegal character: '#'
    #the two loops here add the knights and ladies to their respective
    ^
Main.java:45: error: illegal character: '#'
    #arrays that mark them as unwed. The initialization invariants in
    ^
Main.java:46: error: illegal character: '#'
    #both these loops are that there are absolutely no pairs so far
    ^
Main.java:48: error: illegal character: '#'
        #the maintenance invariant is that the knight or lady who's
        ^
Main.java:48: error: unclosed character literal
        #the maintenance invariant is that the knight or lady who's
                                                                 ^
Main.java:49: error: illegal character: '#'
        #preferences are being considered is marked as unwed
        ^
Main.java:51: error: illegal character: '#'
    #the termination invariant for both loops is that all the knights
    ^
Main.java:52: error: illegal character: '#'
    #and ladies are marked as unwed
    ^
Main.java:57: error: illegal character: '#'
    #the initialization invariant of this loop is that there are no preferences
    ^
Main.java:58: error: illegal character: '#'
    #that would conflict with the current match. The maintenance invariants would
    ^
Main.java:59: error: illegal character: '#'
    #be that either the a knight and a lady become a couple, or a lady who is
    ^
Main.java:60: error: illegal character: '#'
    #currently matched is matched again with someone who's higher on their
    ^
Main.java:60: error: unclosed character literal
    #currently matched is matched again with someone who's higher on their
                                                        ^
Main.java:61: error: illegal character: '#'
    #priority list. The termination invariant is that the lady and the knight
    ^
Main.java:62: error: illegal character: '#'
    #are in their first match, or a new one.
    ^
Main.java:64: error: illegal character: '#'
        #for each lady preferred by the knight, a boolean value is taken to
        ^
Main.java:65: error: illegal character: '#'
        #see if they are already in a match
        ^
Main.java:67: error: illegal character: '#'
        #if the lady is single, then she and the knight are added as
        ^
Main.java:68: error: illegal character: '#'
        #maybe engaged, and the loop breaks
        ^
Main.java:72: error: illegal character: '#'
            #print("matching knight and lady")
            ^
Main.java:74: error: illegal character: '#'
        #else, if the lady is already in a match, then the preference of the
        ^
Main.java:75: error: illegal character: '#'
        #lady is tested to see if the knight is higher on her preference list
        ^
Main.java:79: error: illegal character: '#'
            #comparing the current and potential husbands. If the potential
            ^
Main.java:80: error: illegal character: '#'
            #husband is preferred, then their positions are switched, and
            ^
Main.java:81: error: illegal character: '#'
            #the loop breaks. If not, nothing is changed
            ^
Main.java:89: error: illegal character: '#'
#the overall matching algorithm
^
Main.java:91: error: illegal character: '#'
    #the first loop in the matching algorithm, the initialization invariant
    ^
Main.java:92: error: illegal character: '#'
    #is that the length of the array unwedKnights is greater than 0. The
    ^
Main.java:93: error: illegal character: '#'
    #maintenance invariant is that a knight and lady are paired
    ^
Main.java:94: error: illegal character: '#'
    #together and no longer unwed. The termination invariant is
    ^
Main.java:95: error: illegal character: '#'
    #that there are no more unwed knights and ladies
    ^
Main.java:97: error: illegal character: '#'
        #the initialization invariant for this loop is that the knight
        ^
Main.java:98: error: illegal character: '#'
        #is currently unwed. the maintenance invariants are that the
        ^
Main.java:99: error: illegal character: '#'
        #knight is either the maintenance invariants are that the knight
        ^
Main.java:100: error: illegal character: '#'
        #is either the maintenance invariants are that the knight is either
        ^
Main.java:101: error: illegal character: '#'
        #wed to a lady or remains free. the termination invariant is that
        ^
Main.java:102: error: illegal character: '#'
        #the knight is probably married
        ^
Main.java:104: error: illegal character: '#'
            #the part of the matching algorithm that works for one
            ^
Main.java:105: error: illegal character: '#'
            #knight at a time
            ^
Main.java:108: error: illegal character: '#'
#the main function
^
Main.java:112: error: illegal character: '#'
    #calculating the runtime 
    ^
Main.java:115: error: unclosed character literal
    if not inputFile.endswith('.txt'):
                              ^
Main.java:115: error: unclosed character literal
    if not inputFile.endswith('.txt'):
                                   ^
Main.java:121: error: illegal character: '#'
    #printing the runtime
    ^
65 errors

Standard output is empty