Golden Choice - Javascript - is this level completed?


#1

Playing “Golden Choice” with Javascript today I noticed that the source code provided originally seemed to be buggy. :frowning: I rewrote the provided code and completed the level, but I had some questions.

  1. 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)

  2. 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.

  3. 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?

  4. What was the lesson that was being taught for this level?


#2
  1. You should be able to find the path with the most gold from the grid.
  2. See number 1.
  3. 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. :wink:
  4. Pathfinding, dynamic programming, BFS…it’s kind of just a puzzle level to me. (Maybe @Bryukh could answer that.)

#3

Thanks. I will check the sample code. I tested it at the launch time, maybe something was changed.

  1. That number is just “decoration”. Like a hint, debugging hint, how much you can collect.

  2. If you can collect more than the warlock said - please, tell me about, because it’s some cheat in my level :wink:

  3. Should work. I’ll check it again. That code creates the map of coins. Just a little help to abstract and write pure algorithm.

  4. 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.


#4

Fixed sample JS code.


#5

@Bryukh : Thank you for replying.

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)

#6

Let me know about it if you can. I tested that.

Of course, you can solve it even with random chosen route with multiple tries. But would you be satisfied? It’s the same as complete Doom with IDDQD :wink:

Hm, it’s weird. I will check. Not sure how it’s possible.


#7

Yep. You are right. Thanks! I adjusted constants and now it should be closed. Please try now. (use direct version if you still have that hack)


#8

Description in the code:

You must collect the required amount of gold.

# 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”


#9

Some of levels. But we trying to avoid it if it’s possible.

I solved it with O(N) (where N is the number of lines) :wink:

it’s possible to do early the last line only with “cheats”, but thank you for the help to find them.

Yep, but try to think out-of-the-box.

Yes.


#10

I will reload from http://direct.codecombat.com/play/level/golden-choice

I will test walking between the coins tomorrow.


#11

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.


#12

Just thought I would pull this down into a separate reply in case it got lost. These were the other 2 points I noticed about the level.


#13

Hint: Dynamic programming

Let me know about them.
Thank you for the feedback. Feedbacks like those help to find weak points (cheats) at levels and make them better.


#14

You can still win without leaving the last coin spot. (if that was suppose to be ? )


#15

Yeah, it’s ok. The main goal is completed and exit is clear.


#16

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.


#17

How? Could you tell me how you did it?


#18

I just “tried” to send you a message. Let me know if you received it. I didn’t want to post any solutions to the general forum.


#19

Yep. Thanks. I will examine it (and will close “hacks” :imp:)


#20

Oh! I got how you did it. It’s the result of the another closed “hack”, as the result I got that one.