Part One:
GCDivide and Conquer
Having spent the day improving the lives of both the mathematicians and the flintknapper, you pause to take it all in. Problems solved, tools restored, and burdens lifted… it feels like a fitting repayment for the generosity and hospitality this village has shown you since your arrival. But, as charming as this place is, and as warm as its people have been, you know you cannot simply settle here and live out your days.
Your real task still looms: you must find your crewmates and Captain Xarlos, and figure out how to fix this time-slip. Are they even anywhere near this region? Are they even in the same century?
To properly say your goodbyes and show gratitude, you visit the tribal elder. During your time together, you ask her for guidance on where you should begin your journey. In response, she tells you the legend of the Great Crossing Dinosaur (GCD), known to her people as the Sooshasaurus.
According to tradition, a primeval, gentle giant has roamed these lands since time immemorial: a magnificent creature with a long, elegant neck, a great sweeping tail, and skin that glitters like diamonds in the sunlight. What makes the Sooshasaurus remarkable is not just its size, but its path. It travels in a perfect diagonal across the vast region separating this village from the next: a region that is a tapestry of thorns, mud, puddles, grass, stone, logs, flowers, pebbles, sand, forest, sea, ash, and frost.
Over generations, the creature has learned the safest, most stable route across this unruly terrain. Its path is as reliable as it is ancient.
The elder presses a map, your puzzle input, into your hands. It is a great scroll marked with capital letters that denote the ground type in each square of the terrain.
"You must follow the Great Crossing Dinosaur's route," she says, pointing to the top-left corner. "Begin where we stand, and travel to the bottom-right corner. The land is treacherous, so stay on the diagonal the Sooshasaurus has walked since the first dawn."
You unroll the map, and immediately understand why she calls the journey perilous. It's a sprawling mosaic of hazards and beauty alike. Each square is labeled with a letter indicating a particular terrain:
- L and Y: Mud
- Z and D: Volcanic Ash
- G and V: Grass
- O and T: Fallen Logs
- N and U: Deep Water
- A and K: Thorns
- M and C: Sand
- I and Q: Flowers
- H and F: Forests
- J and R: Permafrost
- E and X: Shallow Water
- S and W: Pebbles
- P and B: Rocks
To follow the Sooshasaurus' diagonal path from the top left to the bottom right, you must first determine how many squares that ancient creature's footsteps truly cross.
If the diagonal passes even slightly through a square, that square is considered crossed.
If the diagonal passes exactly through the vertex, then neither square to the left nor the right of the diagonal is touched.
For example:
If your map is a 4x6 grid:
traveling from the top-left corner to the bottom-right corner
would cross 8 squares.