Playing “Golden Choice” with Javascript today I noticed that the source code provided originally seemed to be buggy. I rewrote the provided code and completed the level, but I had some questions.
How is one suppose to be able to interpret the number stated by the “warlock” ? Outside of creative coding, or picking the highest value route, I didn’t see a way to read this value. On earlier “wizard” levels one could use the command: hero.findNearestFriend().getSecret(); (Blackwoods Forest - The Wizards Plane)
Should the level require you to get exactly the number of coins that the “warlock” states? Right now you just have to pickup more coins then the number stated.
Is the Javascript code that was originally provided suppose to work? The code provided didn’t work like I thought it should. I could provide you with my version of the original code, that I have confirmed works and provides locations/values for all of the coins. What was the goal for the standard code base?
What was the lesson that was being taught for this level?
You should be able to find the path with the most gold from the grid.
See number 1.
JS code doesn’t seem to work, but it was mainly to generate a 2D array representing the map of gold. Though it is an advanced level, so I don’t think the sample code is too necessary.
Pathfinding, dynamic programming, BFS…it’s kind of just a puzzle level to me. (Maybe @Bryukh could answer that.)
Thanks. I will check the sample code. I tested it at the launch time, maybe something was changed.
That number is just “decoration”. Like a hint, debugging hint, how much you can collect.
If you can collect more than the warlock said - please, tell me about, because it’s some cheat in my level
Should work. I’ll check it again. That code creates the map of coins. Just a little help to abstract and write pure algorithm.
It’s advanced level, so you can solve it as you want. I hope you’ll use DP. But recursion of BFS (DFS) is ok here thus the level is small. But be careful for recursion for real cases, because it’s O(2^N) for that problem.
Just to be sure, what do the following acronyms stand for: BFS, DFS.
2. I will look into, but I was sure that I was seeing things like 74 required, but I collected 75… I finished it after being tired though, so I might have been imaging it. I will look into this for you. I know that at one point my algorithm was using “===” and I changed that to “>=” and it seemed to work better. I will rework the problem to look for the highest amount.
Several things to note about the level.
it is possible to solve the level by multiple tries and a simple start at MAX value of base ROW, then to check either check the 2 closest options on the next row up, or 4 options on that row (2 left, 2 right). One can for instance diagonal from a coin on Row 1 (2nd row) Col “1.5” to a coin on Row 2 (3rd row) Col “3”. Probably within 20 re-tries. Though the 4 choice option doesn’t create an optimal finish time…
I believe you can walk “between the coins” and cherry pick coins. from each row in kind. I will look into a solution that selects the highest coins from each row this way.
[edit]added more[/edit]
You don’t have to move after getting the last coin. The trigger seems to occur on leaving the coin space not when you take the coin.
You don’t have to move to the door to compete the level. (In many of the Kithgard dungeon levels, you are encouraged to move to the door to finish the level)
# The gate keeper will tell you how much you need.
# Always move in the direction of the exit.
# For each row you can take only one coin.
# Choose only one from the nearest coins in the next row.
Hint:
The gate keeper will tell you how much gold you need to collect.
Move in the direction of the exit.
After each coin choose one of the two (or one for edges) nearest coins in the next row.
Don’t stop and move exactly to the next coin. One wrong step and deadly beams will burn you.
And this is how I interpreted it:
Look for a way to read the gatekeepers number
Use this number as the magic key to search for during the execution of the algorithm
Create an algorithm that checks each node in the next row (up to 2 checks)
Stop when you reach the gatekeepers number and exit the algorithm
Build a “path” through the coins that can be later traversed
Walk to the door to exit the level
After preliminary assessment of the problem it was apparent that if we check 2 options per row per node it becomes 2^n. So for 10 rows it was 2^10 or 512. And since we had 10 columns or starting nodes, it was a maximum for 5,120 checks to solve the problem. Though since we were restricted to a small space and not a trapezoid the checks would range from the edge case of ~256 to the center of ~512. So somewhere around 3,900 tests. I resolved that recursion in this case would be fine as there were limited tests < 10k.
What I found frustrating is that I kept thinking that the warlock had a secret property that I could read like “.vale” or something to get this number. Since other levels in the game allowed you to do this it had created that association for me.
Perhaps what might have helped me is a statement like the following.
“Are you as smart as the gatekeeper of time?”
“The gatekeeper of time knows all and has instantly chosen the path with the greatest amount of gold”
“Can you find this path before time runs out?”
“The gatekeeper says how much gold is in the path, but you will have to find the right path on your own”
Hint:
“Look for the path with the greatest amount of gold”
No kidding you did! I saw that run time! I will try caching and think about an O(n) solution. Might take a while though. For most of the levels I was trying to get through them to finish more than create the optimal solution. That is for the second “go around” and refactoring.
The level can also be completed by walking “between the lines” and doing a MAX on each row. Which then gives the player more coins then the stated amount. For instance I was able to collect 88 coins on a level that required only 78.
This was achieved using horizontal and vertical path finding, not the diagonal. The diagonal doesn’t work any longer.
I rewrote the provided code and completed the level, but I had some questions.
)