Pythonic solutions to the Facebook Hacker Cup 2014 Qualification Round

Facebook organizes this cool competition called the Hacker Cup. Yesterday the Qualification Round finished, and the user solutions got published. So, since the problems text is under a CC license (thanks FB!) I’m publishing here the problems and my answers.

This code pretty much embodies why I love Python: it’s clear, fast to write and reads almost like English. When I (thought I) needed speed, I just turned at Cython with a few edits to the code.

NOTE: if for some reason I misunderstood and I wasn’t allowed to do this, please get in contact with me ASAP and I’ll take this down.

Square Detector

Read the problem and check out the test cases and the answer.

This was an easy one, I just scanned the grid until I found a #, assumed it was the upper-left corner and counted the following # to learn the edge length. At this point I had all the info to build a model of how a correct grid should look like, so I just checked the real one against it.

#!/usr/bin/env python3 #-*- coding:utf-8 -*- import sys T = int(sys.stdin.readline().strip()) for t in range(1, T + 1): N = int(sys.stdin.readline().strip()) GRID = [sys.stdin.readline().strip() for i in range(N)] # Find the the upper-left corner (J, I) and the edge K for I, row in enumerate(GRID): if not '#' in row: continue K = 0 J = row.index('#') for x in range(J, N): if row[x] == '#': K += 1 else: break break # If the square would not fit, fail if I + K > N: print('Case #%i: NO' % t) continue # Build a module of how a row including the square should look like MOD = (J * '.' + K * '#').ljust(N, '.') # Check that the grid looks like what it should for i, row in enumerate(GRID): if i >= I and i < I + K: if row != MOD: break else: if row != N * '.': break else: # Reached if we didn't break out of the loop # Ok, I'll admit that for-else is not that clear print('Case #%i: YES' % t) continue print('Case #%i: NO' % t)

Basketball Game

Read the problem and check out the test cases and the answer.

This is actually my favorite. The problem was fun and the Python code reads as if it was English. It makes hard use of mutable objects and their properties.

#!/usr/bin/env python3 #-*- coding:utf-8 -*- import sys INPUT = open(sys.argv[1]) class Player(): name = None shot_percentage = None height = None draft = None time_played = 0 T = int(INPUT.readline().strip()) for t in range(1, T + 1): N, M, P = [int(x) for x in INPUT.readline().strip().split(' ')] PLAYERS = [] for _ in range(N): player = Player() player.name, s, h = INPUT.readline().strip().split(' ') player.shot_percentage, player.height = int(s), int(h) PLAYERS.append(player) PLAYERS.sort(reverse=True, key=lambda p: (p.shot_percentage, p.height)) for n, p in enumerate(PLAYERS): p.draft = n + 1 TEAM_A = [p for p in PLAYERS if p.draft % 2 != 0] TEAM_B = [p for p in PLAYERS if p.draft % 2 == 0] PLAYING_A = TEAM_A[:P] PLAYING_B = TEAM_B[:P] for _ in range(M): for TEAM, PLAYING in ((TEAM_A, PLAYING_A), (TEAM_B, PLAYING_B)): if len(TEAM) == len(PLAYING): continue for p in PLAYING: p.time_played += 1 BENCH = [p for p in TEAM if p not in PLAYING] leaving = sorted(PLAYING, key=lambda p: (p.time_played, p.draft))[-1] entering = sorted(BENCH, key=lambda p: (p.time_played, p.draft))[0] PLAYING.remove(leaving) PLAYING.append(entering) BENCH.remove(entering) BENCH.append(leaving) print('Case #%i: ' % t + ' '.join(sorted(p.name for p in PLAYING_A + PLAYING_B)))

Tennison

Read the problem and check out the test cases and the answer.

Finally the hardest one. This was a nice recursive problem. The constrains allowed for a lot of big test cases, so I went a bit overkill with speed, wrote some custom caching, ported my actual recursive function to Cython (it’s awesome! Just check out the -a HTML output to figure out what you have to optimize and you’re done) and made the program parallelizable.

Turns out, memoization would have been enough. Still, it has been really fun!

#!/usr/bin/env python3 #-*- coding:utf-8 -*- import pyximport; pyximport.install() from fast_Tennison import play_a_set from multiprocessing import Pool import sys T = int(sys.stdin.readline().strip()) TEST_CASES = [] for t in range(1, T + 1): l = sys.stdin.readline().strip().split(' ') K = int(l[0]) ps, pr, pi, pu, pw, pd, pl = (float(x) for x in l[1:]) won, lost = 0, 0 TEST_CASES.append((t, {}, K, won, lost, pi, ps, pr, pu, pw, pd, pl)) def do(x): r = play_a_set(*x[1:]) sys.stderr.write('#{}: {:f}\n'.format(x[0], r)) return r pool = Pool(processes=8) RESULTS = pool.map(do, TEST_CASES, chunksize=1) for t in range(1, T + 1): print('Case #{}: {:f}'.format(t, RESULTS[t-1]))

cpdef double play_a_set(cache, int K, int won, int lost, double p_sun, double ps, double pr, double pu, double pw, double pd, double pl): cdef double new_p_sun, positive if won == K: return 1 if lost == K: return 0 if won * 1000 + lost * 10 + p_sun in cache: return cache[won * 1000 + lost * 10 + p_sun] positive = 0 ## There is sun P: p_sun #### He wins P: ps ###### p_sun changes P: pw new_p_sun = min(1, p_sun + pu) positive += p_sun * ps * pw * play_a_set(cache, K, won+1, lost, new_p_sun, ps, pr, pu, pw, pd, pl) ###### p_sun stays P: 1 - pw positive += p_sun * ps * (1 - pw) * play_a_set(cache, K, won+1, lost, p_sun, ps, pr, pu, pw, pd, pl) #### He loses P: 1 - ps ###### p_sun changes P: pl new_p_sun = max(0, p_sun - pd) positive += p_sun * (1 - ps) * pl * play_a_set(cache, K, won, lost+1, new_p_sun, ps, pr, pu, pw, pd, pl) ###### p_sun stays P: 1 - pl positive += p_sun * (1 - ps) * (1 - pl) * play_a_set(cache, K, won, lost+1, p_sun, ps, pr, pu, pw, pd, pl) ## There is rain P: 1 - p_sun #### He wins P: pr ###### p_sun changes P: pw new_p_sun = min(1, p_sun + pu) positive += (1 - p_sun) * pr * pw * play_a_set(cache, K, won+1, lost, new_p_sun, ps, pr, pu, pw, pd, pl) ###### p_sun stays P: 1 - pw positive += (1 - p_sun) * pr * (1 - pw) * play_a_set(cache, K, won+1, lost, p_sun, ps, pr, pu, pw, pd, pl) #### He loses P: 1 - pr ###### p_sun changes P: pl new_p_sun = max(0, p_sun - pd) positive += (1 - p_sun) * (1 - pr) * pl * play_a_set(cache, K, won, lost+1, new_p_sun, ps, pr, pu, pw, pd, pl) ###### p_sun stays P: 1 - pl positive += (1 - p_sun) * (1 - pr) * (1 - pl) * play_a_set(cache, K, won, lost+1, p_sun, ps, pr, pu, pw, pd, pl) cache[won * 1000 + lost * 10 + p_sun] = positive return positive

That’s all! I got admitted to the next round, so maybe follow me on Twitter if you want to read the next batch of problems and solutions!

PyTux

Trips of a curious penguin.

Pythonic solutions to the Facebook Hacker Cup 2014 Qualification Round

Square Detector

Basketball Game

Tennison