a java solution to the "honeycomb" puzzle

honeycomb.java

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);
    }
}