# Brute-Force

When you're not sure where to begin with a problem, a good place to start is to come up with a brute-force solution. That is, a solution that simply tries every possibility.

Take a look at the problem Frog from AIO 2013. In this problem, you're tasked with helping Bazza and Shazza pick three fence posts to make the most difficult obstacle course for the sugar frogs.

It's not easy to know which fence posts you should pick, so why not try every possible combination? This is quite inefficient, but if you look at the Constraints section at the bottom, there are marks available for less efficient solutions. A brute-force algorithm looks something like this:

for i = 1 to N:
for j = i+1 to N:
for k = j+1 to N:
# Check if the i-th, j-th and k-th fence posts form a valid obstable course.
# If they do, record the difficulty.

# Print the greatest difficulty seen.

This algorithm pretty clearly produces the correct answer since it tries every possibility. This is unfortunately really slow, but it is good enough to run in time for $$N \leq 300$$. Implementing this would give us 30 marks. Not bad!

We haven't yet discussed how to tell an algorithm is too slow, but as a general rule of thumb: the more nested loops your program has, the slower it is. We'll cover this topic in more detail later.

Brute force solutions are rarely efficient enough for full marks, but they can often score you partial marks, and serve as a good stepping stone towards the full solution.

## Exercises

• Implement the brute-force solution for Frog.
• Come up with a brute-force solution for Snap Dragons and implement it (scoring 50 marks).
• Extension: Can you come up with a more efficient solution to Frog?