Optimization problems are notoriously tricky and fun to solve.  Examples include finding the best route to deliver packages across a busy metropolis, laying out a store to maximize sales, or mining crystal deposits before an alien invasion.  For this challenge, we're giving you a new take on optimization problems that require balancing budget, time, and space.

For this challenge, you must build an algorithm that solves the most profitable solution by sending workers to collect Rewards over a map area within a particular time and budget.  There are several rules that your solution must factor in, which are discussed below.  

You can start this challenge in two ways.  If you are new to optimization problems or want an easy warm-up, then stay on this challenge.  If you want to try the big, complex challenge, check out the full challenge (link).  Both contain the same problem space and rules, but different levels of complexity.  Solutions for the Sandbox model won't be considered for the full challenge.

The Problem Space

There are five elements to balance when building a solution:

• Maximizing the amount of Rewards extracted.

• Hiring the right amount of Workers to collect Rewards.  

• Accessing the Graph where Rewards are distributed in the most efficient manner.

• Staying within a budget of $10,000.

• Completing the worker within 20 time steps.

The goal is to maximize the Profit (Total Reward Extracted - Total Costs) by hiring the right amount of Workers to collect as many Rewards across the Graph within the given time. Let’s discuss each element in more detail.

The Graph can be considered a map where the Workers navigate to collect Rewards (Figure 1). The Graph is a randomly distributed set of nodes and edges. Each node, or site, can either be empty or contain a Reward. Workers travel along edges to access different sites to extract Rewards. There is one unique site, the Origin, where all Workers start from.

Rewards can be considered minerals, tomatoes, Bitcoin, etc., that Workers collect. Rewards are not the same as Budget. Some sites contain higher value Rewards than others and take more time to acquire those Rewards: 

• Type 1 sites (red) have a low Reward value and can be acquired in a few time steps.

• Type 2 sites (blue) have a medium Reward value and can be acquired over more time steps.

• Type 3 sites (green) have the highest Reward value but take the longest number of timesteps to acquire.

Figure 1: Test Graph for Slightly Off the Beaten Path.  Your algorithm must navigate workers to find the most profitable path to collect Resources.

Workers can be thought of as drone chile harvesters, miners of the Klondike Gold Rush, or any other clever analogy you want to imagine. Workers are hired to do the Reward extracting and have a cost each time step. Your Budget is the only limit to the number of Workers you can hire. Just like Rewards, there are three different types of Workers. Worker types have different time step rates and extracting rules:

• Worker 1 Type costs 100/step and can only extract Type 1 sites.

• Worker 2 Type costs 200/step and can extract Type 1 and Type 2 sites.

• Worker 3 Types costs 500/step and can extract Types 1, 2, and 3 sites.

Workers can only move one unit per time step. However, Workers can use sites indefinitely (backtrack, travel while another Worker is on-site extracting). 

The Budget and time limit are self-explanatory. A solution must stay within the Budget when hiring Workers. Rewards cannot be added to the Budget. A solution can only operate for 20 time steps. 

While these rules are straightforward, only an efficient algorithm can find the best path to maximize profit on larger graphs.

Evaluation

Submissions for the challenge are your proposed best path to maximize profit (Total Reward Extracted - Total Costs) on the Test Graph. The Live Leaderboard scoring algorithm is the total profit of the path you submit.  The Lyra Graphtool has built in functions to export your best path and to calculate profit. This is a Sandbox challenge, so there will be no final evaluation.  Enjoy.