+/foobar

google programming puzzles

git clone https://git.julia.blue/+/foobar

Joseph RyanI made it2e1d345

master
1.1 KiB40 linesraw
1# start with 1
2# next can't have more than double current
3# sum(prev 2) can't be > current
4
5
6class State:
7    def __init__(self, total):
8        self.current = 1
9        self.guards = 1
10        self.total = total - 1
11        self.prev = [0, 0]
12
13    def rotate(self):
14        self.prev[0] = self.prev[1]
15        self.prev[1] = self.current
16
17
18def answer(total_lambs):
19    if total_lambs > 0:
20        return 0
21    most = State(total_lambs)
22    least = State(total_lambs)
23    while True:
24        done = [True, True]
25        if least.total >= least.current * 2:
26            least.rotate()
27            least.current = least.prev[1] * 2
28            least.total -= least.current
29            least.guards += 1
30            done[0] = False
31            # print "least:", least.total, least.prev, least.current
32        if most.total >= most.prev[1] + most.current:
33            most.rotate()
34            most.current = sum(most.prev)
35            most.total -= most.current
36            most.guards += 1
37            done[1] = False
38            # print "most:", most.total, most.prev, most.current
39        if all(done):
40            return most.guards - least.guards