Last active
February 21, 2021 09:09
-
-
Save nichanank/9e35b1188019eb9513d322eec185ec12 to your computer and use it in GitHub Desktop.
adapted version of bytebracket_scorer
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
| """ | |
| This is an adapted version of the original ByteBracket library https://gist.github.com/pursuingpareto/b15f1197d96b1a2bbc48 that was implemented to score a 63-game NCAA tournament | |
| Whitepaper: https://drive.google.com/file/d/0BxHbbgrucCx2N1MxcnA1ZE1WQW8/view | |
| """ | |
| import random | |
| def score(bracket, results, filt, | |
| teams_remaining, blacklist, round_num=0): | |
| """ | |
| Recursively calculates the score of a prediction | |
| bracket against a results bracket. | |
| - bracket | |
| A bitstring representing a prediction bracket. For | |
| a 64 game tournament this would be 63 bits. | |
| - results | |
| A bitstring representing the actual outcome of | |
| a tournament. | |
| - filt | |
| With the exception of the first round in a tournament, | |
| its not possible to score a round by just comparing | |
| the bits in bracket to the bits in results. For example, | |
| correctly predicting the championship game requires not | |
| only the correct bit for that game, but also the correct | |
| prediction for all the games the tournament winner had | |
| won before the final round. | |
| The filt parameter is a one time pre-computed bitstring | |
| used to indicate which games in a round must be | |
| correctly predicted in order to correctly predict | |
| successive games. For a 64 game tournament filt would | |
| contain 62 bits. | |
| if we have a four game brakcet | |
| - teams_remaining | |
| This is a recursive function where each call | |
| represents another tournament round. | |
| teams_remaining gives the number of teams left in the | |
| tournament as of this function call. | |
| - blacklist | |
| This parameter is a sequence of N bits where N is | |
| the number of games in the current round. It uses | |
| the accuracy of predictions from previous rounds to | |
| "remember" which games are possible to correctly | |
| predict. When calling the score function initially | |
| these bits should all be set to 1. | |
| - round_num | |
| A number representing the current round. For a 64 team | |
| tournament this would take the values 0,1,2,3,4, and 5 | |
| """ | |
| # First check if there is a winner | |
| if teams_remaining == 1 : | |
| return 0 | |
| # 1. get points for THIS round | |
| # compute constants for round | |
| num_games = int(teams_remaining / 2) | |
| round_mask = 2 ** num_games - 1 # all bits set to 0 except the bits corresponding to the current round | |
| # the current round is encoded in num_games | |
| # least significant bits. Likewise for results and filter | |
| round_predictions = bracket & round_mask | |
| round_results = results & round_mask | |
| round_filter = filt & round_mask | |
| # The overlap between the prediction bits and the | |
| # results bits is calculated by XORing the two and | |
| # then flipping the bits remaining. | |
| overlap = ~(round_predictions ^ round_results) | |
| # blacklist tells you to not count scores with wrong predictions in previous rounds. decrease the number of 1s in overlap | |
| # In all rounds except the first, overlap will tend | |
| # to overestimate a bracket's correctness. This is | |
| # corrected by ANDing the overlap with the blacklist | |
| scores = overlap & blacklist | |
| # the points for this round are calculated by counting | |
| # the number of 1s in the scores bitstring and then | |
| # multiplying by 2 ^ round_num (this multiplication | |
| # is used to weigh predictions in later rounds more | |
| # heavily than earlier rounds) | |
| points = popcount(scores) << round_num | |
| # 2. remember stuff based on where you were correct | |
| # with the points calculated we can now use the pre-computed filter to figure out which of these predictions may impact future predictions | |
| # round filter tells you what matters for subsequent rounds | |
| relevant_scores = scores & round_filter | |
| # For each pair of games in this round, look for a 1 in either of the bits to compute the blacklist for the next round. | |
| # in the next round, adjacent bits are playing against eachother | |
| even_bits, odd_bits = get_odds_and_evens_32(relevant_scores) | |
| blacklist = even_bits | odd_bits | |
| # 3. update variables for the next recursive call | |
| bracket = bracket >> num_games | |
| results = results >> num_games | |
| filt = filt >> num_games | |
| # print "----------------" | |
| # print "Round score: " + str(points) | |
| # print "----------------" | |
| return points + score(bracket, results, filt, | |
| int(teams_remaining / 2), blacklist, round_num + 1) | |
| def score_group_stage(bracket, results): | |
| # 1. split prediction and results brackets into separate arrays of its odd and even elements | |
| bracketEvens, bracketOdds = get_odds_and_evens_64(bracket) | |
| resultsEvens, resultsOdds = get_odds_and_evens_64(results) | |
| # 2. find the overlap between the odd and even elements of prediction and results | |
| evensOverlap = ~(bracketEvens ^ resultsEvens) | |
| oddsOverlap = ~(bracketOdds ^ resultsOdds) | |
| # 3. find the overall overlap by ANDing the even and odds overlap | |
| # both the even and odd elements have to match for the player to score a point | |
| overlap = evensOverlap & oddsOverlap | |
| # 4. count the number of 1s in the overlap | |
| scores = popcount_32(overlap) | |
| return scores | |
| def get_odds_and_evens_8(bits): | |
| """ | |
| Separates the even and odd bits by repeatedly | |
| shuffling smaller segments of a bitstring. | |
| """ | |
| tmp = (bits ^ (bits >> 1)) & 0x22; # 00100010 | |
| bits ^= (tmp ^ (tmp << 1)); | |
| tmp = (bits ^ (bits >> 2)) & 0x0c; # 00001100 | |
| bits ^= (tmp ^ (tmp << 2)); | |
| evens = bits >> 4 | |
| odds = bits % 0x10 | |
| return evens, odds | |
| def get_odds_and_evens_16(bits): | |
| """ | |
| Separates the even and odd bits by repeatedly | |
| shuffling smaller segments of a bitstring. | |
| """ | |
| tmp = (bits ^ (bits >> 1)) & 0x2222; # 0010001000100010 | |
| bits ^= (tmp ^ (tmp << 1)); | |
| tmp = (bits ^ (bits >> 2)) & 0x0c0c; # 0000110000001100 | |
| bits ^= (tmp ^ (tmp << 2)); | |
| tmp = (bits ^ (bits >> 4)) & 0x00f0; # 0000000011110000 | |
| bits ^= (tmp ^ (tmp << 4)); | |
| evens = bits >> 8 | |
| odds = bits % 0x100 | |
| return evens, odds | |
| def get_odds_and_evens_32(bits): | |
| """ | |
| Separates the even and odd bits by repeatedly | |
| shuffling smaller segments of a bitstring. | |
| """ | |
| tmp = (bits ^ (bits >> 1)) & 0x22222222; # 00100010001000100010001000100010 | |
| bits ^= (tmp ^ (tmp << 1)); | |
| tmp = (bits ^ (bits >> 2)) & 0x0c0c0c0c; # 00001100000011000000110000001100 | |
| bits ^= (tmp ^ (tmp << 2)); | |
| tmp = (bits ^ (bits >> 4)) & 0x00f000f0; # 00000000111100000000000011110000 | |
| bits ^= (tmp ^ (tmp << 4)); | |
| tmp = (bits ^ (bits >> 8)) & 0x0000ff00; # 00000000000000001111111100000000 | |
| bits ^= (tmp ^ (tmp << 8)); | |
| evens = bits >> 16 | |
| odds = bits % 0x10000 | |
| return evens, odds | |
| def get_odds_and_evens_64(bits): | |
| """ | |
| Separates the even and odd bits by repeatedly | |
| shuffling smaller segments of a bitstring. | |
| """ | |
| tmp = (bits ^ (bits >> 1)) & 0x2222222222222222; # 0010001000100010001000100010001000100010001000100010001000100010 | |
| bits ^= (tmp ^ (tmp << 1)); | |
| tmp = (bits ^ (bits >> 2)) & 0x0c0c0c0c0c0c0c0c; # 0000110000001100000011000000110000001100000011000000110000001100 | |
| bits ^= (tmp ^ (tmp << 2)); | |
| tmp = (bits ^ (bits >> 4)) & 0x00f000f000f000f0; # 0000000011110000000000001111000000000000111100000000000011110000 | |
| bits ^= (tmp ^ (tmp << 4)); | |
| tmp = (bits ^ (bits >> 8)) & 0x0000ff000000ff00; # 0000000000000000111111110000000000000000000000001111111100000000 | |
| bits ^= (tmp ^ (tmp << 8)); | |
| tmp = (bits ^ (bits >> 16)) & 0x00000000ffff0000; # 0000000000000000000000000000000011111111111111110000000000000000 | |
| bits ^= (tmp ^ (tmp << 16)); | |
| evens = bits >> 32 | |
| odds = bits % 0x100000000 | |
| return evens, odds | |
| def get_odds_and_evens_96(bits): | |
| """ | |
| Separates the even and odd bits by repeatedly | |
| shuffling smaller segments of a bitstring. | |
| """ | |
| tmp = (bits ^ (bits >> 1)) & 0x222222222222222222222222; # 001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010 | |
| bits ^= (tmp ^ (tmp << 1)); | |
| tmp = (bits ^ (bits >> 2)) & 0x0c0c0c0c0c0c0c0c0c0c0c0c; # 000011000000110000001100000011000000110000001100000011000000110000001100000011000000110000001100 | |
| bits ^= (tmp ^ (tmp << 2)); | |
| tmp = (bits ^ (bits >> 4)) & 0x000000f000f000f000f000f0; # 000000001111000000000000111100000000000011110000000000001111000000000000111100000000000011110000 | |
| bits ^= (tmp ^ (tmp << 4)); | |
| tmp = (bits ^ (bits >> 8)) & 0x0000ff000000ff000000ff00; # 000000000000000011111111000000000000000000000000111111110000000000000000000000001111111100000000 | |
| bits ^= (tmp ^ (tmp << 8)); | |
| tmp = (bits ^ (bits >> 16)) & 0x00000000ffff000000000000; # 000000000000000000000000000000001111111111111111000000000000000000000000000000000000000000000000 | |
| bits ^= (tmp ^ (tmp << 16)); | |
| tmp = (bits ^ (bits >> 24)) & 0x000000000000ffffff000000; # 000000000000000000000000000000000000000000000000111111111111111111111111000000000000000000000000 | |
| bits ^= (tmp ^ (tmp << 24)); | |
| # tmp = (bits ^ (bits >> 32)) & 0x0000000000000000ffffffff; # 000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111 | |
| # bits ^= (tmp ^ (tmp << 32)); | |
| evens = bits >> 38 | |
| odds = bits % 0x1000000000000 | |
| return evens, odds | |
| def get_odds_and_evens_128(bits): | |
| """ | |
| Separates the even and odd bits by repeatedly | |
| shuffling smaller segments of a bitstring. | |
| """ | |
| tmp = (bits ^ (bits >> 1)) & 0x22222222222222222222222222222222; # 00100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010 | |
| bits ^= (tmp ^ (tmp << 1)); | |
| tmp = (bits ^ (bits >> 2)) & 0x0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c; # 00001100000011000000110000001100000011000000110000001100000011000000110000001100000011000000110000001100000011000000110000001100 | |
| bits ^= (tmp ^ (tmp << 2)); | |
| tmp = (bits ^ (bits >> 4)) & 0x00f000f000f000f000f000f000f000f0; # 00000000111100000000000011110000000000001111000000000000111100000000000011110000000000001111000000000000111100000000000011110000 | |
| bits ^= (tmp ^ (tmp << 4)); | |
| tmp = (bits ^ (bits >> 8)) & 0x0000ff000000ff000000ff000000ff00; # 00000000000000001111111100000000000000000000000011111111000000000000000000000000111111110000000000000000000000001111111100000000 | |
| bits ^= (tmp ^ (tmp << 8)); | |
| tmp = (bits ^ (bits >> 16)) & 0x00000000ffff000000000000ffff0000; # 00000000000000000000000000000000111111111111111100000000000000000000000000000000000000000000000011111111111111110000000000000000 | |
| bits ^= (tmp ^ (tmp << 16)); | |
| tmp = (bits ^ (bits >> 32)) & 0x0000000000000000ffffffff00000000; # 00000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111100000000000000000000000000000000 | |
| bits ^= (tmp ^ (tmp << 32)); | |
| evens = bits >> 64 | |
| odds = bits % 0x10000000000000000 | |
| return evens, odds | |
| def popcount_8(i): | |
| """ | |
| Counts the number of 1s in an 8-bit bitstring. | |
| """ | |
| i = i - ((i >> 1) & 0x55) | |
| i = (i & 0x33) + ((i >> 2) & 0x33) | |
| i = (i + (i >> 4)) & 0x0f | |
| return ((i * 0x01) & 0xff) | |
| def popcount_16(i): | |
| """ | |
| Counts the number of 1s in a 16-bit bitstring. | |
| """ | |
| i = i - ((i >> 1) & 0x5555) | |
| i = (i & 0x3333) + ((i >> 2) & 0x3333) | |
| i = (i + (i >> 4)) & 0x0f0f | |
| return ((i * 0x0101) & 0xffff) >> 8 | |
| def popcount_32(i): | |
| """ | |
| Counts the number of 1s in a 32-bit bitstring. | |
| """ | |
| i = i - ((i >> 1) & 0x55555555) | |
| i = (i & 0x33333333) + ((i >> 2) & 0x33333333) | |
| i = (i + (i >> 4)) & 0x0f0f0f0f | |
| return ((i * 0x01010101) & 0xffffffff) >> 24 | |
| def popcount_48(i): | |
| """ | |
| Counts the number of 1s in a 48-bit bitstring. | |
| """ | |
| i = i - ((i >> 1) & 0x555555555555) | |
| i = (i & 0x333333333333) + ((i >> 2) & 0x333333333333) | |
| i = (i + (i >> 4)) & 0x0f0f0f0f0f0f | |
| return ((i * 0x010101010101) & 0xffffffffffff) >> 40 | |
| def popcount_64(i): | |
| """ | |
| Counts the number of 1s in a 64-bit bitstring. | |
| """ | |
| i = i - ((i >> 1) & 0x5555555555555555) | |
| i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333) | |
| i = (i + (i >> 4)) & 0x0f0f0f0f0f0f0f0f | |
| return ((i * 0x0101010101010101) & 0xffffffffffffffff) >> 56 | |
| def popcount_96(i): | |
| """ | |
| Counts the number of 1s in a 96-bit bitstring. | |
| """ | |
| i = i - ((i >> 1) & 0x555555555555555555555555) | |
| i = (i & 0x333333333333333333333333) + ((i >> 2) & 0x333333333333333333333333) | |
| i = (i + (i >> 4)) & 0x0f0f0f0f0f0f0f0f0f0f0f0f | |
| return ((i * 0x010101010101010101010101) & 0xffffffffffffffffffffffff) >> 88 | |
| def popcount(x): | |
| """ | |
| Counts the number of 1s in a bitstring. | |
| """ | |
| x -= (x >> 1) & 0x5555555555555555 | |
| x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333) | |
| x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f | |
| return ((x * 0x0101010101010101) & 0xffffffffffffffff ) >> 56 | |
| # this function can be slow since it would only be called once | |
| # when the tournament is over. | |
| def make_mask_binary(results, teams_remaining): | |
| future_rounds = results & (2 ** (teams_remaining/2) - 1) | |
| mask = "" | |
| for res in bin(future_rounds)[2:]: # count from second MSB | |
| # if lower team wins, only care about lower team | |
| if res == "0": | |
| mask += "01" | |
| else: | |
| mask += "10" | |
| mask = mask[::-1] | |
| return int(mask, 2) | |
| def make_test(bracket, results, N=64): | |
| blacklist = int("1" * (N/2), 2) | |
| filt = make_mask_binary(results, N) | |
| return blacklist, filt | |
| def test_ncaa_scoring(): | |
| results = int("1" * 63, 2) | |
| bracket = int("1" * 63, 2) | |
| blacklist, filt = make_test(bracket, results) | |
| assert score(bracket, results, filt, 64, blacklist) == 192 | |
| bracket = int("0" * 31 + "1" * 32, 2) | |
| blacklist, filt = make_test(bracket, results) | |
| assert score(bracket, results, filt, 64, blacklist) == 32 | |
| bracket = int("1" * 15 + "0" * 16 + "1" * 32, 2) | |
| blacklist, filt = make_test(bracket, results) | |
| assert score(bracket, results, filt, 64, blacklist) == 32 | |
| bracket = int("1" * 15 + "01" * 8 + "1" * 32, 2) | |
| blacklist, filt = make_test(bracket, results) | |
| assert score(bracket, results, filt, 64, blacklist) == (192 - 2*8) | |
| bracket = int("1" * 15 + "10" * 8 + "1" * 32, 2) | |
| blacklist, filt = make_test(bracket, results) | |
| assert score(bracket, results, filt, 64, blacklist) == (32 + 2*8) | |
| for _ in range(10): | |
| s = "" | |
| for i in range(63): | |
| s += random.choice(["1", "0"]) | |
| bracket = int(s, 2) | |
| results = bracket | |
| assert score(bracket, results, filt, 64, blacklist) == 192 | |
| print "ncaa 64-team bracket tests pass" | |
| def test_knockout_stage_scoring(): | |
| print "Scenario: perfect bracket" | |
| print "Calculation: (4*2) + (2*4) + (1*8)" | |
| results = int("1111111", 2) | |
| bracket = int("1111111", 2) | |
| blacklist, filt = make_test(bracket, results, 8) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| print "---------" | |
| print "Total: " + str(final_score) | |
| print "---------\n" | |
| assert final_score == 24 | |
| print "Scenario: all of first round correct, all of second round correct, last round incorrect" | |
| print "Calculation: (4*2) + (2*4) + 0" | |
| bracket = int("0" + "11" + "1111", 2) | |
| blacklist, filt = make_test(bracket, results, 8) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| print "---------" | |
| print "Total: " + str(final_score) | |
| print "---------\n" | |
| assert final_score == 16 | |
| print "Scenario: all of first round correct, half of second round correct, last round correct (doens't count)" | |
| print "Calculation: (4*2) + (1*4)" | |
| bracket = int("1" + "10" + "1111", 2) | |
| blacklist, filt = make_test(bracket, results, 8) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| print "---------" | |
| print "Total: " + str(final_score) | |
| print "---------\n" | |
| assert final_score == 12 | |
| print "Scenario: all of first round correct, half of second round correct, last round correct (counts)" | |
| print "Calculation: (4*2) + (1*4) + (1*8)" | |
| bracket = int("1" + "01" + "1111", 2) | |
| blacklist, filt = make_test(bracket, results, 8) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| print "---------" | |
| print "Total: " + str(final_score) | |
| print "---------\n" | |
| assert final_score == 20 | |
| print "Scenario: all of first round correct, none of subsequent rounds correct" | |
| print "Calculation: (4*2) + 0 + 0" | |
| bracket = int("0" * 3 + "1" * 4, 2) | |
| blacklist, filt = make_test(bracket, results, 8) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| print "---------" | |
| print "Total: " + str(final_score) | |
| print "---------\n" | |
| assert final_score == 8 | |
| print "Scenario: half of first round correct, none of subsequent rounds correct" | |
| print "Calculation: (2*2) + 0 + 0" | |
| bracket = int("0" * 3 + "10" * 2, 2) | |
| blacklist, filt = make_test(bracket, results, 8) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| print "---------" | |
| print "Total: " + str(final_score) | |
| print "---------\n" | |
| assert final_score == 4 | |
| print "Scenario: half of first round correct, all subsequent rounds correct (counts)" | |
| print "Calculation: (2*2) + (2*4) + (1*8)" | |
| bracket = int("1" + "11" + "0101", 2) | |
| blacklist, filt = make_test(bracket, results, 8) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| print "---------" | |
| print "Total: " + str(final_score) | |
| print "---------\n" | |
| assert final_score == 20 | |
| print "Scenario: half of first round correct, all subsequent rounds correct (doesn't count)" | |
| print "Calculation: (2*2) + 0 + 0" | |
| bracket = int("1" + "11" + "1010", 2) | |
| blacklist, filt = make_test(bracket, results, 8) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| print "---------" | |
| print "Total: " + str(final_score) | |
| print "---------\n" | |
| assert final_score == 4 | |
| print "Scenario: 3/4 of first round correct, none of subsequent rounds correct" | |
| print "Calculation: (3*2) + 0 + 0" | |
| bracket = int("0" + "00" + "0111", 2) | |
| blacklist, filt = make_test(bracket, results, 8) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| print "---------" | |
| print "Total: " + str(final_score) | |
| print "---------\n" | |
| assert final_score == 6 | |
| print "Scenario: 3/4 of first round correct, all second round correct, last round incorrect" | |
| print "Calculation: (3*2) + (2*4) + 0" | |
| bracket = int("0" + "11" + "0111", 2) | |
| blacklist, filt = make_test(bracket, results, 8) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| print "---------" | |
| print "Total: " + str(final_score) | |
| print "---------\n" | |
| assert final_score == 14 | |
| print "Scenario: 3/4 of first round correct, half of second round correct, last round incorrect" | |
| print "Calculation: (3*2) + (1*4) + 0" | |
| bracket = int("0" + "01" + "0111", 2) | |
| blacklist, filt = make_test(bracket, results, 8) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| print "---------" | |
| print "Total: " + str(final_score) | |
| print "---------\n" | |
| assert final_score == 10 | |
| print "Scenario: 3/4 of first round correct, half of second round correct, last round correct (doesn't count)" | |
| print "Calculation: (3*2) + (1*4) + 0" | |
| bracket = int("1" + "10" + "0111", 2) | |
| blacklist, filt = make_test(bracket, results, 8) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| print "---------" | |
| print "Total: " + str(final_score) | |
| print "---------\n" | |
| assert final_score == 10 | |
| print "Scenario: 3/4 of first round correct, half of second round correct, last round correct (counts)" | |
| print "Calculation: (3*2) + (1*4) + (1*8)" | |
| bracket = int("1" + "01" + "0111", 2) | |
| blacklist, filt = make_test(bracket, results, 8) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| print "---------" | |
| print "Total: " + str(final_score) | |
| print "---------\n" | |
| assert final_score == 18 | |
| for _ in range(10): | |
| s = "" | |
| for i in range(7): | |
| s += random.choice(["1", "0"]) | |
| bracket = int(s, 2) | |
| results = bracket | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| assert final_score == 24 | |
| for _ in range(100): | |
| s = "" | |
| r = "" | |
| for i in range(7): | |
| s += random.choice(["1", "0"]) | |
| for j in range(7): | |
| r += random.choice(["1", "0"]) | |
| bracket = int(s, 2) | |
| results = int(r, 2) | |
| final_score = score(bracket, results, filt, 8, blacklist, 1) | |
| # all possible scores are even numbers between 0 and 24 | |
| assert 0 <= final_score <= 24 and final_score % 2 == 0 | |
| print "knockout stage tests pass" | |
| def test_get_odds_and_evens_8(): | |
| for _ in range(10): | |
| test_case = "" | |
| expected_odds = "" | |
| expected_evens = "" | |
| expected = 0 | |
| for i in range(8): | |
| next_bit = random.choice(["1", "0"]) | |
| if i % 2 != 0: | |
| expected_evens += next_bit | |
| else: | |
| expected_odds += next_bit | |
| test_case += next_bit | |
| (test_odds, test_evens) = get_odds_and_evens_8(int(test_case, 2)) | |
| # add padding as python automatically truncates leading 0s in binary | |
| padding_odds = "0" * (len(expected_odds) - len(bin(test_odds)[2:])) | |
| padding_evens = "0" * (len(expected_evens) - len(bin(test_evens)[2:])) | |
| assert padding_odds + bin(test_odds)[2:] == expected_odds | |
| assert padding_evens + bin(test_evens)[2:] == expected_evens | |
| print "get_odds_and_evens_8 tests pass" | |
| def test_get_odds_and_evens_16(): | |
| for _ in range(10): | |
| test_case = "" | |
| expected_odds = "" | |
| expected_evens = "" | |
| expected = 0 | |
| for i in range(16): | |
| next_bit = random.choice(["1", "0"]) | |
| if i % 2 != 0: | |
| expected_evens += next_bit | |
| else: | |
| expected_odds += next_bit | |
| test_case += next_bit | |
| (test_odds, test_evens) = get_odds_and_evens_16(int(test_case, 2)) | |
| # add padding as python automatically truncates leading 0s in binary | |
| padding_odds = "0" * (len(expected_odds) - len(bin(test_odds)[2:])) | |
| padding_evens = "0" * (len(expected_evens) - len(bin(test_evens)[2:])) | |
| assert padding_odds + bin(test_odds)[2:] == expected_odds | |
| assert padding_evens + bin(test_evens)[2:] == expected_evens | |
| print "get_odds_and_evens_16 tests pass" | |
| def test_get_odds_and_evens_32(): | |
| for _ in range(10): | |
| test_case = "" | |
| expected_odds = "" | |
| expected_evens = "" | |
| expected = 0 | |
| for i in range(32): | |
| next_bit = random.choice(["1", "0"]) | |
| if i % 2 != 0: | |
| expected_evens += next_bit | |
| else: | |
| expected_odds += next_bit | |
| test_case += next_bit | |
| (test_odds, test_evens) = get_odds_and_evens_32(int(test_case, 2)) | |
| # add padding as python automatically truncates leading 0s in binary | |
| padding_odds = "0" * (len(expected_odds) - len(bin(test_odds)[2:])) | |
| padding_evens = "0" * (len(expected_evens) - len(bin(test_evens)[2:])) | |
| assert padding_odds + bin(test_odds)[2:] == expected_odds | |
| assert padding_evens + bin(test_evens)[2:] == expected_evens | |
| print "get_odds_and_evens_32 tests pass" | |
| def test_get_odds_and_evens_64(): | |
| for _ in range(10): | |
| test_case = "" | |
| expected_odds = "" | |
| expected_evens = "" | |
| expected = 0 | |
| for i in range(64): | |
| next_bit = random.choice(["1", "0"]) | |
| if i % 2 != 0: | |
| expected_evens += next_bit | |
| else: | |
| expected_odds += next_bit | |
| test_case += next_bit | |
| (test_odds, test_evens) = get_odds_and_evens_64(int(test_case, 2)) | |
| # add padding as python automatically truncates leading 0s in binary | |
| padding_odds = "0" * (len(expected_odds) - len(bin(test_odds)[2:])) | |
| padding_evens = "0" * (len(expected_evens) - len(bin(test_evens)[2:])) | |
| assert padding_odds + bin(test_odds)[2:] == expected_odds | |
| assert padding_evens + bin(test_evens)[2:] == expected_evens | |
| print "get_odds_and_evens_64 tests pass" | |
| def test_get_odds_and_evens_96(): | |
| for _ in range(10): | |
| test_case = "" | |
| expected_odds = "" | |
| expected_evens = "" | |
| expected = 0 | |
| for i in range(96): | |
| next_bit = random.choice(["1", "0"]) | |
| if i % 2 != 0: | |
| expected_evens += next_bit | |
| else: | |
| expected_odds += next_bit | |
| test_case += next_bit | |
| (test_odds, test_evens) = get_odds_and_evens_96(int(test_case, 2)) | |
| # add padding as python automatically truncates leading 0s in binary | |
| padding_odds = "0" * (len(expected_odds) - len(bin(test_odds)[2:])) | |
| padding_evens = "0" * (len(expected_evens) - len(bin(test_evens)[2:])) | |
| print expected_evens | |
| print bin(test_evens)[2:] | |
| print expected_odds | |
| print bin(test_odds)[2:] | |
| # print expected_evens | |
| # print padding_evens + bin(test_evens)[2:] | |
| # print expected_odds | |
| # print padding_odds + bin(test_odds)[2:] | |
| assert padding_odds + bin(test_odds)[2:] == expected_odds | |
| assert padding_evens + bin(test_evens)[2:] == expected_evens | |
| print "get_odds_and_evens_96 tests pass" | |
| def test_get_odds_and_evens_128(): | |
| for _ in range(10): | |
| test_case = "" | |
| expected_odds = "" | |
| expected_evens = "" | |
| expected = 0 | |
| for i in range(128): | |
| next_bit = random.choice(["1", "0"]) | |
| if i % 2 != 0: | |
| expected_evens += next_bit | |
| else: | |
| expected_odds += next_bit | |
| test_case += next_bit | |
| (test_odds, test_evens) = get_odds_and_evens_128(int(test_case, 2)) | |
| # add padding as python automatically truncates leading 0s in binary | |
| padding_odds = "0" * (len(expected_odds) - len(bin(test_odds)[2:])) | |
| padding_evens = "0" * (len(expected_evens) - len(bin(test_evens)[2:])) | |
| assert padding_odds + bin(test_odds)[2:] == expected_odds | |
| assert padding_evens + bin(test_evens)[2:] == expected_evens | |
| print "get_odds_and_evens_128 tests pass" | |
| def test_popcount_8(): | |
| for _ in range(10): | |
| test_case = "" | |
| expected = 0 | |
| for i in range(8): | |
| next_bit = random.choice(["1", "0"]) | |
| if next_bit == "1": | |
| expected += 1 | |
| test_case += next_bit | |
| assert popcount_8(int(test_case, 2)) == expected | |
| print "popcount_8 tests pass" | |
| def test_popcount_16(): | |
| for _ in range(10): | |
| test_case = "" | |
| expected = 0 | |
| for i in range(16): | |
| next_bit = random.choice(["1", "0"]) | |
| if next_bit == "1": | |
| expected += 1 | |
| test_case += next_bit | |
| assert popcount_16(int(test_case, 2)) == expected | |
| print "popcount_16 tests pass" | |
| def test_popcount_32(): | |
| for _ in range(10): | |
| test_case = "" | |
| expected = 0 | |
| for i in range(32): | |
| next_bit = random.choice(["1", "0"]) | |
| if next_bit == "1": | |
| expected += 1 | |
| test_case += next_bit | |
| assert popcount_32(int(test_case, 2)) == expected | |
| print "popcount_32 tests pass" | |
| def test_popcount_48(): | |
| for _ in range(10): | |
| test_case = "" | |
| expected = 0 | |
| for i in range(48): | |
| next_bit = random.choice(["1", "0"]) | |
| if next_bit == "1": | |
| expected += 1 | |
| test_case += next_bit | |
| assert popcount_48(int(test_case, 2)) == expected | |
| print "popcount_48 tests pass" | |
| def test_popcount_64(): | |
| for _ in range(10): | |
| test_case = "" | |
| expected = 0 | |
| for i in range(64): | |
| next_bit = random.choice(["1", "0"]) | |
| if next_bit == "1": | |
| expected += 1 | |
| test_case += next_bit | |
| assert popcount_64(int(test_case, 2)) == expected | |
| print "popcount_64 tests pass" | |
| def test_popcount_96(): | |
| for _ in range(10): | |
| test_case = "" | |
| expected = 0 | |
| for i in range(96): | |
| next_bit = random.choice(["1", "0"]) | |
| if next_bit == "1": | |
| expected += 1 | |
| test_case += next_bit | |
| assert popcount_96(int(test_case, 2)) == expected | |
| print "popcount_96 tests pass" | |
| def test_group_stage_scoring(): | |
| for _ in range(10): | |
| test_bracket = "" | |
| test_result = "" | |
| expected_score = 0 | |
| for i in range(32): | |
| next_result = random.choice(["10", "01", "11"]) | |
| next_bracket = random.choice(["10", "01", "11"]) | |
| if next_bracket == next_result: | |
| expected_score += 1 | |
| test_bracket += next_bracket | |
| test_result += next_result | |
| test_score = score_group_stage(int(test_bracket, 2), int(test_result, 2)) | |
| assert test_score == expected_score | |
| print "group stage tests pass" | |
| test_popcount_8() | |
| test_popcount_16() | |
| test_popcount_32() | |
| test_popcount_48() | |
| test_popcount_64() | |
| test_popcount_96() | |
| test_get_odds_and_evens_8() | |
| test_get_odds_and_evens_16() | |
| test_get_odds_and_evens_32() | |
| test_get_odds_and_evens_64() | |
| # test_get_odds_and_evens_96() | |
| test_get_odds_and_evens_128() | |
| test_ncaa_scoring() | |
| test_group_stage_scoring() | |
| test_knockout_stage_scoring() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment