Instantly share code, notes, and snippets.

# geospiza-fortis/main.py

Last active August 1, 2021 06:31
Star You must be signed in to star a gist
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 from constraint import Problem, MinSumConstraint from functools import partial from random import randint from math import ceil def solve_naive(lower, upper, hp): avg = (upper + lower) / 2 return hp / avg def _valid_min_hits(hp, *hits): """Each variable represents a hit on a monster, which can be within a range. We assert that the value is valid if we cannot drop one of the values and still maintain our original constraint.""" acc = 0 for i, hit in enumerate(hits): acc += hit if acc >= hp and i < len(hits) - 1: # the monster would have already been dead by this point return False return True # return the number of solutions that are possible def _solve_exact_k(lower, upper, hp, k): problem = Problem() vars = [f"hit_{i}" for i in range(k)] for var in vars: problem.addVariable(var, list(range(lower, upper + 1))) problem.addConstraint(MinSumConstraint(hp)) problem.addConstraint(partial(_valid_min_hits, hp), vars) return problem.getSolutions() def get_num_solutions(att_lower, att_upper, hp, bound_lower, bound_upper): # solution at index 0 is always 0 res =  * bound_lower for i in range(bound_lower, bound_upper + 1): res_k = _solve_exact_k(att_lower, att_upper, hp, i) res.append(len(res_k)) return res def solve_exact(lower, upper, hp): min_hits = ceil(hp / upper) max_hits = ceil(hp / lower) # be aware, this will be very slow if the minimum number of hits to kill is large... problem = Problem() s = get_num_solutions(lower, upper, hp, min_hits, max_hits) print(s) # inclusive range r = upper - lower + 1 # possible ways is based on the size of the range... return sum([i * s_i / (r ** i) for i, s_i in enumerate(s)]) def solve_approx(lower, upper, hp, samples=1000): min_hits = ceil(hp / upper) max_hits = ceil(hp / lower) # this may be slow if range of hits is wide weights =  * min_hits for k in range(min_hits, max_hits + 1): valid = 0 for _ in range(samples): # sample uniformly from the range hits = [randint(lower, upper) for _ in range(k)] # check if this is valid valid += 1 if sum(hits) >= hp and _valid_min_hits(hp, *hits) else 0 weights += [valid / samples] print(weights) return sum([i * w_i for i, w_i in enumerate(weights)]) / sum(weights) def debug_exact(*args): print("exact", *args, "=>", solve_naive(*args), solve_exact(*args)) def debug_approx(*args): print("approx", *args, "=>", solve_naive(*args), solve_approx(*args)) debug_exact(40, 60, 150) debug_approx(40, 60, 150) debug_exact(40, 80, 150) debug_approx(40, 80, 150) # debug_exact(40, 120, 150) debug_approx(1500, 3000, 15000) debug_approx(1500, 5000, 15000) debug_approx(1500, 8000, 15000)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 python-constraint==1.4.0

### geospiza-fortis commented Mar 11, 2021 • edited

``````[0, 0, 0, 4796, 93765]
exact 40 60 150 => 3.0 3.48212935968038
[0, 0, 0, 0.517, 0.476]
approx 40 60 150 => 3.0 3.479355488418933
[0, 0, 66, 61255, 203360]
exact 40 80 150 => 2.5 3.03270411050333
[0, 0, 0.048, 0.889, 0.078]
approx 40 80 150 => 2.5 3.0295566502463047
[0, 0, 0, 0, 0, 0.0, 0.094, 0.671, 0.248, 0.008, 0.0]
approx 1500 3000 15000 => 6.666666666666667 7.166503428011754
[0, 0, 0, 0.0, 0.176, 0.533, 0.284, 0.039, 0.003, 0.0, 0.0]
approx 1500 5000 15000 => 4.615384615384615 5.188405797101449
[0, 0, 0.015, 0.404, 0.41, 0.124, 0.019, 0.0, 0.0, 0.0, 0.0]
approx 1500 8000 15000 => 3.1578947368421053 3.7201646090534983
``````