Google Tech Challenge 2019 - Puzzle Level 1
These puzzles are from an annual coding/puzzle competition formerly called Google Games. I got very bored in quarentine and decided to solve all of the puzzles I did not solve during the competition, and do write-ups for all of them. I really enjoyed the mix of code and puzzles in the competition, and even though we only came in fourth I had a great time (and won a plush android).
The competition was broken up into 4 sections: puzzle level 1, word association, puzzle level 2 and coding speedrun. I have the puzzle level 2 up in another blog post if these 12 are not enough for you!
Puzzles in this level:
- Anthology
- Bomb Search
- Coin Blocks
- Game Genie
- Hack ‘n Slash’
- King’s Salesman
- Metamorphic Rocks
- Number Munchers
- Patch Notes
- Puyo Puyo
- Quotris
- Slide to Safety
Anthology
Description
If you loved Tales of Symphonia and Tales of Berseria, then get ready for the next game in the series:
- Stories describing the product of the Haber process
- Stories about a beaver-like rodent once prized for its fur
- Stories made from a natural sugar substitute
- Stories prefaced by a personal appeal from founder Jimmy Wales
- Stories to which Le Châtelier’s Principle applies
- Stories about crowns, sceptres, and other royal emblems
- Stories featuring Italian bread similar to pizza dough
- Stories about badges on a military officer’s uniform
- Stories about tea plants
- Stories told by common freshwater food fish
- Stories read when having trouble falling asleep
- Stories using words that resemble the sound they describe
- Stories that say, “Hey, do you remember that one song from middle school?”
Work
Tales of Symphonia and Tales of Berseria are both part of the Tales Of series of Japanese video games.
The order of these games is:
| Year | Game Name |
|---|---|
| 1997 | Tales of Destiny |
| 2000 | Tales of Eternia |
| 2002 | Tales of Destiny 2 |
| 2003 | Tales of Symphonia |
| 2004 | Tales of Rebirth |
| 2005 | Tales of Legendia Tales of the Abyss |
| 2006 | Tales of the Tempest |
| 2007 | Tales of Innocence |
| 2008 | Tales of Vesperia Tales of Symphonia: Dawn of the New World Tales of Hearts |
| 2009 | Tales of Graces |
| 2011 | Tales of Xillia |
| 2012 | Tales of Xillia 2 |
| 2015 | Tales of Zestiria |
| 2016 | Tales of Berseria |
| 2020 | Tales of Arise |
Notably, a lot of the video game titles end with -ia, which gives a clue to the answers to each clue in the description.
- Stories describing the product of the Haber process
- Ammonia
- Stories about a beaver-like rodent once prized for its fur
- Nutria
- Stories made from a natural sugar substitute
- Stevia
- Stories prefaced by a personal appeal from founder Jimmy Wales
- Wikipedia
- Stories to which Le Châtelier’s Principle applies
- Equilibria
- Stories about crowns, sceptres, and other royal emblems
- Regalia
- Stories featuring Italian bread similar to pizza dough
- Foccacia
- Stories about badges on a military officer’s uniform
- Insignia
- Stories about tea plants
- Camellia
- Stories told by common freshwater food fish
- Tilapia
- Stories read when having trouble falling asleep
- Insomnia
- Stories using words that resemble the sound they describe
- Onomatopoeia
- Stories that say, “Hey, do you remember that one song from middle school?”
- Nostalgia
Taking the first letter of all of the answers we get ANSWERFICTION
Answer
FICTION
Bomb Search
Description
Search for the bombs below, but be careful if you find yourself in the crossfire. Unlike in Bomberman, these bombs are infinitely powerful and can explode any number of times.
K O G J S E R J P G N B Y
C T O N T E M B I A I L F
F E A E I G T O W M I C O
V D Z A H O N U C L E A R
C P R U N B R S K O U N K
G H S S E R M T G A N R I
T O E T K E A P T E R A S
A T E R H U N L Z X E F R
S O T O R F I M E P V I O
H U S G H Y D R O G E N L
C I Z N J S V A M T E D A
- Atomic
- Carpet
- Cherry
- Fork
- Hydrogen
- Neutron
- Nuclear
- Photo
- Smoke
- Stink
- Time
Work
Right away we can find a few words in the word search, namely HYDROGEN, NUCLEAR, FORK. CHERRY, and PHOTO. We are told in the description to pay attention to the “crossfire”, so much like Bomberman, we eliminate each row and column where an intersection of words occurs.
Once we make those first eliminations, the game board shrinks to 8x10, and we can now find more words, namely NEUTRON, and STINK. We then eliminate the rows and columns in the same manner.
For the next round we can find SMOKE (diagonally), and then we remove the intersected rows and columns. In the next round we find CARPET (diagonally) and TIME. Remove the intersected rows and columns. we then find ATOMIC, remove rows and columns, and then MAIL.
Once we’ve removed all of the intersected rows and columns, we are left with a 3x4 grid that spells out the answer.
Answer
COUNTERACTED
Coin Blocks
Description
Mario is on a platform with one thousand coin blocks! Eager to collect as many coins as possible, Mario hits each block until no more coins come out. Seeing so much treasure leaves him fizzing and buzzing with excitement.
The coin blocks are numbered in order from 1 to 1000. Hitting each of the coin blocks yields a certain number of coins.
- By default, each block contains the same number of coins as the block number (from 1 to 1000).
- Block number 3 and every 3rd block thereafter has double the number of coins as normal.
- Block number 5 and every 5th block thereafter has triple the number of coins as normal.
- Block number 15 and every 15th block thereafter has an extra bonus: instead of double or triple, there are ten times as many coins as normal.
Based on this information, here are the total numbers of coins in each of the first 15 blocks:
| Block number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Base coins | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| Multiplier | - | - | ×2 | - | ×3 | ×2 | - | - | ×2 | ×3 | - | ×2 | - | - | ×10 |
| Total coins | 1 | 2 | 6 | 4 | 15 | 12 | 7 | 8 | 18 | 30 | 11 | 24 | 13 | 14 | 150 |
After passing by the first 15 blocks, Mario has already collected 1 + 2 + 6 + 4 + 15 + 12 + 7 + 8 + 18 + 30 + 11 + 24 + 13 + 14 + 150 = 315 coins.
In total, how many coins will Mario have collected at the end of the level after exhausting all 1000 coin blocks?
Work
public static void main(String [] args){
int total = 0;
for (int i = 1; i <= 1000; i++) {
int val = i;
// Do NOT stack modifers
if (i % 15 == 0) {
val *= 10;
} else if (i % 5 == 0) {
val *= 3;
} else if (i % 3 == 0) {
val *= 2;
}
total += val;
}
System.out.println(total);
}
Answer
1067323
Game Genie
Description
You acquire a strangely shaped golden video game cartridge for an ancient system called the NES. It is a bit tarnished, so you tried to polish it. And behold, a genie pops out! However, everything he says is garbled:
QBI
LANJCNM
SECCQDTUH
YSSB
?
You transcribe down a bunch of the phrases he says and soon figure out that his speech is encrypted using its “jump distance.” For example, the jump distance for “QBI” is 6. That means that every letter in “QBI” needs to “jump” 6 letters forward.
- Q → R → S → T → U → V → W
- B → C → D → E → F → G → H
- I → J → K → L → M → N → O
Q jumps forward 6 letters to become W, B jumps forward 6 letters to become H, and I jumps forward 6 letters to become O. Therefore, “QBI” is decrypted to “WHO”.
Note that if a jump goes past the letter Z, it wraps back around to the beginning of the alphabet. For example, Z might “jump” forward 6 letters to F.
However, every word was encrypted using a different jump distance, chosen at random. In the above example, “LANJCNM” has a jump distance of 17, “SECCQDTUH” has a jump distance of 10, and “YSSB” has a jump distance of 12. Once you have determined these values, you can decrypt “LANJCNM” to be “CREATED”, “SECCQDTUH” to be “COMMANDER” and “YSSB” to be “KEEN”. The entire decrypted question, then, is “WHO CREATED COMMANDER KEEN?”. To which you know you must answer TOM HALL.
Using this technique, you need to figure out the jump distance for each word in the Genie’s question in order to decrypt it, and then give your answer to his question:
SDWP
PBZCNAL
IJXNLSJI
UIF
EYKC
SQZUQ
?
Work
“Jump Distance” is the same concept as a caesar cipher, which we can use an online tool to easily try different jump lengths.
PBZCNAL => COMPANY with jump distance 13 IJXNLSJI => DESIGNED with jump distance 21 UIF => THE with jump distance 25 EYKC => GAME with jump distance 2 SQZUQ => GENIE with jump distance 14 ? =>
This gives us the phrase COMPANY DESIGNED THE GAME GENIE?
Answer
CODEMASTERS
Hack ‘n Slash’
Description
Someone hacked into the game index overnight and slashed up some of the art displays. What were they up to?
Work
First we need to identify all of the games in the slashed images. This was done by searching for game art online and just personal knowledge.
From left to right and top to bottom:
- Dark Souls - 5 slashes
- Torchlight - 1 slash
- Darksiders - 2 slashes
- Bayonetta - 1 slash
- Diablo II - 4 slashes
- Devil May Cry - 4 slashes
- Ninja Gaiden - 3 slashes
- God of War - 1 slash
#/media/File:Ninja_Gaiden_(NES).jpg){kind=link}
So all of the images are video game box art, and the number of slashes represent the number letter we want to get in the game title (1 indexed). Putting these letters together gives us the answer.
Answer
STABBING
King’s Salesman
Description
King Maximus is in peril, and he needs you to visit all the towns of his vast and sprawling kingdom spread across four continents to sell Royal Certificates of Good Will.
Within each of the four continents, you begin at a particular town. You can travel to any town connected by a path to the town you are in currently, taking the indicated number of days to travel that distance. Once you have visited every town on a continent, you can move on immediately to the next continent, starting where indicated.
It’s a long way, but this is a land of sorcery and you have a great power: the *Town Gate* spell. Town Gate allows you to instantly return to any town on the same continent that you have already visited without any travel cost. The trouble is that your power is also limited, and the nature of magic is strange. This forces the following requirements:
- You can only cast Town Gate a total of 6 times.
- You cannot cast Town Gate the same number of times on two different continents.
King Maximus is impatient, and he wants you to complete the trip in as few days as possible. You get the feeling you’ll need to try this again next year, so you resolve to remember any shortcuts you took.
But what did you return to the King?
Continentia
Forestria
Archipelia
Saharia
Work
This is a variation of the Traveling Salesman problem, but since the maps are so small, I decided to do this one by hand, rather than spend my time debugging. Since we cannot cast the same number of spells on any two islands, and we can only cast 6 total, we know that we must cast the spell 0, 1, 2, and 3 times on the 4 continents, in some order. We know this because any other combination of 4 numbers 1-6 will lead to duplicates, or going over the limit of 6. Because of this, we can ignore any paths that require more than 3 spells.
Contentia
0 Teleports:
Dark corner --8-> Topshore --11-> Woods End --4-> Elan's Landing --4-> Woods End --10-> Hunterville --5-> bayside
Total: 42 days
1 Teleport:
Dark corner --8-> topshore --11-> woods end --4-> Elans landing --0-> Dark corner --10-> Hunterville --5-> Bayside
Total: 38 Days
2 Teleports:
No difference to the 1 teleport path
Forestia
0 Teleports:
Riverton --10-> Yakonia --20-> Isla Vista --5-> Xoctan --5-> Isla Vista --17-> Anomaly --20-> Kings Haven
Total: 77 days
1 Teleport:
Riverton --10-> Anomaly --20-> Kings Haven --0-> Riverton --10-> Yakonia --20-> Isla Vista --5-> xoctan
Total: 65 Days
2 Teleports:
Riverton --10-> Anomaly --20-> King’s Haven --0-> Anomaly --17-> Isla Vista --5-> Xoctan --0-> Riverton --10-> Yakonia
Total: 62 Days
Archipelia
0 Teleports:
Requires at least +23
1 Teleport:
Quiln’s Point --10-> Endryx --5-> Nyre --7-> Centrapf --15-> Lakeview --12-> Path’s End --10--> Japper --3-> fjord --18-> Grimold --0-> Nyre --10-> Vengeance
Total: 90 days
2 Teleports:
Quiln’s point --10-> Endryx --5-> Nyre --7-> Centrapf --11-> Fjord --3-> Japper --1--> Path’s End --12-> Lakeview --0-> Nyre --10-> Vengeance --0-> Fjord --18-> Grimwald
Total: 89 days
Saharia
3 Teleports:
Midland --18-> Elan’s Landing --18-> Midland --22-> Duovok --0-> Midland --30-> overthere --17-> Underfoot --17-> Overthere --18-> Zaezoizu --0-> Overthere --10-> Simpelton --20-> Irok --20-> Simpleton --23-> Azram
Total: 193 Days
Since Saharia has the largest penalties for taking less optimal paths, I just calculated with the max of 3 teleports. Next we find the path with 2 teleports that has the highest difference between the path with 1 teleport. This is the Forestia 2 teleport path. Next we find the path with 1 teleports that has the highest difference between the path with 0 teleports, which is the Archipelia path with 1 teleport. Finally, we know we take the Contentia 0 teleports path.
So, all the paths we need to take are:
Contentia
0 Teleports:
Dark corner --8-> Topshore --11-> Woods End --4-> Elan's Landing --4-> Woods End --10-> Hunterville --5-> bayside
Total: 42 days
Forestia
2 Teleports:
Riverton --10-> Anomaly --20-> King’s Haven --0-> Anomaly --17-> Isla Vista --5-> Xoctan --0-> Riverton --10-> Yakonia
Total: 62 Days
Archipedia
1 Teleport:
Quiln’s Point --10-> Endryx --5-> Nyre --7-> Centrapf --15-> Lakeview --12-> Path’s End --10--> Japper --3-> fjord --18-> Grimold --0-> Nyre --10-> Vengeance
Total: 90 days
Saharia
3 Teleports:
Midland --18-> Elan’s Landing --18-> Midland --22-> Duovok --0-> Midland --30-> overthere --17-> Underfoot --17-> Overthere --18-> Zaezoizu --0-> Overthere --10-> Simpelton --20-> Irok --0-> Simpleton --23-> Azram
Total: 193 Days
This gives us a total of 387 days, but the clue says we must “resolve to remember any shortcuts you took”, so let’s look at all the Town Gate spells we used.
King’s Haven --0-> Anomaly
Xoctan --0-> Riverton
Grimold --0-> Nyre
Duovok --0-> Midland
Zaezoizu --0-> Overthere
Irok --0-> Simpleton
Looking at the first letter of each shortcut destination, we get ARNMOS. Unscrambinling this string gives us the answer.
Answer
RANSOM
Metamorphic Rocks
Description
LAB BOOK
NAME: Prof. Rowan
- Specimen #044
- Reaction is catalyzed by fluorite and exposure to ultraviolet light.
- Specimen #090
- Reaction is catalyzed by calcite and addition of water.
- Specimen #176
- Reaction is catalyzed by topaz and exposure to intense, dazzling light.
- Specimen #200
- Reaction is catalyzed by quartz in the absence of light.
- Specimen #281
- Reaction is catalyzed by talc at sunrise. Only half of the subject population reacts.
- Specimen #546
- Reaction is catalyzed by corundum and exposure to ultraviolet light.
- Specimen #548
- Reaction is catalyzed by orthoclase and exposure to ultraviolet light.
- Specimen #603
- Reaction is catalyzed by diamond and application of electric current.
- Specimen #680
- Reaction is catalyzed by gypsum in the absence of light.
- Specimen #694
- Reaction is catalyzed by apatite and exposure to ultraviolet light.
Work
Professor Rowan is a professor in the Sinnoh region of Pokemon, which leeds us to believe that the specimen numbers may correspond to Pokemon! Furthermore, the title “Metamorphic”, as well as the pokemon the numbers correspond to, hints that each pokemon needs a special stone to evolve. The stone needed to evolve is suggested by the description as well. For example, “exposure to ultraviolet light” suggests a Sun Stone.
In addition, each specimen description has a mineral, which are all on the Mohs Hardness Scale. The scale is:
- Talc
- Gypsum
- Calcite
- Fluorite
- Apatite
- Orthoclase feldspar
- Quartz
- Topaz
- Corundum
- Diamond
- Specimen #044
- Gloom
- Sun Stone -> Bellossom
- Fluorite has a Mohs hardness rating of 4
- Specimen #090
- Shellder
- Water Stone -> Cloyster
- Calcite has a Mohs hardness rating of 3
- Specimen #176
- Togetic
- Shiny Stone -> Togekiss
- Topaz has a Mohs hardness rating of 8
- Specimen #200
- Misdreavus
- Dark Stone -> Mismagius
- Quartz has a Mohs hardness rating of 7
- Specimen #281
- Kirlia
- Dawn Stone -> Gallede
- Talc has a Mohs hardness rating of 1
- Specimen #546
- Cottonee
- Sun Stone -> Whimsicott
- Corundum has a Mohs hardness rating of 9
- Specimen #548
- Petilil
- Sun Stone -> Lilligant
- Orthoclase has a Mohs hardness rating of 6
- Specimen #603
- Eelektrik
- Thunder Stone -> Eelektross
- Diamond has a Mohs hardness rating of 10
- Specimen #680
- Doublade
- Dusk Stone -> Aegislash
- Gypsum has a Mohs hardness rating of 2
- Specimen #694
- Helioptileel
- Sun Stone -> Heliolisk
- Apatite has a Mohs hardness rating of 5
We use the Mohs hardness scale to get the character at that index of the evolved Pokemon (1 based)
This gives us
L O S I G T G S E O
with the corresponding hardness scale of
4 3 8 7 1 9 6 10 2 5
Then we just need to arrange the letters in the order of the hardness scale.
Answer
GEOLOGISTS
Number Munchers
Description
The Munchicus digitus has become much more intelligent and discerning over the years. It now only wants to eat magic duos. A magic duo is any pair of positive integers that when multiplied together produce a number that has digits in strictly ascending order (e.g. 1456, 689, 4, 259).
An example magic duo is 13 and 53, because 13 × 53 = 689, and the digits in 689 are in ascending order and don’t repeat.
Examples of numbers that are not magic duos:
- 11 and 23, because 11 × 23 = 253, and the digits in 253 are not in ascending order.
- 9 and 13, because 9 × 13 = 117, and the digit 1 repeats, so the digits are not in strictly ascending order.
However, the Muncher’s mouth isn’t very large, so it can only eat magic duos that when multiplied together yield a product less than 1,000.
How many magic duos can the Muncher eat?
Note that magic duos have no order. For example, {13, 53} and {53, 13} count as the same magic duo. However, the numbers in a magic duo don’t have to be distinct. {5, 5} is a magic duo, because 5 × 5 = 25 and 25 has digits in strictly ascending order.
Work
Not that we’re looking for the number of duos, not the number of strictly ascending numbers.
public class HelloWorld {
public static void main (String[] args) {
int numDuos = 0;
for (int i = 1; i <= 1000; i++) {
for (int j = i; j <= 1000; j++) {
int product = i * j;
// Make sure it meets the conditions
if (product < 1000 && isDuo(product)) {
numDuos++;
}
}
}
System.out.println(numDuos);
}
// Method to determine if a number is strictly ascending
public static boolean isDuo (int num) {
String s = num + "";
int prev = -1;
for (int i = 0; i < s.length(); i++) {
// Use the fact that 0-9 ASCII codes are strictly ascending
if (s.charAt(i) <= prev) {
return false;
}
prev = s.charAt(i);
}
return true;
}
}
Answer
328
Patch Notes
Looks like every character got either a buff or a nerf.
- Sacrificial location
- For Your Eyes Only Villain Kristatos
- Middle name of the author of Aurora Leigh
- Ernie’s friend
- Wireless personal area network tech. with low power reqs.
- Instructions for a party where drinks are not provided
- Device used to bind sausages
- Movie with a heavenly Alanis Morissette
- Miss Kitt and others
- From A to U?
- Beethoven’s 3rd symphony
- Elvis Costello’s record label in the early 80s
- Bandmate of Alex and Neil
- Former mayor of Reykjavik and founder of the Best Party
- Big Yellow Taxi singer Mitchell
- Noisy
- Capital of the Maldives
- Prefix for 2^20 bytes
- Author of How to Live Safely in a Science Fictional Universe to his children’s friends?
- Small horse in Madrid
- Finnish site of one of the largest jazz festivals in Europe
- Gold dissolving mixture aqua __
- Musical instruction meaning dry
- One of the two main branches of Islam
- Genus and species of the little bustard
- Color slightly
- Fuzzy Wuzzy end?
- Daughter of Lenny K and Lisa B
[After this is a long list of 28 pictures of video game characters that I am not going to upload all of]
Work
Notice that the answes to each list are all in alphabetical order, which makes it easier to deduce the right answer for each.
- Sacrificial location
- Altar
- For Your Eyes Only Villain Kristatos
- Aris
- Middle name of the author of Aurora Leigh
- Barrett
- Ernie’s friend
- Bert
- Wireless personal area network tech. with low power reqs.
- BLE
- Instructions for a party where drinks are not provided
- BYOB
- Device used to bind sausages
- Caser
- Movie with a heavenly Alanis Morissette
- Dogma
- Miss Kitt and others
- Earthas
- From A to U?
- EIO
- Beethoven’s 3rd symphony
- Eroica
- Elvis Costello’s record label in the early 80s
- F-Beat
- Bandmate of Alex and Neil
- Geddy
- Former mayor of Reykjavik and founder of the Best Party
- Gnarr
- Big Yellow Taxi singer Mitchell
- Joni
- Noisy
- Loud
- Capital of the Maldives
- Male
- Prefix for 2^20 bytes
- Mebi
- Author of How to Live Safely in a Science Fictional Universe to his children’s friends?
- Mr. Yu
- Small horse in Madrid
- Poni
- Finnish site of one of the largest jazz festivals in Europe
- Pori
- Gold dissolving mixture aqua __
- Regia
- Musical instruction meaning dry
- Secco
- One of the two main branches of Islam
- Shia
- Genus and species of the little bustard
- Tetrax
- Color slightly
- Tinge
- Fuzzy Wuzzy end?
- Was he
- Daughter of Lenny K and Lisa B
- Zoe K
Video game characters (right to left, top to bottom)
- Aeris - Final Fantasy VII -> Aris
- Nerf -> E
- Altair - Assassins Creed -> Altar
- Nerf -> I
- Aponi Brightmane - World of Warcraft -> Poni
- Nerf -> A
- Arthas - Heroes of the Storm -> Earthas
- Buff -> E
- Ashe - League of Legends -> Was he
- Buff -> W
- Barret Wallace - Final Fantasy VII -> Barrett
- Buff -> T
- Beat - Jet Set Radio -> F-Beat
- Buff -> F
- Blue - Pokemon -> Ble
- Nerf -> U
- Bob - Bubble Bobble -> BYOB
- Nerf -> Y
- Chaser - Chaser -> Caser
- Nerf -> H
- Cloud - Final Fantasy -> Loud
- Nerf -> C
- Ecco - Ecco the Dolphin -> Secco
- Buff -> S
- Eddy - Tekken 7 -> Geddy
- Buff -> G
- Erica Ricci - Contra -> Eroica
- Buff -> O
- Ezio - Assassins Creed -> EIO
- Nerf -> Z
- Gnar - League of Legends -> Gnarr
- Buff -> R
- Mable - Mable and the Wood -> Male
- Nerf -> N
- Mei - Overwatch -> Mebi
- Buff -> B
- Ogma - Fire Emblem: Shadow Dragon -> Dogma
- Buff -> D
- Oni - Street Fighter -> Joni
- Buff -> J
- Ori - Ori and the Blind Forest -> Pori
- Buff -> P
- Qbert - Qbert -> Bert
- Nerf -> Q
- Regina - Dino Crisis -> Regia
- Nerf -> N
- Ryu - Street Fighter -> Mr. Yu
- Buff -> M
- Shiva - Final Fantasy IV -> Shia
- Nerf -> V
- Tetra - Legend of Zelda Wind Waker -> Tetrax
- Buff -> X
- Tingle - The Legend of Zelda -> Tinge
- Buff -> L
- Zoe - League of Legends -> Zoe K
- Buff -> K
We noticed that each video game character was only one letter off to the answers to the earlier clues. Each one is either missing a character (nerf), or gained a character (buff). In the crossword, we notice a pattern that the buffs are across clues while the nerfs are down clues. Each letter in the upper left corner of a square on the rossword means that we need the video game characters name who was either buffed or nerfed by that character.
Finally, we can see the answer revealed by the green squares, by reading them left to right, top to bottom.
Answer
LEVELTHREE
Puyo Puyo
Description
Basic rules
Puyo Puyo is a puzzle game. The player drops pairs of little colorful blobs (Puyo) into a well. After gravity does its work and all pieces come to rest, if any group of 4 or more Puyo of the same color are connected to each other orthogonally, they burst, allowing the Puyo above them to fall down in their place. If two or more such groups exist, they all burst simultaneously.
This can cause a chain reaction. If the effects of gravity cause another group of 4+ Puyo to become connected, then those burst. This continues until no such groups remain, at which time the player can drop the next piece.
The problem
You will be given an input representing a Puyo Puyo game. The well is empty at the start of the game. Compute the score of the game after all given pieces have been dropped.
The well is 6 columns wide and 12 rows deep. You may assume that the Puyo will never be stacked to a height greater than 12 at any point during the game. You may also ignore the red “X” in the given examples; in the real game, covering this “X” causes the player to lose the game. This will not happen in this problem.
Scoring
Note that this problem uses a simplified scoring system that differs from real Puyo Puyo games.
When one or more groups of Puyo burst, they score P2 × C2 points, where:
- P is the number of Puyo that burst simultaneously. Note that only the total number of Puyo matters; the number of different colored groups that burst in each round of the chain is irrelevant.
- C is the current chain level. For Puyo that burst as a direct result of the player dropping a piece, C = 1. The value of C goes up by 1 each time the chain is extended because gravity caused another set of Puyo to burst.
Input format
Each line of the input represents one 2×1 piece being dropped into the well. Each line contains 4 characters, separated by spaces:
- The color of the “first” Puyo. There are four possible colors: R, G, B, or Y.
- The color of the “second” Puyo. Again: R, G, B, or Y.
- The orientation in which the piece was dropped:
- H means horizontal. The “first” Puyo goes on the left, and the “second” Puyo goes immediately to its right.
- V means vertical. The “first” Puyo goes on the bottom, and the “second” Puyo goes on top of it.
- The column in which the “first” Puyo was dropped. The columns of the well are numbered 0 through 5, from left to right.
- For Horizontal pieces, this value can be between 0 and 4, inclusive. The “second” Puyo falls in the next column to the right, i.e., between 1 and 5, inclusive.
- For Vertical pieces, this value can be between 0 and 5, inclusive.
This input describes the 5 pieces dropped in the example video above:
R Y V 0
G G V 3
R B H 4
B Y H 1
Y G H 1
Your input
The input is 140 lines long. It is also available for download as a text file.
Work
public class HelloWorld{
// Create a 6x12 board
static char[][] board = new char[12][6];
public static void main(String []args){
String input = "R R H 0,Y R V 1,Y Y V 0,G Y V 0,B G H 2,R B V 2,G B H 1,G R V 1,G R H 1,B G V 3,Y G V 4,Y Y V 5,G Y H 3,Y R H 4,R R V 4,R B H 4,B B H 4,Y B H 3,Y Y H 2,R R V 2,B R H 0,B B V 0,Y B V 3,Y R V 1,Y Y H 2,G G V 4,R B V 5,G G V 4,R G H 1,R Y H 1,G B H 3,G R H 3,G B H 0,B R V 2,Y G V 3,R Y V 4,Y B H 4,B Y V 4,Y Y V 3,G R H 0,G R H 0,R G V 1,G Y V 4,B B V 3,B R H 3,R B V 4,R Y H 1,G R V 3,G Y H 2,R Y H 4,B Y H 3,B G V 3,G B H 3,B G V 4,Y R V 5,B R H 4,Y Y V 4,G B V 3,Y G H 1,R R V 3,G B H 2,Y Y V 2,R B H 2,B R H 1,R G H 0,G R H 1,B B V 0,G Y V 1,Y G H 4,G Y V 5,B Y H 0,R R H 1,B R V 0,G G H 1,R G H 0,Y Y H 1,B B V 1,R G H 3,Y G V 2,G Y V 3,R Y H 1,B B V 0,B R H 3,Y G H 2,R B H 4,R B H 4,R R H 4,B R H 4,Y G H 2,G Y H 3,Y G V 3,B B V 4,G Y H 3,R Y V 2,B R H 4,G G V 3,B R H 4,B G V 4,B Y H 2,Y G H 0,R Y V 4,Y R V 0,R R V 0,B B V 5,G R H 3,B G H 2,G Y V 3,Y B V 5,Y G V 3,B G H 4,B Y H 4,R G H 3,Y G H 3,R Y V 2,Y R V 2,G B H 4,B R V 4,R B H 4,Y G H 3,R B H 4,Y G H 3,G R V 1,R B H 4,B G H 3,Y Y V 1,Y B H 4,R R V 5,G Y H 2,B R H 0,G Y H 1,G B V 1,G R H 2,B Y V 4,R Y V 2,G B V 5,R Y H 3,G B H 4,Y R V 3,R G V 3,B B V 5";
String sample = "R G H 0,R G H 0,R G H 0,Y Y H 0,Y G H 0,R B H 0,Y B H 0,B B H 2,B G H 2,R B H 4,R B H 4,G Y H 1,G R H 3,B Y H 1";
String[] moves = input.split(",");
int score = 0;
for (String move : moves) {
System.out.println (move);
// Parse input
char color1 = move.charAt(0);
char color2 = move.charAt(2);
char orientation = move.charAt(4);
boolean horizontal = false;
if (orientation == 'H') {
horizontal = true;
}
int col = Integer.parseInt(move.charAt(6) + "");
// Drop the puyos
dropPuyos (color1, color2, horizontal, col);
printBoard();
score += getMoveScore();
}
System.out.println(score);
}
// Drop a two-puyo piece on the board
public static void dropPuyos (char color1, char color2, boolean horizontal, int col) {
dropPuyo(color1, col);
if (horizontal) {
dropPuyo(color2, col + 1);
} else {
dropPuyo(color2, col);
}
}
// Drop a single puyo on the board
public static void dropPuyo (char color, int col) {
int row = board.length-1;
while (board[row][col] != '\u0000') {
row--;
}
board[row][col] = color;
}
// Get the score after a single move
public static int getMoveScore () {
int score = (int) Math.pow(combine(), 2);
int chain = 1;
int totalscore = 0;
// Loop until we're done combining
while (score != 0) {
totalscore += score * (int) (Math.pow(chain, 2));
clear ();
chain++;
score = (int) Math.pow(combine(), 2);
}
return totalscore;
}
// Combine and and disappear 4 or more connected puyo
public static int combine() {
int score = 0;
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[r].length; c++) {
if (board[r][c] != '\u0000' && board[r][c] != '!') {
int numConnected = numConnected(r, c, board[r][c]);
// More than 4 puyo were connected
if (numConnected >= 4) {
score += numConnected;
mark (r, c, board[r][c]);
}
}
}
}
return count();
}
// Count the number of '!'s on the board
public static int count () {
int count = 0;
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[r].length; c++) {
if (board[r][c] == '!') {
count++;
}
}
}
return count;
}
// Get the number of connected
public static int numConnected (int r, int c, char tgt) {
// Base case, we're out of bounds
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {
return 0;
}
// Base case, we're not touching the same color
if (board[r][c] != tgt) {
return 0;
}
board[r][c] = '!';
// Check the other 4 directions
int score = 1 +
numConnected (r+1, c, tgt) +
numConnected (r-1, c, tgt) +
numConnected (r, c+1, tgt) +
numConnected (r, c-1, tgt);
board[r][c] = tgt;
return score;
}
// Mark connected puyo with '!'
public static void mark (int r, int c, char tgt) {
// Base case, we're out of bounds
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {
return;
}
// Base case, we're not touching the same color
if (board[r][c] != tgt) {
return;
}
board[r][c] = '!';
// Check the other 4 directions
mark (r+1, c, tgt);
mark (r-1, c, tgt);
mark (r, c+1, tgt);
mark (r, c-1, tgt);
}
// Clear all blocks with a '!'
public static void clear () {
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[r].length; c++) {
// Found a square that needs to be cleared
if (board[r][c] == '!') {
for (int i = r; i > 0; i--) {
board[i][c] = board[i-1][c];
}
board[0][c] = '\u0000';
}
}
}
}
// Print out a representation of the board
public static void printBoard() {
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[r].length; c++) {
if (board[r][c] != '\u0000') {
System.out.print (board[r][c] + " ");
} else {
System.out.print (". ");
}
}
System.out.println();
}
System.out.println();
System.out.println();
}
}
Answer
17777
Quotris
Be sure to clean up when you’re done.
Work
Based on the layout of this puzzle, we know that it is referencing Tetris, so we assume that the pieces will drop on the board like in tetris (from top to bottom). Each piece is 4 blocks, and there are 10 of them, and it takes 4 full rows (or 40 blocks), to get a tetris. With that in mind, we’re looking for an arrangement of blocks that can be dropped in the order given, and will fill 4 rows completely. And although blocks in Tetris can be rotated, since the letters are in a clear orientation here, I avoided rotations.
Using photoshop, I arranged the pieces according to the constraints, and it helped that words soon began to form between the pieces, which speeded up solving time.
Reading the letters from left to right, top to bottom, we get
ANSWER IS NAME OF TYPE A THEME COMPOSER
Type A is one of the soundtracks in the original Tetris game, so all we need to do is look up the composer of that work.
Answer
HIROKAZUTANAKA
Slide to Safety
Description
Oh no! While out exploring the ice caves, the ground underneath you collapsed and you fell down into a particularly icy cavern below. You’ll need to escape quickly before you freeze!
When you are standing still, you can move to an adjacent square in any of the four directions (up, left, down, or right). But each time you move, you will slide on the ice, lose control, and continue moving in the same direction until you hit a boulder.
- Sliding to an adjacent square takes 1 second for each square you move.
- Hitting a boulder will stun you so that you are unable to move for 60 seconds.
- You cannot occupy the same square as a boulder, or pass through a square with a boulder. If you slide into a boulder, you will be stunned and stop in the square next to the one with the boulder.
- The time stops when you reach the open square in the center of the bottom row of the cave. There is no ice here, so you can stop on this square without hitting a boulder (and without being stunned).
If you take the fastest route, how long will it take, in seconds, for you to exit the cave as you slide to safety?
Example: For your first move, you can move to the left or the right because there is a boulder in the way if you try to go either up or down. If you go left, you will slide 1 square for 1 second, hit a boulder, and then be stunned for 60 seconds, meaning you can move again in 61 seconds. If you go right, you will slide for 14 squares, hit a boulder, and then be stunned for 60 seconds, meaning you can move again in 74 seconds.
Data for the cave is provided below. It is also available for download as a text file. All coordinates are listed with the vertical coordinate first and the horizontal coordinate second, where (0, 0) is in the upper left corner of the cave. The grid of boulders and list of boulder locations represent the same data, just in different formats — feel free to use whichever is most convenient.
Cave height: 30
Cave width: 51
Starting location: 1, 25
Target location: 29, 25
Grid of boulders:
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
B B B B BB B B B B
B B B BB B B B B B
BBBB B BB B B B B B B B B B B
B BB B BB B B BBB B B BBB B B B
BB B B B B B B B BB
B B B B B BB B B
BB B B B B B B B B
B B B B B B BB B B B B
B B BB B B B B B B
B BB B B BB B B B B
B B B BB B BBB B
B B BB B B B BB B B BB
B B BB B B B BBB
B B B B B B B BB
B B BB B B B B BB
B B B B B BBB BBB B
B B B B B B BB
BB B BB BB B B B B
B B B B B B B B B
BB B BBB B B B B B B B B
B B B B B B B BB B
B B B B B BB BB
B B BB B B B B B B B B
B B BB B B B B
B B B BB B B B
BB B B BB BBB B B BBB B B
B B B B B B B
B B BB B B B BB B B B B
BBBBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBBBB
Work
I represented the cave as a graph, where the outgoing position edges from a free space represented the spaces you could slide to. Then I ran Dijkstra’s algorithm to get the shortest path.
import java.util.*;
import java.io.*;
public class Test {
// Nested node class
public static class Node implements Comparable<Node> {
String coord;
List<Edge> outgoing;
boolean visited;
int pathWeight;
public Node (int r, int c) {
this.coord = r + "," + c;
this.outgoing = new ArrayList<>();
this.visited = false;
this.pathWeight = Integer.MAX_VALUE;
}
public int compareTo(Node other) {
return Integer.compare(this.pathWeight, other.pathWeight);
}
}
// Nested class for an edge in the graph
public static class Edge {
String dest;
int cost;
public Edge (int r, int c, int cost) {
this.dest = r + "," + c;
this.cost = cost;
}
}
static HashMap<String, Node> graph = new HashMap<>();
public static void main (String[] args) {
// Create the cave and the other given variables
boolean[][] cave = new boolean[30][51];
int startRow = 1;
int startCol = 25;
int endRow = 29;
int endCol = 25;
Scanner sc = null;
// Get the boulder location input
try {
sc = new Scanner (new File("input.txt"));
} catch (FileNotFoundException e) {}
int r = 0;
// Read in the input
while (sc.hasNextLine()) {
String line = sc.nextLine();
for (int c = 0; c < line.length(); c++) {
if (line.charAt(c) == 'B') {
cave[r][c] = true;
}
}
r++;
}
// Build the graph
for (r = 0; r < cave.length; r++) {
for (int c = 0; c < cave[0].length; c++) {
if (!cave[r][c]) {
buildGraph(cave, r, c);
}
}
}
// Run shortest path algorithm on the graph
System.out.println(dijkstra(startRow, startCol, endRow, endCol));
}
// Given a free space, find the boulders you would run into when
// sliding up, down, left and right
public static void buildGraph(boolean[][] cave, int r, int c) {
Node newNode = new Node(r, c);
// Slide down
int i = r;
while ((i+1) < cave.length && !cave[i+1][c]) {
i++;
}
newNode.outgoing.add(new Edge(i, c, Math.abs(r-i)));
// Slide up
i = r;
while (!cave[i-1][c]) {
i--;
}
newNode.outgoing.add(new Edge(i, c, Math.abs(r-i)));
// Slide right
i = c;
while (!cave[r][i+1]) {
i++;
}
newNode.outgoing.add(new Edge(r, i, Math.abs(c-i)));
// Slide left
i = c;
while (!cave[r][i-1]) {
i--;
}
newNode.outgoing.add(new Edge(r, i, Math.abs(c-i)));
// Put nodes in graph
graph.put (r + "," + c, newNode);
}
// Find shortest path
public static int dijkstra (int startRow, int startCol, int endRow, int endCol) {
Node startNode = graph.get(startRow + "," + startCol);
startNode.pathWeight = 0;
String end = endRow + "," + endCol;
PriorityQueue<Node> queue = new PriorityQueue<>();
queue.add(startNode);
while (!queue.isEmpty()) {
Node cur = queue.remove();
// Have we seen this node before
if (!cur.visited) {
cur.visited = true;
// We've reached the end
if (cur.coord.equals(end)) {
return cur.pathWeight;
}
// Loop through all connected vertices
for (Edge edge : cur.outgoing) {
Node nextNode = graph.get(edge.dest);
int newCost = cur.pathWeight + edge.cost;
// Account for slamming into a boulder unless we're at the end
if (!edge.dest.equals(end)){
newCost += 60;
}
// Check if the new path is better
if (!nextNode.visited && newCost < nextNode.pathWeight) {
nextNode.pathWeight = newCost;
queue.add(nextNode);
}
}
}
}
return -1;
}
}
Answer
134