We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Gena Playing Hanoi
  2. Discussions

Gena Playing Hanoi

Sort by

recency

|

8 Discussions

|

  • vadym_usatiuk
     + 0 comments

    Java O(2 to the power of 2n)

    static private long base;
    static private int numOfRods;
    static private int INF;

    static private int[] fillRods(List<Integer> posts) {
        int[] res = new int[numOfRods];

        int n = posts.size();
        for (int i = 0; i < n; i++) {
            int rod = posts.get(i) - 1;
            int diskVal = (int) Math.pow(2, i);

            res[rod] += diskVal;
        }

        return res;
    }

    public static long findState(int[] rods) {
        long res = 0;

        for (int i = 0; i < numOfRods; i++) {
            res += (long) rods[i] * (long) Math.pow(base, numOfRods - i - 1);
        }

        return res;
    }

    public static int[] fromStateToRods(long state) {
        int[] res = new int[numOfRods];

        for (int i = 0; i < numOfRods; i++) {
            res[i] = (int) ((state / Math.pow(base, numOfRods - i - 1)) % base);
        }

        return res;
    }

    public static int[] findTopDisks(int[] curRods) {
        int[] res = new int[numOfRods];

        for (int i = 0; i < numOfRods; i++) {
            if (curRods[i] == 0) {
                res[i] = INF;
            } else {
                res[i] = curRods[i] ^ (curRods[i] & (curRods[i] - 1));
            }
        }

        return res;
    }

    public static int hanoi(List<Integer> posts) {
        int n = posts.size();

        numOfRods = 4;
        base = (long) Math.pow(2, n);
        INF = (int) Math.pow(2, n);

        int[] rods = fillRods(posts);

        long startState = findState(rods);
        long winState = (base - 1) * (long) Math.pow(base, numOfRods - 1);

        LinkedList<ArrayList<Long>> queue = new LinkedList<>();
        TreeMap<Long, ArrayList<Integer>> checked = new TreeMap<>();

        queue.add(new ArrayList<>(Arrays.asList(startState, 1L, 0L)));
        checked.put(startState, new ArrayList<>(Arrays.asList(1, 0)));

        queue.add(new ArrayList<>(Arrays.asList(winState, 2L, 0L)));
        checked.put(winState, new ArrayList<>(Arrays.asList(2, 0)));

        long state;
        long stateType;
        long stateMoves;
        long toAdd;
        long toSubtract;
        long newState;
        int[] curRods = new int[numOfRods];
        int[] topDisks = new int[numOfRods];
        ArrayList<Long> queueObject;

        while (!queue.isEmpty()) {
            queueObject = queue.pollFirst();

            state = queueObject.get(0);
            stateType = queueObject.get(1);
            stateMoves = queueObject.get(2);

            curRods = fromStateToRods(state);
            topDisks = findTopDisks(curRods);

            for (int i = 0; i < 4; i++) {
                for (int j = i + 1; j < 4; j++) {

                    if (topDisks[i] == INF && topDisks[j] == INF) {
                        continue;
                    }

                    if (topDisks[j] < topDisks[i]) {
                        toSubtract = (long) topDisks[j] * (long) Math.pow(base, numOfRods - j - 1);
                        toAdd = (long) topDisks[j] * (long) Math.pow(base, numOfRods - i - 1);
                    } else {
                        toSubtract = (long) topDisks[i] * (long) Math.pow(base, numOfRods - i - 1);
                        toAdd = (long) topDisks[i] * (long) Math.pow(base, numOfRods - j - 1);
                    }

                    newState = state - toSubtract + toAdd;
                    queueObject = new ArrayList<>(Arrays.asList(newState, stateType, stateMoves + 1));

                    if (checked.get(newState) == null) {
                        queue.add(queueObject);
                        checked.put(newState, new ArrayList<>(Arrays.asList((int) stateType, (int) stateMoves + 1)));
                    } else if (checked.get(newState).get(0) != stateType) {
                        return (int) stateMoves + 1 + checked.get(newState).get(1);
                    }
                }
            }
        }

        return -1;
    }

  • thangda
     + 0 comments

    JavaScript based on solution from @chuntao_liu_0118

    function hanoi(posts) {
    // Write your code here
    const n = posts.length;
    const rods = [0, 0, 0, 0];
    for (let i = 0; i < n; i++) {
        rods[posts[i] - 1] += 2 ** i;
    }
    const base = 2 ** n;
    const win_state = (base - 1) * (base ** 3);
    const start_state =
        rods[0] * (base ** 3) + rods[1] * (base ** 2) + rods[2] * base + rods[3];
    const visited = new Set();
    let current = [start_state];
    let moves = 0;

    while (current.length > 0) {
        const next = [];

        for (const state of current) {
            if (state === win_state) {
                return moves;
            }
            if (visited.has(state)) {
                continue;
            }
            visited.add(state);
            const rods = [
                Math.floor((state / (base ** 3)) % base),
                Math.floor((state / (base ** 2)) % base),
                Math.floor((state / base) % base),
                state % base
            ];
            const top_discs = rods.map(n =>
                n === 0 ? Infinity : n ^ (n & (n - 1))
            );

            for (let i = 0; i < 4; i++) {
                for (let j = i + 1; j < 4; j++) {
                    if (top_discs[i] === Infinity && top_discs[j] === Infinity) {
                        continue;
                    }
                    let new_state;
                    if (top_discs[i] < top_discs[j]) {
                        new_state =
                            state -
                            top_discs[i] * (base ** (3 - i)) +
                            top_discs[i] * (base ** (3 - j));
                    } else {
                        new_state =
                            state +
                            top_discs[j] * (base ** (3 - i)) -
                            top_discs[j] * (base ** (3 - j));
                    }
                    if (!visited.has(new_state)) {
                        next.push(new_state);
                    }
                }
            }
        }
        moves += 1;
        current = next;
    }
}

  • khiemnd9112
     + 0 comments

    Java8, based on @chuntao_liu_0118 states and Bidirectional BFS of @haiyuz226354. I don't know why but single directional BFS return tle in Java8...

    static private long base;
