Hello, codeforces!
I'm making a game for a university project, and I faced this problem and thought discussing it on codeforces would be nice because it's somehow related to CP, and shows how CP is useful in real life.
The game is actually about 2 players (Multiplayer game) starting in a room in a house and the goal is to reach another specified room, the house is partitioned into a number of rooms, and each room has colored walls.
- Each room has at most one hidden gem, and each player can hold at most two gems at the same time.
- When a player carries a gem of color $$$X$$$ he can pass through any wall of color $$$X$$$ (penetrates the wall to the next room).
- The two players can collaborate and exchange gems with each other if they are in the same room.
- If a player found a hidden gem in some room, he can either take it if he carries less than 2 gems, or if he had at least one gem, he can exchange it with one of his gems (this operation is reversible and possible any number of times).
My part is to make a levels generator! until now I finished the basic house structure generator, but I'm stuck on generating a valid distribution for gems. I want to generate the MINIMUM number of gems to make the level solvable!
the number of rooms is at most 20 and there are at most 7 colors. (white walls can't be penetrated, so no gems of white color).
what is the best solution you can come up with :) ?
Wall colors are generated before generating gems!
this solution came to my mind but the results are not accurate.
try like 10000 distribution of gems and get the best answer of them after checking each distribution validation
nice work keep going
Really interesting problem.
Really interesting comment.
Really interesting comment.
Really interesting comment.
Really interesting comment
Really interesting comment.
Really interesting comment
Really interesting comment
Really interesting comment
Great problem idea bro keep going :)
Can you drop gems? If so, you can just carry an infinite number of gems with these rules: hold a purple gem + 1 other gem, walk through purple door, drop other gem, walk back through the door, pick up another gem, walk through again...
Even then, it's NP-hard to find the minimum number of colours. Reduction to 3SAT: have 2n colours, two for each variable, one representing the negation. Have a long hallway with the start at one end and the target at the other end. We can add a "at least one" constraint by adding any number of parallel doors of different colours. Then, just have an "at least one" constraint for each variable and its negation, and after that a "at least one" constraint for every 3-variable clause. You can place n colours of keys if and only if the 3SAT instance is solvable.
Checking if a set of gems is solvable is of course easy, just maintain the reachable region and update it whenever you are able to pick up a gem.
Can you drop gems?No.but your answer is really amazing
Now I'm not even able to find a way to check the validity of a gems set
Could you clarify what happens when I exchange the gems? Let's say I currently hold gems $$$A$$$ and $$$B$$$, and now find hidden gem $$$C$$$ in the room I enter. I now exchange $$$C$$$ with $$$A$$$, so I hold $$$C$$$ and $$$B$$$. Is $$$A$$$ now dropped into the room, or does it stay in some inventory from where I can swap it out again (regardless of which room I'm in)?
$$$A$$$ now is in the previous place of $$$C$$$.
so you actually exchanged $$$A$$$ with $$$C$$$.
you can't drop gems anywhere in the room.
more clearly, when you find a hidden gem, you are also finding a place in the room to store a gem. (this place initially stored the hidden gem)
After spending hours and days, I figured out that sometimes it's better to change the problem rather than solving it !
so I changed some rules in the game to make it possible :)