A sequence of events: I write a solution for Pattern Chaser. I attend Hack Reactor and become a much better coder. Coderbyte asks me to write a solution post for their blog. I look at my code and weep for its complexity. I write a better solution for Pattern Chaser.

Here is my improved solution with comments:

function PatternChaser(str) {

  // Best practice: define our variables up front
  var l, i, pattern, count;

  // For each possible pattern length, starting at the max
  // and counting down to 2, the minimum possible length
  for (l = Math.floor(str.length / 2); l >= 2; l--) {

    // Iterate through each starting position that
    // won't put us over the end, given the current max
    for (i = 0; i < str.length - l; i++) {

      // Capture a possible pattern as a string
      pattern = str.substr(i, l);

      // Create a new regular expression consisting of the
      // possible pattern, and see how many times it occurs
      count = str.match(new RegExp(pattern,'g')).length;

      // If the string occurs more than once, it is a pattern
      // and we return a properly formatted success string
      if (count > 1) return 'yes ' + pattern;
    }
  }

  // If we went all the way through our iterations and no
  // pattern was found, return the failure string
  return 'no null';
}

You can view the whole post including aselbie’s original solution to the challenge on his blog.

View aselbie’s profile and solution on Coderbyte.

The Gas Station challenge is as follows: in the input array, N will be the number of gas stations in a circular route and each subsequent element will be the string g:c where g is the amount of gas in gallons at that gas station and c will be the amount of gallons of gas needed to get to the following gas station. Your progam should return the index of the starting gas station that will allow you to travel around the whole route once, otherwise return the string impossible.

Here is my solution:

def GasStation(strArr): 
 amount, tank = int(strArr[0]), 0
 stations = [i.split(":") for i in (strArr[1:] + strArr[1:-1])]
 
 for start in range(amount):
    for curr in range(start, start+amount):
      tank = tank + int(stations[curr][0]) - int(stations[curr][1])   
      if tank < 0: break      
    if tank>=0: return start+1
    else:tank = 0 
 return "impossible"
    
print GasStation(raw_input())       

Explanation

amount represents the total number of gas stations.
tank represents the amount of gas currently in the tank.
stations is the array of stations with every element being an array itself consisting of two elements (amount of gallons obtained at that station and amount of gallons required to get to the next one).
start is our starting gas station number.
curr number of the current station being examined.

Generally, we need to check if we can start at a station and pass through all the rest (in the set order), without running out of gas.

The algorithm loops through each station, setting it as the starting station. Within this loop there is another loop that (starting at the set “start” station) goes through all the remaining stations (in order), checking if it is possible to travel to each one of them (if there is sufficient gas in the tank at each station).

The algorithm does this by looping through each station, starting at the start station (curr represents the number of the current station which the car reached) and checking if it is possible to travel to the next one by doing the following: add the gas obtained at the current station to the tank variable and subtract the amount of gas needed to reach the next one. This will show the amount of gas the car will have after reaching the next station. If there is not enough gas (hence “tank < 0”), we exit the inner loop and start at the next gas station. Otherwise the loop continues to the next station.

Once we left the inner loop, if tank>=0, then we have successfully passed all stations, and hence we exit the function and return “start+1” (+1 because indexes of the array are 0-based, but indexes of gas stations are not).

If tank<0, this means we exited the loop unsuccessfully, we therefore set tank to 0 and continue the outer loop, starting at the next station.

If we reach the end of the outer loop with no acceptable stations, we return “impossible”.

Note that in the beginning we add a repeat of the first (n-1) stations to the end of the stations array (hence we have all stations, and a repeat of the first n-1 stations as elements), our loop however only covers the non-repeated stations (given by the number “N”). This is done so that we can start at any station and still have all the other stations later on in the array, avoiding the need to reset indexes but still being able to pass through each station.

View Decay’s profile and solution on Coderbyte.

I am going to show you how I solved the LCS (Longest Common Subsequence) challenge using JavaScript. The challenge is as follows: your program will receive an array of 2 strings, each string being a random length made containing only three possible characters ‘a’, ‘b’ and ‘c’, the program must return the length of the longest common subsequence between the two strings, some characters from each string can be omitted to make the sequence.

