Solución:
Java: solución óptima (1080544 movimientos)
Esta solución crea un árbol de ruta más corto desde el objetivo y hacia atrás, luego atraviesa la ruta desde el estado inicial hasta el objetivo. Mucho espacio para mejorar la velocidad, pero aún resuelve todos los 55986 problemas en aproximadamente un minuto.
Suponiendo que el algoritmo se implemente correctamente, esta debería ser la mejor solución teóricamente.
import java.util.*;
public class HanoiSort
public static void main(String[] args)
int sumNumMoves = 0;
for (int size = 1; size <= 6; ++size)
Collection> initMainStacks = generateInitMainStacks(Collections.emptyList(), size);
for (List initMainStack : initMainStacks)
sumNumMoves += solve(initMainStack);
System.out.println(sumNumMoves);
/*
* Recursively create initial main stacks
*/
private static Collection> generateInitMainStacks(List mainStack, int remainingSize)
Collection> initMainStacks;
if (remainingSize > 0)
initMainStacks = new ArrayList<>();
for (int number = 1; number <= 6; ++number)
List nextMainStack = new ArrayList<>(mainStack);
nextMainStack.add(number);
initMainStacks.addAll(generateInitMainStacks(nextMainStack, remainingSize - 1));
else
List initMainStack = new ArrayList<>(mainStack);
initMainStacks = Collections.singleton(initMainStack);
return initMainStacks;
private static final List EMPTY_STACK = Collections.emptyList();
/*
* Create a shortest path tree, starting from the target state (sorted main stack). Break when the initial state
* is found, since there can be no shorter path. This is akin to building a chess endgame tablebase.
*
* Traverse the path from initial state to the target state to count the number of moves.
*/
private static int solve(List initMainStack)
List> initState = Arrays.asList(new ArrayList<>(initMainStack), EMPTY_STACK, EMPTY_STACK);
List targetMainStack = new ArrayList<>(initMainStack);
Collections.sort(targetMainStack);
List> targetState = Arrays.asList(new ArrayList<>(targetMainStack), EMPTY_STACK, EMPTY_STACK);
Map>,List>> tablebase = new HashMap<>();
Deque>> workQueue = new ArrayDeque<>();
tablebase.put(targetState, null);
workQueue.add(targetState);
while (!tablebase.containsKey(initState))
assert !workQueue.isEmpty() : initState.toString();
List> state = workQueue.removeFirst();
Collection>> prevStates = calcPrevStates(state);
for (List> prevState : prevStates)
if (!tablebase.containsKey(prevState))
tablebase.put(prevState, state);
workQueue.add(prevState);
int numMoves = 0;
List> state = tablebase.get(initState);
while (state != null)
++numMoves;
state = tablebase.get(state);
return numMoves;
/*
* Given a state, calculate all possible previous states
*/
private static Collection>> calcPrevStates(List> state)
Collection>> prevStates = new ArrayList<>();
for (int fromStackNo = 0; fromStackNo < 3; ++fromStackNo)
List fromStack = state.get(fromStackNo);
if (!fromStack.isEmpty())
int number = fromStack.get(0);
for (int toStackNo = 0; toStackNo < 3; ++toStackNo)
if (toStackNo != fromStackNo)
List toStack = state.get(toStackNo);
if ((toStackNo == 0)
return prevStates;
Pitón, 3983838 3912258 se mueve sobre 55986 entradas
Este es muy ineficiente.
Agregaré el número total de movimientos después de que el OP aclare si son para todos esos casos o para otros casos específicos.
from itertools import product # Required for testing
import time # Required if you want to see it in action.
from pycallgraph import PyCallGraph
from pycallgraph.output import GraphvizOutput
def main( l ):
################### Data ###################
global a , b , c , d , copy , total_moves
total_moves = 0
a = [ x for x in l ] # Input stack, order doesn't matter, we'll try to empty this one
b = [] # Usable stack, restricted by order, we'll try to get the final sorted order here
c = [] # Usable stack, restricted by order, but we'll try to keep it as empty as possible
d = 'a':a , 'b':b , 'c':c # Passing the stacks to the nested functions by their names as a string
copy = [ x for x in a ] # reference copy, read-only
################### Functions ###################
def is_correct( stack ):
if d[ stack ] == sorted( copy , reverse = True ):
return True
else:
return False
def reverse_exchange( source , destination , keep = 0 ):
#
# keep is the number of elements to keep at the bottom of the source stack
# The remaining top elements are moved to the destination stack
# We first move the top elements to stack a
# and from a to c so that the order is preserved
# effectively splitting the source stack into two
#
i = 0
while len( d[ source ] ) > keep :
move( source , 'a' )
i += 1
else:
while i > 0:
move( 'a' , destination )
i -= 1
# def validate( source , destination ):
# #
# # Validates the give move
# #
# if len( d[ source ] ) == 0:
# return False
# if destination == 'a' or len( d[ destination ] ) == 0:
# return True
# else:
# if d[ destination ][ len( d[ destination ] ) - 1 ] >= d[ source ][ len( d[ source ] ) - 1 ]:
# return True
# else:
# return False
def move( source , destination ):
global total_moves
# if validate( source , destination ):
d[ destination ].append( d[ source ].pop() )
total_moves += 1
# Uncomment the following to view the workings step-by-step
# print 'n'
# print a
# print b
# print c
# print 'n'
# time.sleep(0.1)
return True
# else:
# return False
################### Actual logic ###################
while ( not is_correct( 'a' ) ):
copy_b = [x for x in b ] # Checking where the topmost element of a
top_of_a = a[ len(a) - 1 ] # should be inserted
copy_b.append( top_of_a ) #
sorted_copy_b = sorted( copy_b , reverse = True ) #
reverse_exchange( 'b' , 'c' , sorted_copy_b.index( top_of_a ) ) # Sandwiching the top-most element
move( 'a' , 'b' ) # to proper position in b
while (len(b) > 0 and len(c) > 0 and len(a) > 0) and (sorted (b , reverse = True)[0] <= a[len(a) - 1] <= c[0]): # # Optimization
move( 'a' , 'b' ) # #
reverse_exchange( 'c' , 'b' ) # b is always sorted, c is always empty
if is_correct( 'b' ): # Just moving b to a
while ( not is_correct( 'a' ) ): # The entire program focuses on "insertion sorting"
reverse_exchange( 'b' , 'c' , 1 ) # elements of a onto b while keeping c empty
move( 'b' , 'a' ) #
if len(c) > 0 : #
reverse_exchange( 'c' , 'b' , 1 ) # Slightly more efficient
move('c' , 'a' ) #
return total_moves
# with PyCallGraph( output= GraphvizOutput() ):
################### Test cases #############
i = 0
for elements in xrange( 1 , 7 ):
for cartesian_product in product( [ 1 , 2 , 3 , 4 , 5 , 6 ] , repeat = elements ):
input_list = [ int( y ) for y in cartesian_product ]
i += main(input_list)
print i
print i
Explicación
¿Qué, los comentarios no son lo suficientemente buenos para ti?
Nota para OP: Gracias por no hacer este código de golf.
C – 2547172 para 55986 entradas
Aquí hay mucho margen de mejora. Por mi propia cordura, simplifiqué esto para que solo fuera posible inspeccionar el elemento superior de cada pila. El levantamiento de esta restricción autoimpuesta permitiría optimizaciones como determinar el orden final por adelantado y tratar de minimizar el número de movimientos necesarios para lograrlo. Un ejemplo convincente es que mi implementación tiene el peor comportamiento de caso si la pila principal ya está ordenada.
Algoritmo:
- Llene ambas pilas auxiliares (espacio para la optimización aquí, posiblemente asignando a qué pila en función de algún tipo de pivote).
- Combinar y ordenar las pilas auxiliares de nuevo en la pila principal.
- Repita 1-2 hasta que la pila principal esté ordenada (pero al revés).
- Invierta la pila principal (más espacio para la optimización, mezclando muchos de los mismos elementos repetidamente).
Análisis:
- La complejidad adicional del espacio es O (n) (para las dos pilas auxiliares), lo cual es bueno, ya que era un requisito del problema.
- La complejidad del tiempo es O (n ^ 2) según mi recuento. Las correcciones son bienvenidas.
#include
#include
#define SIZE 6
int s0[SIZE + 1];
int s1[SIZE + 1];
int s2[SIZE + 1];
int
count(int *stack)
return stack[0];
int
top(int *stack)
return stack[stack[0]];
void
push(int *stack, int value)
assert(count(stack) < SIZE && "stack overflow");
assert((stack == s0
int
pop(int *stack)
int result = stack[stack[0]];
assert(count(stack) > 0 && "stack underflow");
stack[stack[0]] = 0;
stack[0]--;
return result;
int permutations;
void
permute(int len, int range, void (*cb)(void))
int i;
if(len == 0)
permutations++;
cb();
return;
for(i = 1; i <= range; i++)
push(s0, i);
permute(len - 1, range, cb);
pop(s0);
void
print(void)
int i;
for(i = 1; i <= count(s0); i++)
printf("%d ", s0[i]);
printf("n");
int save[SIZE + 1];
void
copy(int *src, int *dst)
int i;
for(i = 0; i <= SIZE; i++)
dst[i] = src[i];
int total;
void
move(int *src, int *dst)
total++;
push(dst, pop(src));
void
merge(void)
while(1)
if(count(s1) == 0 && count(s2) == 0)
break;
else if(count(s1) == 0
void
reverse(void)
while(1)
top(s2) < top(s0))
while(count(s2) > 0)
move(s2, s0);
break;
while(count(s0) > 0 && (count(s1) == 0
void
sort(void)
while(1)
top(s2) >= top(s0))
move(s0, s2);
else
merge();
void
helper(void)
copy(s0, save);
sort();
copy(save, s0);
int
main(void)
permute(1, 6, helper);
permute(2, 6, helper);
permute(3, 6, helper);
permute(4, 6, helper);
permute(5, 6, helper);
permute(6, 6, helper);
printf("%dn", permutations);
printf("%dn", total);
return 0;
Acuérdate de que tienes la capacidad de decir si te ayudó.
¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)