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, TT. This will be the number of grids for which you must solve the given puzzle. T1T \geq 1 always.
  • This will be followed by TT mazes, each of the following format:
    • The first line will have two numbers separated by a space: WW and HH. These indicate the width and height of the grid, respectively, and W,H1W, H \geq 1 always.
    • The next HH lines will each contain WW 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.
  • L\text{L} represents Link's starting location, if applicable to the current problem. The square is considered to be open ground for traversal purposes.
  • H\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.

Problems 1-5:

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.

Problems 6-10:

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.

Problems 11-15:

These problems are designed to be challenging to all participants. If problems 1-5 aren't a walk in the park for you, these problems are quite possibly beyond your reach. 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
4 years, 11 months ago

No vote yet
1 vote

  Easy Math Editor

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. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...