| Part 1 | Part 2 | Total | |
|---|---|---|---|
| Time | 9:16:10 | 35:56 | 9:52:06 |
This is the first day that I didn't stay up until midnight to do the problem when it came out. Fortunately no one else in the NJIT ACM private leaderboard did either, probably due to exams like me.
Part 1 was a "just do it" kind of problem that is easily solveable with recursion. I decided to not use eval this time :).
from helpers.datagetter import data_in, submit
ans = 0
din = data_in(split=True, numbers=False)
states = {}
for line in din:
line = line.split(" ")
out = line[1:]
if out[0].isnumeric():
out = int(out[0])
states[line[0][:-1]] = out
# print(states)
def evaluate(var):
# print(var, states[var])
if type(states[var]) is int:
return states[var]
val1, op, val2 = states[var]
val1 = evaluate(val1)
val2 = evaluate(val2)
if op == "+":
return val1 + val2
elif op == "/":
return val1 / val2
elif op == "*":
return val1 * val2
elif op == "-":
return val1 - val2
ans = evaluate("root")
print(ans)
submit(ans)Once I had Part 1, I took a break and walked back to my room and started on Part 2.
It was again pretty simple, with the trick I used being the following. I start with a range = [-bound, bound] and check the difference between the left and right values that root calls for human values of range[0], (range[1] - range[0]) // 2 + range[0], and range[1]. This effectively checks the start, middle, and end of the range.
Then, based on the difference of val1 and val2 that the root monkey sees, we subdivide the range using the following pseudo-code:
if start_diff + middle_diff > middle_diff + end_diff:
start = middle
elif start_diff + middle_diff < middle_diff + end_diff:
end = middle
else # if dists are equal
return range[0] + 1
This has the effect of subdividing the range to check until the range is of length 3 and centered around the true value. For the example given, if the range starts at [-512, 512], it would become [0, 512], then [256, 512], then [256, 384], ... then [300, 302]. At this point we know the human value should be 301.
There is one more wrinkle: we don't know the bounds of the true value. Because of this, I start with a bound of [-1, 1] and run the process. If we don't find anything, then I just increase the bound by a factor of 2, becoming [-2, 2]. And so on until it finds a bound that contains the true value. I'm sure there's a smarter way to do this, but that's what I've got and it runs in just over a second on my machine.
from helpers.datagetter import data_in, submit
ans = 0
din = data_in(split=True, numbers=False)
states = {}
for line in din:
line = line.split(" ")
out = line[1:]
if out[0].isnumeric():
out = int(out[0])
states[line[0][:-1]] = out
def converge():
def evaluate(var, human):
# print(var, states[var])
if var == "humn":
# print("HUMAN FOUND")
return human
if type(states[var]) is int:
return states[var]
val1, op, val2 = states[var]
val1 = evaluate(val1, human)
val2 = evaluate(val2, human)
if var == "root":
return abs(val1 - val2)
if op == "+":
return val1 + val2
elif op == "/":
return val1 / val2
elif op == "*":
return val1 * val2
elif op == "-":
return val1 - val2
def converge(bound):
range = [-bound, bound]
while range[1] - range[0] >= 1:
dist1 = evaluate('root', range[0])
middle = evaluate('root', ((range[1] - range[0]) // 2) + range[0])
dist2 = evaluate('root', range[1])
# print(dist1, middle, dist2)
# print(range)
if dist1 + middle > middle + dist2:
range[0] = ((range[1] - range[0]) // 2) + range[0]
elif dist1 + middle < middle + dist2:
range[1] = ((range[1] - range[0]) // 2) + range[0]
else:
return range[0] + 1
if range[1] - range[0] == 1:
return False
bound = 1
while converge(bound) is False:
bound *= 2
return converge(bound)
ans = converge()
print(ans)
submit(ans)