Main image of article May's Programming Challenge: Resource Trading
In this problem, you are given a 20x20 map that contains 20 trading islands, each occupying a square. Each island is a trading port for gold, iron and wood. The map also contains a few reefs and uninhabited islands. The goal is simply to sail a ship from the top left square (0,0) and eventually end up at the bottom right (19,19) having earned as much as possible. Click here to find Java developer jobs. Your ship can sail to any island and buy or sell resources, but the prices of the resources vary depending on the island. You start with $10,000 and it costs $4 to move from one square on the map to the next. The total cost of your moves is deducted when you reach square (19,19), not during the voyage. Your ship can carry no more than 2,000 of each resource, and has fuel and food for the crew for 1,000 moves.

Choosing the Winner

Once your ship enters (19,19), the gold, iron and wood on board is valued at the average price across all 20 islands and any remaining cash is added. The number of moves * $4 is then deducted, and the highest remaining value wins. If your ship runs out of moves before reaching (19,19), it’s classified as “lost at sea” and automatically receives a score of zero.

The Programs

Your program should read in a text file (input.txt) from the same folder your program’s in; It contains 40 lines of input, the first of which are 20 rows of 20 characters: the map. The trading islands are represented in them by the letters A through T. The other characters represent either sea (‘~’), or reefs and unoccupied islands (‘*’). After the first 20 lines, there’s another 20 lines containing four comma separated integers. The first, a number from one to 20, is the island index (corresponding with the letters A through T), and the other three are the prices of gold, iron and wood on that island, respectively. Here’s a sample input file. Your Program must calculate a route to earn you as much money as possible. Note the following:
  1. Your ship must visit a minimum of ten islands. If it fails to visit at least 10, it’s disqualified.
  2. Visiting an island means moving to any of the sea squares next to the island square, horizontally, vertically or diagonally.
  3. Ships cannot move into or through islands or reefs.
  4. The sample map provided is not the map that will be used!
  5. The ship starts with 0 Gold, 0 Wood, and 0 Iron.
  6. You can spend or buy any amount at each island, issuing 0 or one buy orders and/or 0 or one sell orders for each visit to the island.
  7. You can only exchange dollars for gold, wood or iron when next to an island, at that island's prices. You can also exchange gold, wood and iron for dollars when you’re next to an island, at the island’s price.
  8. You can visit any island without buying or selling.
  9. You can revisit an island as often as you like.
  10. Your program should take no longer than one minute to run. Any longer and it's "lost at sea."

The Output

Please output the following to a file called voyage.txt in the same location as your program: Each time you move from one island to another, print your voyage as a series of numbers (1-8), with each number representing the direction of the next square on the map to which you moved. Use the number one to represent a move north, two to represent north-east, and so on, with eight representing north-west. Thanks to this system, you might end up sailing 5543333333333333. Output that as one line, followed by a line stating the amount of gold, iron and wood you want to buy; a line with the amount of gold, iron and wood you want to sell; and then the map (all 20 x 20 chars) where you use a ‘^’ to show each square you sailed through (and an ‘@’ at your current location). So the first move might be: 
333
Buy 50/0/0 at 4/8/10 costing $200 leaves $9,800.
^^^@~~~~~~~~G~~~~~~~
~~~~A~~~~~~~~~~~~Q~~
...
~~~~~~T~~~~~~~~~J*~~
another possible move: 
3333444
Buy 0/100/0 at 5/7/11 costing $700 leaves $9,350.
Sell 50/0/0 at 5/7/11 earning $250 leaves $10,050
^^^^^~~~~~~~G~~~~~~~
~~~~A^~~~~~~~~~~~Q~~
~~~~~~^~~~***~~~~~~~
~~***~~@F~~~**~~~~~~
...
Please output the whole journey in the one file. Each section should have one line listing the moves, 0-2 lines for any buy/sell orders, and 20 lines showing the map. The last line in the voyage.txt file should be the total number of moves, the total cost of them (the number of moves * $4) and the total money left over after the moves are subtracted. 
800 moves costs $3200 leaving $24,567.

Submitting Code and Compiling

Please submit your C, C++, C# or Java entry zipped up as an attachment to this email address, and please don’t include any executable binaries such as exes or dlls. C++ and C# programs will be compiled in Visual Studio 2012. Please include all the project and solution files such as .suo, so I can open the solution and build it. Code built with earlier versions (VS 2003, VS 2005, VS 2008 and VS 2010) is acceptable. If you use GCC/G++, please let me know and include your preferred command. I use MinGW to build that on my Windows PC. All programs are compiled in Release mode, so please specify any optimization flags for GCC/G++ or specify them in the solution. For Java, I have Java 7 installed on my PC. If you use any third-party open source libraries that need to be installed, please let me know. I try to compile/run them using javac but I can build projects in Eclipse if needed. It’s acceptable to submit newer versions throughout the month of May, right up until the deadline of June 5th. If you’ve sent in several, the most recent will be used. The prize is glory and a Dice USB wall adapter. At the end of the competition, we’ll publish a discussion of the algorithms used and highlight a winner. Be sure to include your name and website in the source code comments. By entering this contest you agree to allow Dice to publish your source code with credit to you as the copyright owner.

Related Stories

Image: Wikipedia