Skip to content

Instantly share code, notes, and snippets.

@rayjcwu
Created February 26, 2014 01:06
Show Gist options
  • Select an option

  • Save rayjcwu/9221420 to your computer and use it in GitHub Desktop.

Select an option

Save rayjcwu/9221420 to your computer and use it in GitHub Desktop.
import java.util.Scanner;
public class HoneyComb {
public static void main(String []argv) throws Exception {
HoneyComb hc = new HoneyComb();
hc.enter();
}
public void enter() {
Scanner scanner = new Scanner(System.in);
final long A = scanner.nextLong();
final long B = scanner.nextLong();
Coord a = toCoord(A);
Coord b = toCoord(B);
System.out.println(dist(a, b));
}
// number of accumulate elements till x-th wrap
private long accu(long x) {
return 1 + 3 * (x + 1) * x;
}
private long initX(long N) {
long x = 0;
while (accu(x + 1) < N) {
x++;
}
return x;
}
// (x, y) movement in six different area
final int []xMove = {-1, -1, 0, 1, 1, 0};
final int []yMove = {-1, 0, 1, 1, 0, -1};
private Coord toCoord(long N) {
if (N == 1) {
return new Coord(0, 0);
} else {
long x = initX(N);
long y = 0;
long left = N - accu(x);
if (left == 0) {
return new Coord(x, y);
}
// move around hex
x++;
final long step = x;
int area = 0;
while (left > 0) {
if (left <= step) {
x += left * xMove[area];
y += left * yMove[area];
break;
} else {
left -= step;
x += step * xMove[area];
y += step * yMove[area];
area++;
}
}
return new Coord(x, y);
}
}
private long dist(Coord a, Coord b) {
// move along (1, 0), (0, 1), (1, 1) axis
// dist 1 is moving along (1, 0) and (0, 1)
final long d1 = Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
// dist 2 is moving along (1, 1) and (1, 0)
// first move a.y to b.y along (1, 1), calculate new x
long dir = b.y - a.y;
long tx = a.x + dir;
// then move a.x to b.x along (1, 0)
final long d2 = Math.abs(dir) + Math.abs(tx - b.x);
// dist 3 is moving along (1, 1) and (0, 1)
// first move a.x to b.x along (1, 1), calculate new y
dir = b.x - a.x;
long ty = a.y + dir;
// then move a.y to b.y along (0, 1)
final long d3 = Math.abs(dir) + Math.abs(ty - b.y);
return Math.min(Math.min(d1, d2), d3);
}
}
class Coord {
long x;
long y;
public Coord(long x, long y) {
this.x = x;
this.y = y;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment