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
|
#!/usr/bin/env python3
import bottle
import random
def max(answer):
return answer
def min(answer):
return not answer
class Find:
def __init__(self):
self.reset()
def reset(self):
self._algo = None
self._count = None
self._result = 0
self._pos = 0
self._rid = None
def new(self, algo, count):
assert count > 0
if count == 1:
# List has length 1: we know the answer.
return self.done(0)
self.reset()
self._algo = algo
self._count = count
return self.next(self._result)
def decide(self, answer, rid):
assert rid == self._rid
if self._algo(answer):
# use previous "right" item in comparison
return self.next(self._pos)
else:
# use previous result
return self.next(self._result)
def next(self, new_result):
self._result = new_result
# Choose next item to compare.
self._pos += 1
if self._pos >= self._count:
# We have reached the end of the list.
return self.done(self._result)
# Compare newly chosen item with current result.
return self.compare(self._result, self._pos)
def compare(self, left, right):
self._rid = random.randint(1, 2 ** 30)
return {
"type": "compare",
"left": left,
"right": right,
"request_id": self._rid,
}
def done(self, n):
return {"type": "done", "result": n}
session = Find()
@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, session._pos)
bottle.response.content_type = "application/json"
return o
bottle.run(host="localhost", port=5000)
|
