This problem asks:

Given: An RNA string s of length at most 80 bp having the same number of occurrences of ‘A’ as ‘U’ and the same number of occurrences of ‘C’ as ‘G’.

Return: The total possible number of perfect matchings of basepair edges in the bonding graph of s.

Required reading

  1. RNA folding
  2. Nucleic acid secondary structure
  3. Zebrafish Yes, zebrafish.
  4. Stem loops
  5. Matching graphs
  6. Perfect matching
  7. Complete graphs
  8. Bonding graph
  9. Adjacency edges
  10. Recurrence relations
  11. Complete bipartite graphs

Restate the problem

I’m going to get an RNA string up to 80 characters long with the same number of A’s as U’s and the same number of C’s as G’s. I need to return the count of perfect matchings possible.

Solution steps

First, I wrote the recurrence relation equation that appears in the challenge explanation:

return ((2*n)-1) * x(n - 1)

Then, I tried to get the correct sample output given the sample dataset, but failed.

I realized that there are two disconnected graphs at work here. The A-U graph and the C-G graph. The total number of pairings is the number of A-U pairings times the number of C-G pairings.

The number of A-U graphs is A! The number of C-G graphs is C!

print(fact(A) * fact(G))

I used my simple recursive factorial code from an earlier challenge:

def fact(n):
    if n < 2:
        return 1
    else:
        return n * fact(n - 1)

I returned a correct response on my first attempt. 3,972 people solved this challenge before me.