freeCodeCamp Algorithm Challenge Guide: Steamroller

freeCodeCamp Algorithm Challenge Guide: Steamroller
0

#1

:triangular_flag_on_post: Remember to use Read-Search-Ask if you get stuck. Try to pair program :busts_in_silhouette: and write your own code :pencil:

:checkered_flag: Problem Explanation:

This problem seems simple but you need to make sure to flatten any array, regardless of the level which is what adds a bit of difficulty to the problem.

Relevant Links

:speech_balloon: Hint: 1

You need to check if an element is an array or not.

try to solve the problem now

:speech_balloon: Hint: 2

If you are dealing with an array, then you need flatten it by getting the value inside of the array. This means if you have [[4]] then instead of returning [4] you need to return 4. If you get [[[4]]] then the same, you want the 4. You can access it with arr[index1][index2] to go a level deeper.

try to solve the problem now

:speech_balloon: Hint: 3

You will definitely need recursion or another way to go beyond two level arrays to make the code flexible and not hard-coded to the answers needed. Have fun!

try to solve the problem now

Spoiler Alert!

687474703a2f2f7777772e796f75726472756d2e636f6d2f796f75726472756d2f696d616765732f323030372f31302f31302f7265645f7761726e696e675f7369676e5f322e676966.gif

Solution ahead!

:beginner: Basic Code Solution:

function steamrollArray(arr) {
  var flattenedArray = [];

  // Create function that adds an element if it is not an array.
  // If it is an array, then loops through it and uses recursion on that array.
  var flatten = function(arg) {
    if (!Array.isArray(arg)) {
      flattenedArray.push(arg);
    } else {
      for (var a in arg) {
        flatten(arg[a]);
      }
    }
  };

  // Call the function for each element in the array
  arr.forEach(flatten);
  return flattenedArray;
}

// test here
steamrollArray([1, [2], [3, [[4]]]]);

:rocket: Run Code

Code Explanation:

  • Create a new variable to keep flattened arrays.
  • Create a function that will add non array elements to the new variable, and for the ones that are array it loops through them to get the element.
  • It does that by using recursion, if the element is an array then call the function again with a layer of array deeper to check if it is an array or not. if it is not then push that non-array element to the variable that gets returned. Otherwise, keep going deeper.
  • Invoke the function, the first time you will always pass it an array, so it always fall in to the isArray branch
  • Return the flattened array.

Relevant Links

:sunflower: Intermediate Code Solution:

function steamrollArray(arr) {
  let flat = [].concat(...arr);
  return flat.some(Array.isArray) ? steamrollArray(flat) : flat;
}

flattenArray([1, [2], [3, [[4]]]]);

:rocket: Run Code

Code Explanation:

  • Use spread operator to concatenate each element of arr with an empty array
  • Use Array.some() method to find out if the new array contains an array still
  • If it does, use recursion call steamrollArray again, passing in the new array to repeat the process on the arrays that were deeply nested
  • If it does not, return the flattened array

Relevant Links

:rotating_light: Advanced Code Solution:

function steamrollArray(arr) {
  return arr.toString()
    .replace(',,', ',')       // "1,2,,3" => "1,2,3"
    .split(',')               // ['1','2','3']
    .map(function(v) {
      if (v == '[object Object]') { // bring back empty objects
        return {};
      } else if (isNaN(v)) {        // if not a number (string)
        return v;
      } else {
        return parseInt(v);         // if a number in a string, convert it
      }
    });
}

:rocket: Run Code

Code Explanation:

  • First we turn the array to a string, which will give us a string of numbers seperated by a comma, double comma if there was an empty array and literal object text if there was an object, which we can fix it later in our if statement.
  • We replace the double comma with one, then split it back into an array.
  • map through the array and fix object values and convert string numbers to regular numbers.

:clipboard: NOTES FOR CONTRIBUTIONS:

  • :warning: DO NOT add solutions that are similar to any existing solutions. If you think it is similar but better, then try to merge (or replace) the existing similar solution.
  • Add an explanation of your solution.
  • Categorize the solution in one of the following categories — Basic, Intermediate and Advanced. :traffic_light:

See :point_right: Wiki Challenge Solution Template for reference.


Flattening nested arrays
#2

#3

#4
function steamrollArray(arr) {
  // Recursion is the breakfast of champions. ― Don Stewart
  var steamrolled = [];
  for (var i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) {
      var subArray = steamrollArray(arr[i]);
      steamrolled = steamrolled.concat(subArray);
    } else {
      steamrolled.push(arr[i]);
    }
  }
  return steamrolled;
}

#5
function steamrollArray(arr) {
  var flattened = arr.reduce(function(a, b) {return a.concat(b);}, []);
  
  for(var i = 0; i < flattened.length; i++) {
    while(Array.isArray(flattened[i])) {
      flattened[i] = flattened[i].reduce(function(a, b) {return a.concat(b);});
    }
  }
  
  return flattened;
}

#6

Hey, I like your code but it’s not universally applicable since it has a flaw: try “steamrollArray([1, [2, [3, [4]]]]);”. It will throw the error “a.concat is not a function”. That is because you eventually try to concatenate a number with an array like “3.concat[]” which won’t work. Can’t figure out a solution myself at the moment to fix this. Maybe someone else has an idea?

Using recursion it’s actually easier to grasp and it works for all cases:

function steamrollArray(arr) {
  return arr.reduce(function(a, b) {
      return a.concat(Array.isArray(b) ? steamrollArray(b) : b );
  }, []);
}

#7
function steamrollArray(arr) {
  // I'm a steamroller, baby
    var newArr = [];

    function check(val2) {
        if (!Array.isArray(val2)) {
            return newArr.push(val2);
        } else
            return val2.map(check);
    }

    arr.map(check);
    return newArr;
}

