Algorithm

Topcoder data science Marathon match 125

| Shadek

This was my fourth match in Topcoder data science marathon. If you don’t know what a data science marathon match is, here is a short description.

Marathon match runs for about a week. Each participant can submit their code during this period as many times as they want and only the last submission is considered for scoring.

Now regarding the type of problem you will be given in Marathon match: There is no universal optimal solution to the problem you are given. Your task is to optimize the solution as much as you can based on heuristics, advanced data structure and algorithm, genetic algorithm, machine learning algorithm, probability, statistics and so on.

Marathon Match 125

In this match, you were to solve a square grid to make as many horizontal, vertical or diagonal lines as possible with length of at least 5 grids of same color. At the end of every move three random balls with random colors will appear in the board. In each move, you can only move a ball from its position to an empty position by following a 4-connected path of empty squares.

Full problem statement: https://www.topcoder.com/challenges/39f57908-803c-4b69-b208-4fc03717ab12

My Approach

My approach was to evaluate the board using a scoring function for every valid moves on the current grid and choose a move that leads to maximum score.

The score of a board is sum of scores coming from every possible grid segment of 5 length (horizontally, vertically or diagonally). In my solution, I didn’t consider diagonal segments as they block balls to move in the grid.

Now the scoring of a single segment is done by counting frequency of colors in that segment. The score is exponentially related to count of dominant color minus the count of other colors)

Now regarding optimization of time so that my code can execute as many moves as possible: I calculated the base score of the current grid before each move and stored all segment scores. Now each candidate move, affects only the segments that include either (fromX, fromY) cell or (toX, toY) cell. So to calculate the score of the board resulting from the candidate move, I only calculated those segments that are affected and adding all those segment scores from base score that ARE not affected.

My code submission and other materials on this match can be found here.

Topcoder SRM 800 div2 medium

| Shadek

Topcoder achieved a milestone by arranging 800 Single Round Algorithm Matches (SRM) to the coder all over the world. Topcoder arranged a virtual party before this 800th match. Among this 800 matches, I participated in over 150 matches. (See my Topcoder profile). Thank you Topcoder for helping me improve my coding skill.

Let’s get back to the problem. This problem was worth 400 points. Please take a look at the problem statement as I am not gonna repeat the problem statement.

Look at the above picture to visualize this problem. As like this picture, our goal is to get letter ‘c’ (cherry) in all reels.

Key insights from this problem:

  • There are maximum 5 reels.
  • Each reel has maximum 10 fruits (or letters) in a circular fashion.

    • From these two constraints, we know that there could be maximum 10*10*10*10*10 = 10^5 different display strings you will see based on positions of the fruits although two different configurations might end up with same display string as there could be duplicate letters in a reel.

    My approach for this problem is to play the slot machine rounds and keeping track of configurations in a map or dictionary. If a configuration repeats before getting a jackpot, that basically means the game entered into a cycle and we can return “impossible” in this case. Each configuration corresponds to a set of position indices of current display letters from all reels. Now the question is – how to store these configurations in map? My approach is to use unique letters to denote each index across all reels. For example ‘a’ is for index 0, ‘b’ is for index 1 and so on. The good thing is we will never run out of letters to represent indices as there would be maximum 10 letters (meaning 10 positions) in each reel. Remember that, this configuration letters are different from the letters in each reel.

    After each round of play, we have to adjust the positions for next round. See the code below for a better understanding of my approach.

    #include<bits/stdc++.h>
using namespace std;

class SlotMachineHacking {
public:
int win(vector reels, vector steps) {
map uniq_configs;
string jackpot = ""; //jackpot string: all 'c'
int i,j,k;
for(i = 0;i<reels.size();i++)
{
jackpot = jackpot + 'c';
}
int cnt = 0;
int n = reels.size();
int pos[n]; //indices of current display letters for all reel strings
for(i=0;i<n;i++)
{
pos[i] = 0;
}
auto newpos = [&pos, &reels, &steps](int n){
int i;
for(i=0;i<n;i++){
pos[i] = (pos[i]+ steps[i])%reels[i].size();
}
};
while (true){
string curr_display = "";
newpos(n);
for(i=0;i<n;i++)
{
curr_display += reels[i][pos[i]];
}
if(curr_display == jackpot)  //current display matches jackpot
return cnt;
string curr_config= "";
for(i = 0;i<n;i++){
curr_config = curr_config + char(('a'+pos[i]));
}
if(uniq_configs[curr_config])
return -1;
uniq_configs[curr_config] = 1;
cnt += 1;
}
return -1;
}
};

    In the above code you will see a c++ closure defined.

    Another approach is to run the simulation for 10^5 times without keeping a map

    more specifically,

    number of rounds, R = Length(reels[0])*Length(reels[1])*…..Length(reels[n-1]);
    n is total number of reels.

    So if you don’t hit jackpot during this many rounds, you will never hit jackpot. Because if you do not enter into cycle during this many rounds, you will cycle in the very next round (i.e R+1‘th round)

    References

    1. image source