About the Firebase Programming Challenge
The goal of our programming challenge is to give you a difficult CS problem and ample time so that we can see how you tackle hard problems. We'll evaluate your solution first and foremost by the score achieved when it is run against a secret "master" test file. But we'll also closely review your code for readability, algorithm / data structure choices, performance, correctness, etc. So please make sure your code is reasonably clean for your final submission. Consider adding comments to explain key elements, known deficiencies, etc.
If you are asked to come interview on-site at Firebase, we will use your solution to this challenge as a starting point for technical conversations. Be prepared to present and discuss your code.
This test is intended to take about 6 hours. You may spend more or less as you see fit, but there is a hard time limit of 16 hours.
You may use whatever programming language you like to complete this test. We really don't care as long as it works and is readable. We recommend using whatever language you are most comfortable with (don't, for instance, write it in C just for better performance).
You must submit your solution by emailing it to challenge@firebase.com. Please provide directions on how to execute your program if it is not obvious. Note that you are welcome to make multiple submissions, and we'll only evaluate the best one. So if you have something "pretty good" after 4 hours, we suggest sending that in before diving into a crazy new algorithm. Submitting a working version early also allows us to give you feedback in case we're not able to get your solution working on our side.
We'll run your solution on a current-gen Macbook Pro and it must complete in under 10 minutes on a test size of 100 maps. Weight will be given to time-efficient algorithms.
You may use the internet during this test. However, if you use code from any 3rd party source, you must identify it as such and cite where you got it. Any hint of plagiarism will immediately disqualify you. PLEASE DO NOT discuss this test with anyone, either while you are taking it or after the fact. We want to keep it a secret so that everyone is on a level playing field.
The Gold Mine
Imagine you are a miner in an underground cavern. Your job is to collect nuggets of gold from the cave. You have been provided a map of the cave and need to plan what route you are going to take through the cave to get the largest amount of gold possible in the time provided.
An example map looks like this:
=3,3,4 s.1 .w. .d6
The first line in a map will always begin with an '='. This marks the beginning of a map. After the '=' are the number of rows, number of columns, and the number of moves you are allowed to make.
The following lines represent a grid consisting of various different characters with the following meanings:
| s | Your start position |
| . | empty space |
| w | A wall. You cannot pass through a wall. |
| d | A "pickaxe" that will double the points you score for all gold you pick up after this point. "pickaxes" stack, so if you pick up 2 'd's, then all gold will be worth 4 times as much from that point on. (The 'd' stands for 'double'). |
| 1-9 | Gold, in varying amounts. You'll score points when you pick these up. |
Your solution for a map should be a string containing the steps you should take to score the maximum number of points (the most gold). It should be in the form of a string using the characters 'l' (left), 'r' (right), 'u' (up) , and 'd' (down). You can only move in these directions. You cannot move diagonally. You can only consume gold and pickaxes once.
An example solution to the map above could be:
ddrr
This would score you 12 points, as you would pick up the pickaxe (the 'd') which doubles future points, and then you would pick up 6 gold.
Your Task
Write a program that takes a file as input that contains many maps (one after another) and outputs another file that contains one solution for each map, with the solutions separated by newlines.
Your total score for this test will consist of the sum of your scores on 100 large maps, each with sizes of 30-50 per side and 30-50 allowed moves (You may need to optimize your algorithm accordingly). Note that if you provide a solution that runs you off of the map, into a wall, or uses more than the allowed number of moves you will recieve a zero for that map (and too many of these will automatically disqualify you... it's best to never give "illegal" solutions). Note, however, that you may use fewer than the allowed number of moves with no penalty.
To test your program, you can run it against the example test files we've provided below or you can generate similar test files using GoldMine.jar.
Your goal is to score higher than the GoldMine.jar reference implementation below.
Tips
- We recommend starting with a simple algorithm that generates valid solutions (regardless of score) before diving into a more complicated solution. Once completed, you can send it to challenge@firebase.com.
- Do not attempt to find the optimal solution. We don't believe this is possible within the given constraints. Try to just find a *good* algorithm that runs in a reasonable amount of time and beats the reference implementation in the jar file.
- The data that we run your solution against is a secret "master" test file. It will be very similar to the data in the fulltests file below. The tests are randomly generated and have the same distribution of different map elements. We are not hand-crafting maps in an attempt to break certain types of algorithms. However, you should be careful of edge cases which could crash your solution.
Resources
Example test file
Example answer file - Set of example solutions for above test file.
Example "Full" test file - a test file of the same size and approximate distribution of items as the one
we will use to evaluate your solution.
GoldMine.jas is a utility that can help you create tests and check your answers. It has 3 modes:
1) Evaluate solutions. This command will check your answers against a test file and give your answers a score. The arguments here are the test file and the answer file. Example:
java -jar GoldMine.jar evaluate testfile answerfile
2) Solve test files using Reference Implementation. This is here to show you how your program should behave and is the baseline against which your solution will be compared.
Example:
java -jar GoldMine.jar solve testfile answerfile
3) Create random tests. You can use this to generate extra test files for testing. The arguments are the number of tests to generate in the file, and the name of the output file. Example:
java -jar GoldMine.jar generate 100 outfile