Freelancer Challenge: Sijmen's Solution
The challenge [source web / source code] is as follows:
The destruction of Freeport 7 left you with almost nothing. The only thing you managed to save was your ship (with a bit of ore, water and engine parts stored in the cargo hold) and a star map. You decide to head to you home planet in the Codestar system and rebuild, trading at each planet you find along the way, so you have plenty of money when you arrive.
Sound easy enough? Well.. It wasn't for me. For 3 days straight I've been on this. Somehow it got me at third place.
The code on this branch is the latest greatest. I don't really understand how this configuration get's me the best monez.. but it does. There were many iterations:
- A long long time ago, when the challenge was still beatable by mortals I created this beast. It ain't pretty, was quite slow but it got me to the third place. (30s)
- The organizers felt it wasn't nice that 3 people solved it within 12 hours after launch. So they released an update.... this is where hell broke loose.
- I started improving 'te beast', resulting in this much faster knapsack thing. It still feels like magic and felt supersonic (0.3s).
- After inspecting the new challenge a bit I realized: Python ain't gonna cut it. Sooo introducing SPEEEED in the first GoLang version. It does the same, but much faster (0.01s).
- Jumps. 'Jumps are the future' i thought. Oh I was green. Look at this mess..
- It turned out, after struggling for many hours, that I forgot a very important rule:
The last planet in the star map is your destination.. Well shoot. Now I could revert the deals algorithm, the unknown algorithm and the 'smart' algorithm. - So let's revert back to GoLang v1. Now I introduced a weapon shopping list reaching 19093, personal record!
- With some manual tweaking (many more to come of that stuff) I got to 21297. WHOOO! This feels good.
- Now I realized I couldn't just try all combinations of weapons and ships. So i started brute-forcing. It took many many hours but it resulted in my almost all time high: 25383
- In the meantime I figured out that it is possible to describe all possible jumps-combinations in a recursive graph. For example, if you jump
+3, -1, the only way to ensure you can move on without leaving a gap is to immediately do another-1, +3. This graph looks something like:
- I wasn't sure if it is complete but having this graph meant I never ever had to worry again about which way to go. Having pointers in Go helped a lot.
- With this map I started doing lookahead: going forward n steps to see which direction would bring the most profit. I could only do around 10 before the number of options became unsolvable. This got me to 22252, disappointing.
- I did way to much tweaking of the 'best direction' system. I tried future net worth vs balance, I cursed all pointers.
- Like how does it happen that looking forward for 4 times gives a better result than 5, 6 or 7 look ahead? While 8 look ahead works again better? I still don't understand.
- After looking at the code for so many hours I didn't even understand it anymore, somehow I beat my old record by just a few hundred: 25494. This is the algorithm you are looking at now. If you run it you should (tm) get the same result.
This was great fun. A huge congratulations to Roy and Marijn for reaching even higher numbers, you really deserve that prize.
The (boring) licensee stuff
The pdf in this repo is copied from here (also made available here under the MIT License). Be sure to give them love, they are great.
I own all the code in this repo, you can use or change it. If you think it is genious, which I doubt, feel free to credit me. Aaaand if you win using this code, you for sure kan keep the prize. ;)