What to do when you fail an algorithm challenge

Yesterday I woke up bright and early. I poured a strong cup of joe and set off to http://www.codewars.com to train with a new code Kata.  I was filling confident after solving one the day before so I thought why not up the ante a bit and try a 5 kyu challenge called “Weight for weight”. In the end I got a wallop of a black eye. Fortunately, we all do our best learning from struggle.

Yesterday I woke up bright and early. I poured a strong cup of joe and set off to http://www.codewars.com to train with a new code Kata.  I was feeling confident after solving one the day before so I thought why not up the ante a bit and try a 5 kyu challenge called “Weight for weight.” In the end, I got a wallop of a black eye. Fortunately though, we all do our best learning from struggle.

I hacked away at it for hours I must admit and I almost solved it, but in the end I caved under the weight of it all (pun intended).  Let’s see the instructions for the challenge and then I’ll show you my ham-handed attempt at solving it.  After that I’ll show a solution I found on github and how I went about analyzing it with the chrome debugger.

Weight for weight 5 kyu challenge

Instructions:

My friend John and I are members of the “Fat to Fit Club (FFC)”. John is worried because each month a list with the weights of members is published and each month he is the last on the list which means he is the heaviest.

I am the one who establishes the list so I told him: “Don’t worry any more, I will modify the order of the list”. It was decided to attribute a “weight” to numbers. The weight of a number will be from now on the sum of its digits.

For example 99 will have “weight” 18, 100 will have “weight” 1 so in the list 100 will come before 99. Given a string with the weights of FFC members in normal order can you give this string ordered by “weights” of these numbers?

Example:

“56 65 74 100 99 68 86 180 90” ordered by numbers weights becomes: “100 180 90 56 65 74 68 86 99”

When two numbers have the same “weight”, let us class them as if they were strings and not numbers: 100 is before 180 because its “weight” (1) is less than the one of 180 (9) and 180 is before 90 since, having the same “weight” (9) it comes before as a string.

All numbers in the list are positive numbers and the list can be empty.

Here is my almost-working solution.  My solution is not very well composed and doesn’t even address the last bit of instruction listed below:


function orderWeight(strng) {
  var strArr = strng.split(' ');
  var newArr = [];
  var sum = 0;
  var numToAdd = 0;
  var obj = {};
  var orderedArr = [];

  function convertToObj(strArr, obj) {
    strArr.forEach(function(str, index) {
      for (var i = 0; i < str.length; i++) {
        numToAdd = parseInt(str.charAt(i), 10);
        sum += numToAdd;
      }

      obj[str] = sum;
      console.log(obj[str]);
    });
    return obj;
  }
  convertToObj(strArr, obj);

  console.log(obj);

  for (var prop in obj) {
    console.log(prop.toString());

    newArr.push([prop, obj[prop]]);
  }

  newArr = newArr.sort(function(a, b) {
    return a[1] + b[1];
  });

  for (var j = 0; j < newArr.length; j++) {
    orderedArr.push(newArr[j][0]);
  }

  var finalStr = orderedArr.join(" ");
  console.log(finalStr);
}

When two numbers have the same “weight”, let us class them as if they were strings and not numbers: 100 is before 180 because its “weight” (1) is less than the one of 180 (9) and 180 is before 90 since, having the same “weight” (9) it comes before as a string.

My output: 180 100 99 90 86 74 68 65 56
correct output: "100 180 90 56 65 74 68 86 99"

I ended up chasing my own tail like a hyper little dog. You don’t need to concentrate at all on my non-solution, I just want to show you for illustrative purposes. My thinking was to make a simple hash with the prop being the actual number and the prop value being the sum of counting each individual place, so if the num was 235 then the resulting hash would be:

2 + 3 + 5 = 10 {235:10}

The problem with using that method was trying to figure out how to then output the prop name which was the real number in the order I wanted, while also ordering the numbers based on string sort. The evidence of my tail chasing is above. This is not to say I didn’t learn anything. I learned quite a lot about how to manipulate objects from this challenge. At the end of this post I’ll share all the research from my head scratching.

Now let’s see an elegant solution. I ran it through the debugger to understand how it works.  Credit goes to http://www.paigebolduc.com/  for the featured solution.


function orderWeightV2(strng) {
  var weights = strng.split(' '); // splits string into an array based on
spaces

// divide and conquer
// sort takes 2 array index's at a time (a, b) and allows you to do a
comparison between each pair
  weights.sort(function(a, b) {
    var aSum = getSum(a); // call getSum() ie: value 246 = 2 + 4 + 6 = 12
    var bSum = getSum(b); // call it again with b 

    if (aSum === bSum) { // compare based on sum only
      if (a < b) {
        return -1; // -1 means sort a before b
      } else {
        return 1; // 1 means sort b before a
      }

    } else if (aSum < bSum) { if a is less that b keep it same
      return -1;
    }
    return 1;  // otherwise b before a
  });

  return weights.join(" ");
}

// called above inside sort
function getSum(str) {
  return str.split('').reduce(function(sum, next) {
    return sum + Number(next);
  }, 0);
}

