LeetCode/8-28-2018_Bonetrousle.py at master · tobyatgithub/LeetCode · GitHub

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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Aug 28 13:33:23 2018

@author: toby
"""
import os
import sys
import random


#%%
### answer corrected for 10/14 tests
# https://www.hackerrank.com/challenges/bonetrousle/problem
def bonetrousle(n, k, b):
    minV = b*(b+1)/2
    maxV = b*(2*k-b+1)/2 # == sum(range(k-b+1,k+1))

    if n > maxV:
        # print("-1")
        return "-1"
    elif n < minV:
        return "-1"
    else:
        init_result = list(range(1,b+1))
        q = (n-minV)/b
        r = (n-minV)%b
        tmp = [_ + int(q) for _ in init_result]

        for i in range(len(tmp)-int(r),len(tmp)):
            print(i)
            tmp[i] += 1
        return tmp

#%%

n = 1
k = 1
b = 1

minV = b*(b+1)/2
maxV = b*(2*k-b+1)/2 # == sum(range(k-b+1,k+1))

if n > maxV:
    print("-1")

else:
    init_result = list(range(1,b+1))
    q = (n-minV)/b
    r = (n-minV)%b
    tmp = [_ + int(q) for _ in init_result]

    for i in range(len(tmp)-int(r),len(tmp)):
        print(i)
        tmp[i] += 1
    print(tmp)


#%%
#def bonetrousle(n, k, b):

def find_box(b_candidates, b_list, remaining_sticks, b):
    if len(b_list) > b:
        return "negative error"
    if remaining_sticks == 0:
        return b_list
    elif remaining_sticks < 0:
        return "negative error"
    else:
        print("len of b_candidates = ", len(b_candidates))
        this_box_id = random.randint(0,len(b_candidates)-1)
        print("box id = ", this_box_id)
        remaining_sticks = remaining_sticks - b_candidates[this_box_id]
        print("continue, picked box = %d, remaining = %d" %(b_candidates[this_box_id], remaining_sticks))
        b_list.append(b_candidates.pop(this_box_id))
        print(b_candidates, b_list)
        return find_box(b_candidates, b_list, remaining_sticks,b)

n = 9
k = 10
b = 2
buy = []
max_sticks = sum(range(k-b+1,k+1))
if n > max_sticks:
    print("-1")
else:
    tmp = "negative error"
    count = 0
    while (tmp== "negative error") and (count <= 1000):
        tmp = find_box(list(range(1, k)),[],n,b)
        count += 1
print("*"*10)
print(tmp, count)


#%%
r = str(tmp[0])
for i in tmp[1:]:
    r = r + " " + str(i)
r

#%%

r = "hum"
for i in range(10):
    tmp = find_box(list(range(1, 8)),[],12)
    if tmp != "negative error":
        r = tmp

r
#bonetrousle(12,8,3)
#%%
count = 0
while True and (count <= 10):
    count += 1
    print(count)
print("finish")