# TopCoder Single Round Match 257 Round 1 - Division I, Level One

## Programming assignment

Here's the problem I am trying to tackle, property of TopCoder. I will not copy and paste the full description to respect their copyright notice, but I am assuming I can summarise it.

### Summary

If a "weighted sum" of historical stock prices is the sum of addenda obtained by multiplying a subset of these prices by an equal number of "weighting" factors, provided the latter add up to 1.0 and are chosen from the given set of valid values [-1.0, -0.9, ..., 0.9, 1.0], use this formula on all historical data supplied as an argument to your function, examining 5 prices at a time, predicting the next price and returning the permutation of "weighting factors" that yields the lowest average prediction error. There will be at least 6 stock prices in each run so at least one prediction is guaranteed, final results should be accurate within 1E-9.

### Test data

Format:

• One row for input data, in `list` format
• One row for the expected result
• One empty row as a spacer

## My solution

``````import itertools

# For a permutation of factors to be used in a weighted sum, it should be chosen
# such than the sum of all factors is 1.
WEIGHTED_SUM_TOTAL = 1.0
FACTORS_CAN_BE_USED_IN_WEIGHTED_SUM = lambda x: sum(x) == WEIGHTED_SUM_TOTAL

# Historical stock price data should be examined using a sliding window of width
# 5 when making predictions about the next price.
N_RECENT_PRICES = 5

# Valid values for weighting factors are: [-1.0, -0.9, ..., 0.9, 1.0]
VALID_WEIGHTS = [x / 10. for x in range(-10, 11)]

# A pre-calculated list of valid weightings to consider. This is the cartesiant
# product of the set of valid weigths considering only the combinations which
# are valid as components of a weighted sum.
CARTESIAN_PRODUCT_FACTORS = [VALID_WEIGHTS] * N_RECENT_PRICES
ALL_PERMUTATIONS_OF_WEIGHTS = itertools.product(*CARTESIAN_PRODUCT_FACTORS)
WEIGHTED_SUM_WEIGHTS = filter(FACTORS_CAN_BE_USED_IN_WEIGHTED_SUM,
ALL_PERMUTATIONS_OF_WEIGHTS)

# Generator function to get sliding windows of a given width from a data set
def sliding_windows(data, window_width):

for i in range(len(data) - window_width):
yield data[i:i + window_width], data[i + window_width]

def avg_error(data):

# The supplied data will guarantee at least one iteration
n_iterations = len(data) - 5

best_average_error = None

# Consider each valid weighting (e.g. permutation of weights)
for weighting in WEIGHTED_SUM_WEIGHTS:

# Keep track of the prediction errors for this weighting
errors_for_this_weighting = []

for historical_data, next_to_predict in sliding_windows(data,
N_RECENT_PRICES):

prediction = sum([a * b for a, b in zip(weighting, historical_data)])
errors_for_this_weighting.append(abs(next_to_predict - prediction))

average_error = sum(errors_for_this_weighting) / n_iterations

if average_error == 0: return average_error

best_average_error = (average_error if not best_average_error else
min(average_error, best_average_error))

return best_average_error

def main():
with open('data.txt') as input_file:
while True:
if not spacer:
break
result = avg_error(data)
print expected_result, result, (expected_result - result) < 1e-9

if __name__ == '__main__':
main()
``````
-