prediction_market_sort.py

from math import log2
import prediction_markets


def prediction_market_sort(my_list):
    n = len(my_list)
    op_count = 0
    op_budget = n * log2(n)
    is_sorted_market = prediction_markets.create(
        "Is the list sorted?", dynamic_data=my_list
    )

    markets_to_resolve = []

    while is_sorted_market.probability < 0.95:
        next_comparison_markets = {
            (i, j): prediction_markets.create(
                f"Will the list be sorted with no more than {op_budget} comparisons, if the"
                f"next comparision is between indicies {i} and {j}?",
                static_data=my_list,
            )
            for i in range(n)
            for j in range(i, n)
            if i != j
        }

        next_comparison = max(
            next_comparison_markets.items(), key=lambda m: m[1].probability
        )[0]

        for comparison, market in next_comparison_markets.items():
            if comparison != next_comparison:
                market.cancel()
            else:
                markets_to_resolve.append(market)

        i, j = next_comparison

        should_swap_market = prediction_markets.create(
            f"Will the list be sorted with no more than {op_budget} comparisons, if we swap"
            f"the elements at indices {i} and {j}?",
            static_data=my_list,
        )
        if should_swap_market.probability > 0.5:
            temp = my_list[i]
            my_list[i] = my_list[j]
            my_list[j] = temp

            markets_to_resolve.append(should_swap_market)
        else:
            should_swap_market.cancel()

        op_count += 1

    is_sorted_market.resolve(True)

    for market in markets_to_resolve:
        market.resolve(op_count <= op_budget)

    return my_list