RSS

Most votes on algorithm questions 8

Most votes on algorithm questions 8. #71 How does the algorithm to color the song list in iTunes 11 work? #72 Fast ceiling of an integer division in C / C++ #73 What is a loop invariant? #74 What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way? #75 What is dynamic programming? #76 Representing and solving a maze given an image #77 How to determine if a point is in a 2D triangle? #78 The most efficient way to implement an integer based power function pow(int, int) #79 Determine font color based on background color #80 Javascript Array.sort implementation?

Read all the top votes questions and answers in a single page.

#71: How does the algorithm to color the song list in iTunes 11 work? (Score: 298)

Created: 2012-11-30 Last updated: 2013-05-10

Tags: algorithm, user-interface, itunes

The new iTunes 11 has a very nice view for the song list of an album, picking the colors for the fonts and background in function of album cover. Anyone figured out how the algorithm works?

Third Example

#71 Best answer 1 of How does the algorithm to color the song list in iTunes 11 work? (Score: 423)

Created: 2012-12-03 Last updated: 2017-05-23

Example 1

I approximated the iTunes 11 color algorithm in Mathematica given the album cover as input:

Output 1

##How I did it

Through trial and error, I came up with an algorithm that works on ~80% of the albums with which I’ve tested it.

###Color Differences The bulk of the algorithm deals with finding the dominant color of an image. A prerequisite to finding dominant colors, however, is calculating a quantifiable difference between two colors. One way to calculate the difference between two colors is to calculate their Euclidean distance in the RGB color space. However, human color perception doesn’t match up very well with distance in the RGB color space.

Therefore, I wrote a function to convert RGB colors (in the form {1,1,1}) to YUV, a color space which is much better at approximating color perception:

(EDIT: @cormullion and @Drake pointed out that Mathematica’s built-in CIELAB and CIELUV color spaces would be just as suitable… looks like I reinvented the wheel a bit here)

convertToYUV[rawRGB_] :=
    Module[{yuv},
        yuv = {{0.299, 0.587, 0.114}, {-0.14713, -0.28886, 0.436},
            {0.615, -0.51499, -0.10001}};
        yuv . rawRGB
    ]

Next, I wrote a function to calculate color distance with the above conversion:

ColorDistance[rawRGB1_, rawRGB2_] := 
    EuclideanDistance[convertToYUV @ rawRGB1, convertToYUV @ rawRGB2]

###Dominant Colors

I quickly discovered that the built-in Mathematica function DominantColors doesn’t allow enough fine-grained control to approximate the algorithm that iTunes uses. I wrote my own function instead…

A simple method to calculate the dominant color in a group of pixels is to collect all pixels into buckets of similar colors and then find the largest bucket.

