Last active
January 22, 2016 19:21
-
-
Save khannotations/d5ac9009948bd7e3dca4 to your computer and use it in GitHub Desktop.
Rafi's Solution to the HackerRank Problem "Markov Snakes and Ladders"
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
| #!/usr/bin/python | |
| # For hackerrank.com/challenges/markov-snakes-and-ladders | |
| # Uses a simulation. Other possible solutions could use probabilities simply | |
| # compute the answer. | |
| import fileinput | |
| from random import random | |
| class Board: | |
| def __init__(self, slides): | |
| self.current = 1 | |
| self.slides = {} | |
| for p in slides: | |
| start, end = [int(x) for x in p.split(",")] | |
| self.slides[start] = end | |
| def move(self, num): | |
| if self.current + num <= 100: | |
| self.current += num | |
| if self.current in self.slides: | |
| self.current = self.slides[self.current] | |
| return self.current | |
| class Die: | |
| def __init__(self, probs): | |
| self.probs = [float(x) for x in probs] | |
| # if sum(self.probs) != 1.0: | |
| # raise ValueError("Die: Probabilities don't add to one (%s)" % sum(self.probs)) | |
| def roll(self): | |
| rand = random() | |
| for index, prob in enumerate(self.probs): | |
| if rand < prob: | |
| return index + 1 | |
| rand -= prob | |
| return 6 | |
| def play(probs, ladders, snakes): | |
| board = Board(ladders + snakes) | |
| die = Die(probs) | |
| num_moves = 0 | |
| while num_moves < 1000 and board.move(die.roll()) != 100: | |
| num_moves += 1 | |
| return num_moves | |
| def parse_params(): | |
| lines = fileinput.input() | |
| num_tests = int(lines[0]) | |
| tests = [] | |
| i = 0 | |
| while i < num_tests: | |
| probs = lines[4*i + 1].strip().split(",") | |
| num_ladders, num_snakes = lines[4*i + 2].strip().split(",") | |
| ladder_starts = lines[4*i + 3].strip().split(" ") | |
| snake_starts = lines[4*i + 4].strip().split(" ") | |
| # if int(num_ladders) != len(ladder_starts): | |
| # print("ladders:", num_ladders, "actual:", len(ladder_starts)) | |
| # raise ValueError("Number of ladders mismatch") | |
| # if int(num_snakes) != len(snake_starts): | |
| # raise ValueError("Number of snakes mismatch") | |
| tests.append([probs, ladder_starts, snake_starts]) | |
| i += 1 | |
| return tests | |
| def main(): | |
| tests = parse_params() | |
| for params in tests: | |
| sum = 0 | |
| num_trials = 0 | |
| for i in range(5000): # 5000 trials | |
| num_moves = play(*params) | |
| if num_moves < 1000: | |
| sum += num_moves | |
| num_trials += 1 | |
| print (sum / num_trials) | |
| if __name__ == "__main__": | |
| main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment