HackerRank Gena Playing Hanoi Problem Solution

In this post, we will solve HackerRank Gena Playing Hanoi Problem Solution.

The Tower of Hanoi is a famous game consisting of 3 rods and a number of discs of incrementally different diameters. The puzzle starts with the discs neatly stacked on one rod, ordered by ascending size with the smallest disc at the top. The game’s objective is to move the entire stack to another rod, obeying the following rules:

Only one disk can be moved at a time.
In one move, remove the topmost disk from one rod and move it to another rod.
No disk may be placed on top of a smaller disk.
Gena has a modified version of the Tower of Hanoi. This game of Hanoi has 4 rods and n disks ordered by ascending size. Gena has already made a few moves following the rules above. Given the state of Gena’s Hanoi, determine the minimum number of moves needed to restore the tower to its original state with all disks on rod 1.
Note: Gena’s rods are numbered from 1 to 4. The radius of a disk is its index in the input array, so disk 1 is the smallest disk with a radius of 1, and disk n is the largest with a radius of n.

Example
posts = [4, 3, 2, 1]
In this case, the disks are arranged from large to small across the four rods. The largest disk, disk 4, is already on rod 1, so move disks 3,2 and 1 to rod 1, in that order. It takes 3 moves to reset the game.
posts = [4, 2, 2, 1]
The largest disk, disk 4 with radius 4, is already on rod 1. Disk 3 is on rod 2 and must be below disk 2. Move disk 2 to rod 3, disk 3 to rod 1 and disk 2 to rod 1. Now move disk 1 to rod 1. It takes 3 moves to reset the game.
Function Description
Complete the hanoi function below.
hanoi has the following parameters:

int posts[n]: posts[i] is the location of the disk with radius i
Returns
int: the minimum moves to reset the game to its initial state

Input Format
The first line contains a single integer, n, the number of disks.
The second line contains ŉ space-separated integers, where the ¿th integer is the index of the rod where the disk with diameter i is located.

Sample Input

STDIN   Function
-----   --------
3       size of posts[] n = 3
1 4 1   posts = [1, 4, 1]

Sample Output

Explanation

3 moves are enough to build the tower.

HackerRank Gena Playing Hanoi Problem Solution

Gena Playing Hanoi C Solution

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

typedef struct _QueueElement {
    int move;
    int state;
} QueueElement;


int N;


#define QUEUE_SIZE (1024*1024*16)
QueueElement queue[QUEUE_SIZE];
char enqueued[QUEUE_SIZE];
int queueCount = 0;
int queueStart = 0;

int emptyQueue()
{
    return (queueCount == 0);
}


void pushQueue(int move, int state)
{
    int index = queueStart + queueCount;
    if (index >= QUEUE_SIZE) {
        index -= QUEUE_SIZE;
    }
    if (enqueued[state] != move) {
        queue[index].move  = move;
        queue[index].state = state;
        enqueued[state] = move;
        queueCount += 1;
    }
}


int popQueue(int *move)
{
    int res = queue[queueStart].state;
    *move = queue[queueStart].move;
    queueStart += 1;
    if (queueStart >= QUEUE_SIZE) {
        queueStart -= QUEUE_SIZE;
    }
    queueCount -= 1;
    return res;
}


