Get my external IP address on linux

lynx --dump http://ipecho.net/plain

See this link for more details.

Javascript big int operation

Javascript int are actually float. When '&' bit-wise AND is used, the value is converted to integer and operated on. It's 32 bits only, and is signed by default. So for big int longer than this, there is no way to do bit-wise AND.

Here is a solution: first convert the input integer string (a string, not a int) into binary format, then do a bit by bit comparison. Code is below.

function BIGINT_AND(a, b) {
  a = toBinary(a);
  b = toBinary(b);

  for (var i = a.length - 1, j = b.length - 1; i >= 0 && j >= 0; -- i, -- j) {
    if (a[i] == 1 && b[j] == 1) return 1;
  }

  return 0;
}

// convert from decimal format to binary format
function toBinary(decNum){
    return parseInt(decNum,10).toString(2);
}

Java web development review

Just want to review some basic java web development technologies, such as JSP, JSTL and servlets.

Online search on topic "JSP Tutorial" 

Below tutorials are listed in the order of from simple to more complex:

JSP Tutorial - very very basic tutorial
Tutorials Point: Basic JSP Tutorial - a little more detailed
Servlet
 
Building Web Apps in Java: Beginning & Intermediate Servlet & JSP Tutorials
The Java EE 5 tutorial

WYSIWYG web editor

http://ueditor.baidu.com/website/

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.