An answer to this question on Stack Overflow.

Question

I'm not a specialist, but as far as I know, a bit of information in a QR-code is coded more than once, and it is defined as the redundancy level

How can I estimate a QR-code redundancy level ? Is where an mobile app or a website where I can test my QR-code redundancy level easily ? If not, is it an easy algorithm that I can implement ?

Redundancy is sorted in different categories according to this website, but I'd like to have the direct percentage value if possible

Answer

QR codes contain a couple of bits which indicate the error correction level, as depicted below (source):

An answer to this question on Stack Overflow.

Question

The sigmoid function is defined as

S(t) = 1 / (1 + e^(-t)) (where ^ is pow)

I found that using the C built-in function exp() to calculate the value of f(x) is slow. Is there any faster algorithm to calculate the value of f(x)?

Answer

This question has significantly more detail including these benchmarked results:

                                    name      rms_error        maxdiff        time_us        speedup        samples
                      logistic_with_tanh     5.9496e-02     1.5014e-01         0.0393         0.5076      200000001
                      logistic_with_atan     3.9051e-02     9.6934e-02         0.0321         0.6211      200000001
                       logistic_with_erf     6.5068e-02     1.6581e-01         0.0299         0.6676      200000001
            logistic_fexp_quintic_approx     1.2921e-07     5.9050e-07         0.0246         0.8118      200000001
        logistic_product_approx_float128     8.7032e-04     1.7217e-03         0.0209         0.9523      200000001
           logistic_with_exp_no_overflow     4.7660e-17     1.6653e-16         0.0198         1.0084      200000001
              logistic_product_approx128     8.7032e-04     1.7211e-03         0.0164         1.2187      200000001
         log_w_approx_exp_no_overflow128     8.7193e-04     1.7211e-03         0.0158         1.2640      200000001
                      logistic_with_sqrt     8.3414e-02     1.1086e-01         0.0146         1.3662      200000001
          log_w_approx_exp_no_overflow16     6.9726e-03     1.4074e-02         0.0141         1.4114      200000001
  log_w_approx_exp_no_overflow16_clamped     6.9726e-03     1.4074e-02         0.0141         1.4153      200000001
             logistic_schraudolph_approx     1.5661e-03     8.9906e-03         0.0138         1.4497      200000001
                       logistic_with_abs     6.0968e-02     8.2289e-02         0.0134         1.4936      200000001
                           logistic_orig     0.0000e+00     0.0000e+00         0.0199         ------      200000001

An answer to this question on Stack Overflow.

Question

Problem background

• I have a 2D array Map[Height][Width] that stores a bool to represent each cell.

• There exists two non-overlapping regions RegionA and RegionB.

• Each region is a list of unique adjacent integer co-ordinates.

• The number of co-ordinates in RegionA and RegionB are m and n respectively

• A co-ordinate in RegionA will never be horizontally or vertically adjacent to a coordinate in RegionB (i.e. the regions do not touch)

• The bounding box of RegionA could overlap with the bounding box of RegionB

• RegionA and RegionB may have holes

• RegionA may or may not surround RegionB (and vise versa)

• if a co-ordinate (X, Y) is part of a region then Map[Y][X] == 1, otherwise its zero.

Problem

I'm looking for an algorithm to determine the two co-ordinates A and B that have the minimum Euclidean distance, where A is a member of RegionA and B is a member of RegionB.

The brute force method has a time complexity of O(mn).

Is there a more time-efficient algorithm (preferably better than O(mn)) for solving this problem?

The name + link, code, or description of one instance of such an algorithm would be greatly appreciated and will be accepted as an answer.

C++ code to create two random regions A and B

The region generation code is immaterial to the problem being asked. and I am only interested in how close the regions are to each other. In the project I am working on I used cellular automata to create the regions. I can include the code for this if necessary. The Region construction procedure exists only to create relevant examples.

#include <cstdlib>
#include <cstring>
#include <vector>
#include <cstdio>
#include <map>
#include <ctime>
#include <cmath>
constexpr int Width = 150;
constexpr int Height = 37;
bool Map[Height][Width];
struct coord {
	int X, Y;
	coord(int X, int Y): X(X), Y(Y) {}
	bool operator==(const coord& Other) {
		return Other.X == X && Other.Y == Y;
	}
	bool IsAdjacentTo(const coord& Other){
		int ManhattanDistance = abs(X - Other.X) + abs(Y - Other.Y);
		return ManhattanDistance == 1;
	}
	bool IsOnMapEdge(){
		return X == 0 || Y == 0 || X == Width - 1 || Y == Height - 1;
	}
};
using region = std::vector<coord>;
void ClearMap(){
	std::memset(Map, 0, sizeof Map);
}
bool& GetMapBool(coord Coord) {
	return Map[Coord.Y][Coord.X];
}
int RandInt(int LowerBound, int UpperBound){
	return std::rand() % (UpperBound - LowerBound + 1) + LowerBound;
}
region CreateRegion(){
	std::puts("Creating Region");
	ClearMap();
	region Region;
	int RegionSize = RandInt(50, Width * Height / 2);
	Region.reserve(RegionSize);
	while (true){
		Region.emplace_back(
			RandInt(1, Width - 1), 
			RandInt(1, Height - 1)
		);
		if (!Region[0].IsOnMapEdge())
			break;
		else 
			Region.pop_back();
	}
	GetMapBool(Region[0]) = 1;
	while (Region.size() != RegionSize){
		coord Member = Region[RandInt(0, Region.size() - 1)];
		coord NeighbourToMakeAMember {
			RandInt(-1, 1) + Member.X,
			RandInt(-1, 1) + Member.Y
		};
		if (!Member.IsOnMapEdge() && !GetMapBool(NeighbourToMakeAMember) && Member.IsAdjacentTo(NeighbourToMakeAMember)){
			GetMapBool(NeighbourToMakeAMember) = 1;
			Region.push_back(NeighbourToMakeAMember);
		};
	}
	std::puts("Created Region");
	return Region;		
}
std::pair<region, region> CreateTwoRegions(){
	bool RegionsOverlap;
	std::pair<region, region> Regions;
	do {
		Regions.first = CreateRegion();
		Regions.second = CreateRegion();
		ClearMap();
		for (coord Member : Regions.first){
			GetMapBool(Member) = 1;
		}
		RegionsOverlap = 0;
		for (coord Member : Regions.second){
			if (GetMapBool(Member)){
				ClearMap();
				std::puts("Regions Overlap/Touch");
				RegionsOverlap = 1;
				break;
			} else {
				GetMapBool(Member) = 1;
			}
		}
	} while (RegionsOverlap);
	return Regions;
}
void DisplayMap(){
	for (int Y = 0; Y < Height; ++Y){
		for (int X = 0; X < Width; ++X)
			std::printf("%c", (Map[Y][X] ? '1' : '-'));
		std::puts("");
	}
}
int main(){
	int Seed = time(NULL);
	std::srand(Seed);
	ClearMap();
	auto[RegionA, RegionB] = CreateTwoRegions();
	DisplayMap();
}

