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.
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...
staticprivatelongbase;staticprivateintnumOfRods;staticprivateintINF;staticprivateint[]fillRods(List<Integer>posts){int[]res=newint[numOfRods];intn=posts.size();for(inti=0;i<n;i++){introd=posts.get(i)-1;intdiskVal=(int)Math.pow(2,i);res[rod]+=diskVal;}returnres;}publicstaticlongfindState(int[]rods){longres=0;for(inti=0;i<numOfRods;i++){res+=(long)rods[i]*(long)Math.pow(base,numOfRods-i-1);}returnres;}publicstaticint[]fromStateToRods(longstate){int[]res=newint[numOfRods];for(inti=0;i<numOfRods;i++){res[i]=(int)((state/Math.pow(base,numOfRods-i-1))%base);}returnres;}publicstaticint[]findTopDisks(int[]curRods){int[]res=newint[numOfRods];for(inti=0;i<numOfRods;i++){if(curRods[i]==0){res[i]=INF;}else{res[i]=curRods[i]^(curRods[i]&(curRods[i]-1));}}returnres;}publicstaticinthanoi(List<Integer>posts){intn=posts.size();numOfRods=4;base=(long)Math.pow(2,n);INF=(int)Math.pow(2,n);int[]rods=fillRods(posts);longstartState=findState(rods);//win when disks align at rod 1...//base - 1 == 2 ** n - 1 : sum of all bits when translated to decimallongwinState=(base-1)*(long)Math.pow(base,numOfRods-1);LinkedList<ArrayList<Long>>queue=newLinkedList<>();TreeMap<Long,ArrayList<Integer>>checked=newTreeMap<>();//queuing simple wrappers that carry //state, //type (1, 2 as from start, from end),//respective moves//instead of set, using map to store above informationqueue.add(newArrayList<Long>(Arrays.asList(startState,1L,0L)));checked.put(startState,newArrayList<Integer>(Arrays.asList(1,0)));queue.add(newArrayList<Long>(Arrays.asList(winState,2L,0L)));checked.put(winState,newArrayList<Integer>(Arrays.asList(2,0)));longstate;longstateType;longstateMoves;longtoAdd;longtoSubtract;longnewState;int[]curRods=newint[numOfRods];int[]topDisks=newint[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(inti=0;i<4;i++){for(intj=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=newArrayList<Long>(Arrays.asList(newState,stateType,stateMoves+1));if(checked.get(newState)==null){queue.add(queueObject);checked.put(newState,newArrayList<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 moveselseif(checked.get(newState).get(0)!=stateType){return(int)stateMoves+1+checked.get(newState).get(1);}}}}return-1;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
An unexpected error occurred. Please try reloading the page. If problem persists, please contact support@hackerrank.com
Gena Playing Hanoi
You are viewing a single comment's thread. Return to all 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...