andrewmagill · October 25, 2017 21:13 · Oct 25, 2017
diff --git a/message_sorting.py b/message_sorting.py
@@ -0,0 +1,99 @@
+from collections import namedtuple
+import pprint
+
+## parsing user input ##
+
+# named tuples to make things more organized?
+Event = namedtuple('Event','process event')
+Message = namedtuple('Message', 'sender receiver')
+
+# raw input, ostensibly from the user
+raw_msgs = ['1-1->2-2','1-3->3-4','2-3->3-1','3-2->1-2']
+
+# list to hold processed user input
+messages = []
+
+# create message tuples
+for msg in raw_msgs:
+    messages.append(
+        Message(
+            *[Event(*map(int,params.split('-'))) for params in msg.split('->')]
+        )
+    )
+
+# set of process ids
+proc_ids = set([])
+
+# add process id from each message to set (sets do not hold duplicate values)
+for msg in messages:
+    proc_ids.update(set([event.process for event in msg]))
+
+## sort messages sent and received message by process ##
+
+# create two dictionaries (aka hash tables) to store sorted lists of messages
+# by process. The first dictionary (sent) will hold messages in the order in 
+# which they were sent by each process. The second list (received) will hold 
+# messages in the order in which they were received by each process.
+
+sent = dict.fromkeys(proc_ids)
+received = dict.fromkeys(proc_ids)
+
+# populate dictionaries with sorted lists of messages
+for proc_id in proc_ids:
+    # sent message
+    sent_msgs = filter(
+        lambda msg, proc_id=proc_id: msg.sender.process == proc_id, 
+        messages
+    )
+    sent[proc_id] = sorted(sent_msgs, key=lambda message: message.sender.event)
+
+
+    # received messages
+    recvd_msgs = filter(
+        lambda msg, proc_id=proc_id: msg.receiver.process == proc_id, 
+        messages
+    )
+    received[proc_id] = sorted(recvd_msgs, key=lambda message: message.receiver.event)
+
+## create overall sorting of  messages ##
+
+sorted_messages = []
+
+# use our message list like a queue. pop messages off the queue, if the message
+# is the first in the received list for the receiving process, and the first
+# in the sent list for the sending process, add message to queue, and remove
+# messages from the sent and received lists
+
+print '\nsent\n'
+pprint.pprint(sent)
+print '\nreceived\n'
+pprint.pprint(received)
+
+while messages:
+    message = messages.pop()
+
+    first_msg_from_sender = next(iter(sent[message.sender.process]), None)
+    if not first_msg_from_sender:
+        raise(Exception('Message mismatch'))
+
+    first_msg_to_receiver = next(iter(received[message.receiver.process]), None)
+    if not first_msg_to_receiver:
+        raise(Exception('Message mismatch'))
+
+    print '--------'
+    print '\nmessage: \n', message
+    print '\nfirst sender: \n', first_msg_from_sender
+    print '\nfirst receiver: \n', first_msg_to_receiver
+
+    if message == first_msg_to_receiver and message == first_msg_from_sender:
+        # add to final ordering
+        sorted_messages.insert(0, message)
+
+        # remove message from the sent and received collections
+        sent[message.sender.process].remove(message)
+        received[message.receiver.process].remove(message)
+    else:
+        # add back into the queue (to the opposite end from where we pop)
+        messages.insert(0, message)
+
+pprint.pprint(sorted_messages)