#8

I think this may be a bug? It’s saying it’s not returning the correct results even though it is:

var flattened = [];

function steamrollArray(arr) {
  // I'm a steamroller, baby
  for(var i = 0; i < arr.length; i++){
    if (Array.isArray(arr[i])){
      steamrollArray(arr[i]);
    } else {
      flattened.push(arr[i]);
    }
  }
  return flattened;
}

steamrollArray([1, {}, [3, [[4]]]]);

I understand it’s probably not cool with me declaring flattened outside the function but getting error messages saying

steamrollArray([[[“a”]], [[“b”]]]) should return [“a”, “b”].

when it does in fact return ["a", "b"] feels buggy.


#9

I actually came on here to look for an answer on why mine wasn’t being accepted. We had the exact same idea, it looks like, but even though it displays the correct answer it fails all of the tests.

var newArr = [];
function steamrollArray(arr) {
  for (var i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) {
      steamrollArray(arr[i]);
    } else {
      newArr.push(arr[i]);
    }
  }
  return newArr;
}

#10

Can be done without recursion, although not sure about the efficiency since I essentially check the whole array for array elements with every iteration.

function steamrollArray(arr) {
  // I'm a steamroller, baby
  while(arr.findIndex(Array.isArray)>-1){
    var x=arr.shift();
    if(Array.isArray(x)){
      arr=arr.concat(x);
    }else{
      arr.push(x);
    }
    
  }
  return arr;
}

#11

function steamrollArray(arr) {
var newArr=[];
var flat=function(val){
if(!Array.isArray(val)){
newArr.push(val);
}else{
val.forEach(flat);
}
};

arr.forEach(flat);

return newArr;
}

steamrollArray([1, {}, [3, [[4]]]]);


#12

Working but quite slow solution and IMHO not as readable as the second one:

//t: 0.44970703125ms
function steamrollArray(arr) {
  var result = []
  var flatten = function(v) {
    Array.isArray(v) ? v.forEach(flatten) : result.push(v)
  }
  flatten(arr)
  return result
}
steamrollArray([1, {}, [3, [[4]]]])

Way faster while not accepted (for using global result[]) solution:

//t: 0.083251953125ms
var result = []

function steamrollArray(arr) {
  for(var i=0; i < arr.length; i++)
    Array.isArray(arr[i]) ? steamrollArray(arr[i]) : result.push(arr[i])
  return result;
}
steamrollArray([1, [2], [3, [[4]]]]);

Using ES6 notation might help with readability of the first one. With the second one I’m not sure if the recursion from inside the for-loop is good style of code. Additionally it might lead into trouble in other cases?!

I’m pretty sure there is a more elegant solution out there.


#14

That’s my code:

function steamrollArray(arr) {
 
  var flat = [];
  function flatten (a){
    for (var i=0; i<a.length; i++){
      //if array contains array, push loop and call by calling the function again and passing nested array as a parameter
      if(Array.isArray(a[i])){
        flatten(a[i]);
      }else{
        //if its not a nested array push it to the flat array variable
        flat.push(a[i]);
      }
    }
    return flat;
  }
  return flatten(arr);
}
 
//test
steamrollArray([1, [], [3, [[4]]]]);

#15

You are so close

function steamrollArray(arr) {
  var results=[];
  for(var i=0; i < arr.length; i++)
    Array.isArray(arr[i])? results=[...results,...steamrollArray(arr[i])]:results.push(arr[i]);
  return results;
}
steamrollArray([1, [2], [3, [[4]]]]);

you just had to figure how to use recursion to you advantage in making the result array.


#16

My version of code:

//jshint esversion: 6
function steamrollArray(arr) {

  for (var i = 0; i<=arr.length; i++){
  if (Array.isArray(arr[i]) === true){
    arr = arr.reduce( (a, b) => a.concat(b), []);
    i=0;
  }    
  }  

  return arr;
 
}

#17

Here’s my solution and I’ve kept it very short :

function steamrollArray(arr) {
  
  return arr.reduce(function(prev, next) {
    return prev.concat(
      Array.isArray(next) ? steamrollArray(next) : next );
  }, []); 
}

#18

function steamrollArray(arr) {
newArr = [];
for (i = 0; i < arr.length; i++) {
if (Array.isArray(arr[i]) === true) {
newArr = newArr.concat(steamrollArray(arr[i]));
} else if (Array.isArray(arr[i]) === false) {
newArr.push(arr[i]);
}
}
return newArr;
}

steamrollArray([1, [2], [3, [[4]]]]);


#19

Hi there !
I came up with a code similar to yours:
function steamrollArray(arr) {
var newArr = [];
for (i = 0; i < arr.length; i++) {
if (Array.isArray(arr[i])) {
newArr = newArr.concat(steamrollArray(arr[i]));
} else {
newArr.push(arr[i]);
}
}
return newArr;
}

steamrollArray([1, [], [3, [[4]]]]);

However, when I don’t put var i = 0 in the for loop (just i = 0), the code become infinite loop.
I was curious if you have any idea why this happen ?


#20

By omitting the var you’re putting i in the global scope. This leads to problems in your code because the second element of the array you’re passing to steamrollArray is empty. Because it’s also an array, it causes a recursive call to steamrollArray. Because it’s empty, when the recursive call ends, i will be set to 0. Because the var was omitted, this means this is the same i that is being used in the enclosing scope and so we start processing the array again from the beginning and so the function never terminates.

I hope I did a decent job of explaining this very tricky bug. I suggest reading up on the var and newer (and better) let keyword semantics. I use Visual Studio Code along with the @ts-check feature and also ESLint which both help catch these kinds of bugs.

Happy coding!


#21

Thank you sir for the quick reply. It really helped me understand my error.