# The Lost Woods - Foreword

Introduction:

Cue music.

Welcome to The Lost Woods! The fabled forest is a home to many mysteries, myths, and legends, with no small number of challenges to be taken within its far reaching boundaries. Whether you are a beginner, an amateur, an expert, or even if you've never tackled such challenges before, there is certainly something for you here.

These problems are based almost entirely in the realm of Graph Theory. Some of them may simply be classical applications of well known graph problems, requiring very little adaptation on the programmer's part to go from a standard algorithm to one that solves the given problem. Others require more advanced thinking, deeper knowledge of Graph Theory, stronger programming implementation skills, or perhaps some combination of all three.

While the problems themselves will be self-contained, and you will not need to be familiar with advanced CS and Graph terminology to understand the problem, solving the problems often will require such knowledge. At the very least, you should have medium strength or more in some programming language you can execute with, as these problems are not intended to be hand-solvable. It's also recommended that if you intend to tackle multiple problems in this set, to write your code out in a reusable way - some problems may be direct expansions of previous problems, or they may be more easily solved using methods explored in older, more unrelated problems.

Format:

This format is common to all problems in the set. If you followed a link that said 'Input Format' to this note, this is what you're looking for!

While every problem will be unique in terms of what must be solved for, and how the output must be formatted, the input format for each problem will be the same, excepting special markers, so it is highly recommended you make your input-parsing code as reusable as possible. The formal specification is thus:

• The first line in the file will contain a single number, $T$. This will be the number of grids for which you must solve the given puzzle. $T \geq 1$ always.
• This will be followed by $T$ mazes, each of the following format:
• The first line will have two numbers separated by a space: $W$ and $H$. These indicate the width and height of the grid, respectively, and $W, H \geq 1$ always.
• The next $H$ lines will each contain $W$ characters, representing the state of the grid.

Characters:

• $\text{\#}$ represents dense, impenetrable forest. Nothing can pass through it.
• $\text{.}$ represents open ground, through which everything can pass.
• $\text{L}$ represents Link's starting location, if applicable to the current problem. The square is considered to be open ground for traversal purposes.
• $\text{H}$ represents a Heart Piece, something Link often tries to collect. The square is considered to be open ground for traversal purposes.
• Other characters may be defined in the problem statement to represent other things.

Example:

3
3 2
L#H
.#.
5 5
H..#H
##.#.
..L..
.#.##
H#..H
1 7
#
#
#
L
#
#
#


Ranking:

These problems are arranged, subjectively by me, in what I perceive to be an increasing level of difficulty. Since I learned graph theory and programming paradigms in a particular order, and it is very likely that order is not the same order you learned things in, it is very likely you will not perceive the difficulty order of the problems to be perfectly increasing, and perfect consensus will therefore very likely be unattainable. That said, if there's some problem that seems woefully out of order, raise an objection and if there's enough yay-sayers I'll be happy to move it.

Introductory Problems:

These are basic, introductory problems. If you have a degree in CS you should be fine skipping these, but taking them on as a warmup might be preferable.

Intermediate Problems:

These problems require more intermediate difficulty Graph Theory algorithms and concept knowledge. If you have a degree in CS, you may have forgotten some of these if it's been a few years.

These problems are designed to be challenging to all participants. If the Introductory Problems aren't a walk in the park for you, these problems are quite possibly too advanced for your current skill set. Tread cautiously.

NO SPOILERS:

• Please don't post problem solutions or attempts on any of the notes for this set. If you have clarification questions, or wish to discuss solutions, use the appropriate channels for the individual problems as if they were stand-alone.
• All other discussion is perfectly welcome on the notes.

Note by Daniel Ploch
5 years, 5 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
• Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Is this inspired by A Dark Room?

- 5 years, 5 months ago

I've played that before, but I had forgotten its name. The short answer is no, not really - I got this idea a little over a year ago and finally decided to put it into action.

- 5 years, 5 months ago

It's funny to see how the introductory problem is worth 360 points!!!

- 5 years, 5 months ago

Indeed! I don't know how Brilliant ranks problems but I'd guess the high view:attempt ratio has something to do with it.

I think it's mostly just intimidating, instead of hard, but I'd be interested to hear more opinions. There are not many problems that involved large external datasets :)

- 5 years, 5 months ago