void genMoves(int state, int *moves, int *movesCount)
{
    int rod;
    int i = 0;
    int r[4] = { -1, -1, -1, -1 };
    int tmp = state;
    while (tmp) {
        rod = tmp & 0x3;
        if (r[rod] < 0) {
            r[rod] = i;
        }
        tmp >>= 2;
        i += 1;
    }
    *movesCount = 0;
    if (r[0] >= 0) {
        if (r[0] < r[1] || r[1] < 0) {
            moves[*movesCount] = state | (1 << (r[0] * 2));
            *movesCount += 1;
        }
        if (r[0] < r[2] || r[2] < 0) {
            moves[*movesCount] = state | (2 << (r[0] * 2));
            *movesCount += 1;
        }
        if (r[0] < r[3] || r[3] < 0) {
            moves[*movesCount] = state | (3 << (r[0] * 2));
            *movesCount += 1;
        }
    }
    if (r[1] >= 0) {
        if (r[1] < r[0] || r[0] < 0) {
            moves[*movesCount] = state & (~(1 << (r[1] * 2)));
            *movesCount += 1;
        }
        if (r[1] < r[2] || r[2] < 0) {
            moves[*movesCount] = state & (~(1 << (r[1] * 2)));
            moves[*movesCount] |= (2 << (r[1] * 2));
            *movesCount += 1;
        }
        if (r[1] < r[3] || r[3] < 0) {
            moves[*movesCount] = state | (3 << (r[1] * 2));
            *movesCount += 1;
        }
    }
    if (r[2] >= 0) {
        if (r[2] < r[0] || r[0] < 0) {
            moves[*movesCount] = state & (~(2 << (r[2] * 2)));
            *movesCount += 1;
        }
        if (r[2] < r[1] || r[1] < 0) {
            moves[*movesCount] = state & (~(2 << (r[2] * 2)));
            moves[*movesCount] |= (1 << (r[2] * 2));
            *movesCount += 1;
        }
        if (r[2] < r[3] || r[3] < 0) {
            moves[*movesCount] = state | (3 << (r[2] * 2));
            *movesCount += 1;
        }
    }
    if (r[3] >= 0) {
        if (r[3] < r[0] || r[0] < 0) {
            moves[*movesCount] = state & (~(3 << (r[3] * 2)));
            *movesCount += 1;
        }
        if (r[3] < r[1] || r[1] < 0) {
            moves[*movesCount] = state & (~(3 << (r[3] * 2)));
            moves[*movesCount] |= (1 << (r[3] * 2));
            *movesCount += 1;
        }
        if (r[3] < r[2] || r[2] < 0) {
            moves[*movesCount] = state & (~(3 << (r[3] * 2)));
            moves[*movesCount] |= (2 << (r[3] * 2));
            *movesCount += 1;
        }
    }
}


int main()
{
    int i;
    for (i = 0; i < QUEUE_SIZE; ++i) {
        enqueued[i] = -1;
    }
    scanf("%d", &N);
    {
        int state = 0;
        int tmp;
        for (i = 0; i < N; ++i) {
            scanf("%d", &tmp);
            state |= (tmp - 1) << (i * 2);
        }
        pushQueue(0, state);
    }

    {
        int state;
        int move;
        int moves[6];
        int movesCount;

        while (! emptyQueue()) {
            state = popQueue(&move);
            if (! state) {
                break;
            }

            genMoves(state, moves, &movesCount);
            for (i = 0; i < movesCount; ++i) {
                pushQueue(move + 1, moves[i]);
            }
        }

        printf("%d\n", move);
    }

    return 0;
}

Gena Playing Hanoi C++ Solution

#include <cstdio>
#include <queue>
#include <algorithm>

const int MAXN = 10;
const int MAXS = 2e6;

class TState {
public:
    int a[MAXN], p = 0;
    int& operator[] (int idx) {return a[idx];}
};

int n;
bool kt[MAXS];
TState s;

inline int Encode(TState s)
{
    int code = 0;
    for (int i = 0; i < n; ++i) code = code * 4 + s[i];
    return code;
}
int GetBit(int num, int v) {return (num >> v) & 1;}
void SetBit(int &num, int v) {num |= 1 << v;}
int Bfs()
{
    std::queue<TState> q;
    q.push(s);
    kt[Encode(s)] = true;
    while (!q.empty())
    {
        TState u = q.front();
        q.pop();
        int kt1 = 0;
        for (int i = 0; i < n; ++i)
            if (!GetBit(kt1,u[i]))
            {
                SetBit(kt1,u[i]);
                int kt2 = kt1;
                for (int j = 0; j < 4; ++j)
                    if (!GetBit(kt2,j))
                    {
                        SetBit(kt2,j);
                        TState v = u; ++v.p;
                        v[i] = j;
                        int c = Encode(v);
                        if (kt[c]) continue;
                        if (c == 0) return v.p;
                        q.push(v);
                        kt[c] = true;
                    }
            }
    }
    return 0;
}

int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; ++i)
    {
        int x;
        scanf("%d",&x);
        s[i] = x-1;
    }
    printf("%d",Bfs());
    return 0;
}

Gena Playing Hanoi C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Solution {
    static void Main(string[] args)
    {
        int N = Convert.ToInt32(Console.ReadLine());

        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), aTemp => Convert.ToInt32(aTemp));

        int nValue = 0;
        for (int i = a.Length - 1; i >= 0; i--)
        {
            int nPole = a[i] - 1;
            nValue = nValue | nPole << (i * 2);
        }

        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        if (nValue == 0)
        {
            textWriter.WriteLine(0);
            textWriter.Flush();
            textWriter.Close();
            return;
        }

        int nTime = 0;

        List<int> aAPole = new List<int>();
        List<int> aAPole2 = new List<int>();
        aAPole.Add(nValue);

        Dictionary<int, bool> oValueTable = new Dictionary<int, bool>();

        bool bBreak = false;
        while (aAPole.Count > 0)
        {
            nTime++;
            aAPole2.Clear();
            foreach (int aPole2 in aAPole)
            {
                nValue = aPole2;
                int[] aTop = new int[4];
                int nVolume = 0;
                for (int i = 0; i < N; i++)
                {
                    int nIndex = (aPole2 >> (i * 2)) & 3;
                    int nPlate = aTop[nIndex] - 1;
                    if (nPlate == -1)
                    {
                        nVolume++;
                        aTop[nIndex] = i + 1;
                        if (nVolume == 4)
                        {
                            break;
                        }
                    }
                }

                for (int i = 0; i < 4; i++)
                {
                    int nPlate = aTop[i] - 1;
                    if (nPlate == -1)
                    {
                        continue;
                    }
                    for (int j = 0; j < 4; j++)
                    {
                        int nPlate2 = aTop[j] - 1;
                        if (nPlate2 == -1 || nPlate < nPlate2)
                        {
                            int nValue2 = nValue & (~(3 << (nPlate * 2)));
                            nValue2 = nValue2 | (j << (nPlate * 2));
                            if (nValue2 == 0)
                            {
                                bBreak = true;
                                break;
                            }
                            if (!oValueTable.ContainsKey(nValue2))
                            {
                                oValueTable[nValue2] = true;
                                aAPole2.Add(nValue2);
                            }
                        }
                    }

                    if (bBreak)
                    {
                        break;
                    }
                }
                if (bBreak)
                {
                    break;
                }
            }
            if (bBreak)
            {
                break;
            }
            List<int> aAPole4 = aAPole;
            aAPole = aAPole2;
            aAPole2 = aAPole4;
        }

        textWriter.WriteLine(nTime);
        textWriter.Flush();
        textWriter.Close();
    }
}

Gena Playing Hanoi Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {



    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        int ndisc = scan.nextInt();
        int start = 0;
        for (int h = 1; h <= ndisc; ++h) {
            int rod = scan.nextInt();
            --rod;
            start = move(start, rod, h);

        }
        scan.close();
       
        System.out.print(solve(ndisc, start));
    }

    private static int move(int state, int rod, int disc) {
        return (state & ~(3 << 2 * (disc - 1))) | rod << 2 * (disc - 1);
    }

    private static int getDisc(int ndisc, int state, int rod) {

        int disc = ndisc + 1;
        for (int h = ndisc; h != 0; --h) {
            int r = 3 & state >> 2 * (h - 1);
            if (r == rod) {
                disc = h;
            }
        }
        return disc;
    }

    private static long solve(int ndisc, int start) {
        final int win = 0;
        if (start == win) {
            return 0;
        }
        LinkedList<Integer> bfs = new LinkedList<>();
        bfs.addLast(start);
        List<Integer> depth = Arrays.asList(new Integer[1 << 2 * ndisc]);
        depth.set(start, 0);
        while (true) {
            int par = bfs.getFirst();
            bfs.removeFirst();
            int[] d = new int[4];
            for (int rod = 0; rod < 4; ++rod) {
                d[rod] = getDisc(ndisc, par, rod);
            }
            for (int from = 0; from < 4; ++from) {
                if (d[from] == ndisc + 1) {
                    continue;
                }
                for (int to = 0; to < 4; ++to) {
                    if (d[to] > d[from]) {
                        int ch = move(par, to, d[from]);
                        if (ch == win) {
                            return 1 + depth.get(par);
                        }
                        if (depth.get(ch) == null && ch != start) {
                            depth.set(ch, 1 + depth.get(par));
                                                  
                            bfs.addLast(ch);
                        }
                    }
                }
            }
        }

    }
}

