Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
a java solution to the "honeycomb" puzzle
package org.b7j0c.puzzles;
import java.util.EnumMap;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
// the Hex class represents an id with six neighbors. the orientation of the neighbors is irrelevant
// but it is useful to describe them with compass directions as such:
//
// N
// ___
// NW / \ NE
// SW \___/ SE
//
// S
//
final class Hex {
public enum LABEL {
// the compass direction labels
N,NE,SE,S,SW,NW;
// these are static, we can cache them
public static final LABEL values[] = values();
public String toString(LABEL l) {
switch(l) {
case N: return "N";
case NE: return "NE";
case SE: return "SE";
case S: return "S";
case SW: return "SW";
default: return "NW";
}
}
// next clockwise label
public static LABEL next_cw(LABEL l) {
switch(l) {
case N: return NE;
case NE: return SE;
case SE: return S;
case S: return SW;
case SW: return NW;
default: return N; // l == NW
}
}
// next counterclockwise label
public static LABEL next_ccw(LABEL l) {
switch(l) {
case N: return NW;
case NE: return N;
case SE: return NE;
case S: return SE;
case SW: return S;
default: return SW; // l == NW
}
}
// the "opposite" label is defined as the label of the edge on a joined hex.
// if hex 1 joins to hex 2 on its N label, then 2 joins to 1 on its S label
public static LABEL opposite(LABEL l){
switch(l) {
case N: return S;
case NE: return SW;
case SE: return NW;
case S: return N;
case SW: return NE;
default: return SE; // l == NW
}
}
};
static final Integer EMPTY = null;
public EnumMap<LABEL,Integer> edges;
// a hex starts off with no neighbors, all labels empty
public Hex() {
edges = new EnumMap<LABEL,Integer>(LABEL.class);
edges.put(LABEL.N, EMPTY);
edges.put(LABEL.NE,EMPTY);
edges.put(LABEL.SE,EMPTY);
edges.put(LABEL.S, EMPTY);
edges.put(LABEL.SW,EMPTY);
edges.put(LABEL.NW,EMPTY);
}
public boolean empty() {
for (LABEL l: LABEL.values) {
if (EMPTY != this.edges.get(l)) return false;
}
return true;
}
public boolean full() {
for (LABEL l: LABEL.values) {
if (EMPTY == this.edges.get(l)) return false;
}
return true;
}
// select the next clockwise edge that is empty, but itself has a clockwise neighbor
// edge that is not empty.
public LABEL next_cw_join_edge() throws RuntimeException {
if (this.empty() || this.full()) {
throw new IllegalArgumentException("hex cannot meet criteria");
}
for (LABEL l: LABEL.values) {
if ((this.edges.get(l) == EMPTY) && (this.edges.get(Hex.LABEL.next_cw(l)) != EMPTY)) {
return l;
}
}
throw new IllegalArgumentException("hex has no appropriate edge");
}
public String toString() {
StringBuffer s = new StringBuffer();
for (LABEL l: LABEL.values) {
s.append(l + ":" + this.edges.get(l) + " ");
}
return s.toString();
}
}
public class Honeycomb {
// generate the clockwise-spiral of hexagons as described in the problem
public static void place_hexes(Map<Integer,Hex> m,
Integer curr_id,
int lim) throws RuntimeException {
while (curr_id < lim) {
Hex curr_hex = m.get(curr_id);
if (curr_hex == null) {
throw new IllegalArgumentException("cannot find hex for " + curr_id);
}
// assume for the examples below that 2 is the curr_hex and 3 will be the new_hex
Integer new_id = curr_id + 1;
Hex new_hex = new Hex();
// Start at edge N to find a suitable join edge on curr_hex. try to find the next suitable
// join edge in a clockwise traversal from edge N . What qualifies as a selection is the
// clockwise-most edge that is empty, but its clockwise neighbor is not
//
// \_1_/
// -> / 2 \
// \___/
//
// in the case of 2, that is the NW edge, since the N edge is not empty, it joins to hex 1.
Hex.LABEL curr_next_cw_join_edge = Hex.LABEL.N;
try {
curr_next_cw_join_edge = curr_hex.next_cw_join_edge();
} catch (Exception e) {
throw e;
}
// now associate this edge with the new id:
//
// __/ 1 \
// 3 \___/
// __ / 2 \
// \___/
//
// so 2.NW = 3 (joining at 3.SE)
curr_hex.edges.put(curr_next_cw_join_edge,new_id);
// The edge on the new_hex that joins to this will be the opposite
Hex.LABEL new_join_edge = Hex.LABEL.opposite(curr_next_cw_join_edge);
// in our example, 3.SE = 2 (2.NW) as described above
new_hex.edges.put(new_join_edge,curr_id);
// now get the next clockwise edge for curr_next_cw_join_edge, which is 2.N
Hex.LABEL curr_cw_adjacent_edge = Hex.LABEL.next_cw(curr_next_cw_join_edge);
// now get the id for the hex on the cw adjacent edge (should not be empty).
// in our example, this is 1 (resolved at 2.N)
Integer curr_cw_adjacent_id = curr_hex.edges.get(curr_cw_adjacent_edge);
if (curr_cw_adjacent_id == null) {
throw new IllegalArgumentException("no hex id found where should be next " +
"cw adjacent for " + curr_id);
}
Hex curr_cw_adjacent_hex = m.get(curr_cw_adjacent_id);
if (curr_cw_adjacent_hex == null) {
throw new IllegalArgumentException("no hex found where should be next " +
"cw adjacent:" + curr_cw_adjacent_id);
}
// now get the ccw adajcent edge for the join edge (SE) for 3 -> 3.NE
Hex.LABEL new_ccw_adjacent_edge = Hex.LABEL.next_ccw(new_join_edge);
// and join 3.NE -> 1 in our example
new_hex.edges.put(new_ccw_adjacent_edge,curr_cw_adjacent_id);
// the opposite edge on 1 being 1.SW, which we join to 3
Hex.LABEL curr_cw_adjacent_join_edge = Hex.LABEL.opposite(new_ccw_adjacent_edge);
curr_cw_adjacent_hex.edges.put(curr_cw_adjacent_join_edge,new_id);
// and what if the next cw adjacent hex had a hex on the cw edge following the
// one it joined with nex_hex? for example, if 1 had a hex 4 on the next cw edge
// with which it joined with 3
// ___
// / 4 \___/
// \___/ 1 \__
// / 3 \___/
// \__ / 2 \__
// \___/
//
// which would happen if 3 "closed the loop". 3 would have to have it its next ccw edge (N)
// join to 4, which we will call the loop_closer, as it means 1 has all edges now joined
// recall the curr_hex is 2, so the curr_cw_adjacent_hex is 1, and 1's next_cw edge is NW
Hex.LABEL curr_cw_adjacent_hex_next_cw = Hex.LABEL.next_cw(curr_cw_adjacent_join_edge);
Integer loop_closer_id = curr_cw_adjacent_hex.edges.get(curr_cw_adjacent_hex_next_cw);
if (loop_closer_id != null) {
Hex loop_closer_hex = m.get(loop_closer_id);
if (loop_closer_hex == null) {
throw new IllegalArgumentException("no hex found where should be loop closer "
+ loop_closer_id);
}
Hex.LABEL new_ccw_loop_close_edge = Hex.LABEL.next_ccw(new_ccw_adjacent_edge);
Hex.LABEL loop_closer_opposite_edge = Hex.LABEL.opposite(new_ccw_loop_close_edge);
loop_closer_hex.edges.put(loop_closer_opposite_edge,new_id);
new_hex.edges.put(new_ccw_loop_close_edge,loop_closer_id);
m.put(loop_closer_id,loop_closer_hex);
}
// put the updated hex structs back in the map
m.put(curr_id,curr_hex);
m.put(new_id,new_hex);
m.put(curr_cw_adjacent_id,curr_cw_adjacent_hex);
curr_id = new_id;
}
}
// breadth first search starting from start and looking for needle
public static Integer bfs(Map<Integer,Hex> m,Integer start,Integer needle) throws RuntimeException {
if (start == needle) return 0;
List<Integer> curr = new ArrayList<Integer>();
List<Integer> next = new ArrayList<Integer>();
Map<Integer,Integer> seen = new HashMap<Integer,Integer>();
curr.add(start);
Integer dist = 0;
seen.put(start,dist);
dist++;
while (!curr.isEmpty()) {
for (Integer c : curr) {
Hex h = m.get(c);
if (h == null) {
throw new IllegalArgumentException("cannot find hex for " + c);
}
for (Hex.LABEL l : h.edges.keySet()) {
Integer join_id = h.edges.get(l);
if (join_id != Hex.EMPTY) {
if (join_id == needle) return dist;
Integer n = seen.get(join_id);
if (n == null) {
next.add(join_id);
seen.put(join_id,dist);
}
}
}
}
curr = new ArrayList<Integer>(next);
next.clear();
dist++;
}
return null;
}
public static void main(String[] args) throws RuntimeException {
Map<Integer,Hex> m = new HashMap<Integer,Hex>();
Hex hex_one = new Hex();
Hex hex_two = new Hex();
hex_one.edges.put(Hex.LABEL.S,2);
hex_two.edges.put(Hex.LABEL.N,1);
m.put(1,hex_one);
m.put(2,hex_two);
try {
place_hexes(m,2,70);
} catch (Exception e) {
System.err.println("err from place_hexes:" + e.getMessage());
}
// to print out the hex pattern
// for (Integer i: m.keySet()) {
// System.out.println(i);
// Hex h = m.get(i);
// System.out.println(h);
// }
Integer d = bfs(m,55,68);
System.out.println(d);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.