viren0's blog

Help in Cookie Clicker
By viren0, 6 years ago, In English

Can someone help in telling logic behind the logic of this code for this problem.

I found it difficult to implement brute force logic in Java.

Thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

It is basically a Dynamic Programming solution.

This is my Accepted C++14 brute-force recursive solution, which may be more intuitive and simpler to comprehend.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you elaborate your solution

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 10   Vote: I like it -9 Vote: I do not like it

      The idea is to store the present state in a state_t object that consists of the triple:

      1. cookies: the present number of cookies

      2. S: the present number of cookies gained per second

      3. T: the present time in seconds

      The initial state is (0, S, 0), and C is the number of desired cookies.

      A factory is storied as a factory_t object that consists of the triple:

      1. cost: the cost of purchasing the factory

      2. production: the number of bonus cookies it produces when purchased

      3. bought: a boolean flag that indicates whether it has been bought or not

      Initially, all the N factories are not bought.

      The recursive factories_t::min_time( state_t x ) function is a brute-force recursive function that initializes min_time to the minimum number of seconds required so that the number of cookies reaches at least C according to the number of cookies and the gain per second in the present state without purchasing more factories.

      Then, the function iterates on all factories. If some factory[ i ] is not bought yet, then its corresponding delta is computed, which is the minimum time according to the present state such that it is possible to buy such factory. If such number is strictly positive, then the time the present state advanced by that duration. Then, the present state is updated according as the factory is purchased and the factory is marked as bought. The same function is then called recursively with the updated state to compute the minimum time for the update state.

      After returning back from the recursive call, min_time is updated, and the state is backtracked to its previous state so as to check if it is possible to update the minimum time to a lower value by buying another factory at that recursion level.

      → Reply