Random search algorithm explained

zombie-survival.py

import random


E = 30 # expiry of anti-zombie serum
X = 10 # initial ammo supply


class Survival:
    def __init__(self, total_days, pods, supplies_init=[E]*X):
        self.total_days = total_days
        self.pods = pods
        self.supplies = supplies_init

    def _consume(self):
        self.supplies.remove(min(self.supplies))
        self.supplies = list(map(lambda x: x - 1, self.supplies))
        self.supplies = list(filter(lambda x: x != 0, self.supplies))

    def _retrieve(self, risk, quantity):
        new_ammo = [E] * quantity
        cost = quantity**2 * risk
        return new_ammo, cost

    def _get_risk(self, day):
        pod = list(filter(lambda x: x[0] == day, self.pods))
        if len(pod) > 0:
            return pod[0][1]
        return None

    def run(self, retrieval_plan):
        # print (f"START\nDays to go {self.total_days}. Initial ammo count: {len(self.supplies)}.")
        total_risk = 0
        retrieval_idx = 0
        for day in range(1, self.total_days + 1):

            risk_involved = self._get_risk(day)
            if risk_involved:
                new_ammo, partial_risk = self._retrieve(risk_involved, retrieval_plan[retrieval_idx])
                self.supplies    += new_ammo
                total_risk      += partial_risk
                retrieval_idx    += 1

            if len(self.supplies) == 0:
                # print (f"All ammo used! Day: {day}, money spent: {total_risk}.")
                return 0, total_risk, day
            else:
                self._consume()
            # print(f"Day: {day} -> {len(self.supplies)} loaves left, paid: {total_risk}.")

        if len(self.supplies) > 0:
            # print (f"DONE! But we still have: {len(self.supplies)} loaves left, and paid: {total_risk}.")
            pass
        else:
            # print (f"DONE! No ammo left, but paid: {total_risk}.")
            pass

        return len(self.supplies), total_risk, day


def initialize_retrieval_plan(pods, total_days):
    sd = list(map(lambda x: x[0], pods))
    sd.append(total_days)
    return [sd[x + 1] - sd[x] for x in range(len(sd) - 1)]


def is_illegal(plan):
    return (True in [c < 0 for c in plan])


def get_minimum(cache):
    min_risk = min(cache.values())
    key = list(cache.keys())[list(cache.values()).index(min_risk)]
    return [int(x) for x in key.split('-')], min_risk


def calculate_plan(total_days, pods, epochs=300, supplies=[E]*X, attempts=12, radius=4):
    plan = initialize_retrieval_plan(pods, total_days) 
    if is_illegal(plan):
        print ("This retrieval plan cannot possibly get the them to survive.")
        return

    S = Survival(total_days, pods, supplies.copy())
    supplies_size, cost, day = S.run(plan)
    if day < total_days:
        return

    plan_range = range(len(plan))
    cost_history = [9999999] # initializing cost history for early stopping
    last_plan = plan.copy()
    epoch = 1
    while epoch < epochs:
        cache = {}
        for attempt in range(attempts):
            i1 = random.choice(plan_range)
            i2 = random.choice(plan_range)
                
            plan = last_plan.copy()
            qty = random.choice(range(1, radius + 1))
            plan[i1] -= qty
            plan[i2] += qty

            S = Survival(total_days, pods, supplies.copy())
            supplies_size, cost, day = S.run(plan)

            if supplies_size < 0:  # ran out of ammo
                continue
            elif day < total_days: # ran out of days
                continue
            elif is_illegal(plan): # attempt to sell ammo
                continue
            else:                  # solution found
                key = '-'.join([str(x) for x in plan]) 
                cache[key] = cost

        if len(cache) != 0:
            last_plan, cost = get_minimum(cache)
        # print (f"{epoch}, cost: {cost}, plan: {last_plan}")
        epoch += 1
        cost_history.append(cost)
        if cost_history[epoch - 1] == cost_history[epoch - 2]:
            break

    if len(cache) == 0:
        print ("No solution for this case. They must die.")
        return
    else:
        print (f"Solution found, but it'll cost = {cost}.")
        return last_plan

if  __name__ == '__main__':
    pods = [
        (10, 0.2), 
        (20, 0.1), 
        (30, 0.5), 
        (40, 0.3), 
        (50, 0.1), 
        (60, 0.2), 
        (70, 0.3),
        (80, 0.3),
        (90, 0.3),
        (100, 0.1)
        ]
    total_days = 110
    
    plan = calculate_plan(total_days, pods, attempts=ATTEMPTS, radius=RADIUS)