2
$\begingroup$

Background:

  • There are 832 unique Pokemon in the Pokemon universe, and
  • There are 728 fighting moves that the Pokemon can collectively learn.
  • No Pokemon can learn to do every fighting move, and some Pokemon can only learn one.
  • The average Pokemon can learn between 10-30 fighting moves , and
  • Most fighting moves can be learned by multiple Pokemon.

Challenge:

I want to match as many unique Pokemon to one unique move. These are one-to-one matches.

Example with U.S. presidents:

  • Name: Clinton, Moves: Democratify, Impeachify
  • Name: Bush, Moves: Republicanify
  • Name: Obama, Moves: Democratify, Healthcarify
  • Name: Trump, Moves: Republicanify, Impeachify

Example solution that matches the highest number (in this case, all of them)

  • Clinton-Democratify
  • Bush-Republicanify
  • Obama-Healthcarify
  • Trump-Impeachify

Summary: What's an algorithm I could use to get the most potential matches of unique Pokemon to unique move?

Caveat: I'm just a regular guy, no computer science background, and a fuzzy memory of what I learned in my high school calculus class, and a VERY basic understanding of graph theory... so bonus points if you explain it simply enough for me to understand.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

While your description of the problem is not super clear. I can guess that you're looking at a maximum bipartite matching problem. Which by the way, can also be viewed as a degenerate case of maxflow problem. Both problems are classic, you should have no problem finding resources on them. For example, this.

maximum bipartitie matching example graph

maxflow example graph

$\endgroup$
1
  • $\begingroup$ Yep! This is what I was looking for, thanks for pushing me in the right direction! $\endgroup$ Commented Oct 10, 2019 at 5:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.