// the above function uses reduce but could also be written like below
function getTotal(str) {
  str = str.split('');
  var sum = 0;
  for (var i = 0; i < str.length; i++) {
    sum += parseInt(str[i]);
  }
  return sum;
}

I opened the console by hitting Ctrl+Shift J, then moved over to the sources tab and stepped through the solution by hitting F11 (you can see with the featured animation at the top of the post).

My problem was not fully understanding the MDN explanations of sort method.  I found this article called, “Sophisticated Sorting” which made more sense.  It goes into much more versatile ways of using sort().

So I failed the challenge, but in the struggle I learned more about objects and the sort method. I feel like I was able to turn it into a win and that is what practicing algorithms is about. I’ve heard quite a few complaints from Free Code Campers that the algorithms are too hard. They aren’t too hard and your supposed to fall on your face before being able to solve them.

Do not think of them as goals to get past. Approach them as an opportunity to explore new concepts. As with many things in life it’s about the journey and not the end goal sometimes. Of course you want to solve them in the end, but never at the expense of the struggle of finding the solution.

Beyond everything else, remember that you’re not the stupid one. It’s the computer that is dumb as a rock. You just need to learn to give the computer more explicit instructions. 😀

research links from trying to solve this challenge:

Practicing with data (map, filter, loops, objects, arrays)

I thought I would mock up some fun “Star Wars” data and riff on it.

Lets code with the force!

I thought I would mock up some fun “Star Wars” data and riff on it. I’m just gonna play around see what I can come up with using some tools I need to become more familiar with myself. Never underestimate the power of learning through play! Who knows maybe someone else will learn along with me. If you’re at an advanced level this post will not be for you.


var starWarsCharacters = [{
  name: "Darth Vader",
  role: "Evil Sith Lord",
  morals: "evil",
  team: "Galactic Empire",
  episodes: [3, 4, 5, 6],
  relationships: ["husband of Padme",
    "father to Luke Skywalker", "formally known as Anakin Skywalker",
    "Student to Obi Wan"
  ]
}, {
  name: "Luke Skywalker",
  role: "Jedi",
  morals: "good",
  team: "Rebel Alliance",
  episodes: [4, 5, 6, 7],
  relationships: ["Single", "brother of Lea", "son of Darth Vader"]
}, {
  name: "Lea",
  role: "rebel princess",
  morals: "good",
  team: "Rebel Alliance",
  episodes: [4, 5, 6, 7],
  relationships: ["dating Han Solo", "daughter of Darth Vader",
    "sister to Luke Skywalker"
  ]
}, {
  name: "Han Solo",
  role: "smuggler",
  morals: "good",
  team: "Rebel Alliance",
  episodes: [4, 5, 6, 7],
  relationships: ["dating Lea", "Chewbacca's best friend"]
}, {
  name: "Chewbacca",
  role: "smuggler",
  morals: "good",
  team: "Rebel Alliance",
  episodes: [4, 5, 6, 7],
  relationships: ["Han Solo's best friend"]
}, {
  name: "Darth Sidious",
  role: "emperor",
  morals: "evil",
  team: "Galactic Empire",
  episodes: [1, 2, 3, 4, 5, 6],
  relationships: ["Anakin Skywalker's evil mentor", "Darth Maul's Master"]
}, {
  name: "Kylo Ren",
  role: "Leader of the First Order",
  morals: "evil",
  team: "First Order",
  episodes: [7],
  relationships: ["Grand son of Darth Vader",
    "son of Han Solo and Lea Skywalker"
  ]
}, {
  name: "Count Dooku",
  role: "Separatist Leader",
  morals: "evil",
  team: "Separatists",
  episodes: [2, 3],
  relationships: ["Trained Qui Gon Jinn"]
}, {
  name: "Qui Gon Jinn",
  role: "Jedi",
  morals: "good",
  team: "Old Republic",
  episodes: [1],
  relationships: ["Count Dooku's student", "Obi Wan's master"]
}, {
  name: "Obi Wan",
  role: "Jedi",
  morals: "good",
  team: "Old Republic",
  episodes: [1, 2, 3, 4],
  relationships: ["Qui Gon Jinn's student", "Anakin Skywalker's master"]
}, {
  name: "Lando Calrissian",
  role: "Businessman & Scoundrel",
  morals: "good",
  team: "Rebal Alliance",
  episodes: [5, 6],
  relationships: ["Han Solo's friend"]
}, {
  name: "Darth Maul",
  role: "Sith",
  morals: "evil",
  team: "Galactic Empire",
  episodes: [1],
  relationships: ["Darth Sidious's student"]
}];

One thing I remember scratching my head on as an absolute beginner was accessing arrays within objects within arrays.  It gets easier as you practice though and before you know it, it’s second nature!

So first before we start using filter and map and all that fancy stuff lets access it in the most basic way possible.


for (var i = 0; i < starWarsCharacters.length; i++) {
  console.log(starWarsCharacters[i].name);
}

// this prints out all of the names of course

