Created
November 22, 2013 14:06
-
-
Save hur1can3/7600382 to your computer and use it in GitHub Desktop.
I Failed a twitter interview http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/ python solution modification
This file contains hidden or 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
| import numpy as np | |
| from matplotlib import pyplot as plt | |
| import random | |
| import itertools | |
| # ground = [2, 5, 1, 3, 1, 2, 1, 7, 6] # data | |
| #ground = [2, 5, 1, 3, 1, 2, 1, 7, 6, 3, 1, 3] | |
| ground = [] | |
| solutions = [10, 17, 18, 0, 20, 20, 39, 42, 0, 0, 17, 25, | |
| 10, 4, 9, 9, 9, 9, 9, 12, 8, 2, 1, 5, 11, 11] | |
| ground.append([2, 5, 1, 2, 3, 4, 7, 7, 6]) | |
| ground.append([2, 5, 1, 3, 1, 2, 1, 7, 7, 6]) | |
| ground.append([5, 1, 3, 6, 1, 6, 1, 3, 1, 4]) | |
| ground.append([1, 2, 3, 4, 5, 5, 4, 3, 2, 1]) | |
| ground.append([9, 8, 7, 6, 5, 5, 6, 7, 8, 9]) | |
| ground.append([5, 4, 3, 2, 1, 1, 2, 3, 4, 5]) | |
| ground.append([6, 1, 1, 1, 7, 1, 1, 1, 1, 7]) | |
| ground.append([7, 1, 1, 1, 7, 1, 1, 1, 1, 7]) | |
| ground.append([1, 2, 3, 4, 5, 6, 7, 8]) | |
| ground.append([8, 7, 6, 5, 4, 3, 2, 1]) | |
| ground.append([5, 1, 3, 6, 1, 5, 1, 7, 6, 5]) | |
| ground.append([7, 1, 3, 6, 1, 5, 1, 7, 6, 5]) | |
| ground.append([3, 4, 7, 3, 4, 7, 6, 7, 2, 4]) | |
| ground.append([5, 1, 4, 2, 3]) | |
| ground.append([6, 1, 5, 2, 1, 4]) | |
| ground.append([4, 1, 2, 5, 1, 6]) | |
| ground.append([7, 1, 5, 2, 1, 4]) | |
| ground.append([7, 1, 5, 2, 1, 4, 2]) | |
| ground.append([7, 1, 5, 2, 1, 4, 3, 2]) | |
| ground.append([5, 1, 5, 1, 5, 1, 5]) | |
| ground.append([1, 5, 1, 5, 1, 5, 1]) | |
| ground.append([5, 1, 3]) | |
| ground.append([0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1]) | |
| ground.append([2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1]) | |
| ground.append([3, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1]) | |
| ground.append([2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 1]) | |
| def waterfillit(walls): | |
| max_right = walls[0] | |
| water_total = 0 | |
| water_temp = 0 | |
| for i in walls: | |
| if i >= max_right: | |
| water_total += water_temp | |
| water_temp = 0 | |
| max_right = i | |
| elif i < max_right: | |
| water_temp += max_right - i | |
| print water_total | |
| return water_total | |
| def waterfill(walls): | |
| land = np.zeros((len(walls), max(walls)), dtype=int) | |
| # Put the walls | |
| for index, value in enumerate(walls): | |
| land[index, 0:value] = 2 | |
| # Drop water | |
| land[land == 0] = 1 | |
| # Remove flowed-out water | |
| for height in range(0, max(walls))[::-1]: | |
| left_max = land[:, height].argmax() | |
| right_max = len(walls) - land[:, height][::-1].argmax() | |
| land[:left_max, height] = 0 | |
| land[right_max:, height] = 0 | |
| water_total = len(land[land == 1]) | |
| print water_total | |
| return water_total | |
| def waterfill_with_plots(walls): | |
| land = np.zeros((len(walls), max(walls)), dtype=int) | |
| fig = plt.figure() | |
| # Put the walls | |
| for index, value in enumerate(walls): | |
| land[index, 0:value] = 2 | |
| dry_land = np.copy(land) | |
| dry_fig = fig.add_subplot(1, 2, 1) | |
| dry_fig.imshow(np.transpose(dry_land), | |
| origin="lower", | |
| interpolation="none") | |
| # Drop water | |
| land[land == 0] = 1 | |
| # Remove flowed-out water | |
| for height in range(0, max(walls))[::-1]: | |
| left_max = land[:, height].argmax() | |
| right_max = len(walls) - land[:, height][::-1].argmax() | |
| land[:left_max, height] = 0 | |
| land[right_max:, height] = 0 | |
| wet_fig = fig.add_subplot(1, 2, 2) | |
| wet_fig.imshow(np.transpose(land), | |
| origin="lower", | |
| interpolation="none") | |
| water_total = len(land[land == 1]) | |
| fig.suptitle("{} filled blocks".format(water_total)) | |
| plt.show() | |
| print water_total | |
| return water_total | |
| def test_solution(total, solution): | |
| if total == solution: | |
| return True | |
| return False | |
| def shuffle(ary): | |
| a = len(ary) | |
| b = a - 1 | |
| for d in range(b, 0, -1): | |
| e = random.randint(0, d) | |
| if e == d: | |
| continue | |
| ary[d], ary[e] = ary[e], ary[d] | |
| return ary | |
| def valid_combination(combination): | |
| return len(combination) > 0 and combination[0] > combination[1] and combination[1] < combination[2] | |
| def product_with_validation(validation_func, *element_list): | |
| return (combination for combination in itertools.product(*element_list) | |
| if valid_combination(combination)) | |
| for i, g in enumerate(ground): | |
| print g | |
| print solutions[i] | |
| print test_solution(waterfill_with_plots(g), solutions[i]) | |
| max_val = 30 | |
| min_val = 1 | |
| # t = range(min_val, max_val) | |
| # t = list(product_with_validation(valid_combination, | |
| # range(min_val, max_val), range(min_val, max_val))) | |
| # for L in range(0, len(t) + 1): | |
| # for subset in itertools.combinations(t, L): | |
| # print subset | |
| # if len(subset) > 2: | |
| # waterfill_with_plots(subset) | |
| # np.random.shuffle(t) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment