FazeCT Day 12: Christmas Tree Farm
The challenge
You're almost out of time, but there can't be much left to decorate. Although there are no stairs, elevators, escalators, tunnels, chutes, teleporters, firepoles, or conduits here that would take you deeper into the North Pole base, there is a ventilation duct. You jump in.
After bumping around for a few minutes, you emerge into a large, well-lit cavern full of Christmas trees!
There are a few Elves here frantically decorating before the deadline. They think they'll be able to finish most of the work, but the one thing they're worried about is the presents for all the young Elves that live here at the North Pole. It's an ancient tradition to put the presents under the trees, but the Elves are worried they won't fit.
The presents come in a few standard but very weird shapes. The shapes and the regions into which they need to fit are all measured in standard units. To be aesthetically pleasing, the presents need to be placed into the regions in a way that follows a standardized two-dimensional unit grid; you also can't stack presents.
As always, the Elves have a summary of the situation (your puzzle input) for you. First, it contains a list of the presents' shapes. Second, it contains the size of the region under each tree and a list of the number of presents of each shape that need to fit into that region. For example:
0:
###
##.
##.
1:
###
##.
.##
2:
.##
###
##.
3:
##.
###
##.
4:
###
#..
###
5:
###
.#.
###
4x4: 0 0 0 0 2 0
12x5: 1 0 1 0 2 2
12x5: 1 0 1 0 3 2
The first section lists the standard present shapes. For convenience, each shape starts with its index and a colon; then, the shape is displayed visually, where # is part of the shape and . is not.
The second section lists the regions under the trees. Each line starts with the width and length of the region; 12x5 means the region is 12 units wide and 5 units long. The rest of the line describes the presents that need to fit into that region by listing the quantity of each shape of present; 1 0 1 0 3 2 means you need to fit one present with shape index 0, no presents with shape index 1, one present with shape index 2, no presents with shape index 3, three presents with shape index 4, and two presents with shape index 5.
Presents can be rotated and flipped as necessary to make them fit in the available space, but they have to always be placed perfectly on the grid. Shapes can't overlap (that is, the # part from two different presents can't go in the same place on the grid), but they can fit together (that is, the . part in a present's shape's diagram does not block another present from occupying that space on the grid).
The Elves need to know how many of the regions can fit the presents listed. In the above example, there are six unique present shapes and three regions that need checking.
The first region is 4x4:
....
....
....
....
In it, you need to determine whether you could fit two presents that have shape index 4:
###
#..
###
After some experimentation, it turns out that you can fit both presents in this region. Here is one way to do it, using A to represent one present and B to represent the other:
AAA.
ABAB
ABAB
.BBB
The second region, 12x5: 1 0 1 0 2 2, is 12 units wide and 5 units long. In that region, you need to try to fit one present with shape index 0, one present with shape index 2, two presents with shape index 4, and two presents with shape index 5.
It turns out that these presents can all fit in this region. Here is one way to do it, again using different capital letters to represent all the required presents:
....AAAFFE.E
.BBBAAFFFEEE
DDDBAAFFCECE
DBBB....CCC.
DDD.....C.C.
The third region, 12x5: 1 0 1 0 3 2, is the same size as the previous region; the only difference is that this region needs to fit one additional present with shape index 4. Unfortunately, no matter how hard you try, there is no way to fit all of the presents into this region.
So, in this example, 2 regions can fit all of their listed presents.
Consider the regions beneath each tree and the presents the Elves would like to fit into each of them. How many of the regions can fit all of the presents listed?0:
###
#.#
#.#
1:
#.#
###
#.#
2:
.##
###
#.#
3:
.##
##.
#..
4:
###
##.
##.
5:
###
.##
..#
35x43: 24 20 20 32 26 32
38x41: 31 27 25 28 18 26
42x44: 33 27 29 31 43 33
48x41: 35 26 37 41 39 29
38x36: 30 25 23 21 25 19
35x45: 27 28 37 17 32 23
36x49: 37 48 42 59 47 42
45x37: 33 56 34 29 54 47
39x46: 36 27 25 41 35 30
43x46: 36 38 37 31 33 34
37x35: 33 30 35 30 42 28
35x35: 16 14 25 24 21 20
46x42: 49 58 49 46 42 53
48x36: 30 40 29 25 33 34
47x37: 25 36 33 26 29 30
48x49: 37 36 50 44 38 50
42x36: 39 41 41 28 41 40
43x35: 26 37 17 19 24 31
43x38: 23 29 26 30 23 37
43x49: 30 48 45 32 47 22
38x45: 38 45 42 52 43 46
50x39: 55 42 45 42 57 58
42x44: 29 40 28 27 34 38
48x46: 52 61 69 55 54 47
49x39: 48 45 55 57 41 51
47x42: 35 41 28 33 40 33
42x47: 61 49 47 52 46 49
49x43: 43 38 35 45 32 30
36x39: 28 32 25 29 15 26
36x46: 52 45 38 43 43 33
38x37: 51 40 36 33 30 24
37x42: 32 31 34 35 16 19
44x43: 44 47 56 53 48 44
42x43: 28 50 28 28 30 32
41x47: 54 48 51 37 55 48
35x43: 23 29 29 22 27 24
40x46: 36 28 29 48 25 29
44x48: 34 38 32 36 44 39
36x36: 24 15 21 31 25 27
50x46: 31 42 40 45 40 42
35x38: 19 24 26 19 21 23
48x39: 37 32 33 37 39 30
36x36: 29 24 25 26 20 20
45x37: 35 27 37 19 31 31
36x43: 36 41 43 40 41 37
47x43: 56 61 44 47 56 45
50x50: 48 66 63 81 59 74
37x48: 30 30 31 25 31 45
41x42: 32 33 25 31 34 26
47x35: 44 42 38 43 37 51
41x44: 48 41 48 35 54 49
38x35: 40 24 36 37 34 35
49x40: 48 47 47 44 58 57
47x48: 29 56 46 36 30 42
47x36: 37 44 39 51 46 46
43x47: 51 48 55 48 51 58
43x48: 44 36 34 45 31 33
41x46: 46 45 45 41 64 47
49x42: 54 34 41 39 29 27
49x40: 30 34 42 29 40 32
49x41: 35 37 25 38 38 34
41x36: 28 42 51 29 35 40
35x37: 19 25 20 24 26 17
49x39: 36 31 39 28 36 38
36x45: 32 23 27 27 35 36
39x35: 25 23 23 30 22 19
37x49: 40 31 29 28 27 37
49x40: 27 38 37 38 35 32
36x49: 31 36 30 30 35 29
44x49: 49 38 21 46 31 39
47x46: 67 65 49 48 50 51
43x47: 67 48 51 54 50 40
38x42: 27 20 37 24 23 36
41x47: 30 34 29 36 37 29
45x46: 44 46 61 52 58 58
48x37: 35 31 27 33 35 31
36x40: 43 33 38 30 44 31
40x39: 36 41 34 45 38 49
45x42: 42 44 54 48 48 56
43x38: 32 26 25 29 26 29
47x47: 53 59 55 67 54 55
35x38: 33 37 38 32 27 38
39x45: 29 31 35 32 34 33
46x46: 50 54 49 60 52 64
50x37: 57 46 53 43 42 42
44x38: 31 22 21 29 26 38
44x42: 58 48 39 50 46 44
41x48: 52 41 56 53 51 51
42x36: 42 40 38 40 30 44
41x35: 38 28 34 39 44 39
46x39: 34 26 29 30 31 44
41x47: 42 32 32 31 22 35
41x39: 24 20 27 33 40 24
48x44: 60 59 53 56 47 50
35x48: 42 48 46 36 35 51
50x36: 56 40 52 51 37 42
39x47: 45 43 42 56 52 47
45x35: 39 44 41 35 37 46
46x46: 22 40 38 43 37 45
35x39: 28 20 22 24 24 24
38x40: 35 37 41 45 38 40
48x39: 31 40 36 31 36 34
44x47: 33 39 30 39 39 29
42x44: 40 46 47 48 50 55
44x45: 43 57 50 41 61 50
46x43: 46 51 53 59 54 43
39x44: 26 43 20 28 31 33
46x36: 39 47 44 32 49 41
38x42: 28 30 24 23 38 25
45x49: 47 48 30 40 39 36
42x43: 29 34 27 39 34 33
44x47: 56 55 60 56 42 50
39x42: 35 24 37 28 27 31
35x44: 20 27 28 19 35 25
35x41: 30 22 19 24 25 22
35x38: 42 37 29 48 19 34
45x38: 24 28 32 31 37 27
48x41: 41 46 48 63 51 59
35x44: 38 45 40 36 33 45
36x49: 31 39 32 33 29 28
43x42: 51 45 55 45 40 41
40x49: 37 48 55 52 55 56
38x45: 30 31 29 30 31 29
49x42: 59 45 52 55 57 49
35x48: 27 21 26 35 34 32
47x42: 39 55 62 45 53 48
43x49: 58 63 52 45 54 49
49x45: 59 55 54 60 52 61
47x50: 46 40 34 46 41 32
50x38: 50 45 55 51 44 48
39x44: 41 41 43 52 48 41
40x43: 34 49 47 43 51 40
43x35: 19 35 27 24 25 23
42x48: 32 38 40 35 34 45
42x41: 39 50 45 42 49 39
48x35: 24 31 32 27 37 24
38x45: 43 46 42 37 46 48
42x36: 39 44 34 36 36 44
41x46: 49 40 53 55 54 40
35x49: 38 41 52 42 45 46
47x49: 40 35 46 35 41 43
44x43: 46 50 52 50 57 35
50x39: 54 51 41 46 51 57
45x41: 45 54 41 33 55 53
37x48: 30 37 37 32 30 26
44x46: 32 36 36 28 46 31
36x47: 29 30 39 19 31 31
38x38: 31 40 43 42 35 32
37x36: 33 21 23 21 21 25
35x46: 51 32 33 53 37 46
46x46: 37 39 37 37 37 37
38x50: 29 26 32 37 36 32
40x35: 37 36 32 38 32 42
39x41: 40 51 36 40 37 42
35x44: 36 36 38 50 41 39
36x44: 28 33 32 29 19 27
42x45: 46 50 51 45 49 49
43x38: 27 20 29 30 32 29
50x38: 30 39 23 41 31 27
41x37: 39 41 35 41 35 44
43x35: 25 26 28 21 28 26
44x43: 50 35 42 60 52 57
44x48: 39 34 39 36 44 32
43x41: 31 45 51 40 59 44
43x46: 53 56 47 43 55 48
50x47: 66 55 65 66 54 57
36x42: 34 21 38 22 33 20
41x46: 36 50 57 51 44 54
38x49: 47 45 53 50 42 51
39x49: 27 28 37 44 35 37
42x38: 45 45 48 33 35 37
44x36: 28 40 42 45 51 39
39x38: 23 25 32 24 26 26
43x44: 51 52 45 50 51 42
42x44: 28 27 29 44 27 40
44x38: 22 34 31 28 21 32
36x48: 30 43 29 31 24 34
50x36: 35 41 28 24 28 36
35x47: 30 31 23 29 18 33
48x46: 43 44 50 26 43 33
49x43: 61 52 62 48 44 56
36x36: 24 19 29 25 17 29
48x37: 50 51 40 36 52 41
36x40: 38 33 45 39 39 27
39x39: 36 33 22 24 36 18
43x47: 33 35 32 43 29 38
38x36: 28 20 23 25 31 17
38x38: 23 26 34 17 25 18
40x37: 29 33 21 30 28 14
37x36: 34 41 35 37 25 34
36x39: 41 40 34 26 32 41
50x43: 66 36 63 63 39 68
46x50: 67 58 62 67 57 43
47x45: 36 35 45 38 40 30
39x36: 36 38 29 31 45 36
48x43: 29 37 32 43 36 46
39x50: 43 30 38 32 36 29
50x38: 50 51 42 58 52 41
42x43: 32 40 36 30 34 24
44x35: 23 18 26 31 29 26
39x35: 34 31 29 35 36 47
46x46: 28 41 47 39 37 32
40x43: 26 27 32 39 27 31
41x47: 37 26 32 34 31 34
50x46: 58 68 62 62 46 59
42x46: 38 31 33 32 39 36
47x38: 37 21 24 31 37 30
37x42: 22 29 22 40 34 21
46x44: 31 34 38 44 36 27
46x48: 66 44 55 46 64 63
37x42: 33 21 27 33 37 17
41x39: 37 45 41 52 35 39
46x38: 40 34 57 50 54 34
42x37: 23 21 30 32 26 35
38x42: 47 42 37 39 41 39
49x46: 39 38 32 39 49 43
39x37: 31 31 24 21 18 30
44x38: 28 27 29 26 28 30
48x42: 38 41 35 32 36 42
44x40: 42 45 37 51 52 46
47x48: 38 33 47 45 42 35
46x40: 48 53 47 52 41 43
38x47: 44 61 38 46 42 44
40x45: 31 34 29 31 30 39
40x45: 38 29 26 38 28 36
44x39: 45 39 42 47 43 50
39x50: 38 36 32 40 28 33
39x48: 19 48 33 30 45 33
37x40: 21 27 20 30 22 35
43x38: 34 52 42 42 39 43
45x41: 36 38 33 34 31 22
37x44: 26 29 26 27 32 28
42x35: 27 20 31 24 26 26
38x36: 32 35 40 31 41 30
50x35: 39 30 30 26 24 27
38x50: 54 43 55 32 49 56
45x40: 31 38 35 32 31 27
41x50: 58 61 47 52 42 56
50x40: 56 54 54 57 42 46
42x46: 55 56 38 47 51 50
40x43: 31 23 31 33 34 30
40x49: 46 45 54 55 48 56
38x49: 46 43 52 50 44 53
45x48: 54 53 54 53 55 64
38x39: 42 43 37 37 32 37
42x41: 24 31 28 34 34 30
43x42: 50 32 36 28 28 22
38x39: 40 36 35 37 35 46
47x46: 27 41 46 40 34 36
45x50: 45 38 43 41 29 44
48x36: 44 51 48 35 44 41
38x40: 36 41 36 43 36 44
35x42: 35 40 34 43 39 37
41x44: 30 28 31 30 36 27
45x44: 30 33 38 41 37 31
48x49: 55 65 64 66 52 62
43x50: 57 66 55 49 55 46
42x41: 50 41 50 38 43 41
43x37: 25 23 34 25 32 29
49x48: 38 32 39 48 52 47
41x50: 49 51 52 58 57 50
50x48: 59 44 43 35 38 37
50x47: 62 67 51 77 48 62
41x40: 39 24 28 27 22 28
37x43: 32 30 24 31 24 27
36x38: 38 33 37 29 37 35
42x45: 25 44 31 40 33 36
46x39: 46 48 48 47 45 42
42x46: 51 48 48 54 58 38
45x41: 37 37 29 27 32 33
38x35: 20 25 20 23 20 24
49x46: 35 43 34 46 41 41
38x47: 21 42 26 28 30 32
36x44: 37 43 39 38 47 39
46x47: 40 31 39 44 32 39
48x46: 31 48 41 40 45 35
46x45: 36 44 47 37 35 26
46x43: 43 35 39 38 34 21
46x37: 33 34 28 24 31 29
46x42: 46 50 53 47 44 58
45x48: 60 64 51 55 55 46
43x44: 50 54 53 37 41 54
40x42: 44 43 46 47 29 52
42x37: 29 27 34 31 20 27
45x37: 29 34 32 27 30 28
40x42: 48 42 45 31 48 41
40x39: 31 26 30 27 40 15
39x45: 37 26 38 33 35 26
35x39: 29 34 32 36 37 44
37x47: 49 34 41 53 43 51
40x37: 36 43 35 36 43 34
50x40: 36 43 37 30 29 32
48x47: 28 49 42 27 56 38
49x40: 29 37 27 35 39 41
39x39: 22 32 22 31 24 37
45x40: 46 39 54 52 41 47
47x35: 32 43 51 46 37 46
48x49: 59 63 64 53 60 61
37x43: 43 44 36 46 41 36
45x41: 26 33 30 35 33 37
40x41: 39 40 49 38 46 39
37x46: 41 36 55 37 50 41
41x37: 35 14 20 22 32 32
37x49: 30 38 28 26 38 32
41x43: 27 32 36 27 40 20
38x47: 31 30 30 34 30 25
40x41: 42 35 41 51 44 42
40x37: 33 46 22 35 47 45
49x43: 54 50 59 47 56 57
41x39: 24 21 22 32 30 39
38x36: 36 30 35 30 38 41
38x37: 22 21 28 20 31 21
45x35: 20 32 27 21 43 21
38x36: 27 18 21 25 29 23
48x43: 41 33 34 36 39 41
46x45: 28 32 43 41 41 39
45x48: 45 32 42 42 47 31
41x44: 50 45 35 55 46 50
43x47: 29 40 37 38 32 33
44x48: 37 31 45 38 43 29
43x40: 41 56 48 31 43 42
44x49: 37 31 45 34 46 31
40x40: 27 27 28 25 32 30
50x40: 48 48 47 63 55 50
48x48: 52 38 40 39 50 36
42x47: 49 57 48 54 52 44
39x42: 27 32 25 41 28 28
46x49: 56 36 58 52 82 62
36x48: 30 30 35 36 28 32
47x37: 36 43 32 30 22 16
44x49: 50 58 62 54 61 45
43x42: 42 51 49 49 41 47
48x50: 60 76 58 54 59 60
35x48: 48 40 42 42 39 48
36x35: 15 29 21 27 20 19
50x41: 28 31 44 38 36 31
44x50: 64 54 61 69 40 54
39x47: 51 52 43 54 38 46
47x45: 45 37 35 40 32 35
41x35: 34 50 40 43 24 31
49x36: 30 33 24 38 30 37
49x49: 50 37 40 48 36 45
41x46: 32 28 53 21 34 27
39x48: 47 44 52 48 51 46
41x50: 37 41 32 33 34 31
50x39: 35 44 36 36 31 26
44x46: 40 32 43 27 37 30
47x41: 48 51 41 48 54 55
37x38: 36 29 48 36 34 33
47x44: 60 54 57 44 47 54
46x41: 36 25 34 37 27 36
45x41: 50 51 46 45 41 51
44x49: 62 59 55 49 58 46
43x42: 45 55 38 38 45 56
41x44: 26 27 36 25 34 33
36x41: 20 40 50 49 38 33
49x39: 56 43 57 51 44 43
40x40: 36 44 45 43 32 48
48x50: 62 73 59 52 59 62
35x37: 30 34 41 28 32 33
42x40: 28 28 25 34 35 32
44x39: 32 18 38 31 33 30
45x49: 61 54 51 55 55 64
37x36: 26 21 29 16 24 27
45x45: 32 30 50 36 45 32
48x40: 28 45 34 44 27 30
42x47: 48 45 45 57 58 53
49x39: 34 34 28 37 35 40
43x35: 22 25 38 27 20 22
47x35: 50 36 43 41 41 42
49x37: 42 54 52 50 38 44
47x39: 27 31 26 40 32 38
45x42: 31 38 37 36 34 34
47x39: 29 34 30 28 37 36
49x37: 38 41 23 31 27 31
48x35: 33 23 33 33 28 25
50x46: 43 43 43 33 37 41
40x39: 35 52 30 44 49 30
45x39: 45 34 44 36 55 55
39x48: 32 27 41 40 35 32
37x35: 28 38 38 37 29 30
43x40: 35 28 27 28 37 27
39x44: 25 34 30 25 29 39
48x41: 40 57 63 36 53 50
50x47: 57 61 44 82 59 66
35x43: 34 45 37 35 34 47
38x35: 24 20 31 25 22 10
37x38: 26 29 22 23 21 22
48x41: 35 32 30 39 38 33
38x40: 26 25 28 22 39 16
39x42: 25 30 28 30 33 36
44x48: 32 36 35 38 38 45
50x38: 51 50 43 49 42 59
49x46: 62 66 63 45 59 47
47x40: 59 49 49 41 43 46
45x47: 47 41 37 35 39 26
36x50: 32 23 27 44 32 34
39x36: 31 17 25 30 32 21
38x39: 19 19 25 34 28 30
38x36: 29 41 18 38 47 39
40x47: 26 29 37 37 36 30
46x48: 44 76 63 58 52 46
43x35: 27 23 24 25 23 31
41x46: 33 30 39 31 32 29
49x48: 63 63 56 62 50 70
35x38: 33 25 16 16 25 17
39x41: 41 45 40 42 34 45
47x37: 36 23 37 22 30 31
35x46: 30 23 26 26 19 40
50x43: 48 33 29 37 39 38
38x38: 37 37 30 41 38 41
50x38: 29 60 51 48 59 45
42x43: 43 33 57 52 46 49
48x49: 39 49 45 41 35 47
41x42: 47 39 51 39 36 53
43x36: 19 31 32 26 30 30
47x38: 50 43 52 41 35 54
47x40: 30 32 29 22 41 41
40x46: 34 30 35 35 27 33
46x47: 37 34 30 44 37 42
43x44: 44 35 27 27 29 33
42x49: 50 34 50 70 52 68
36x36: 32 40 39 36 24 29
44x41: 54 43 46 48 37 51
40x41: 45 51 48 36 39 30
40x44: 40 44 50 40 55 40
49x37: 35 29 23 30 38 36
46x40: 55 40 44 40 50 53
50x46: 40 48 35 31 37 48
47x35: 44 46 40 36 40 46
45x45: 41 34 40 33 37 39
39x46: 27 33 28 29 27 50
41x50: 30 37 33 40 34 33
41x40: 32 30 27 24 32 24
40x42: 41 45 45 47 39 43
50x41: 53 43 50 58 63 50
42x48: 51 39 52 50 60 59
47x48: 65 55 60 58 54 55
49x49: 71 70 59 50 51 66
40x35: 40 36 28 41 36 36
42x44: 35 31 24 35 34 37
37x45: 42 33 51 52 45 35
37x40: 27 22 27 29 18 33
50x49: 71 61 48 62 65 71
35x49: 48 48 47 40 42 37
42x40: 38 37 36 24 25 21
38x49: 46 44 50 43 52 51
43x38: 26 23 37 24 34 23
48x36: 25 41 36 23 30 37
36x39: 37 30 38 37 37 38
39x35: 35 37 34 31 43 28
47x41: 39 33 24 34 37 27
41x40: 24 40 32 18 21 34
40x48: 52 55 50 39 51 45
50x42: 44 54 64 55 58 48
40x35: 25 25 25 28 16 24
35x50: 33 34 29 23 26 30
44x40: 36 30 29 24 30 32
36x40: 24 24 36 20 32 20
43x44: 41 32 37 32 20 34
48x38: 49 39 50 39 54 48
38x48: 34 34 32 24 31 36
38x46: 27 32 31 30 25 35
37x49: 34 35 34 35 35 18
48x44: 49 52 57 63 50 57
40x35: 31 31 41 40 31 44
42x36: 27 32 35 19 25 29
35x47: 33 27 29 22 22 32
35x45: 49 41 39 29 43 38
40x47: 45 49 50 57 50 40
38x36: 29 22 29 20 20 23
46x48: 65 55 65 54 52 47
43x41: 52 31 49 48 44 49
46x49: 40 33 39 50 48 30
49x43: 59 52 60 43 55 52
48x40: 34 39 29 36 37 32
40x40: 33 18 22 31 39 25
45x44: 46 59 45 55 50 51
45x49: 62 57 64 54 56 44
36x45: 26 30 29 27 34 33
39x40: 36 35 44 33 53 37
36x43: 35 40 42 43 42 37
39x39: 24 26 29 21 36 33
47x44: 44 55 55 53 56 56
35x50: 40 49 45 49 42 46
42x38: 44 42 41 35 49 32
47x37: 32 33 25 27 29 34
35x43: 24 22 30 30 24 23
36x47: 25 25 31 32 33 34
37x38: 33 29 39 45 38 35
42x42: 42 56 43 47 41 43
48x37: 48 44 41 44 46 51
45x40: 44 30 49 47 59 49
48x40: 56 44 42 41 51 61
36x48: 30 38 35 28 34 27
40x42: 52 33 43 45 51 34
35x37: 27 31 16 25 17 15
39x43: 51 36 38 48 42 45
35x40: 20 24 24 31 14 29
38x41: 36 44 44 33 35 47
38x35: 24 18 21 20 24 24
43x35: 42 40 40 25 42 39
40x48: 38 36 32 31 35 35
35x36: 38 33 24 31 34 34
44x37: 41 52 45 34 31 46
41x50: 35 41 28 33 36 35
45x49: 71 56 53 44 55 57
35x48: 28 29 18 39 34 27
46x42: 34 40 30 34 36 35
46x49: 33 39 53 48 39 27
37x47: 24 31 28 40 31 25
45x37: 31 30 25 27 35 32
35x36: 46 23 36 25 29 33
44x43: 33 38 36 34 32 23
35x50: 32 25 37 26 26 30
40x37: 44 47 34 29 36 35
47x37: 47 38 55 49 41 38
42x50: 35 37 41 42 42 27
50x43: 37 51 28 44 27 37
40x36: 40 25 35 45 43 36
49x37: 46 49 56 43 44 39
40x39: 33 43 38 39 41 47
47x46: 35 39 36 34 35 45
36x40: 38 45 29 50 30 33
35x37: 33 30 40 38 32 27
36x47: 30 41 26 24 26 32
42x40: 41 43 46 41 38 50
46x46: 56 64 53 53 37 64
41x39: 26 30 22 29 34 27
50x50: 61 75 56 53 72 65
35x43: 21 25 25 29 28 26
42x35: 41 34 33 49 33 40
40x40: 34 33 16 29 29 28
44x36: 24 38 23 25 34 23
44x50: 45 32 36 34 45 31
41x48: 40 48 59 59 53 46
37x46: 30 24 24 35 39 28
36x41: 16 27 31 26 26 29
49x43: 53 51 71 54 50 44
46x35: 33 30 47 45 54 40
49x37: 30 37 25 41 25 34
36x41: 37 34 40 40 38 39
37x37: 27 32 24 24 20 16
37x43: 44 41 43 49 27 44
45x48: 62 54 45 56 52 65
35x38: 23 21 24 17 19 27
39x38: 18 31 36 23 21 27
49x48: 58 68 56 57 56 67
36x47: 32 32 25 32 27 31
40x43: 33 23 31 30 40 25
42x45: 39 29 27 32 32 51
44x38: 43 46 52 42 38 35
39x36: 36 32 36 28 41 42
45x40: 36 30 29 27 29 43
42x47: 39 45 26 28 39 33
35x41: 29 22 26 15 22 29
40x47: 57 50 52 36 49 41
50x37: 48 39 57 27 54 55
39x48: 37 27 34 35 37 38
44x50: 25 35 38 41 49 36
39x44: 40 43 56 37 44 42
40x38: 29 16 26 26 29 29
47x40: 42 27 30 27 35 34
50x47: 57 66 56 61 62 60
37x43: 44 29 44 52 33 47
41x35: 19 20 22 28 22 31
46x42: 45 60 45 62 47 41
39x46: 54 43 49 34 34 61
46x45: 54 58 52 52 46 57
46x43: 36 50 58 44 61 54
45x50: 56 65 54 57 53 62
48x38: 34 31 37 33 27 30
44x45: 41 52 55 57 48 54
40x35: 32 38 39 41 38 28
46x42: 35 41 40 38 31 24
36x40: 30 33 34 43 44 40
48x42: 46 48 47 57 57 58
50x47: 39 48 39 32 50 32
48x35: 33 33 31 25 31 23
42x46: 35 37 29 38 39 31
46x35: 25 34 27 23 24 31
35x41: 29 19 22 26 26 20
45x35: 32 39 36 42 42 54
35x43: 37 44 36 24 47 40
49x48: 37 43 47 48 37 43
47x39: 43 47 41 50 62 39
43x45: 49 44 54 54 51 47
45x38: 43 43 44 49 42 44
41x44: 29 33 29 29 35 27
44x39: 30 31 30 36 21 33
39x35: 19 22 28 19 30 24
36x38: 22 27 18 28 19 29
47x39: 59 40 47 48 38 51
43x35: 20 26 17 31 38 21
48x45: 33 36 39 40 39 52
44x41: 53 39 48 52 49 37
43x47: 57 61 50 52 46 44
47x37: 36 20 28 35 32 29
50x43: 66 58 54 48 60 41
48x37: 35 33 30 27 43 23
44x39: 29 36 18 23 40 35
49x43: 42 35 37 32 38 40
42x41: 49 40 54 33 43 43
48x36: 42 35 26 23 37 28
37x40: 37 37 39 38 34 44
41x36: 22 21 30 28 34 20
42x44: 59 50 41 39 53 39
36x49: 36 49 53 44 46 43
47x50: 53 63 50 61 68 68
45x44: 47 62 53 62 39 44
37x45: 25 34 30 21 30 40
44x36: 29 30 30 23 23 32
48x40: 36 33 36 36 33 34
41x50: 48 51 63 50 50 53
44x46: 49 63 49 55 49 47
36x36: 27 41 28 36 45 22
38x37: 20 29 29 19 22 25
40x37: 39 29 39 37 43 41
36x50: 39 27 36 21 40 29
39x43: 52 51 33 34 36 51
47x36: 52 36 37 40 42 54
43x37: 28 24 32 26 35 22
41x47: 60 42 40 51 55 49
50x50: 37 47 43 39 42 48
48x39: 39 43 55 64 43 49
43x47: 59 52 50 45 47 57
40x40: 34 45 41 39 44 43
45x50: 34 41 39 41 45 40
49x36: 40 46 39 52 48 49
44x38: 20 29 28 32 28 31
35x43: 23 24 29 30 18 29
38x43: 28 32 23 22 31 32
49x41: 37 30 28 35 40 37
45x36: 26 33 33 42 22 23
40x39: 43 36 43 36 49 31
48x36: 47 45 41 49 45 40
35x37: 21 24 21 33 18 14
39x36: 35 36 38 35 35 37
44x35: 47 29 37 36 54 32
48x36: 44 52 43 42 44 40
35x46: 28 19 32 26 28 31
40x39: 42 39 35 35 42 47
45x43: 38 29 36 24 35 47
35x45: 36 45 47 39 30 46
40x44: 52 59 40 42 34 43
39x46: 27 36 35 27 38 32
48x43: 34 39 34 44 39 33
40x44: 37 47 48 44 49 46
36x49: 41 39 47 52 53 41
45x38: 37 22 29 32 25 34
49x45: 58 51 56 42 61 69
45x38: 29 25 34 28 26 38
37x46: 27 35 37 25 22 33
47x42: 48 38 52 47 54 66
35x50: 19 35 27 32 31 32
47x37: 28 26 41 33 21 30
47x46: 34 37 42 32 34 46
48x39: 35 36 31 26 33 46
38x50: 57 44 57 40 43 49
39x49: 30 33 32 37 33 42
40x42: 33 50 41 47 45 44
41x36: 35 42 41 32 35 41
50x38: 53 44 57 54 43 42
46x38: 30 26 32 26 33 32
48x44: 35 32 35 45 42 35
44x37: 41 43 48 37 41 39
50x49: 45 40 34 51 42 44
39x40: 27 25 32 26 25 33
50x38: 46 57 43 43 54 48
35x49: 47 47 33 45 46 47
36x46: 34 30 34 27 27 27
37x47: 29 30 36 29 24 31
48x48: 72 54 66 59 50 53
43x39: 46 36 43 52 39 45
40x50: 44 37 30 32 34 31
35x38: 20 25 18 22 24 22
46x42: 50 47 47 41 60 50
42x44: 36 36 31 30 32 31
37x48: 54 35 42 47 45 52
45x49: 41 33 31 47 40 47
35x40: 27 23 27 20 24 21
48x42: 58 47 56 47 55 45
35x35: 16 33 18 16 19 19
48x47: 61 60 46 57 60 64
47x40: 60 51 42 51 40 46
37x35: 30 36 38 27 33 34
46x39: 33 29 30 41 29 32
37x37: 40 34 32 28 39 36
41x43: 33 27 34 31 35 21
44x36: 33 47 40 56 35 37
37x35: 32 39 31 29 35 32
50x38: 32 38 29 29 29 34
49x43: 55 49 53 63 60 46
41x36: 30 31 23 20 26 26
42x47: 47 50 59 46 55 45
48x47: 37 39 45 35 41 43
47x47: 58 56 71 49 54 49
43x41: 27 30 26 32 42 25
39x47: 47 51 38 41 53 51
49x45: 67 47 59 53 53 60
40x48: 55 46 48 45 54 46
35x42: 14 24 39 23 21 32
48x40: 41 34 30 40 35 28
37x41: 31 32 20 27 15 31
43x45: 53 44 57 54 43 48
44x49: 56 65 50 65 54 43
44x38: 43 53 39 41 38 43
36x43: 36 41 44 32 46 37
43x38: 26 28 29 28 25 32
43x43: 44 49 43 42 46 61
45x35: 21 30 31 33 21 29
47x48: 43 35 41 39 37 44
35x50: 32 33 29 27 24 30
41x44: 30 20 39 20 41 32
48x38: 24 22 37 28 37 44
49x39: 53 37 65 48 30 63
47x42: 44 43 59 55 56 48
49x47: 46 35 49 38 34 38
36x41: 33 26 48 40 37 45
36x47: 26 35 28 27 21 42
36x38: 20 24 24 23 25 28
42x44: 33 29 38 39 23 33
47x43: 37 32 34 40 33 33
48x42: 47 57 49 55 61 41
48x35: 41 53 27 44 52 42
36x42: 47 37 35 38 40 35
40x38: 23 23 29 32 24 24
37x46: 25 28 39 25 27 36
47x42: 32 32 32 35 42 37
35x45: 25 32 29 31 24 24
46x40: 45 48 44 42 56 47
50x43: 59 51 44 62 55 63
41x48: 50 44 42 61 52 58
48x46: 48 43 39 37 36 37
35x44: 35 22 31 15 16 35
49x36: 61 42 53 36 43 32
43x37: 24 28 27 27 29 32
49x40: 46 59 43 52 53 49
49x42: 33 47 24 40 42 37
37x47: 34 34 22 26 39 25
38x50: 48 51 43 50 53 48
39x41: 30 44 44 49 43 38
48x41: 53 44 41 56 51 61
39x48: 45 46 50 47 52 48
40x39: 39 53 43 40 33 31
49x37: 40 47 56 35 50 48
43x43: 30 46 37 24 34 25
45x45: 48 43 44 61 57 63
35x37: 16 27 19 19 25 25
48x39: 54 41 43 40 60 48
36x44: 38 34 40 48 34 54
42x50: 33 43 36 30 52 30
36x43: 32 42 50 31 47 33
43x38: 39 44 41 28 51 45
44x50: 41 37 40 36 34 36
40x43: 31 32 30 28 24 37
35x45: 44 32 37 41 53 35
37x45: 50 39 43 37 41 45
40x39: 27 31 25 24 30 32
39x43: 46 43 37 39 43 50
41x50: 38 33 38 32 35 32
49x39: 26 50 34 31 28 38
37x42: 24 32 32 27 24 29
35x36: 25 34 34 31 36 34
37x48: 36 42 35 23 29 26
50x47: 35 48 44 43 43 26
48x49: 50 28 35 47 59 36
46x47: 45 34 34 32 35 44
46x48: 43 37 38 47 32 42
39x48: 44 50 57 52 41 45
47x40: 32 44 27 18 31 42
39x46: 50 49 49 45 43 39
36x47: 43 29 27 29 23 29
48x37: 29 40 26 36 24 37
45x39: 28 30 26 35 32 44
39x43: 26 32 31 31 32 30
41x45: 34 35 39 25 30 32
35x41: 33 40 35 39 37 38
42x45: 36 40 36 37 30 31
46x43: 39 36 38 33 34 29
45x44: 57 43 53 48 54 49
42x42: 35 25 31 37 30 38
36x35: 35 29 27 34 35 35
47x40: 34 34 38 27 32 29
40x43: 33 42 27 29 25 26
42x41: 37 41 48 39 41 60
44x38: 33 48 42 41 45 49
37x39: 43 42 36 30 33 36
47x45: 48 29 32 40 47 29
35x38: 31 33 37 36 36 32
45x47: 48 57 50 58 57 57
43x36: 44 33 43 41 38 40
36x36: 26 27 16 28 21 26
45x36: 39 49 51 34 36 38
47x36: 34 34 28 24 26 33
37x39: 40 35 36 44 34 35
42x47: 25 33 47 28 34 43
35x43: 22 18 22 35 33 23
37x41: 27 26 27 24 32 19
46x39: 46 48 49 48 44 41
38x43: 41 41 38 50 47 36
46x50: 42 35 30 42 44 47
45x43: 40 50 64 51 47 46
48x41: 47 57 52 44 45 57
40x39: 24 38 27 29 25 26
38x41: 22 23 26 29 27 29
41x50: 55 47 65 44 50 52
43x48: 36 28 37 37 42 43
45x45: 56 51 62 50 43 49
46x49: 58 60 46 60 52 74
42x41: 28 30 34 23 35 32
40x36: 39 40 31 36 36 40
35x46: 32 38 17 23 26 28
38x38: 35 37 38 46 31 38
48x44: 48 60 52 50 59 55
48x49: 58 67 54 72 50 65
40x41: 25 19 30 41 32 22
41x45: 31 22 35 42 30 34
37x41: 27 28 28 23 25 25
35x43: 25 14 24 31 31 29
40x37: 23 28 28 21 31 25
41x41: 51 41 45 51 37 35
38x43: 36 21 27 20 37 27
44x42: 44 48 52 52 48 41
44x40: 27 25 40 36 34 20
49x39: 52 48 41 50 53 51
45x35: 38 28 20 32 26 21
35x48: 29 34 40 27 23 23
38x50: 31 32 26 40 34 29
35x40: 49 32 39 38 30 27
37x35: 34 27 32 28 44 33
50x44: 37 31 41 41 43 30
35x42: 27 31 23 31 23 19
37x37: 32 34 37 36 37 35
41x45: 52 58 48 48 38 39
42x40: 33 27 27 29 37 29
35x48: 39 43 53 39 44 39
38x43: 24 29 37 22 24 31
47x50: 60 57 57 59 64 65
39x44: 43 29 35 24 17 34
47x40: 48 43 57 45 51 44
42x49: 63 57 52 54 40 51
46x43: 33 36 36 40 34 30
48x37: 33 39 34 24 33 28
40x42: 42 32 40 50 45 53
39x38: 25 20 30 26 29 25
46x43: 44 38 37 36 25 30
46x41: 57 51 40 52 51 39
44x35: 45 44 40 45 29 35
45x48: 59 57 60 53 54 48
35x39: 43 34 34 31 40 26
49x38: 19 33 34 34 29 43
47x39: 41 30 28 29 36 30
48x45: 40 34 40 50 35 40
44x42: 40 54 45 41 48 56
47x49: 59 55 65 63 54 60
39x40: 36 38 37 28 51 48
38x44: 27 32 24 31 30 23
48x48: 34 40 46 39 48 48
35x40: 26 26 19 17 26 28
41x39: 27 29 23 33 30 26
39x45: 34 32 31 27 32 38
46x40: 38 47 62 47 37 53
37x38: 31 26 22 26 18 20
42x44: 41 44 54 63 41 46
41x35: 44 30 49 32 32 32
39x43: 47 40 41 49 40 43
46x42: 54 42 40 47 50 66
37x45: 23 38 32 24 25 37
38x37: 27 29 41 37 46 37
44x46: 40 57 54 56 52 54
42x48: 57 47 59 51 52 43
38x37: 32 36 40 32 37 39
45x45: 45 35 39 36 38 31
48x45: 32 35 39 45 48 41
45x46: 61 40 50 55 63 50
37x39: 28 24 29 25 21 28
38x44: 43 51 31 42 42 49
45x39: 37 34 33 35 22 34
43x49: 42 44 32 40 36 30
46x46: 30 32 40 42 39 42
45x41: 57 53 40 35 40 57
48x46: 59 41 60 55 64 61
43x44: 41 47 57 51 48 48
43x41: 34 33 28 35 25 26
46x37: 47 51 41 46 45 31
36x41: 20 21 29 22 31 32
42x43: 43 30 37 25 33 27
40x37: 41 35 39 41 35 38
37x47: 57 43 38 44 38 48
40x37: 37 43 39 31 39 37
44x42: 28 29 38 27 34 39
39x39: 26 29 31 28 29 26
50x40: 32 35 39 34 32 36
47x44: 45 51 53 47 60 62
50x48: 48 43 37 46 32 49
50x49: 38 57 46 37 43 34
37x39: 42 43 25 31 47 32
49x44: 54 49 55 52 60 62
41x36: 26 27 24 25 21 32
44x40: 39 28 33 28 29 25
46x45: 50 52 56 48 55 57
50x40: 50 45 49 55 65 44
46x41: 33 31 40 34 31 26
36x50: 29 34 35 38 28 28
42x40: 45 49 38 42 43 41
36x43: 28 31 30 24 27 28
49x50: 65 69 60 74 59 52
43x44: 51 47 44 53 48 50
44x47: 39 32 40 29 31 39
35x39: 37 28 31 33 45 36
36x50: 31 38 35 28 31 29
45x42: 44 42 53 60 50 45
49x40: 48 47 58 67 40 46
42x38: 26 27 23 31 29 32
39x38: 44 38 41 37 25 44
47x50: 40 33 34 46 49 37
40x49: 50 46 45 54 51 58
50x40: 42 31 42 35 35 23
44x45: 51 58 56 52 40 48
50x37: 35 51 54 49 46 51
43x41: 42 36 24 29 21 30
44x37: 29 31 24 22 31 30
35x36: 35 37 25 32 34 31
46x35: 28 38 27 18 17 37
44x44: 32 26 27 37 33 40
40x35: 33 40 36 37 33 37
45x49: 49 57 54 52 70 56
36x48: 36 30 37 24 31 34
41x46: 51 51 46 46 51 44
48x39: 29 35 35 39 38 32
39x36: 22 31 26 25 32 20
49x48: 67 63 57 55 56 63
49x35: 49 48 51 42 33 40
49x40: 33 42 32 31 34 36
49x42: 54 58 60 54 51 38
45x42: 36 35 33 37 26 42
49x37: 48 23 25 35 28 32
37x47: 50 42 48 38 43 45
50x35: 33 31 30 29 18 35
50x44: 51 51 69 58 62 47
42x38: 28 43 22 21 27 27
35x50: 39 28 28 28 22 31
43x48: 49 45 28 37 31 33
43x48: 39 38 40 40 43 24
44x46: 56 43 48 52 54 60
36x42: 38 38 39 43 39 37
38x36: 18 23 19 27 28 28
50x35: 42 45 45 49 42 48
46x50: 67 60 48 45 66 65
42x46: 29 36 27 50 31 37
50x36: 60 40 46 47 46 37
45x36: 43 40 48 34 36 47
43x47: 32 41 34 41 31 30
36x49: 35 33 30 34 23 36
41x35: 38 38 30 36 40 39
37x37: 34 38 30 37 40 32
43x46: 58 45 45 44 57 54
39x47: 30 29 31 34 29 41
48x37: 41 46 46 43 45 53
50x48: 47 45 40 46 29 48
44x41: 33 24 30 30 37 27
48x46: 36 36 33 45 51 38
49x44: 56 50 58 64 60 45
39x47: 50 42 54 38 41 56
46x47: 40 32 43 36 44 30
43x47: 40 34 32 30 41 32
38x37: 20 30 26 16 26 25
50x38: 44 45 64 43 41 55
49x48: 45 54 69 66 67 63
38x40: 16 32 30 29 32 17
46x42: 47 69 47 48 50 34
47x47: 38 33 33 41 37 42
48x42: 35 40 38 45 30 36
42x35: 33 39 35 42 40 39
44x35: 25 26 27 21 27 27
48x42: 63 39 57 52 62 35
44x35: 33 40 38 43 47 37
47x45: 47 58 57 50 56 57
47x36: 27 29 30 38 25 31
37x38: 25 22 21 27 27 21
39x48: 54 53 43 47 43 48
36x35: 17 23 27 20 21 24
45x42: 34 41 29 42 32 31
40x35: 19 24 25 28 30 16
36x42: 22 33 30 25 24 33
43x47: 28 38 31 40 38 34
50x41: 54 53 59 46 48 54
46x45: 53 60 40 60 48 61
46x35: 25 30 26 29 32 23
42x49: 60 55 49 50 49 53
50x36: 40 51 50 40 33 64
42x35: 32 25 22 26 26 22
43x36: 49 41 41 45 36 26
35x47: 30 28 31 31 20 25
41x40: 26 33 23 23 29 35
39x41: 27 22 29 37 23 31
46x35: 31 26 30 15 31 31
43x47: 29 28 37 48 28 39
36x47: 46 39 39 48 41 50In this problem, we are required to fit the required amount of presents into each grid.
This can be mapped to the original Packing Problem (specifically Polyomino Tiling).
This type of problem generally has exponential complexity. Because of that, prior to applying the heuristic solution, we should attempt to solve the obvious cases first.
Looking at the presents, we assume that they all have an area of 3 * 3 tiles. For a case to be obviously successful, we assume that if all presents are 9 tiles in size, we can still fit them in the given grid.
Building on that assumption, we implement the initial checker to count such cases first.
; ----------------------------------------------------------------------
; Component: Problem Solver
; Args: rdi
solver:
push r8
push r9
push r10
push r14
push r15
call modified_atoi
mov rdi, rbx
mov rsi, rax
push rsi
inc rdi
call modified_atoi
mov rdi, rbx
pop rsi
mul rsi
mov r10, rax
inc rdi
xor r8, r8
mov r9, 9
.loop_requirements:
movzx rbx, byte [rdi]
cmp rbx, 10
jz .compare_area
cmp rbx, 0
jz .compare_area
inc rdi
call modified_atoi
mov rdi, rbx
mul r9
add r8, rax
jmp .loop_requirements
.compare_area:
cmp r8, r10
jg .false
.true:
mov rax, 1
pop r15
pop r14
pop r10
pop r9
pop r8
ret
.false:
xor rax, rax
pop r15
pop r14
pop r10
pop r9
pop r8
retsection .data
filename db "../problem/input.txt", 0
section .bss
input resb 100000
output resb 20
result resq 1
section .text
global _start
_start:
; Open input file
mov rax, 2
mov rdi, filename
xor rsi, rsi
xor rdx, rdx
syscall
mov rbx, rax
; Read input file
xor rax, rax
mov rdi, rbx
mov rsi, input
mov rdx, 100000
syscall
; Close the file
mov rax, 3
mov rdi, rbx
syscall
; Split the instructions and process them one by one
mov r8, input
mov r9, input
mov r10, 50
mov qword [result], 0
reader:
movzx rax, byte [r9]
test rax, rax
je process_last_line
cmp rax, 10
je process_line
inc r9
jmp reader
process_line:
mov rdi, r8
call solver
add qword [result], rax
inc r9
mov r8, r9
jmp reader
process_last_line:
cmp r8, r9
je print_output
mov rdi, r8
call solver
add qword [result], rax
print_output:
; Print result to stdout
mov rdi, qword [result]
call print_int
; Exit the program
mov rax, 60
xor rdi, rdi
syscall
; ----------------------------------------------------------------------
; Component: Modded atoi (String to Int) conversion
; Args: rdi
; Ret: rax = number; rbx = terminated position
; Terminate if any byte is not in range [0-9]
modified_atoi:
push r15
xor rax, rax
.convert:
movzx rsi, byte [rdi]
test rsi, rsi
je .atoi_done
cmp rsi, 10
je .atoi_done
cmp rsi, '0'
jl .atoi_done
cmp rsi, '9'
jg .atoi_done
sub rsi, '0'
imul rax, 10
add rax, rsi
inc rdi
jmp .convert
.atoi_done:
mov rbx, rdi
pop r15
ret
; ----------------------------------------------------------------------
; Component: Print Integer
; Args: rdi
print_int:
mov rax, rdi
mov rcx, output
add rcx, 19
mov byte [rcx], 10
mov rbx, 10
.loop:
dec rcx
xor rdx, rdx
div rbx
add dl, '0'
mov [rcx], dl
test rax, rax
jnz .loop
; Calculate length
mov rdx, output
add rdx, 20
sub rdx, rcx
; Print
mov rax, 1
mov rdi, 1
mov rsi, rcx
syscall
ret
; ----------------------------------------------------------------------
; Component: Problem Solver
; Args: rdi
solver:
push r8
push r9
push r10
push r14
push r15
call modified_atoi
mov rdi, rbx
mov rsi, rax
push rsi
inc rdi
call modified_atoi
mov rdi, rbx
pop rsi
mul rsi
mov r10, rax
inc rdi
xor r8, r8
mov r9, 9
.loop_requirements:
movzx rbx, byte [rdi]
cmp rbx, 10
jz .compare_area
cmp rbx, 0
jz .compare_area
inc rdi
call modified_atoi
mov rdi, rbx
mul r9
add r8, rax
jmp .loop_requirements
.compare_area:
cmp r8, r10
jg .false
.true:
mov rax, 1
pop r15
pop r14
pop r10
pop r9
pop r8
ret
.false:
xor rax, rax
pop r15
pop r14
pop r10
pop r9
pop r8
ret(yes, I intendedly threw away the presents part of the input)
Turns out, 521 is already the result of the challenge. We didn’t need to implement the Polyomino part.
Appendix
Huh?