Facebook Hacker Cup 2015 Solutions Python

In case you are wondering how to solve the problem of Facebook Hacker Cup 2015 Edition, here follows my simple solutions using in Python. I just copy pasted the code from my editor ;) No explanation the code is pretty self-explanatory and very easy to follow. I hope you find them useful.

Cooking the Books

Look at the Problem statement (official link)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

def main(contents):
    output = ""
    it = iter(contents.splitlines())
    num_testcases = int(it.next())

    for testcase in xrange(1, num_testcases + 1):
        n = list(it.next())
        l = u = int(''.join(n))

        for i in xrange(len(n)):
            for j in xrange(i + 1, len(n)):
                n[i], n[j] = n[j], n[i]

                if n[0] == '0':
                    continue

                l = min(int(''.join(n)), l)
                u = max(int(''.join(n)), u)

                n[i], n[j] = n[j], n[i]

        output += "Case #%d: %d %d\n" % (testcase, l, u)

    return output


input_file = """5
31524
897
123
10
5
"""

assert main(input_file) == """Case #1: 13524 51324
Case #2: 798 987
Case #3: 123 321
Case #4: 10 10
Case #5: 5 5
"""

New Year's Resolution

Look at the Problem statement (official link)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

def solve(gp, gc, gf, xs):
    if gp == 0 and gc == 0 and gf == 0:
        return True

    if gp < 0 or gc < 0 or gf < 0:
        return False

    if not xs:
        return False

    p, c, f = xs[0]
    xs = xs[1:]

    return solve(gp - p, gc - c, gf - f, xs) or solve(gp, gc, gf, xs)


def main(contents):
    output = ""
    it = iter(contents.splitlines())
    num_testcases = int(it.next())

    for testcase in xrange(1, num_testcases + 1):
        gp, gc, gf = map(int, it.next().split())
        n = int(it.next())

        xs = []

        for i in xrange(n):
            tup = map(int, it.next().split())
            xs.append(tup)

        xs.sort(key=lambda x: x[0])
        solvable = solve(gp, gc, gf, xs)

        output += "Case #%d: %s\n" % (testcase, solvable and "yes" or "no")

    return output


input_file = """5
100 100 100
1
100 100 100
100 100 100
3
10 10 40
10 30 10
10 60 50
100 100 100
5
40 70 30
30 10 40
20 20 50
10 50 90
40 10 20
292 264 512
20
909 302 261
705 597 823
291 51 126
28 697 57
593 31 826
311 256 57
292 14 47
29 730 716
12 529 146
768 16 439
37 472 15
350 192 34
163 468 238
69 173 10
203 72 690
424 875 213
223 593 292
151 46 10
88 90 16
773 653 711
991 827 352
20
29 560 929
139 681 102
144 853 10
84 729 80
218 20 67
140 80 901
428 20 500
520 970 128
422 419 30
413 101 192
467 448 501
32 939 684
34 20 38
251 317 132
588 437 10
648 21 79
391 25 14
499 22 24
854 77 361
405 25 20
"""

assert main(input_file) == """Case #1: yes
Case #2: no
Case #3: yes
Case #4: no
Case #5: yes
"""

Laser Maze

Look at the Problem statement (official link)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

import sys

MOVES = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def turn_lasers(lasers):
    trans = {
        '<': '^',
        '^': '>',
        '>': 'v',
        'v': '<'
    }
    return [(i, j, trans[t]) for i, j, t in lasers]


def was_hit(x, y, lasers):
    for lx, ly, t in lasers:
        if lx == x:
            if t == '<' and y <= ly:
                return True
            if t == '>' and y >= ly:
                return True

        if ly == y:
            if t == '^' and x <= lx:
                return True
            if t == 'v' and x >= lx:
                return True

    return False


def solve_maze(ts, maze, lasers, visited, x, y, end):
    lasers = turn_lasers(lasers)
    dead = was_hit(x, y, lasers)

    if x < 0 or y < 0 or x >= len(maze) or y >= len(maze[0]) or \
       dead or (x, y, ts % 4) in visited:
        return sys.maxint

    if (x, y) == end:
        return 0

    # We also consider laser positions in the state space
    visited.add((x, y, ts % 4))

    return 1 + min(
        (solve_maze(ts + 1, maze, lasers, visited, x + i, y + j, end)
            for i, j in MOVES)
    )


def main(contents):
    output = ""
    it = iter(contents.splitlines())
    num_testcases = int(it.next())

    for testcase in xrange(1, num_testcases + 1):
        h, w = map(int, it.next().split())

        maze = []
        lasers = []
        beg = None
        end = None

        for i in xrange(h):
            line = []
            for j, ch in enumerate(it.next()):
                line.append(ch)

                if ch == 'S':
                    beg = (i, j)
                if ch == 'G':
                    end = (i, j)
                if ch in '<>^v':
                    lasers.append((i, j, ch))

            maze.append(line)

        steps = min(
            solve_maze(0, maze, lasers, set(), beg[0] + 1, beg[1] + 0, end),
            solve_maze(0, maze, lasers, set(), beg[0] + 0, beg[1] + 1, end),
            solve_maze(0, maze, lasers, set(), beg[0] - 1, beg[1] + 0, end),
            solve_maze(0, maze, lasers, set(), beg[0] + 0, beg[1] - 1, end),
        )

        output += "Case #%d: %s\n" % (
            testcase,
            (steps == sys.maxint) and "impossible" or str(steps + 1)
        )

    return output

input_file = """5
2 5
##^##
S...G
2 5
##v##
S...G
1 5
S..G<
1 6
S...G<
5 5
S....
.....
.>v..
.^<..
....G
"""

output_file = """Case #1: 6
Case #2: 4
Case #3: 3
Case #4: impossible
Case #5: 8
"""

output = main(input_file)
assert output == output_file