|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +There are two kinds of threads, oxygen and hydrogen. Your goal is to group these |
| 4 | +threads to form water molecules. There is a barrier where each thread has to |
| 5 | +wait until a complete molecule can be formed. Hydrogen and oxygen threads will |
| 6 | +be given releaseHydrogen and releaseOxygen methods respectively, which will |
| 7 | +allow them to pass the barrier. These threads should pass the barrier in groups |
| 8 | +of three, and they must be able to immediately bond with each other to form a |
| 9 | +water molecule. You must guarantee that all the threads from one molecule bond |
| 10 | +before any other threads from the next molecule do. |
| 11 | +
|
| 12 | +In other words: |
| 13 | +If an oxygen thread arrives at the barrier when no hydrogen threads are |
| 14 | +present, it has to wait for two hydrogen threads. |
| 15 | +If a hydrogen thread arrives at the barrier when no other threads are present, |
| 16 | +it has to wait for an oxygen thread and another hydrogen thread. |
| 17 | +We don’t have to worry about matching the threads up explicitly; that is, the |
| 18 | +threads do not necessarily know which other threads they are paired up with. The |
| 19 | +key is just that threads pass the barrier in complete sets; thus, if we examine |
| 20 | +the sequence of threads that bond and divide them into groups of three, each |
| 21 | +group should contain one oxygen and two hydrogen threads. |
| 22 | +
|
| 23 | +Write synchronization code for oxygen and hydrogen molecules that enforces these |
| 24 | +constraints. |
| 25 | +
|
| 26 | +Example 1: |
| 27 | +
|
| 28 | +Input: "HOH" |
| 29 | +Output: "HHO" |
| 30 | +Explanation: "HOH" and "OHH" are also valid answers. |
| 31 | +Example 2: |
| 32 | +
|
| 33 | +Input: "OOHHHH" |
| 34 | +Output: "HHOHHO" |
| 35 | +Explanation: "HOHHHO", "OHHHHO", "HHOHOH", "HOHHOH", "OHHHOH", "HHOOHH", |
| 36 | +"HOHOHH" and "OHHOHH" are also valid answers. |
| 37 | +
|
| 38 | +Constraints: |
| 39 | +
|
| 40 | +Total length of input string will be 3n, where 1 ≤ n ≤ 20. |
| 41 | +Total number of H will be 2n in the input string. |
| 42 | +Total number of O will be n in the input string. |
| 43 | +""" |
| 44 | +fromtypingimportCallable |
| 45 | +fromthreadingimportSemaphore |
| 46 | + |
| 47 | +fromcollectionsimportdeque |
| 48 | + |
| 49 | +classH2O: |
| 50 | +def__init__(self): |
| 51 | +self.hq=deque() |
| 52 | +self.oq=deque() |
| 53 | + |
| 54 | +defhydrogen(self,releaseHydrogen:Callable[[],None])->None: |
| 55 | +self.hq.append(releaseHydrogen) |
| 56 | +self.try_output() |
| 57 | + |
| 58 | +defoxygen(self,releaseOxygen:Callable[[],None])->None: |
| 59 | +self.oq.append(releaseOxygen) |
| 60 | +self.try_output() |
| 61 | + |
| 62 | +deftry_output(self): |
| 63 | +iflen(self.hq)>=2andlen(self.oq)>=1: |
| 64 | +self.hq.popleft()() |
| 65 | +self.hq.popleft()() |
| 66 | +self.oq.popleft()() |
| 67 | + |
| 68 | + |
| 69 | +classH2O_TLE2: |
| 70 | +def__init__(self): |
| 71 | +""" |
| 72 | + Conditional Variable as counter? - Semaphore |
| 73 | + """ |
| 74 | +self.gates= [Semaphore(2),Semaphore(0)]# inititally allow 2 H, 0 O |
| 75 | + |
| 76 | +defhydrogen(self,releaseHydrogen:Callable[[],None])->None: |
| 77 | +self.gates[0].acquire() |
| 78 | +# releaseHydrogen() outputs "H". Do not change or remove this line. |
| 79 | +releaseHydrogen() |
| 80 | +ifself.gates[0].acquire(blocking=False):# self.gates[0]._value > 0 |
| 81 | +# still have available count |
| 82 | +self.gates[0].release() |
| 83 | +else: |
| 84 | +self.gates[1].release() |
| 85 | + |
| 86 | + |
| 87 | +defoxygen(self,releaseOxygen:Callable[[],None])->None: |
| 88 | +self.gates[1].acquire() |
| 89 | +# releaseOxygen() outputs "O". Do not change or remove this line. |
| 90 | +releaseOxygen() |
| 91 | +self.gates[0].release() |
| 92 | +self.gates[0].release() |
| 93 | + |
| 94 | + |
| 95 | +classH2O_TLE: |
| 96 | +def__init__(self): |
| 97 | +""" |
| 98 | + Conditional Variable as counter? |
| 99 | + Fixed at HHO pattern |
| 100 | + """ |
| 101 | +self.h_cnt=0 |
| 102 | +self.locks= [Lock()for_inrange(3)] |
| 103 | +self.locks[1].acquire() |
| 104 | + |
| 105 | + |
| 106 | +defhydrogen(self,releaseHydrogen:Callable[[],None])->None: |
| 107 | +self.locks[0].acquire() |
| 108 | +self.h_cnt+=1 |
| 109 | +# releaseHydrogen() outputs "H". Do not change or remove this line. |
| 110 | +releaseHydrogen() |
| 111 | +ifself.h_cnt<2: |
| 112 | +self.locks[0].release() |
| 113 | +else: |
| 114 | +self.locks[1].release() |
| 115 | + |
| 116 | + |
| 117 | +defoxygen(self,releaseOxygen:Callable[[],None])->None: |
| 118 | +self.locks[1].acquire() |
| 119 | +# releaseOxygen() outputs "O". Do not change or remove this line. |
| 120 | +releaseOxygen() |
| 121 | +self.h_cnt=0 |
| 122 | +self.locks[0].release() |