Twice before, I’ve pitted Riddler Nation against itself in a battle royale for national domination. War must wage once more. Here are the rules. There are two warlords: you and your archenemy, with whom you’re competing to conquer castles and collect the most victory points. Each of the 10 castles has its own strategic value for a would-be conqueror. Specifically, the castles are worth 1, 2, 3, … , 9 and 10 victory points. You and your enemy each have 100 soldiers to distribute between any of the 10 castles. Whoever sends more soldiers to a given castle conquers that castle and wins its victory points. (If you each send the same number of troops, you split the points.) Whoever ends up with the most points wins.
But now, you have a spy! You know how many soldiers your archenemy will send to each castle. The bad news, though, is that you no longer have 100 soldiers — your army suffered some losses in a previous battle.
What is the value of the spy?
That is, how many soldiers do you need to have in order to win, no matter the distribution of your opponent’s soldiers? Put another way: What k is the minimum number such that, for any distribution of 100 soldiers in the 10 castles by your opponent, you can distribute k soldiers and win the battle?
In [24]:
import csv
import numpy as np
In [47]:
with open('castle-solutions.csv', newline='', encoding='latin1') as prev_castles_file:
file_reader = csv.reader(prev_castles_file)
ARMIES = list(file_reader)
ARMIES = ARMIES[1:]
ARMIES = [tuple(int(n) for n in row[:10]) for row in ARMIES]
TOTAL_SOLDIERS = 100
NUM_CASTLES = 10
POINTS = np.array([1,2,3,4,5,6,7,8,9,10])
NEEDED_SCORE = 28
In [28]:
def normalize_army(army):
army_sum = sum(army)
for i in range(len(army)):
army[i] = int((army[i]/army_sum)*TOTAL_SOLDIERS)
army_sum = sum(army)
if army_sum < TOTAL_SOLDIERS:
army[army.index(min(army))] += TOTAL_SOLDIERS - army_sum
if army_sum > TOTAL_SOLDIERS:
army[army.index(max(army))] -= army_sum - TOTAL_SOLDIERS
return army
In [29]:
def generate_random_army():
army = [random.randint(0,TOTAL_SOLDIERS) for _ in range(NUM_CASTLES)]
return normalize_army(army)
In [50]:
def min_solders_simple(army):
score = 0
soldiers_needed = 0
points_per_solder = np.divide(POINTS,army)
for pps,soldiers,point in sorted(zip(points_per_solder,army,POINTS),
key=lambda x: x[0],
reverse=True):
if score < NEEDED_SCORE:
soldiers_needed += soldiers
score += point
else:
break
return soldiers_needed
In [51]:
min_solders_simple(ARMIES[25])
Out[51]:
In [ ]: