TedTest

From the Ted Talk by Lisa Winer: Can you solve the virus riddle?

Unscramble the Blue Letters

Your research team has found a prehistoric vruis pversreed in the permafrost and ieasoltd it for study. After a late night woirkng, you're just closing up the lab when a sudden earthquake hits and konkcs 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 dsteroy it, the vtens will soon open and unleash a deadly aroirnbe 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 rmoos 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 encnrate. To destroy it, you must enter each cttmoaainned room and pull its emergency self-destruct switch. But there's a catch. Because the security stseym 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 svvurie to tell the story? psuae here if you want to frigue it out for yourself. Answer in: 3 Answer in: 2 aesnwr in: 1 If your first instinct is to try to graph your possible mevos on a grid, you've got the right idea. This plzzue is related to the Hamiltonian path problem naemd after the 19th cetnury iisrh mathematician William Rowan Hamilton. The challenge of the path problem is to find whether a given graph has a hnalmiation path. That's a route that visits every point within it exactly once. This type of problem, classified as NP-complete, is nsiootulroy difficult when the garph is sufficiently large. Although any popesord 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 rliealby find such solutions, either. This puzzle adds a twist to the Hamiltonian path problem in that you have to start and end at sifepcic 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 ttoal number of sruaqes because an even number teims 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 baclk. However, in any grid with even nueermbd sdeis, 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 laeve it once without pulling the sitcwh and return there when you've destroyed either of these two rooms. The corenr room may have been contaminated from the alirock 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 doseyretd this room first. Congratulations. You've prevented an epidemic of apocalyptic proportions, but after such a stressful episode, you need a beark. Maybe you should take up that recent job offer to become a traveling salesman.

Open Cloze

Your research team has found a prehistoric _____ _________ in the permafrost and ________ it for study. After a late night _______, you're just closing up the lab when a sudden earthquake hits and ______ 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 _______ it, the _____ will soon open and unleash a deadly ________ 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 _____ 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 ________. 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 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 _______ to tell the story? _____ here if you want to ______ it out for yourself. Answer in: 3 Answer in: 2 ______ in: 1 If your first instinct is to try to graph your possible _____ on a grid, you've got the right idea. This ______ is related to the Hamiltonian path problem _____ after the 19th _______ _____ mathematician William Rowan Hamilton. The challenge of the path problem is to find whether a given graph has a ___________ path. That's a route that visits every point within it exactly once. This type of problem, classified as NP-complete, is ___________ difficult when the _____ is sufficiently large. Although any ________ 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 ________ find such solutions, either. This puzzle adds a twist to the Hamiltonian path problem in that you have to start and end at ________ 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 _____ number of _______ because an even number _____ 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 _____. However, in any grid with even ________ _____, 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 _____ it once without pulling the ______ and return there when you've destroyed either of these two rooms. The ______ room may have been contaminated from the _______ 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 _________ this room first. Congratulations. You've prevented an epidemic of apocalyptic proportions, but after such a stressful episode, you need a _____. Maybe you should take up that recent job offer to become a traveling salesman.

Solution

puzzle
century
working
pause
isolated
total
squares
graph
answer
virus
vents
reliably
destroy
switch
preserved
airlock
numbered
sides
moves
notoriously
figure
irish
entrance
rooms
break
black
system
knocks
specific
times
destroyed
corner
survive
proposed
leave
contaminated
named
hamiltonian
airborne

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

activate
activating
adds
adjacent
airborne
airlock
alarm
alternate
answer
apocalyptic
black
break
broken
carefully
catch
century
challenge
checkerboard
classified
closing
color
compound
computers
configuration
confirms
congratulations
connected
contained
contaminated
corner
corners
deadly
destroy
destroyed
determining
difficult
draw
earthquake
easily
emergency
ends
enter
entrance
epidemic
episode
exception
exists
exit
figure
find
finding
form
formula
generators
grab
graph
grid
grids
hamilton
hamiltonian
hazmat
hesitation
hits
idea
important
impossible
instinct
irish
isolated
job
kick
knocks
lab
large
late
leave
lockdown
luck
mathematician
means
missing
moves
named
night
northwest
notice
notoriously
number
numbered
offer
open
opening
options
pad
paper
path
pause
permafrost
plague
point
points
power
prehistoric
preserved
prevented
problem
proportions
proposed
pull
pulling
puzzle
ready
related
released
reliable
reliably
research
return
room
rooms
route
routes
rowan
rules
salesman
sample
save
security
set
shortcut
side
sides
similar
solution
solutions
southeast
specific
squares
start
starts
story
stressful
study
successful
sudden
sufficiently
suit
survive
switch
system
team
times
ton
total
traveling
trip
true
twist
type
understanding
unleash
vents
verified
vials
virus
visit
visits
waste
white
william
working
world
worst