Topcoder Data Science Marathon Match 126

You can check the details of this marathon match in topcoder site: https://www.topcoder.com/challenges/82eb883d-85e9-442f-b0eb-91631d3d2a8f?tab=details

Problem Summary

You are given a 2D grid containing few holes, number blocks and empty cells. Your task is to move numbered cells to any hole using Slide or Move operations. Along the way, your goal is to maximize game score based on certain defined rules.

My Approach

My approach was to use simulated annealing (SA). In every iteration of the SA, I swapped the position of two numbered cells from an ordered list of numbered cells. This ordered list represents the order in which I want to move/slide blocks to holes one by one and one at a time.

Now my score boosted up after few optimization on baseline SA.

1. When you move a block to hole, move it using shortest number of operations.
2. Instead of always choosing two random number blocks I fixed one index, which is the last number block index in previous iteration where the process stopped due to Z <= 1 (score multiplier, see description) or no way to move that block
3. Instead of having a random initial order of blocks, I used a greedy approach to sort the block based on shortest moves first, then based on block value.

A demo of my solution for one of the test cases is below.

My code and along with other resources (including other competitor’s approaches) of this match can be found in my Topcoder repository

Here is another blog article on this match.

Some contestants used Beam Search in this match. Here is the wiki book link for that.

Topcoder data science Marathon match 125

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.