[Community Puzzle] Treasure hunt

Puzzles
1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @lhm,validated by @DGITAlley,@vpoulailleau and @natrian.
If you have any issues, feel free to ping them.

3

My solution is accepted, but I know that it is not a good solution (and it failed the 5th test case). Check the validator to fix this bug. If you have any more question, just write me, :slight_smile:

4

path finding in easy? isnt it too much?

10 Likes
5

Hello @DGITAlley ,
I implemented a recursive function and solved all testcases, but do not pass the Validator#1. I have no idea why. How can I find out what the problem is?

2 Likes
6

Hi @Duck8008135 ,

With expert mode enabled in your settings, try the following custom input test case (it is not validator #1 but it is very similar) :

3 3
X##
 8#
2 7

Expected output : 15

4 Likes
7

@b0n5a1 thanks, found my error.
I had an error like this in my function: copy_list = list instead of copy_list = list.copy()

2 Likes
8

Yeah how is this easy? How to determine path on first try??

Edit: nvm its finding the maximum.Still.

9

Hello everyone ! I am working on Treasure Hunt. I have some issues because I am first finding where “X” is thanks to a list. I did it in Python, it works well for the first test, but it “takes too much time” for the other tests (2 “for” loops and 1 while or if). It forces me to do it otherwise but for now, I don’t know how to start my way from “X” without knowing its coordinates in the map.
Could you help me please ?

Thanks :slight_smile:

10

As you are reading the inputs line by line, you should at the same time count which line it is. When you get to the line which contains “X”, you check at which position it is in that line. Combining the two pieces of information together, you get to know the coordinates of “X”. Basically, the above can be achieved with 1 or 2 for-loops.

1 Like
11

I think this is a pretty hard problem for beginners and should probably be classified as Medium.
(I solved this with a recursive search)

2 Likes
12

It definetly not an easy problem and it should be marked as recursion too because everyone solve it that way. Not the level of an easy problem

1 Like
13

I didn’t use recursion in my solution.

1 Like
14

I didn’t use recursion either, and also I think this puzzle could become a lot cooler if the post-submission benchmark pushed the limits a little.

In university we’d often get a “training set” of problems that we could code against, but then the (hidden) evaluation set would include corner cases, degenerate examples etc.

I’ve looked at a few solutions here and indeed I see a lot of recursion going on. Would be cool if the hidden test set could just throw a map of 1000x1000 in there to see which solutions hold up.
Likewise, my queue based solution is definitely extremely memory hungry (I basically treated the whole thing as an abstract state search) so it might fall down for larger instances of the problem as well.

Plus, every solution I have seen does an exhaustive search of the state space, which might make them slow in big and degenerate examples.

Even though this is an “easy” puzzle to solve, it’s actually pretty interesting to solve it well. I think generally the scoring post-submission could reflect that. If we’re worried about frustrating beginners (which is a valid concern) then these hard cases could be listed separately on the scoring page, with a note “These are hard stretch goals. Come back later to finish these off.”

Or there could just be a “v2” of this puzzle where the test set is much, much harder.

1 Like
15

If validator 1 is similar to this then I think it is not fear fro mthe creator as the test is not giving any situation like this one.
Here you have to look for various directions by going back to initial map as marking last positions would block you to get 7 +8 if you pass throug 2 first.
Any of the tests are requiring that, it is then the reason of my fail…
Please care on generating similar constraints on test than on validators else people can’t develop correctly…

16

Yes but…say that directly to lazy creator and validators who did not care about checking and testing…not to me.

17

I really enjoyed this problem, but (IMO) there is no way this should be classified as easy. I didn’t use recursion - I used a queue. I used a DFS path finding approach, but you have to keep track of the max treasure recovered so far at each node and also whether or not the path tries to include an already visited node. How is the skill “Arrays” the only thing listed? That makes no sense.

18

I don’t know if they explained it to you at university or not, but if a task has a condition (in this case, it’s an array with a maximum size of 100x100), then the task MUST adhere to this condition.

20

I believe the problem is actually NP, since the DP-caching requires tracking visited paths.
The validators are very simple and they accept a simple brute force solution.

However, a graph with all '1’s and just a single ‘X’ will already time out for H=W=20.

100x100 map it would take years for a brute-force solution to finish.

Are there some optimizations to solve ANY map in just a few seconds? Or is this just a bad problem with bad validators?

21

GPT agreed lol:
You’re absolutely right in your analysis:

  • This problem is NP-hard in nature because it essentially reduces to the Longest Path with weights (in this case, gold) in a graph where you cannot revisit nodes.
  • There is no efficient DP caching unless you track the set of visited cells, which becomes exponential in size.

Why Brute Force Fails

  • In the worst case (e.g., a full grid of '1’s with no walls), the number of paths from a starting point is factorial in the number of free cells.
  • For a 20x20 grid (~400 cells), brute force is totally infeasible.
  • Even a DFS with pruning can’t survive if too many directions are viable at each step.

The Validators Are Weak

You’re correct again: if brute force passes, the validators are:

  • Either very constrained (small maps, lots of walls),
  • Or the test generator does not produce adversarial input (e.g. open fields),
  • Or the time limits are generous enough to let an unoptimized DFS squeeze by on sparse maps.

Can It Be Solved for 100x100 in a Few Seconds?

Yes, but only under certain assumptions or constraints. Some possible practical optimizations:

:white_check_mark: Optimization Techniques

1. Pre-prune unreachable regions

  • Use BFS from 'X' to mark all reachable nodes. Ignore the rest.

2. Only explore useful branches

  • Don’t go into empty cells (' ') unless they are required to reach a gold cell.
  • Use flood-fill to cluster gold-rich areas and only move between them.

3. Memoization with limited visited info

  • Memoize (x, y, gold_so_far) for small neighborhoods.
  • But full visited tracking makes caching explode.

4. Beam Search / A (Heuristics)*

  • Score paths by potential gold nearby.
  • Use a priority queue and a heuristic to prefer paths likely to lead to more gold.

5. Connected Component Decomposition

  • Treat each connected component of walkable space as a subgraph.
  • Precompute maximum gold in small components with full DFS.

6. Greedy+Backtrack Hybrid

  • First, do a greedy walk (always take the adjacent max-gold cell).
  • Then backtrack from that path and try 1-2 deviations.

:x: What Won’t Work in General

  • Full memoization of visited sets — it’s exponential.
  • Dijkstra-style shortest/longest path — because of no revisiting.

:white_check_mark: Alternative: Bitmask DP

Only feasible when number of nodes is small (like 15–20 gold nodes). Then:

  1. Extract all gold nodes and 'X'.
  2. Build a graph between them using BFS.
  3. Use bitmask DP to find the best tour.

python

CopyEdit

# Let G[i][j] = shortest path cost between node i and node j
# dp[mask][i] = max gold collected visiting mask ending at node i

This reduces state size to 2^N * N, feasible for N <= 20.

:bulb: Final Take

  • The problem is poorly scaled if it’s intended to support 100x100 maps with no structure.
  • Solvable with clever pruning, but a truly general and fast algorithm would need:
    • Graph analysis
    • Heuristics
    • Component-wise strategies

Would you like a reference implementation of a smarter approach (like component + bitmask DP)?

22

From what I’ve seen of the existing solutions, no one attempted the same method as I did, and I was successful at testing mine with many custom 100x100 test cases and it still succeeded in time in the codingame expert tester. For any no wall map starting at 0,0, it only takes one path after setting up the game state bitmap to decide it’s done.