Posts

Showing posts from April, 2017

Counting Regions in Images II

Image
Carrying on from the previous post, in order to better illustrate the affects of the different thresholds, the thresholds were made as input parameters to this new algorithm, and in addition the color of each region was made different from each other, plus some bug fixes (casting fixes, etc.). To illustrate the concept I picked up an image of me running and applied the algorithm varying the thresholds. As you can see from the image below, the smaller the thresholds the more regions it finds, and conversely as we increase the thresholds the bigger and the fewer the regions are. If one makes the thresholds zero, it will imply that each pixel will be its own region. Similarly, when the threshold goes to infinity, the entire image becomes just one big region. Hope this helps - cheers, Marcelo. using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Drawing; using System.Collections; namespace CountRegi

Counting Regions in Images

Image
Suppose that you're given an image on white background and you have a task to count the number of regions in that image where a region is loosely defined by these properties: A) A region is a set of adjacent pixels, AND B) The absolute color difference between adjacent pixels are within a certain threshold, AND C) The absolute color difference between any two pixels in the region are within a certain threshold In other words, a region consists of a chunk of pixels near each other that more or less share the same color. How would you write an algorithm to detect such regions? One option is to implement the following approach: 1) Define two thresholds: one is between the adjacent pixels (called the "neighbor threshold") and the other one is between any pixel in the region and the center pixel (called the "seed threshold"). The tighter these thresholds the more precised the algorithm (precision-based), and conversely the more relaxed the thresholds the les

Gaming Array, by HackerRank

Image
Problem statement:  https://www.hackerrank.com/challenges/an-interesting-game-1 . Given the constraints of 10^5, we're likely either looking for a linear solution or worst case an NLogN. I decided to go with the latter. For that there are multiple ways of doing it (sorting strategies), the one I picked is the following: Build a Heap Add the elements of the array to the heap, descending order In addition to the element, have the index of the element in the heap When the game starts: Pick the latest from the heap (LogN) If less than the current min, that's a valid move, replace current min and change the current winner Do this until you get an index of zero (first element), hence all the elements are covered (N) Total execution time: NLogN Total space: N (heap) Works well for the problem, code is below, have a great night folks!!! Marcelo using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution {  

Min Loss, by HackerRank

Image
Problem statement is here:  https://www.hackerrank.com/challenges/minimum-loss . At first I thought about an N^2 solution, but with N ~= 10^5, such approach would definitely time out. I read some of the discussions (no shame, really, purpose of hacker-rank practice is for one to learn) and an idea was brought up there:  Build a Binary Search Tree out of the numbers  As you add a new number, while going down the tree keep track of the min-loss Assuming that the tree is going to be relatively balanced (and that's a fair assumption given the statement that the input numbers are all unique), the execution time becomes near NLogN, which works quick enough for N ~= 10^5. Code is below, and a picture of me and the team who's bringing Bots to Search Engines !!! :) Many cheers, Marcelo. using System; using System.Collections.Generic; using System.IO; class Solution {     static void Main(String[] args)     {         int n = Int32.Parse(Console.ReadLine());        

K-Factorization

Image
Problem statement:  https://www.hackerrank.com/challenges/k-factorization . The most annoying part of this problem is the "sorting in lexicographic order", which is the code in the base case. Some string manipulation and calculation block according to the definition of lexicographic order in the problem statement is necessary. Rest of the code is an immediate brute-force using Depth-First-Search (DFS) approach. My first implementation was failing due to stack-overflow: changing the data types from Int32 to Int64 solved that problem. The second implementation was timing out: adding a "current index" to the function and starting the loop from that index (instead of starting from zero) did the job. Code is down below. May your week be awesome, folks!!! Also, see a pic of me and a bunch of kids watching #bossbaby today. Bye!!! Marcelo. using System; using System.Collections.Generic; using System.IO; class Solution {     static void Main(String[] args

Password Cracker

Image
Problem is described here:  https://www.hackerrank.com/challenges/password-cracker.  First, this is in the recursion section of the page - that should give you a hint that a recursive solution might be your best bet. The problem can be solved by:  - Determining whether the attempt password starts with one of the passwords  - If so, remove it from the attempt password, call it recursively  - Keep track of the passwords used  - The moment that the attempt password is empty, you have found a solution  - If none is found, well, none is found My first attempt kind of worked, but timed out on few cases: When looking at the test cases that timed out, one stood out: a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaaa aaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa b Now if you notice it, it is clear that the attempt password will never have a solution given that there is one character in the attempt password that is not present in any