Interesting REAL life problem !

Revision en1, by SleepingThread, 2023-05-21 00:07:51

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 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 with :) ?

Tags games, nice problem, game design, brute force, dynamic programming, best solution

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English SleepingThread 2023-05-21 01:12:04 32
en5 English SleepingThread 2023-05-21 00:12:16 0 (published)
en4 English SleepingThread 2023-05-21 00:11:14 23
en3 English SleepingThread 2023-05-21 00:09:04 10
en2 English SleepingThread 2023-05-21 00:08:42 13
en1 English SleepingThread 2023-05-21 00:07:51 1491 Initial revision (saved to drafts)