main.js:98 Darth Vader
main.js:98 Luke Skywalker
main.js:98 Lea
main.js:98 Han Solo
main.js:98 Chewbacca
main.js:98 Darth Sidious
main.js:98 Kylo Ren
main.js:98 Count Dooku
main.js:98 Qui Gon Jinn
main.js:98 Obi Wan
main.js:98 Lando Calrissian
main.js:98 Darth Maul

What if we wanted to only print out the names of good guys?


for (var i = 0; i < starWarsCharacters.length; i++) {
  if (starWarsCharacters[i].morals !== "evil") {
    console.log(starWarsCharacters[i].name);
  }
}

// this prints out all the good guys and gals!

main.js:103 Luke Skywalker
main.js:103 Lea
main.js:103 Han Solo
main.js:103 Chewbacca
main.js:103 Qui Gon Jinn
main.js:103 Obi Wan
main.js:103 Lando Calrissian

Now lets do the same thing in a less ugly way using the filter method.

var goodguys = starWarsCharacters.filter(function(character) {
  return character.morals !== "evil";
});
console.log(goodguys);

// output is an array of objects
main.js:110 [Object, Object, Object, Object, Object, Object, Object]

Now if we go back and change the previous vanilla for loop we can do the same thing.


var arr = [];
for (var i = 0; i < starWarsCharacters.length; i++) {
    if (starWarsCharacters[i].morals !== "evil") {
        arr.push(starWarsCharacters[i]);
}
}

// exactly the same output with way more typing

main.js:120 [Object, Object, Object, Object, Object, Object, Object]

Lets build a simple filter function to do the same thing again.  (You don’t have to use this ever again.) Use the one that is already attached to Array.prototype out of the box.  It’s only being shown so that you can easily understand what is going on behind the scenes.  The Polyfill is much more complicated.


function filterIt(arr, test) {
  var passTest = [];
  for (var i = 0; i < arr.length; i++) {
    if (test(arr[i])) {
      passTest.push(arr[i]);
    }
  }
  return passTest;
}

console.log(filterIt(starWarsCharacters, function(character) {
  return character.morals !== "evil";
}));

// again same output of objects

Next how about we build a function to see which team each character is on.


var team = function(alliance) {
  var alliances = starWarsCharacters.filter(function(char) {
    return char.team.toLowerCase() === alliance.toLowerCase();
  });
  // map is used here to build an entirely new returned object of only the relevant data
  alliances = alliances.map(function(char) {
    return {
      name: char.name,
      team: char.team
    };
  });
  return alliances;
};

console.log(JSON.stringify(team("rebel AlLiance"), null, 4));

[
    {
        "name": "Luke Skywalker",
        "team": "Rebel Alliance"
    },
    {
        "name": "Lea",
        "team": "Rebel Alliance"
    },
    {
        "name": "Han Solo",
        "team": "Rebel Alliance"
    },
    {
        "name": "Chewbacca",
        "team": "Rebel Alliance"
    }
]


Next we will write a function that will give us all the characters in a selected episode we select as an argument.


var charactersInEpisode = function(episode) {
  var chars = [];
  starWarsCharacters.forEach(function(char) {
    char.episodes.forEach(function(ep) {
      if (ep === episode) {
        chars.push(char.name);
      }
    });
  });
  return chars;
};

console.log(JSON.stringify(charactersInEpisode(2), null, 4));

[
    "Darth Sidious",
    "Count Dooku",
    "Obi Wan"
]

How about a function that finds related characters?


var related = function(char) {
  var chars = [];
  starWarsCharacters.filter(function(character) {
    return character.relationships.filter(function(relationship) {
      if (relationship.toLowerCase().match(char.toLowerCase())) {
        chars.push(character.name);
        return;
      }
    });
  });
  return chars;
};

console.log(JSON.stringify(related("DaRTh VaDeR"), null, 4));

[
    "Luke Skywalker",
    "Lea",
    "Kylo Ren"
]

How about a function to win star wars by rejecting all the bad guys and while we are at it let’s show how many episodes they were in.


var winStarWars = starWarsCharacters.filter(function(char) {
  return char.morals !== 'evil';
});

var goodchars = winStarWars.map(function(goodchar) {
  // transform data into a new object
  return {
    name: goodchar.name,
    episodesIn: goodchar.episodes.length,
    role: goodchar.role
  };
});

console.log(JSON.stringify(goodchars, null, 4));

[
    {
        "name": "Luke Skywalker",
        "episodesIn": 4,
        "role": "Jedi"
    },
    {
        "name": "Lea",
        "episodesIn": 4,
        "role": "rebel princess"
    },
    {
        "name": "Han Solo",
        "episodesIn": 4,
        "role": "smuggler"
    },
    {
        "name": "Chewbacca",
        "episodesIn": 4,
        "role": "smuggler"
    },
    {
        "name": "Qui Gon Jinn",
        "episodesIn": 1,
        "role": "Jedi"
    },
    {
        "name": "Obi Wan",
        "episodesIn": 4,
        "role": "Jedi"
    },
    {
        "name": "Lando Calrissian",
        "episodesIn": 2,
        "role": "Businessman & Scoundrel"
    }
]

That is enough for now! Below is a resource I found informative and useful in learning some of these concepts.

joepie91’s Ramblings