static private int numOfRods;
static private int INF;

static private int[] fillRods(List<Integer> posts) {
    int[] res = new int[numOfRods];

    int n = posts.size();
    for (int i = 0; i < n; i ++) {
        int rod = posts.get(i) - 1;
        int diskVal = (int) Math.pow(2, i);
                    
        res[rod] += diskVal;    
    }        
    
    return res;
}

public static long findState(int[] rods) {
    long res = 0;
    
    for (int i = 0; i < numOfRods; i++) {
        res += (long) rods[i] * (long) Math.pow(base, numOfRods - i - 1);
    }
    
    return res;
}

public static int[] fromStateToRods(long state) {
    int[] res = new int[numOfRods];
    
    for (int i = 0; i < numOfRods; i ++) {
        res[i] = (int) ((state / Math.pow(base, numOfRods - i - 1)) % base);
    }
    
    return res;
}

public static int[] findTopDisks(int[] curRods) {
    int[] res = new int[numOfRods];
    
    for (int i = 0; i < numOfRods; i++) {
        if (curRods[i] == 0) {
            res[i] = INF;
        }
        else {
            res[i] = curRods[i] ^ (curRods[i] & (curRods[i] - 1));
        }
    }
    
    return res;
}
    
public static int hanoi(List<Integer> posts) { 

    int n = posts.size();
    
    numOfRods = 4;
    base = (long) Math.pow(2, n);
    INF = (int) Math.pow(2, n);
    
    int[] rods = fillRods(posts);
    
    long startState = findState(rods);

//win when disks align at rod 1...
//base - 1 == 2 ** n - 1 : sum of all bits when translated to decimal

    long winState = (base - 1) * (long) Math.pow(base, numOfRods - 1);
    
    LinkedList<ArrayList<Long>> queue = new LinkedList<>();
    TreeMap<Long, ArrayList<Integer>> checked = new TreeMap<>();

//queuing simple wrappers that carry 
//state, 
//type (1, 2 as from start, from end),
//respective moves

//instead of set, using map to store above information

    queue.add(new ArrayList<Long>(Arrays.asList(startState, 1L, 0L)));
    checked.put(startState, new ArrayList<Integer>(Arrays.asList(1, 0)));
    
    queue.add(new ArrayList<Long>(Arrays.asList(winState, 2L, 0L)));
    checked.put(winState, new ArrayList<Integer>(Arrays.asList(2, 0)));

    long state;
    long stateType;
    long stateMoves;
    long toAdd;
    long toSubtract;
    long newState;
    int[] curRods = new int[numOfRods];
    int[] topDisks = new int[numOfRods];
    ArrayList<Long> queueObject;
    
    while (!queue.isEmpty()) {
        
        queueObject = queue.pollFirst();
        
        state = queueObject.get(0);
        stateType = queueObject.get(1);
        stateMoves = queueObject.get(2);

        curRods = fromStateToRods(state);
        topDisks = findTopDisks(curRods);
    
        for (int i = 0; i < 4; i ++) {
            for (int j = i + 1; j < 4; j ++) {
                
                if (topDisks[i] == INF && topDisks[j] == INF) {
                    continue;
                }
                
                if (topDisks[j] < topDisks[i]) {
                    toSubtract = (long) topDisks[j] * (long) Math.pow(base, numOfRods - j - 1);
                    toAdd = (long) topDisks[j] * (long) Math.pow(base, numOfRods - i - 1);
                }
                else {
                    toSubtract = (long) topDisks[i] * (long) Math.pow(base, numOfRods - i - 1);
                    toAdd = (long) topDisks[i] * (long) Math.pow(base, numOfRods - j - 1);
                }
                
                newState = state - toSubtract + toAdd;      
                queueObject = new ArrayList<Long>(Arrays
                                    .asList(newState, stateType, stateMoves + 1));   
                
                if (checked.get(newState) == null) {
                    queue.add(queueObject);
                    checked.put(newState, new ArrayList<Integer>(Arrays
                                    .asList((int) stateType, (int) stateMoves + 1)));
                }

//if states overlap, we found the middle point
//then adding 2 move numbers should give us the total moves

                else if (checked.get(newState).get(0) != stateType) {
                    return (int) stateMoves + 1 + checked.get(newState).get(1);
                }
            }
        }
    }
    
    return -1;
}

  • callison_adam
     + 0 comments

    Python 3, based on solution from @chuntao_liu_0118 in these comments. Splits up the logic a bit into a few functions with the intention to be slightly more readable. Also should work for arbitrarily many posts.

    def hanoi_posts_to_int(nstacks, posts):
    ndisks = len(posts)
    base = 2**ndisks
    res = 0
    for j, post in enumerate(posts):
        res += (2**j)*(base**(nstacks-post))
    return res

def hanoi_neighbours(state, nstacks, ndisks):
    base = 2**ndisks
    nums = [(state // (base**j)) % base for j in range(nstacks-1, -1, -1)]
    top_nums = [2**ndisks if num == 0 else (num&~(num-1)) for num in nums]
    
    for j, tnj in enumerate(top_nums):
        for k, tnk in enumerate(top_nums):
            if (j == k) or (tnj >= tnk): continue
            neighbour = state - ((tnj)*(base**((nstacks-1)-j))) + ((tnj)*(base**((nstacks-1)-k)))
            yield neighbour
    
def hanoi_general(nstacks, posts):
    ndisks = len(posts)
    source = hanoi_posts_to_int(nstacks, posts)
    base = 2**ndisks
    target = ((2**ndisks)-1)*(base**(nstacks-1))
    to_explore = [source]
    explored = set([source])
    parent = {}
    while to_explore:
        to_explore_next = []
        for v in to_explore:
            for w in hanoi_neighbours(v, nstacks, ndisks):
                if w in explored: continue
                explored.add(w)
                parent[w] = v
                if w == target: break
                to_explore_next.append(w)
        to_explore = to_explore_next

    curr = target
    moves = 0
    while curr in parent:
        moves += 1
        curr = parent[curr]
    return moves

def hanoi(posts):
    return hanoi_general(4, posts)

  • minhnghia_pham_1
     + 0 comments

    https://www.hackerrank.com/challenges/gena/forum all solution