Here is my solution:

function LCS(strArr) {    
    var s1 = strArr[0], s2 = strArr[1];
    var possChars = ['a', 'b', 'c'];
    function longest(len, start1, start2) {
        var p = [len];
        for (var i = 0; i < possChars.length; i += 1) {
            var n1 = s1.indexOf(possChars[i], start1),
                n2 = s2.indexOf(possChars[i], start2);
            if (n1 > -1 && n2 > -1) {
                p.push(longest(len + 1, n1 + 1, n2 + 1));
            }
        }
        return Math.max.apply(null, p);
    }
    return longest(0);
}
LCS(readline());

First let’s think about the desired output: the length of the subsequence. The only way we are going to know this is to find all sub sequences that exist for both strings and find the one with the longest length. Without looking at the characters in the strings we can find all possible sequences by using a k-ary tree. The figure below shows a tree with all possible sequences to a maximum length of three.

We are going to use a depth-first search algorithm to find all the sequences and eliminate nodes as we go to avoid searching branches that contain sequences that don’t exist in the strings. 

We will use a recursive function, longest, to evaluate each node with the parameters len, start1 and start2.  In to these parameters we will pass three values respectively:  how deep we have searched into the tree, the index of the next possible character in the sequence in the first string and the same for the second string. 

On the first call to longest we will pass 0 as the first argument as we have not yet searched any levels.  We won’t pass any arguments for start1 or start2, this will cause the function to search from the beginning of the strings. 

Within the function we will evaluate each possible character for the next part of the sequence by searching string 1 and string 2 from the point of the passed in index to see if that character occurs. If none of the characters can be found in both string 1 and string 2 then we return len, as this is the longest valid sequence on the branch we are searching.  If there are more found characters we will recur for each passing in len + 1 and the indices of the characters after the found valid character.  As we are looking for the length of the largest subsequence, we then return the largest value that each recursion yields.

Here is the solution again with comments:

function LCS(strArr) {
    // split array into convenient references
    var s1 = strArr[0], s2 = strArr[1];
    // declare the possible characters for each position in the sequence
    var possChars = ['a', 'b', 'c'];
    // declare the recursive function that will do the searching
    function longest(len, start1, start2) {
        // this array stores the lengths of the found sequences from this
        // node, note we initially populate it with len as this is the 
        // length of the sequence we have found so far
        var p = [len];
        // go through each possible character in turn 
        for (var i = 0; i < possChars.length; i += 1) {
            // search for the character in each string
            var n1 = s1.indexOf(possChars[i], start1),
                n2 = s2.indexOf(possChars[i], start2);
            // if the character in both strings then search for all
            // possible sequences that begin with this character
            if (n1 > -1 && n2 > -1) {
                p.push(longest(len + 1, n1 + 1, n2 + 1));
            }
        }
        // return the maximum length of all sequences
        return Math.max.apply(null, p);
    }
    // find and return the answer
    return longest(0);
}
LCS(readline());

View jackgeek’s profile and solution on Coderbyte.

Learn how to create a simple tic-tac-toe game using HTML, CSS and some basic jQuery functions!

Link to tutorial

The Coderbyte API is now public, access it with the link below.

http://coderbyte.com/api/

A new feature on Codebyte allows you to ask programming questions and receive answers from all the other coders! Check it out below.

http://www.coderbyte.com/CodingArea/Questions/

Badges are back up on Coderbyte. You can view them on your own or other user’s profiles. 

Also, the Game challenges page has been added. Currently there is one practice challenge available—check it out at the link below.

http://www.coderbyte.com/CodingArea/Challenges/

Coderbyte just reached its goal on Kickstarter! Thanks so much everyone!!!

http://www.kickstarter.com/projects/607387981/coderbyte-a-tool-for-programmers

That’s right! Check it out here. 

You can now connect your Coderbyte account on coderbits to gather points and badges! Thanks @coderbits.