All Hail The Almighty CharMap!
Yesterday, I signed up for the Puerto Rico Summer Coding Challenge. It’s a fundraising challenge brought to us by Math is More Than Numbers where participants aim to solve over 100 bioinformatics-related algorithm challenges in the next two months (five weeks, at most, for me!). I signed up here:
From that webpage: “The Puerto Rico Summer Coding Challenge is an opportunity to learn Biology, Coding and so much more, while potentially contributing to Scientific Communication. Join us, as we work through the main rosalind.info problem set, competing for a grand prize starting at $200. The race has already begun!”
I registered and selected Ciencia Puerto Rico as my Donation Pledge organization. I know little of bioinformatics — and admit to liking only math and physics from the science curriculum in high school — but one of my oldest friends, from said high school (¡UHS fuá!), loves the field of science so much, she became Executive Director for that noble organization that aims to promote the love of sciences in Puerto Rico from their New Haven, CT headquarters. The only requirement for this Puerto Rico Summer Coding Challenge, is to have some connection to the little piece of land we know and love (cue in only Rita Moreno’s first verse, from West Side Story’s America: 🎼 “Puerto Rico, my heart’s devotion” 🎶)
Here’s the evidence I’m more than amply qualified to take part in this Summer Coding Challenge 😉:
I looked through the problem set and pulled the one below haphazardly. My first thought was this is one I can easily handle. I’d had the same eerie feeling, of surprise mixed with relief, a few weeks ago when I got together via Zoom with one of my best bootcamp buddies and he asked for my take on solving one of the algorithms he had on his plate. Surprisingly, I thought to myself, I have the tool to approach it, thereby solve it, and I wanted to write about it here today.
I thought to whip out a character map, or CharMap, for this problem. This is a Swiss-army-knife-like technique I learned about on Stephen Grider’s Udemy course titled “The Coding Interview Bootcamp: Algorithms + Data Structures”. Here’s the approach: You take a string and convert it into an object where “the keys of the object are the characters from the string and the values are the numbers of times that that character has been found.” (quote from 2 mins and 50s into the Section 6 Max Chars Problem video)
This kind of CharMap approach handles many-a-string-related challenge, for example if the problem asks for “What is the most common character in the string?”, or “Does String A have the same characters as String B (that is, is it an anagram)?” or even “Does the string have any repeated characters in it?” Let’s see this technique in action, shall we?
You create a function that takes a string as an argument. In that function, the first thing you do is initialize an empty object. Next, you iterate through the string, using the flattened-out for loop I discuss here:
In this iterative exercise, we’re asking whether a specific character in the string currently has a place in our object. If it does, wonderful, add one to it; if it doesn’t exist, create one with an initial value of ‘1’. In the end, we must always remember to return. This exercise specifically asks for a return that’s four integers, with a single space separating them, and the order of the characters must be A C G T. As a test, if you enter this string, “AGCTTTTCATTCTGACTGCAACGGGCAATATGTCTCTGTGTGGATTAAAAAAAGAGTGTCTGATAGCAGC”, the function is expected to return 20 12 17 21. And it does, hurray! Science is cool. 🤓
