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
|
#!/usr/bin/env python3
import bottle
import random
class Max:
def __init__(self):
self.new(0)
def new(self, count):
if count == 1:
# List has length 1: we know the answer.
return self.done(0)
self._count = count
self._result = 0
self._pos = 0
self._rid = None
return self.next(self._result)
def decide(self, answer, rid):
assert rid == self._rid
if answer:
# left < right: use previous "right" item
return self.next(self._pos)
else:
# left >= right: use current best 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)
self._pos = right
return {
"type": "compare",
"left": left,
"right": right,
"request_id": self._rid,
}
def done(self, n):
return {"type": "done", "result": n}
session = Max()
@bottle.post("/")
def root():
msg = bottle.request.json
print("request", msg)
msg_type = msg.get("type")
assert msg_type in ("compute_max", "comp_result")
if msg_type == "compute_max":
n = msg["length"]
assert n > 0
o = session.new(n)
else:
o = session.decide(msg["answer"], msg["request_id"])
print("result", o, session._pos)
bottle.response.content_type = "application/json"
return o
bottle.run(host="localhost", port=5000)
|
