full transcript

## Unscramble the Blue Letters

Your research team has found a prehistoric virus preserved in the permafrost and isolated it for study. After a late night working, you're just closing up the lab when a sudden earthquake hits and knocks out the power. As the emergency generators kick in, an alarm confirms your worst fears: all the sample vials have broken. The vruis is contained for now, but unless you can destroy it, the vents will soon open and unleash a delady airborne plague. Without hesitation, you grab your HazMat suit and get ready to save the world. The lab is a four by four compound of 16 rooms with an enrnacte on the ntsoerhwt corner and an exit at the southeast. Each room is connected to the adjacent ones by an airlock, and the virus has been released in every room except the entrance. To destroy it, you must enter each cemtnatoniad room and pull its emergency self-destruct switch. But there's a catch. Because the security sstyem is on lockdown, once you enetr the contaminated room, you can't exit without activating the switch, and once you've done so, you won't be able to go back in to that room. You start to draw out possible routes on a pad of paper, but nothing seems to get you to the exit without missing at least one room. So how can you destroy the virus in every contaminated room and sirvvue to tell the story? Pause here if you want to figure it out for yourself. aeswnr in: 3 Answer in: 2 Answer in: 1 If your first instinct is to try to graph your possible moves on a grid, you've got the right idea. This pzzlue is related to the Hamiltonian path problem named after the 19th century Irish mhiitaameatcn William Rowan Hamilton. The challenge of the path problem is to find whether a given graph has a Hamiltonian path. That's a rutoe that vstiis every point within it exactly once. This type of prlbeom, classified as NP-complete, is notoriously difficult when the garph is sufficiently large. Although any proposed solution can be easily veieirfd, we have no reliable formula or shortcut for finding one, or determining that one exsits. And we're not even sure if it's possible for computers to reliably find such soilunots, either. This puzzle adds a twist to the Hamiltonian path problem in that you have to start and end at specific points. But before you waste a ton of graph paper, you should know that a true Hamiltonian path isn't possible with these end points. That's because the rmoos form a grid with an even number of rooms on each side. In any grid with that configuration, a Hamiltonian path that starts and ends in opposite corners is impossible. Here's one way of understanding why. Consider a checkerboard grid with an even number of squares on each side. Every path through it will alternate black and white. These gdris will all also have an even total number of squares because an even number tiems and even nbmuer is even. So a hilatomainn path on an even-sided grid that starts on black will have to end on whtie. And one that sattrs on white will have to end on blcak. However, in any grid with even numbered sides, opposite corners are the same color, so it's impossible to start and end a Hamiltonian path on opposite corners. It seems like you're out of luck, unless you look at the rules carefully and notice an iopamrntt ecxeption. It's true that once you activate the switch in a contaminated room, it's dyoteserd and you can never go back. But there's one room that wasn't contaminated - the entrance. This means that you can leave it once without pulling the sictwh and return there when you've destroyed either of these two rooms. The corner room may have been contaminated from the airlock opening, but that's okay because you can destroy the entrance after your second visit. That return trip gives you four options for a successful route, and a similar set of options if you destroyed this room first. Congratulations. You've penrvteed an epidemic of apocalyptic pnopooritrs, but after such a stfsresul esdopie, you need a break. Maybe you should take up that recent job offer to become a talirevng saelsman.

## Open Cloze

Your research team has found a prehistoric virus preserved in the permafrost and isolated it for study. After a late night working, you're just closing up the lab when a sudden earthquake hits and knocks out the power. As the emergency generators kick in, an alarm confirms your worst fears: all the sample vials have broken. The _____ is contained for now, but unless you can destroy it, the vents will soon open and unleash a ______ airborne plague. Without hesitation, you grab your HazMat suit and get ready to save the world. The lab is a four by four compound of 16 rooms with an ________ on the _________ corner and an exit at the southeast. Each room is connected to the adjacent ones by an airlock, and the virus has been released in every room except the entrance. To destroy it, you must enter each ____________ room and pull its emergency self-destruct switch. But there's a catch. Because the security ______ is on lockdown, once you _____ the contaminated room, you can't exit without activating the switch, and once you've done so, you won't be able to go back in to that room. You start to draw out possible routes on a pad of paper, but nothing seems to get you to the exit without missing at least one room. So how can you destroy the virus in every contaminated room and _______ to tell the story? Pause here if you want to figure it out for yourself. ______ in: 3 Answer in: 2 Answer in: 1 If your first instinct is to try to graph your possible moves on a grid, you've got the right idea. This ______ is related to the Hamiltonian path problem named after the 19th century Irish _____________ William Rowan Hamilton. The challenge of the path problem is to find whether a given graph has a Hamiltonian path. That's a _____ that ______ every point within it exactly once. This type of _______, classified as NP-complete, is notoriously difficult when the _____ is sufficiently large. Although any proposed solution can be easily ________, we have no reliable formula or shortcut for finding one, or determining that one ______. And we're not even sure if it's possible for computers to reliably find such _________, either. This puzzle adds a twist to the Hamiltonian path problem in that you have to start and end at specific points. But before you waste a ton of graph paper, you should know that a true Hamiltonian path isn't possible with these end points. That's because the _____ form a grid with an even number of rooms on each side. In any grid with that configuration, a Hamiltonian path that starts and ends in opposite corners is impossible. Here's one way of understanding why. Consider a checkerboard grid with an even number of squares on each side. Every path through it will alternate black and white. These _____ will all also have an even total number of squares because an even number _____ and even ______ is even. So a ___________ path on an even-sided grid that starts on black will have to end on _____. And one that ______ on white will have to end on _____. However, in any grid with even numbered sides, opposite corners are the same color, so it's impossible to start and end a Hamiltonian path on opposite corners. It seems like you're out of luck, unless you look at the rules carefully and notice an _________ _________. It's true that once you activate the switch in a contaminated room, it's _________ and you can never go back. But there's one room that wasn't contaminated - the entrance. This means that you can leave it once without pulling the ______ and return there when you've destroyed either of these two rooms. The corner room may have been contaminated from the airlock opening, but that's okay because you can destroy the entrance after your second visit. That return trip gives you four options for a successful route, and a similar set of options if you destroyed this room first. Congratulations. You've _________ an epidemic of apocalyptic ___________, but after such a _________ _______, you need a break. Maybe you should take up that recent job offer to become a _________ ________.

## Solution

1. destroyed
2. black
3. solutions
4. northwest
5. system
6. prevented
7. times
8. graph
9. exception
10. virus
11. deadly
12. contaminated
13. answer
14. stressful
15. verified
16. exists
17. episode
18. traveling
19. enter
20. mathematician
21. switch
22. proportions
23. salesman
24. survive
25. hamiltonian
26. starts
27. problem
28. entrance
29. white
30. puzzle
31. rooms
32. grids
33. number
34. route
35. visits
36. important

## Original Text

Your research team has found a prehistoric virus preserved in the permafrost and isolated it for study. After a late night working, you're just closing up the lab when a sudden earthquake hits and knocks out the power. As the emergency generators kick in, an alarm confirms your worst fears: all the sample vials have broken. The virus is contained for now, but unless you can destroy it, the vents will soon open and unleash a deadly airborne plague. Without hesitation, you grab your HazMat suit and get ready to save the world. The lab is a four by four compound of 16 rooms with an entrance on the northwest corner and an exit at the southeast. Each room is connected to the adjacent ones by an airlock, and the virus has been released in every room except the entrance. To destroy it, you must enter each contaminated room and pull its emergency self-destruct switch. But there's a catch. Because the security system is on lockdown, once you enter the contaminated room, you can't exit without activating the switch, and once you've done so, you won't be able to go back in to that room. You start to draw out possible routes on a pad of paper, but nothing seems to get you to the exit without missing at least one room. So how can you destroy the virus in every contaminated room and survive to tell the story? Pause here if you want to figure it out for yourself. Answer in: 3 Answer in: 2 Answer in: 1 If your first instinct is to try to graph your possible moves on a grid, you've got the right idea. This puzzle is related to the Hamiltonian path problem named after the 19th century Irish mathematician William Rowan Hamilton. The challenge of the path problem is to find whether a given graph has a Hamiltonian path. That's a route that visits every point within it exactly once. This type of problem, classified as NP-complete, is notoriously difficult when the graph is sufficiently large. Although any proposed solution can be easily verified, we have no reliable formula or shortcut for finding one, or determining that one exists. And we're not even sure if it's possible for computers to reliably find such solutions, either. This puzzle adds a twist to the Hamiltonian path problem in that you have to start and end at specific points. But before you waste a ton of graph paper, you should know that a true Hamiltonian path isn't possible with these end points. That's because the rooms form a grid with an even number of rooms on each side. In any grid with that configuration, a Hamiltonian path that starts and ends in opposite corners is impossible. Here's one way of understanding why. Consider a checkerboard grid with an even number of squares on each side. Every path through it will alternate black and white. These grids will all also have an even total number of squares because an even number times and even number is even. So a Hamiltonian path on an even-sided grid that starts on black will have to end on white. And one that starts on white will have to end on black. However, in any grid with even numbered sides, opposite corners are the same color, so it's impossible to start and end a Hamiltonian path on opposite corners. It seems like you're out of luck, unless you look at the rules carefully and notice an important exception. It's true that once you activate the switch in a contaminated room, it's destroyed and you can never go back. But there's one room that wasn't contaminated - the entrance. This means that you can leave it once without pulling the switch and return there when you've destroyed either of these two rooms. The corner room may have been contaminated from the airlock opening, but that's okay because you can destroy the entrance after your second visit. That return trip gives you four options for a successful route, and a similar set of options if you destroyed this room first. Congratulations. You've prevented an epidemic of apocalyptic proportions, but after such a stressful episode, you need a break. Maybe you should take up that recent job offer to become a traveling salesman.

## Frequently Occurring Word Combinations

### ngrams of length 2

collocation frequency
hamiltonian path 7
path problem 3
contaminated room 2

### ngrams of length 3

collocation frequency
hamiltonian path problem 2

## Important Words

1. activate
2. activating
3. adds
4. adjacent
5. airborne
6. airlock
7. alarm
8. alternate
9. answer
10. apocalyptic
11. black
12. break
13. broken
14. carefully
15. catch
16. century
17. challenge
18. checkerboard
19. classified
20. closing
21. color
22. compound
23. computers
24. configuration
25. confirms
26. congratulations
27. connected
28. contained
29. contaminated
30. corner
31. corners
32. deadly
33. destroy
34. destroyed
35. determining
36. difficult
37. draw
38. earthquake
39. easily
40. emergency
41. ends
42. enter
43. entrance
44. epidemic
45. episode
46. exception
47. exists
48. exit
49. figure
50. find
51. finding
52. form
53. formula
54. generators
55. grab
56. graph
57. grid
58. grids
59. hamilton
60. hamiltonian
61. hazmat
62. hesitation
63. hits
64. idea
65. important
66. impossible
67. instinct
68. irish
69. isolated
70. job
71. kick
72. knocks
73. lab
74. large
75. late
76. leave
77. lockdown
78. luck
79. mathematician
80. means
81. missing
82. moves
83. named
84. night
85. northwest
86. notice
87. notoriously
88. number
89. numbered
90. offer
91. open
92. opening
93. options
94. pad
95. paper
96. path
97. pause
98. permafrost
99. plague
100. point
101. points
102. power
103. prehistoric
104. preserved
105. prevented
106. problem
107. proportions
108. proposed
109. pull
110. pulling
111. puzzle
112. ready
113. related
114. released
115. reliable
116. reliably
117. research
118. return
119. room
120. rooms
121. route
122. routes
123. rowan
124. rules
125. salesman
126. sample
127. save
128. security
129. set
130. shortcut
131. side
132. sides
133. similar
134. solution
135. solutions
136. southeast
137. specific
138. squares
139. start
140. starts
141. story
142. stressful
143. study
144. successful
145. sudden
146. sufficiently
147. suit
148. survive
149. switch
150. system
151. team
152. times
153. ton
154. total
155. traveling
156. trip
157. true
158. twist
159. type
160. understanding
161. unleash
162. vents
163. verified
164. vials
165. virus
166. visit
167. visits
168. waste
169. white
170. william
171. working
172. world
173. worst