Problem illustration

What are the co-ordinates of the points A and B that form the minimum Euclidean distance between the two regions?

Answer

Notes on finding the nearest points between two regions

As others have mentioned, you can improve on finding the closest points between the two regions of n and m points by first filtering each region's points to only those which border unassigned cells and then doing an all-pairs search between the boundaries. For a roughly rectangular region this would take O(m + n + 16 √m √n) time: two linear filters and then the all-pairs search. I've implemented an example of this search below.

But this will not save you any time if your regions are shaped like this:

########
#      #
# #### #
# #  # #
# # ## #
# #    #
# ######

If you are using larger datasets and can tolerate preprocessing you can get further acceleration using a 2D k-d tree.

Construction takes O(n log n) time after which you can search the tree in O(log n) time for m queries. So the total time to find the closest points is then O(m log n + n log n) or O(n log m + m log m).

You can do some benchmarking to determine if it is better to build the k-d tree for the larger or the smaller of the regions. Remember that this answer may change depending on how many times you're able to reuse the same k-d tree for queries against different regions.

For small datasets you'll probably find that the all-pairs comparison is faster because it has much greater cache locality.

Note that implementing a k-d tree is tricky, so you'll probably want to use an existing library or definitely use test cases if you're rolling your own.

Another algorithm

If we happen to know that the regions are within a distance d of each other we can get an even faster algorithm.

For one of the regions we can build a hash table where a reference to each member cell is stored at a hash location (c.y // d) * height + (c.x // d). To find the nearest neighbor to a query point we then do an all-pairs check against the points referenced in the associated "meta-cell" and as well as the meta-cell's neighbors.

Notes on region building

On the off-chance you're trying to grow the regions quickly, but their boundaries can overlap, this should do the trick.

Note that your question can be improved by stating why you are trying to calculate a thing. If you want to know the closest-cell so you have a primitive to build regions more quickly, then reconsidering how region building works might be a better use of your time, and it's what I address here.

If region generation is immaterial and you're only interested in how close they are to each other, then focus on defining, conceptually, what a region is and be very clear that your region construction procedure exists only to create relevant examples.

The fundamental trick we'll use to accelerate region construction is to make a space-time tradeoff. Rather than storing the map as a set of boolean values, we'll store it as a set of 8-bit integers. We reserve a few of these integers for special purposes:

• 0 - An unassigned space that a region may be built on
• 1 - A buffer cell that isn't part of any region, but close to one. This is not available for building on.
• 2, 3, 4, ... - valid region labels.

Thus, the algorithm for building a region becomes simple:

• Find a valid seed cell
• Grow outward from the seed cell via 4-connected cells until the desired number of cells is reached
  • A new Region Cell can only be placed in an Unassigned Space
• Iterate over Region Cells marking their 8-connected neighbors as Buffer cells.
  • Note that, if we add the new Buffer cells to the list of Region Cells and repeat the last step, we can grow arbitrarily large buffers between regions.

A few other parts of your code needed cleaning. Types are typically defined using Camel Case and variables use snake case. I prefer snake_case for functions as well. See a style guide for more opinions.

Do not use global variables they are bad and, in the fullness of time, they will bring you nothing but sorrow.

You're using C++, avoid using headers such as stdio, stdlib, and cstring. They provide the C way of doing things, which often come with disadvantageous such as diminished type safety.

Any time your if statements have a lot of conditions, ask yourself whether they can be simplified by inverting one or more of the conditions (that is, switching is_good() to !is_good()) and doing an early exit. This can make your code much easier to read and reasonable about.

An answer to this question on Stack Overflow.

Question

There are 3 (which I know) ways to suppress the "unused variable" warning. Any particular way is better than other ?

First

- (void)testString:(NSString *)testString
{
     (void)testString;
}

Second

- (void)testString:(NSString *)__unused testString
{
}

Third

- (void)testString:(NSString *)testString
{
    #pragma unused(testString)
}

Answer

In C23 you can write

[[maybe_unused]] int somevar;

(details)