Gena Playing Hanoi JavaScript Solution

'use strict';

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

function solveProblem(a, n) {
    let b = [];
    function initialize() {
        for (var i = 0; i < n; i++) {
            a[i]--;
        }
        for (i = 0; i < Math.pow(4, n); i++) {
            b[i] = -1;
        }
    }

    function convertStateToNumber(arr) {
        let value = 0;
        for (var i = 0; i < n; i++) {
            value = value | (arr[i] << (2 * i));
        }
        return value;
    }

    function convertNumberToState(num) {
        let arr2 = [];
        for (var i = 0; i < n; i++) {
            arr2[i] = num & 3;
            num = num >> 2;
        }
        return arr2;
    }

    function getTopDiskInRod(tempArr) {
        let top2 = [];
        for (let j = 0; j < 4; j++) {
            top2[j] = n;
        }
        for (let j = n - 1; j >= 0; j--) {
            top2[tempArr[j]] = j;
        }
        return top2;
    }

    function findSolution() {
        let num = convertStateToNumber(a);
        let queue = [num];
        let arr;
        b[num] = 0;
        let count = 1, idx = 0;
        while (idx < count) {
            num = queue[idx];
            idx++;
            if (num == 0) return b[num];
            arr = convertNumberToState(num);
            let top = getTopDiskInRod(arr);
            for (var i = 0; i < 4; i++) {
                if (top[i] < n) {
                    for (var j = 0; j < 4; j++) {
                        if (top[i] < top[j]) {
                            let newArr = arr.slice();
                            newArr[top[i]] = j;
                            let newNum = convertStateToNumber(newArr);
                            if (b[newNum] == -1) {
                                queue[count] = newNum;
                                count++;
                                b[newNum] = b[num] + 1;
                            }
                        }
                    }
                }
            }
        }
    }
    initialize();
    return (findSolution());
}

function main() {
    const N = parseInt(readLine(), 10);
    const a = readLine().split(' ').map(aTemp => parseInt(aTemp, 10));
    console.log(solveProblem(a, N));
}

Gena Playing Hanoi Python Solution

from collections import deque


def legal_moves(x):
    for i in range(len(x)):
        if x[i]:
            for j in range(len(x)):
                if not x[j] or x[i][-1] < x[j][-1]:
                    yield (i, j)


def is_goal(x):
    return all([len(x[i]) == 0 for i in range(1, len(x))])


def bfs(x):
    def tuplify(z):
        return tuple(tuple(t) for t in z)

    def do_move(g, m):
        y = [list(t) for t in g]
        y[m[1]].append(y[m[0]].pop())
        # WLOG sort 2nd-4th stacks by order of largest disk
        y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)  
        return tuplify(y)

    visited = set()

    start = (tuplify(x), 0)

    q = deque([start])
    visited.add(start)

    while q:
        node, depth = q.popleft()

        if is_goal(node):
            return depth

        for move in legal_moves(node):
            child = do_move(node, move)
            if child not in visited:
                visited.add(child)
                q.append((child, depth+1))

# load the representation from stdin
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
    A[R[i]-1] = [(i+1)] + A[R[i]-1]

print(bfs(A))

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python