Algorithms Are Monsters (but don't be afraid)

The monster is Victor Frankenstein's creation, assembled from old body parts and strange chemicals, animated by a mysterious spark.
-- Spark Notes

This week, I failed my first coding challenge spectacularly. But I walked away from that experience with a better understanding on how I approach algorithms.

If you’re looking to solve algorithms the optimal way, this isn’t the article for you. However, if you’re stuck at just where to start when you encounter a new problem, this article may be helpful. There are many different ways to solve and think about these problems, and the steps below are what I found helpful when I start a new algo:

• understand the parts you need

• use past experiences

• try, fail, try again

I’ve never felt particularly strong at algorithms or attune to these types of problems. When I first started solving them, my mind struggled to break these problem down into steps. I tried to follow the advice I heard from peers and professionals: understand the problem, break it down into steps, understand the constraints, the input, the output. With so many thoughts buzzing in my head, it’s no wonder I struggled so long to find my footing.

Exhibit 1: A Monster

Problem:

Given a rectangular matrix of characters, add a border of asterisks(*) to it.
Code Signal

My solution:

function addBorder(picture) {
   let longestLen = findLongestString(picture) + 2
   let stars = '*'.repeat(longestLen)
   let newString = ""
   let rect = []
   rect.push(stars)
   for(let i = 0; i < picture.length; i++){
     newString = '*' + picture[i] + '*'
     rect.push(newString)
   }
   rect.push(stars)
   return rect
}


function findLongestString(inputArray) {
   let len = 0;
   for (let i = 0; i < inputArray.length; i++){
       if(inputArray[i].length > len){
           len = inputArray[i].length
       }
   }
   return len
}

This is my big win for today. It’s a problem I solved in a comparatively short amount of time compared to others. It’s also a problem that could have helped me on my code challenge if I’d encountered it sooner.

I know this isn’t an optimal solution, but it’s easy for me to understand and walk through. I can understand every part of it, which is where its real value lies.

Understand: the parts you need

You’ve got to understand a problem before you can solve it, at least, that’s what I’ve heard.

But what does it truly mean to understand a problem? This was something I had a hard time with. Even when I was sure I knew what it was asking and what the outputs, inputs, and constraints were, I struggled with where to start. Now I know, instead of thinking about these components individually, I should have grouped them together into the parts I needed.

In my case, to understand a problem, I need to understand the parts of need to solve it. Perhaps I need to return a new array. That means my output should be an array, that means I need to initialize an array somewhere. Perhaps I need to keep track of a variable. That means I need to initialize a variable somewhere.

Sometimes it’s easy to see what parts I’ll need. Sometimes, by working through a problem, I’ll realize I will or won’t need a part of that I thought I needed.

Take, for instance, the variable initializations at the beginning of Exhibit 1. It may not look very pretty, but those are the building blocks of the problem. I knew I needed a string of asterisks at the beginning and end of the matrix.

  let longestLen = findLongestString(picture) + 2
   let stars = '*'.repeat(longestLen)
   let newString = ""
   let rect = []

As I worked through the problem, I rediscovered that strings are immutable, so I needed to save these instances in a variable called newString as I went through the loop.

Finally, I knew I needed to return a new matrix, so I initialized a new one and called it rect (short for rectangle).

Use past experiences

Since I’ve committed to practicing algorithms almost daily, I’m seeing more and more past problems in present problems. The helper function findLongestString is a part of another problem I solved previously.

function findLongestString(inputArray) {
   let len = 0;
   for (let i = 0; i < inputArray.length; i++){
       if(inputArray[i].length > len){
           len = inputArray[i].length
       }
   }
   return len
}

For this problem, I knew that I needed the length of the longest strings in the picture array in order to determine how long the borders would be. It was a good thing I’d already written this in the allLongestStrings function:

def allLongestStrings(inputArray)

    len = 0
    longest = []

    inputArray.each do |el|
        if el.length > len 
            len = el.length 
        end  
    end 

    inputArray.each do |st|
        if st.length == len
            longest.push(st)
        end
    end 

    longest 
end

Each new problem does not necessarily mean we need a completely new way to solve it. Programming should be recyclable and you should be able to use old problem parts if you need to.

Try, fail, try

Another common saying in programming is fail fast.

When I first started trying to solve algorithms, I strived for the optimal way. I wanted my solutions to be faster, cleaner, without nested for-loops. While this is important, it’s the kind of mindset that kept me from seeing the simple way.

And sometimes the simple way is the best way.

Sometimes your first instinct is the one you should listen to.

I struggled with algorithms for so long because I was trying to be perfect and make them perfect. Now I know to listen to the creative spark in my head. Sometimes it works and it’s awesome. Sometimes it fails and I learn. But at least I’m learning.

Conclusion

This isn’t a be-all, end-all when it comes to algorithms. I’ll still struggle. I’ll still slip up and try to be perfect every once in a while.

But I’ve learned to understand these monsters called algorithms and bit more. And that’s made me less afraid of them.

Comments

[pentacular]

It might be worth considering a different approach to finding the maximum.

const length = (input) => input.length;
const lengths = (inputs) => inputs.map(length);
const maxLength = (inputs) => Math.max(...lengths(inputs));

I'm not convinced that it is a better approach than what you're doing now, but it can be nice to think about decomposing the solution into parts with clearer meanings.

Actually, if you look at your code, you make an assumption that makes this unnecessary.

 newString = '*' + picture[i] + '*'

This will fail to work if the length of picture[i] varies with i.

Which means that you can find the correct length by using picture[0].length + 2.

So, think about either padding each row of picture out to the maximum length, or don't bother finding the global maximum, since you don't make proper use it of anyhow. :)

Which can reduce the solution down to something like this:

const addBorder = (picture) => {
  const rowLength = picture[0].length + 2;
  const rowOfStars = '*'.repeat(rowLength);
  return [
    rowOfStars,
    ...picture.map(row => `*${row}*`),
    rowOfStars
  ];
}

[Kailana Kahawaii]

Great alternative! Thank you!