1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
#!/usr/bin/env python3
import bottle
import random
# Base class for a choosing algorithm.
class Algorithm:
def __init__(self, count):
self._count = count
self._rid = None
self._left = None
self._right = None
def first(self):
# Decide first action: return result or first comparison.
raise NotImplementedError()
def decide(self, left_is_smaller):
# Given the result of the previous less-than comparison, return new
# message to return to client.
#
# If the right value is past the end of the list, the caller should
# end the process.
raise NotImplementedError()
def rid(self):
# Return id of latest request.
return self._rid
def done(self, result):
return {"type": "done", "result": result}
def compare(self, left, right):
self._rid = random.randint(1, 2 ** 30)
self._left = left
self._right = right
return {
"type": "compare",
"left": left,
"right": right,
"request_id": self._rid,
}
class MinOrMax(Algorithm):
# Find index of smallest or largest item.
def first(self):
if self._count == 1:
return self.done(0)
return self.compare(0, 1)
def decide(self, left_is_smaller):
self._result = self.choose(self._left, self._right, left_is_smaller)
right = self._right + 1
if right >= self._count:
return self.done(self._result)
return self.compare(self._result, right)
def choose(self, left, right, left_is_smaller):
raise NotImplementedError()
class Max(MinOrMax):
# Find index of largest item.
def choose(self, left, right, left_is_smaller):
if left_is_smaller:
return right
else:
return left
class Min(MinOrMax):
# Find index of smallest item.
def choose(self, left, right, left_is_smaller):
if left_is_smaller:
return left
else:
return right
class Computer:
def __init__(self):
self.reset(None)
def reset(self, algo):
self._algo = algo
def new(self, algo):
self.reset(algo)
return self._algo.first()
def decide(self, answer, rid):
assert rid == self._algo.rid()
return self._algo.decide(answer)
session = Computer()
@bottle.post("/")
def root():
msg = bottle.request.json
print("request", msg)
msg_type = msg.get("type")
if msg_type == "compute_max":
o = session.new(Max(msg["length"]))
elif msg_type == "compute_min":
o = session.new(Min(msg["length"]))
elif msg_type == "comp_result":
o = session.decide(msg["answer"], msg["request_id"])
else:
assert False
print("result", o)
bottle.response.content_type = "application/json"
return o
bottle.run(host="localhost", port=5000)
|