DominantColorSimple[pixelArray_] :=
    Module[{buckets},
        buckets = Gather[pixelArray, ColorDistance[#1,#2] < .1 &];
        buckets = Sort[buckets, Length[#1] > Length[#2] &];
        RGBColor @@ Mean @ First @ buckets
    ]

Note that .1 is the tolerance for how different colors must be to be considered separate. Also note that although the input is an array of pixels in raw triplet form ({{1,1,1},{0,0,0}}), I return a Mathematica RGBColor element to better approximate the built-in DominantColors function.

My actual function DominantColorsNew adds the option of returning up to n dominant colors after filtering out a given other color. It also exposes tolerances for each color comparison:

DominantColorsNew[pixelArray_, threshold_: .1, n_: 1, 
    numThreshold_: .2, filterColor_: 0, filterThreshold_: .5] :=
    Module[
        {buckets, color, previous, output},
        buckets = Gather[pixelArray, ColorDistance[#1, #2] < threshold &];
        If[filterColor =!= 0, 
        buckets = 
            Select[buckets, 
                ColorDistance[ Mean[#1], filterColor] > filterThreshold &]];
        buckets = Sort[buckets, Length[#1] > Length[#2] &];
        If[Length @ buckets == 0, Return[{}]];
        color = Mean @ First @ buckets;
        buckets = Drop[buckets, 1];
        output = List[RGBColor @@ color];
        previous = color;
        Do[
            If[Length @ buckets == 0, Return[output]];
            While[
                ColorDistance[(color = Mean @ First @ buckets), previous] < 
                    numThreshold, 
                If[Length @ buckets != 0, buckets = Drop[buckets, 1], 
                    Return[output]]
            ];
            output = Append[output, RGBColor @@ color];
            previous = color,
            {i, n - 1}
        ];
        output
    ]

###The Rest of the Algorithm

First I resized the album cover (36px, 36px) & reduced detail with a bilateral filter

image = Import["http://i.imgur.com/z2t8y.jpg"]
thumb = ImageResize[ image, 36, Resampling -> "Nearest"];
thumb = BilateralFilter[thumb, 1, .2, MaxIterations -> 2];

iTunes picks the background color by finding the dominant color along the edges of the album. However, it ignores narrow album cover borders by cropping the image.

thumb = ImageCrop[thumb, 34];

Next, I found the dominant color (with the new function above) along the outermost edge of the image with a default tolerance of .1.

border = Flatten[
    Join[ImageData[thumb][[1 ;; 34 ;; 33]] , 
        Transpose @ ImageData[thumb][[All, 1 ;; 34 ;; 33]]], 1];
background = DominantColorsNew[border][[1]];

Lastly, I returned 2 dominant colors in the image as a whole, telling the function to filter out the background color as well.

highlights = DominantColorsNew[Flatten[ImageData[thumb], 1], .1, 2, .2, 
    List @@ background, .5];
title = highlights[[1]];
songs = highlights[[2]];

The tolerance values above are as follows: .1 is the minimum difference between “separate” colors; .2 is the minimum difference between numerous dominant colors (A lower value might return black and dark gray, while a higher value ensures more diversity in the dominant colors); .5 is the minimum difference between dominant colors and the background (A higher value will yield higher-contrast color combinations)

Voila!

Graphics[{background, Disk[]}]
Graphics[{title, Disk[]}]
Graphics[{songs, Disk[]}]

Final Output

###Notes

The algorithm can be applied very generally. I tweaked the above settings and tolerance values to the point where they work to produce generally correct colors for ~80% of the album covers I tested. A few edge cases occur when DominantColorsNew doesn’t find two colors to return for the highlights (i.e. when the album cover is monochrome). My algorithm doesn’t address these cases, but it would be trivial to duplicate iTunes' functionality: when the album yields less than two highlights, the title becomes white or black depending on the best contrast with the background. Then the songs become the one highlight color if there is one, or the title color faded into the background a bit.

##More Examples

More Examples

#71 Best answer 2 of How does the algorithm to color the song list in iTunes 11 work?(Score: 44)

Created: 2012-12-12 Last updated: 2012-12-12

With the answer of @Seth-thompson and the comment of @bluedog, I build a little Objective-C (Cocoa-Touch) project to generate color schemes in function of an image.

You can check the project at :

https://github.com/luisespinoza/LEColorPicker

For now, LEColorPicker is doing:

  1. Image is scaled to 36x36 px (this reduce the compute time).
  2. It generates a pixel array from the image.
  3. Converts the pixel array to YUV space.
  4. Gather colors as Seth Thompson’s code does it.
  5. The color’s sets are sorted by count.
  6. The algorithm select the three most dominant colors.
  7. The most dominant is asigned as Background.
  8. The second and third most dominants are tested using the w3c color contrast formula, to check if the colors has enought contrast with the background.
  9. If one of the text colors don’t pass the test, then is asigned to white or black, depending of the Y component.

That is for now, I will be checking the ColorTunes project (https://github.com/Dannvix/ColorTunes) and the Wade Cosgrove project for new features. Also I have some new ideas for improve the color scheme result.

Screenshot_Mona

See also original question in stackoverflow

#72: Fast ceiling of an integer division in C / C++ (Score: 292)

Created: 2010-04-30 Last updated: 2015-01-27

Tags: c++, c, algorithm, math

Given integer values x and y, C and C++ both return as the quotient q = x/y the floor of the floating point equivalent. I’m interested in a method of returning the ceiling instead. For example, ceil(10/5)=2 and ceil(11/5)=3.

The obvious approach involves something like:

q = x / y;
if (q * y < x) ++q;

This requires an extra comparison and multiplication; and other methods I’ve seen (used in fact) involve casting as a float or double. Is there a more direct method that avoids the additional multiplication (or a second division) and branch, and that also avoids casting as a floating point number?

#72 Best answer 1 of Fast ceiling of an integer division in C / C++ (Score: 433)

Created: 2010-04-30 Last updated: 2019-05-28

For positive numbers

unsigned int x, y, q;

To round up …

q = (x + y - 1) / y;

or (avoiding overflow in x+y)

q = 1 + ((x - 1) / y); // if x != 0

#72 Best answer 2 of Fast ceiling of an integer division in C / C++(Score: 96)

Created: 2013-02-14

For positive numbers:

    q = x/y + (x % y != 0);

See also original question in stackoverflow

#73: What is a loop invariant? (Score: 288)

Created: 2010-07-11 Last updated: 2018-11-10

Tags: algorithm, terminology, definition, clrs, loop-invariant

I’m reading “Introduction to Algorithm” by CLRS. In chapter 2, the authors mention “loop invariants”. What is a loop invariant?

#73 Best answer 1 of What is a loop invariant? (Score: 370)

Created: 2010-07-11 Last updated: 2018-02-27

In simple words, a loop invariant is some predicate (condition) that holds for every iteration of the loop. For example, let’s look at a simple for loop that looks like this:

int j = 9;
for(int i=0; i<10; i++)  
  j--;

In this example it is true (for every iteration) that i + j == 9. A weaker invariant that is also true is that i >= 0 && i <= 10.

#73 Best answer 2 of What is a loop invariant?(Score: 131)

Created: 2010-07-11 Last updated: 2017-11-07

I like this very simple definition: (source)

A loop invariant is a condition [among program variables] that is necessarily true immediately before and immediately after each iteration of a loop. (Note that this says nothing about its truth or falsity part way through an iteration.)

By itself, a loop invariant doesn’t do much. However, given an appropriate invariant, it can be used to help prove the correctness of an algorithm. The simple example in CLRS probably has to do with sorting. For example, let your loop invariant be something like, at the start of the loop, the first i entries of this array are sorted. If you can prove that this is indeed a loop invariant (i.e. that it holds before and after every loop iteration), you can use this to prove the correctness of a sorting algorithm: at the termination of the loop, the loop invariant is still satisfied, and the counter i is the length of the array. Therefore, the first i entries are sorted means the entire array is sorted.

An even simpler example: Loops Invariants, Correctness, and Program Derivation.

The way I understand a loop invariant is as a systematic, formal tool to reason about programs. We make a single statement that we focus on proving true, and we call it the loop invariant. This organizes our logic. While we can just as well argue informally about the correctness of some algorithm, using a loop invariant forces us to think very carefully and ensures our reasoning is airtight.

See also original question in stackoverflow

#74: What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way? (Score: 284)

Created: 2009-07-31 Last updated: 2017-01-05

Tags: algorithm, packing

Ive got a bunch of rectangular objects which I need to pack into the smallest space possible (the dimensions of this space should be powers of two).

I’m aware of various packing algorithms that will pack the items as well as possible into a given space, however in this case I need the algorithm to work out how large that space should be as well.

Eg say Ive got the following rectangles

  • 128*32
  • 128*64
  • 64*32
  • 64*32

They can be packed into a 128*128 space

 _________________
|128*32          |
|________________|
|128*64          |
|                |
|                |
|________________|
|64*32  |64*32   |
|_______|________|

However if there was also a 160*32 and a 64*64 one it would need a 256*128 space

 ________________________________
|128*32          |64*64  |64*32  |
|________________|       |_______|
|128*64          |       |64*32  |
|                |_______|_______|
|                |               |
|________________|___            |
|160*32              |           |
|____________________|___________|

What algorithms are there that are able to pack a bunch of rectangles and determine the required size for the container (to a power of 2, and within a given maximum size for each dimension)?

#74 Best answer 1 of What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way? (Score: 94)

Created: 2010-11-24 Last updated: 2014-01-18

See this page on the ARC project for a survey of solutions, there is a trade-off between implementation complexity/time and optimality, but there is a wide range of algorithms to choose from.

Here’s an extract of the algorithms:

  1. First-Fit Decreasing Height (FFDH) algorithm
    FFDH packs the next item R (in non-increasing height) on the first level where R fits. If no level can accommodate R, a new level is created.
    Time complexity of FFDH: O(n·log n).
    Approximation ratio: FFDH(I)<=(17/10)·OPT(I)+1; the asymptotic bound of 17/10 is tight.

  2. Next-Fit Decreasing Height (NFDH) algorithm
    NFDH packs the next item R (in non-increasing height) on the current level if R fits. Otherwise, the current level is “closed” and a new level is created.
    Time complexity: O(n·log n).
    Approximation ratio: NFDH(I) <= 2·OPT(I)+1; the asymptotic bound of 2 is tight.

  3. Best-Fit Decreasing Height (BFDH) algorithm
    BFDH packs the next item R (in non-increasing height) on the level, among those that can accommodate R, for which the residual horizontal space is the minimum. If no level can accommodate R, a new level is created.

  4. Bottom-Left (BL) Algorithm
    BL first order items by non-increasing width. BL packs the next item as near to the bottom as it will fit and then as close to the left as it can go without overlapping with any packed item. Note that BL is not a level-oriented packing algorithm.
    Time complexity: O(n^2).
    Approximation ratio: BL(I) <= 3·OPT(I).

  5. Baker’s Up-Down (UD) algorithm
    UD uses a combination of BL and a generalization of NFDH. The width of the strip and the items are normalized so that the strip is of unit width. UD orders the items in non-increasing width and then divides the items into five groups, each with width in the range (1/2, 1], (1/3,1/2], (1/4,1/3], (1/5,1/4], (0,1/5]. The strip is also divided into five regions R1, ··· , R5. Basically, some items of width in the range (1/i+1, 1/i], for 1 <= i <= 4, are packed to region Ri by BL. Since BL leaves a space of increasing width from top to bottom at the right side of the strip, UD takes this advantage by first packing the item to Rj for j = 1, ··· , 4 (in order) from top to bottom. If there is no such space, the item is packed to Ri by BL. Finally, items of size at most 1/5 are packed to the spaces in R1, ··· , R4 by the (generalized) NFDH algorithm. Again if there is no space in these regions, the item is packed to R5 using NFDH.
    Approximation ratio: UD(I) <= (5/4) · OPT(I)+(53/8)H, where H is the maximum height of the items; the asymptotic bound of 5/4 is tight.

  6. Reverse-fit (RF) algorithm
    RF also normalizes the width of the strip and the items so that the strip is of unit width. RF first stacks all items of width greater than 1/2. Remaining items are sorted in non-increasing height and will be packed above the height H0 reached by those greater than 1/2. Then RF repeats the following process. Roughly speaking, RF packs items from left to right with their bottom along the line of height H0 until there is no more room. Then packs items from right to left and from top to bottom (called reverse-level) until the total width is at least 1/2. Then the reverse-level is dropped down until (at least) one of them touches some item below. The drop down is somehow repeated.
    Approximation ratio: RF(I) <= 2·OPT(I).

  7. Steinberg’s algorithm
    Steinberg’s algorithm, denoted as M in the paper, estimates an upper bound of the height H required to pack all the items such that it is proved that the input items can be packed into a rectangle of width W and height H. They then define seven procedures (with seven conditions), each to divide a problem into two smaller ones and solve them recursively. It has been showed that any tractable problem satisfies one of the seven conditions.
    Approximation ratio: M(I) <= 2·OPT(I).

  8. Split-Fit algorithm (SF) SF divides items into two groups, L1 with width greater than 1/2 and L2 at most 1/2. All items of L1 are first packed by FFDH. Then they are arranged so that all items with width more than 2/3 are below those with width at most 2/3. This creates a rectangle R of space with width 1/3. Remaining items in L2 are then packed to R and the space above those packed with L1 using FFDH. The levels created in R are considered to be below those created above the packing of L1.
    Approximation ratio: SF(I) <= (3/2) ·OPT(I) + 2; the asymptotic bound of 3/2 is tight.

  9. Sleator’s algorithm
    Sleater’s algorithm consists of four steps:

  10. All items of width greater than 1/2 are packed on top of one another in the bottom of the strip. Suppose h0 is the height of the resulting packing All subsequent packing will occur above h0.

  11. Remaining items are ordered by non-increasing height. A level of items are packed (in non-increasing height order) from left to right along the line of height h0.

  12. A vertical line is then drawn in the middle to cut the strip into two equal halves (note this line may cut an item that is packed partially in the right half). Draw two horizontal line segments of length one half, one across the left half (called the left baseline) and one across the right half (called the right baseline) as low as possible such that the two lines do not cross any item.

  13. Choose the left or right baseline which is of a lower height and pack a level of items into the corresponding half of the strip until the next item is too wide.

A new baseline is formed and Step (4) is repeated on the lower baseline until all items are packed.
Time complexity: O(n ·log n).
The approximation ratio of Sleator’s algorithm is 2.5 which is tight.

#74 Best answer 2 of What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way?(Score: 71)

Created: 2009-07-31

The quick and dirty first pass solution is always a great one to start with, as a comparison if nothing else.

Greedy placement from large to small.

Put the largest rectangle remaining into your packed area. If it can’t fit anywhere, place it in a place that extends the pack region as little as possible. Repeat until you finish with the smallest rectangle.

It’s not perfect at all but it’s easy and a nice baseline. It would still pack your original example perfectly, and give you an equivalent answer for the second as well.

See also original question in stackoverflow

#75: What is dynamic programming? (Score: 283)

Created: 2009-06-30 Last updated: 2019-01-25

Tags: algorithm, dynamic-programming

What is dynamic programming?

How is it different from recursion, memoization, etc?

I have read the wikipedia article on it, but I still don’t really understand it.

#75 Best answer 1 of What is dynamic programming? (Score: 215)

Created: 2009-06-30 Last updated: 2017-04-26

Dynamic programming is when you use past knowledge to make solving a future problem easier.

A good example is solving the Fibonacci sequence for n=1,000,002.

This will be a very long process, but what if I give you the results for n=1,000,000 and n=1,000,001? Suddenly the problem just became more manageable.

Dynamic programming is used a lot in string problems, such as the string edit problem. You solve a subset(s) of the problem and then use that information to solve the more difficult original problem.

With dynamic programming, you store your results in some sort of table generally. When you need the answer to a problem, you reference the table and see if you already know what it is. If not, you use the data in your table to give yourself a stepping stone towards the answer.

The Cormen Algorithms book has a great chapter about dynamic programming. AND it’s free on Google Books! Check it out here.

#75 Best answer 2 of What is dynamic programming?(Score: 189)

Created: 2015-03-19 Last updated: 2019-11-09

Dynamic programming is a technique used to avoid computing multiple times the same subproblem in a recursive algorithm.

Let’s take the simple example of the Fibonacci numbers: finding the n th Fibonacci number defined by

Fn = Fn-1 + Fn-2 and F0 = 0, F1 = 1

Recursion

The obvious way to do this is recursive:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

Dynamic Programming

  • Top Down - Memoization

The recursion does a lot of unnecessary calculations because a given Fibonacci number will be calculated multiple times. An easy way to improve this is to cache the results:

cache = {}

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n in cache:
        return cache[n]

    cache[n] = fibonacci(n - 1) + fibonacci(n - 2)

    return cache[n]
  • Bottom-Up

A better way to do this is to get rid of the recursion all-together by evaluating the results in the right order:

cache = {}

def fibonacci(n):
    cache[0] = 0
    cache[1] = 1

    for i in range(2, n + 1):
        cache[i] = cache[i - 1] +  cache[i - 2]

    return cache[n]

We can even use constant space and store only the necessary partial results along the way:

def fibonacci(n):
  fi_minus_2 = 0
  fi_minus_1 = 1

  for i in range(2, n + 1):
      fi = fi_minus_1 + fi_minus_2
      fi_minus_1, fi_minus_2 = fi, fi_minus_1

  return fi
  • How apply dynamic programming?
  1. Find the recursion in the problem.
  2. Top-down: store the answer for each subproblem in a table to avoid having to recompute them.
  3. Bottom-up: Find the right order to evaluate the results so that partial results are available when needed.

Dynamic programming generally works for problems that have an inherent left to right order such as strings, trees or integer sequences. If the naive recursive algorithm does not compute the same subproblem multiple times, dynamic programming won’t help.

I made a collection of problems to help understand the logic: https://github.com/tristanguigue/dynamic-programing

See also original question in stackoverflow

#76: Representing and solving a maze given an image (Score: 281)

Created: 2012-10-21 Last updated: 2017-05-23

Tags: python, algorithm, matlab, image-processing, maze

What is the best way to represent and solve a maze given an image?

The cover image of The Scope Issue 134

Given an JPEG image (as seen above), what’s the best way to read it in, parse it into some data structure and solve the maze? My first instinct is to read the image in pixel by pixel and store it in a list (array) of boolean values: True for a white pixel, and False for a non-white pixel (the colours can be discarded). The issue with this method, is that the image may not be “pixel perfect”. By that I simply mean that if there is a white pixel somewhere on a wall it may create an unintended path.

Another method (which came to me after a bit of thought) is to convert the image to an SVG file - which is a list of paths drawn on a canvas. This way, the paths could be read into the same sort of list (boolean values) where True indicates a path or wall, False indicating a travel-able space. An issue with this method arises if the conversion is not 100% accurate, and does not fully connect all of the walls, creating gaps.

Also an issue with converting to SVG is that the lines are not “perfectly” straight. This results in the paths being cubic bezier curves. With a list (array) of boolean values indexed by integers, the curves would not transfer easily, and all the points that line on the curve would have to be calculated, but won’t exactly match to list indices.

I assume that while one of these methods may work (though probably not) that they are woefully inefficient given such a large image, and that there exists a better way. How is this best (most efficiently and/or with the least complexity) done? Is there even a best way?

Then comes the solving of the maze. If I use either of the first two methods, I will essentially end up with a matrix. According to this answer, a good way to represent a maze is using a tree, and a good way to solve it is using the A* algorithm. How would one create a tree from the image? Any ideas?

TL;DR
Best way to parse? Into what data structure? How would said structure help/hinder solving?

UPDATE
I’ve tried my hand at implementing what @Mikhail has written in Python, using numpy, as @Thomas recommended. I feel that the algorithm is correct, but it’s not working as hoped. (Code below.) The PNG library is PyPNG.

import png, numpy, Queue, operator, itertools

def is_white(coord, image):
  """ Returns whether (x, y) is approx. a white pixel."""
  a = True
  for i in xrange(3):
    if not a: break
    a = image[coord[1]][coord[0] * 3 + i] > 240
  return a

def bfs(s, e, i, visited):
  """ Perform a breadth-first search. """
  frontier = Queue.Queue()
  while s != e:
    for d in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
      np = tuple(map(operator.add, s, d))
      if is_white(np, i) and np not in visited:
        frontier.put(np)
    visited.append(s)
    s = frontier.get()
  return visited

def main():
  r = png.Reader(filename = "thescope-134.png")
  rows, cols, pixels, meta = r.asDirect()
  assert meta['planes'] == 3 # ensure the file is RGB
  image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels))
  start, end = (402, 985), (398, 27)
  print bfs(start, end, image2d, [])

#76 Best answer 1 of Representing and solving a maze given an image (Score: 241)

Created: 2012-10-21 Last updated: 2017-11-11

Here is a solution.

  1. Convert image to grayscale (not yet binary), adjusting weights for the colors so that final grayscale image is approximately uniform. You can do it simply by controlling sliders in Photoshop in Image -> Adjustments -> Black & White.
  2. Convert image to binary by setting appropriate threshold in Photoshop in Image -> Adjustments -> Threshold.
  3. Make sure threshold is selected right. Use the Magic Wand Tool with 0 tolerance, point sample, contiguous, no anti-aliasing. Check that edges at which selection breaks are not false edges introduced by wrong threshold. In fact, all interior points of this maze are accessible from the start.
  4. Add artificial borders on the maze to make sure virtual traveler will not walk around it :)
  5. Implement breadth-first search (BFS) in your favorite language and run it from the start. I prefer MATLAB for this task. As @Thomas already mentioned, there is no need to mess with regular representation of graphs. You can work with binarized image directly.

Here is the MATLAB code for BFS:

function path = solve_maze(img_file)
  %% Init data
  img = imread(img_file);
  img = rgb2gray(img);
  maze = img > 0;
  start = [985 398];
  finish = [26 399];

  %% Init BFS
  n = numel(maze);
  Q = zeros(n, 2);
  M = zeros([size(maze) 2]);
  front = 0;
  back = 1;

  function push(p, d)
    q = p + d;
    if maze(q(1), q(2)) && M(q(1), q(2), 1) == 0
      front = front + 1;
      Q(front, :) = q;
      M(q(1), q(2), :) = reshape(p, [1 1 2]);
    end
  end

  push(start, [0 0]);

  d = [0 1; 0 -1; 1 0; -1 0];

  %% Run BFS
  while back <= front
    p = Q(back, :);
    back = back + 1;
    for i = 1:4
      push(p, d(i, :));
    end
  end

  %% Extracting path
  path = finish;
  while true
    q = path(end, :);
    p = reshape(M(q(1), q(2), :), 1, 2);
    path(end + 1, :) = p;
    if isequal(p, start) 
      break;
    end
  end
end

It is really very simple and standard, there should not be difficulties on implementing this in Python or whatever.

And here is the answer:

Enter image description here

#76 Best answer 2 of Representing and solving a maze given an image(Score: 162)

Created: 2012-11-01 Last updated: 2017-07-27

This solution is written in Python. Thanks Mikhail for the pointers on the image preparation.

An animated Breadth-First Search:

Animated version of BFS

The Completed Maze:

Completed Maze

#!/usr/bin/env python

import sys

from Queue import Queue
from PIL import Image

start = (400,984)
end = (398,25)

def iswhite(value):
    if value == (255,255,255):
        return True

def getadjacent(n):
    x,y = n
    return [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]

def BFS(start, end, pixels):
    
    queue = Queue()
    queue.put([start]) # Wrapping the start tuple in a list
    
    while not queue.empty():
        
        path = queue.get() 
        pixel = path[-1]

        if pixel == end:
            return path

        for adjacent in getadjacent(pixel):
            x,y = adjacent
            if iswhite(pixels[x,y]):
                pixels[x,y] = (127,127,127) # see note
                new_path = list(path)
                new_path.append(adjacent)
                queue.put(new_path)

    print "Queue has been exhausted. No answer was found."


if __name__ == '__main__':

    # invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.]
    base_img = Image.open(sys.argv[1])
    base_pixels = base_img.load()

    path = BFS(start, end, base_pixels)

    path_img = Image.open(sys.argv[1])
    path_pixels = path_img.load()

    for position in path:
        x,y = position
        path_pixels[x,y] = (255,0,0) # red

    path_img.save(sys.argv[2])

Note: Marks a white visited pixel grey. This removes the need for a visited list, but this requires a second load of the image file from disk before drawing a path (if you don’t want a composite image of the final path and ALL paths taken).

A blank version of the maze I used.

See also original question in stackoverflow

#77: How to determine if a point is in a 2D triangle? (Score: 278)

Created: 2010-01-12 Last updated: 2016-07-30

Tags: algorithm, math, geometry

Is there an easy way to determine if a point is inside a triangle? It’s 2D, not 3D.

#77 Best answer 1 of How to determine if a point is in a 2D triangle? (Score: 290)

Created: 2010-01-12 Last updated: 2018-10-22

In general, the simplest (and quite optimal) algorithm is checking on which side of the half-plane created by the edges the point is.

Here’s some high quality info in this topic on GameDev, including performance issues.

And here’s some code to get you started:

float sign (fPoint p1, fPoint p2, fPoint p3)
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
    float d1, d2, d3;
    bool has_neg, has_pos;
    
    d1 = sign(pt, v1, v2);
    d2 = sign(pt, v2, v3);
    d3 = sign(pt, v3, v1);

    has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);

    return !(has_neg && has_pos);
}

#77 Best answer 2 of How to determine if a point is in a 2D triangle?(Score: 183)

Created: 2010-01-12 Last updated: 2010-01-12

Solve the following equation system:

p = p0 + (p1 - p0) * s + (p2 - p0) * t

The point p is inside the triangle if 0 <= s <= 1 and 0 <= t <= 1 and s + t <= 1.

s,t and 1 - s - t are called the barycentric coordinates of the point p.

See also original question in stackoverflow

#78: The most efficient way to implement an integer based power function pow(int, int) (Score: 266)

Created: 2008-09-19 Last updated: 2015-01-30

Tags: c, algorithm, math, exponentiation

What is the most efficient way given to raise an integer to the power of another integer in C?

// 2^3
pow(2,3) == 8

// 5^5
pow(5,5) == 3125

#78 Best answer 1 of The most efficient way to implement an integer based power function pow(int, int) (Score: 410)

Created: 2008-09-19 Last updated: 2018-04-04

Exponentiation by squaring.

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

This is the standard method for doing modular exponentiation for huge numbers in asymmetric cryptography.

#78 Best answer 2 of The most efficient way to implement an integer based power function pow(int, int)(Score: 76)

Created: 2008-09-20 Last updated: 2017-09-24

Note that exponentiation by squaring is not the most optimal method. It is probably the best you can do as a general method that works for all exponent values, but for a specific exponent value there might be a better sequence that needs fewer multiplications.

For instance, if you want to compute x^15, the method of exponentiation by squaring will give you:

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^3 = x*x*x

This is a total of 6 multiplications.

It turns out this can be done using “just” 5 multiplications via addition-chain exponentiation.

n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15

There are no efficient algorithms to find this optimal sequence of multiplications. From Wikipedia:

The problem of finding the shortest addition chain cannot be solved by dynamic programming, because it does not satisfy the assumption of optimal substructure. That is, it is not sufficient to decompose the power into smaller powers, each of which is computed minimally, since the addition chains for the smaller powers may be related (to share computations). For example, in the shortest addition chain for a¹⁵ above, the subproblem for a⁶ must be computed as (a³)² since a³ is re-used (as opposed to, say, a⁶ = a²(a²)², which also requires three multiplies).

See also original question in stackoverflow

#79: Determine font color based on background color (Score: 264)

Created: 2009-12-06 Last updated: 2012-01-09

Tags: algorithm, language-agnostic, colors

Given a system (a website for instance) that lets a user customize the background color for some section but not the font color (to keep number of options to a minimum), is there a way to programmatically determine if a “light” or “dark” font color is necessary?

I’m sure there is some algorithm, but I don’t know enough about colors, luminosity, etc to figure it out on my own.

#79 Best answer 1 of Determine font color based on background color (Score: 471)

Created: 2009-12-06 Last updated: 2018-07-24

I encountered similar problem. I had to find a good method of selecting contrastive font color to display text labels on colorscales/heatmaps. It had to be universal method and generated color had to be “good looking”, which means that simple generating complementary color was not good solution - sometimes it generated strange, very intensive colors that were hard to watch and read.

After long hours of testing and trying to solve this problem, I found out that the best solution is to select white font for “dark” colors, and black font for “bright” colors.

Here’s an example of function I am using in C#:

Color ContrastColor(Color color)
{
    int d = 0;

    // Counting the perceptive luminance - human eye favors green color... 
    double luminance = ( 0.299 * color.R + 0.587 * color.G + 0.114 * color.B)/255;

    if (luminance > 0.5)
       d = 0; // bright colors - black font
    else
       d = 255; // dark colors - white font
            
    return  Color.FromArgb(d, d, d);
}

This was tested for many various colorscales (rainbow, grayscale, heat, ice, and many others) and is the only “universal” method I found out.

Edit
Changed the formula of counting a to “perceptive luminance” - it really looks better! Already implemented it in my software, looks great.

Edit 2 @WebSeed provided a great working example of this algorithm: http://codepen.io/WebSeed/full/pvgqEq/

#79 Best answer 2 of Determine font color based on background color(Score: 25)

Created: 2016-04-27 Last updated: 2017-10-09

Just in case someone would like a shorter, maybe easier to understand version of GaceK’s answer:

public Color ContrastColor(Color iColor)
{
   // Calculate the perceptive luminance (aka luma) - human eye favors green color... 
   double luma = ((0.299 * iColor.R) + (0.587 * iColor.G) + (0.114 * iColor.B)) / 255;
   
   // Return black for bright colors, white for dark colors
   return luma > 0.5 ? Color.Black : Color.White;
}

Note: I removed the inversion of the luma value (to make bright colors have a higher value, what seems more natural to me and is also the ‘default’ calculation method.

I used the same constants as GaceK from here since they worked great for me.

(You can also implement this as an Extension Method using the following signature:

public static Color ContrastColor(this Color iColor)

You can then call it via foregroundColor = background.ContrastColor().)

See also original question in stackoverflow

#80: Javascript Array.sort implementation? (Score: 262)

Created: 2008-10-24 Last updated: 2014-01-28

Tags: javascript, algorithm, arrays, sorting

Which algorithm does the JavaScript Array#sort() function use? I understand that it can take all manner of arguments and functions to perform different kinds of sorts, I’m simply interested in which algorithm the vanilla sort uses.

#80 Best answer 1 of Javascript Array.sort implementation? (Score: 323)

Created: 2008-10-25 Last updated: 2017-05-23

I’ve just had a look at the WebKit (Chrome, Safari …) source. Depending on the type of array, different sort methods are used:

Numeric arrays (or arrays of primitive type) are sorted using the C++ standard library function std::qsort which implements some variation of quicksort (usually introsort).

Contiguous arrays of non-numeric type are stringified and sorted using mergesort, if available (to obtain a stable sorting) or qsort if no merge sort is available.

For other types (non-contiguous arrays and presumably for associative arrays) WebKit uses either selection sort (which they call “min” sort) or, in some cases, it sorts via an AVL tree. Unfortunately, the documentation here is rather vague so you’d have to trace the code paths to actually see for which types which sort method is used.

And then there are gems like this comment:

// FIXME: Since we sort by string value, a fast algorithm might be to use a
// radix sort. That would be O(N) rather than O(N log N).

– Let’s just hope that whoever actually “fixes” this has a better understanding of asymptotic runtime than the writer of this comment, and realises that radix sort has a slightly more complex runtime description than simply O(N).

(Thanks to phsource for pointing out the error in the original answer.)

#80 Best answer 2 of Javascript Array.sort implementation?(Score: 78)

Created: 2008-10-24 Last updated: 2008-10-25

If you look at this bug 224128, it appears that MergeSort is being used by Mozilla.

See also original question in stackoverflow


Notes:
  1. This page use API to get the relevant data from stackoverflow community.
  2. Content license on this page is CC BY-SA 3.0.
  3. score = up votes - down votes.