Number system without 7

A special country does not use the number 7. Whenever a 7 is encounter, the next possible
number is used. For example, 7 -> 8, 17 -> 19. Given a number in the country, translate it
into our number.

Solution:

Obviously, this is a base-9 number system, made of digits 0,1,2,3,4,5,6,8,9, where 8 is
actually 7, and 9 is actually 8.

If a number is given as d1d2d3...dn, then the translation is:

D1 * 9^(n-1) + D2 * 9^(n-2) + .. + Dn * 9^0,

where Di = di if di = 0-6,
Di = di - 1 if di = 8 or 9.

Code verification is done below.


#include <iostream>
using namespace std;

// return true if x contains digit 7.
bool contains7(int x) {
    while (x > 0) {
        int y = x % 10;
        if (y == 7) return true;
        x /= 10;
    }
    return false;
}

void getX(int & x) {
    do {
        ++ x;
    } while (contains7(x));
}

// convert new number system number back to normal number.
int convert_back(int x) {
    int v = 0;
    int base = 1;
    while (x > 0) {
        int y = x % 10;
        if (y == 8 || y == 9) y -= 1;
        v += y * base;

        base *= 9;
        x /= 10;
    }
    return v;
}

int main() {
    int x = 0; // new number system number that ignores 7.
    for (int i = 1; i < 1000; ++ i) {
        getX(x);
        string result = (i == convert_back(x) ? "ok" : "err");
        cout << i << "=> " << x << " " << result << "\t";
        if (result == "err") break;
        if (i % 5 == 0) cout << endl;
    }
    cout << endl;
    return 0;
}

Find meeting point

I. Manhattan distance

In a city there are N persons. A person can walk only horizontally or vertically. Find a point that minimizes the sum of distances all persons walk to the point.

This is called the manhattan distance since a person can walk only horizontally or vertically, like in the city of Manhattan.

Let's assume this is 1-dimensional. Then for 2 persons, the point can be any point on the line connecting the 2 persons. For 3 persons , the point is the middle person. For 4 persons, the point can be any point between the middle 2 persons. For 5 persons, the point is the middle person. In general, for odd number of persons, it's the person in the middle; for even number of persons, it's any point between the middle 2 persons.

This can be extended to 2-dimensional. The answer is the point (x, y), where x and y are the median points taken independently of all the xi and yi for i = 1 to n. [1][2]

II. Geometric median.

The geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points [3]. This no longer requires the path be horizontal or vertical.

Despite the simple form, the solution is much more complex than the similar problem of finding the center of mass, which minimizes the sum of the squares of distances of the points to the center. There is no simple formula for the solution.

For 2 points, it's any point on the line connecting the 2 points.

For 3 non-collinear points, the problem is known as Fermat's problem. Solution is in [3]. For 4 co-planar points, the solution is also in [3].

For more points, the solution can be approximated by numerical methods such as the Weiszfeld's algorithm.

References:
[1] Shortest distance travel - common meeting point
[2] Algorithm to find point of minimum total distance from locations
[3] Geometric median

淘宝技术这十年，完整最终确认版

淘宝技术这十年，完整最终确认版

Good to read.