path: root/2022/4.lisp

;;;; aoc-2022-4.lisp

(defpackage #:aoc/2022/4
  (:use #:cl))

(in-package #:aoc/2022/4)

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

(defun contains (l1 l2)
  "Returns true if L1 is fully contained in L2, or viceversa."
  (declare (type list l1 l2))
  (let ((s1 (first l1))
	(e1 (second l1))
	(s2 (first l2))
	(e2 (second l2)))
    (or
     (and (<= s1 s2)
	  (>= e1 e2))
     (and (<= s2 s1)
	  (>= e2 e1)))))

(defun overlaps (l1 l2)
  "Returns true if L1 and L2 overlap."
  (declare (type list l1 l2))
  (let ((s1 (first l1))
	(e1 (second l1))
	(s2 (first l2))
	(e2 (second l2)))
    (or
     (and (<= s1 s2)
	  (<= e1 e2)
	  (>= e1 s2))
     (and (<= s2 s1)
	  (<= e2 e1)
	  (>= e2 s1))
     (contains l1 l2))))

(defun part1 (&optional (input +problem-4-input+))
  (let ((pairs 0))
    (loop :for i :to (length input) :by 2
	  :do
	     (when
		 (let ((left (nth i input))
		       (right (nth (1+ i) input)))
		   (and left right (contains left right)))
	       (incf pairs)))
    pairs))

(defun part2 (&optional (input +problem-4-input+))
  (let ((overlaps 0))
    (loop :for i :to (length input) :by 2
	  :do (when
		  (let ((left (nth i input))
			(right (nth (1+ i) input)))
		    (and left right (overlaps left right)))
		(incf overlaps)))
    overlaps))