diff options
Diffstat (limited to 'kpat/freecell-solver/move.c')
| -rw-r--r-- | kpat/freecell-solver/move.c | 531 |
1 files changed, 531 insertions, 0 deletions
diff --git a/kpat/freecell-solver/move.c b/kpat/freecell-solver/move.c new file mode 100644 index 00000000..aa8ed560 --- /dev/null +++ b/kpat/freecell-solver/move.c @@ -0,0 +1,531 @@ +/* + * move.c - move and move stacks routines for Freecell Solver + * + * Written by Shlomi Fish (shlomif@vipe.technion.ac.il), 2000 + * + * This file is in the public domain (it's uncopyrighted). + */ +#include <stdlib.h> +#include <stdio.h> +#include <string.h> + +#include "move.h" +#include "state.h" + +#ifdef DMALLOC +#include "dmalloc.h" +#endif + +#include "inline.h" + +#if 0 +/* This variable was used for debugging. */ +int msc_counter=0; +#endif + +#if 0 +/* This function allocates an empty move stack */ +fcs_move_stack_t * fcs_move_stack_create(void) +{ + fcs_move_stack_t * ret; + + /* Allocate the data structure itself */ + ret = (fcs_move_stack_t *)malloc(sizeof(fcs_move_stack_t)); + + ret->max_num_moves = FCS_MOVE_STACK_GROW_BY; + ret->num_moves = 0; + /* Allocate some space for the moves */ + ret->moves = (fcs_move_t *)malloc(sizeof(fcs_move_t)*ret->max_num_moves); + + return ret; +} +#endif + +#if 0 +int fcs_move_stack_push(fcs_move_stack_t * stack, fcs_move_t move) +{ + /* If all the moves inside the stack are taken then + resize the move vector */ + + if (stack->num_moves == stack->max_num_moves) + { + int a, b; + a = (stack->max_num_moves >> 3); + b = FCS_MOVE_STACK_GROW_BY; + stack->max_num_moves += max(a,b); + stack->moves = realloc( + stack->moves, + stack->max_num_moves * sizeof(fcs_move_t) + ); + } + stack->moves[stack->num_moves++] = move; + + return 0; +} +#endif + +int freecell_solver_move_stack_pop(fcs_move_stack_t * stack, fcs_move_t * move) +{ + if (stack->num_moves > 0) + { + *move = stack->moves[--stack->num_moves]; + return 0; + } + else + { + return 1; + } +} + +#if 0 +void fcs_move_stack_destroy(fcs_move_stack_t * stack) +{ + free(stack->moves); + free(stack); +} +#endif + +void freecell_solver_move_stack_swallow_stack( + fcs_move_stack_t * stack, + fcs_move_stack_t * src_stack + ) +{ + fcs_move_t move; + while (!fcs_move_stack_pop(src_stack, &move)) + { + fcs_move_stack_push(stack, move); + } + fcs_move_stack_destroy(src_stack); +} + +#if 0 +void fcs_move_stack_reset( + fcs_move_stack_t * stack + ) +{ + stack->num_moves = 0; +} +#endif + +int freecell_solver_move_stack_get_num_moves( + fcs_move_stack_t * stack + ) +{ + return stack->num_moves; +} + +#if 0 +/* + This function duplicates a move stack +*/ +fcs_move_stack_t * fcs_move_stack_duplicate( + fcs_move_stack_t * stack + ) +{ + fcs_move_stack_t * ret; + + ret = (fcs_move_stack_t *)malloc(sizeof(fcs_move_stack_t)); + + ret->max_num_moves = stack->max_num_moves; + ret->num_moves = stack->num_moves; + ret->moves = (fcs_move_t *)malloc(sizeof(fcs_move_t) * ret->max_num_moves); + memcpy(ret->moves, stack->moves, sizeof(fcs_move_t) * ret->max_num_moves); + + return ret; +} +#endif + +#if 0 +extern void fcs_derived_states_list_add_state( + fcs_derived_states_list_t * list, + fcs_state_with_locations_t * state, + fcs_move_stack_t * move_stack + ) +{ + if (list->num_states == list->max_num_states) + { + list->max_num_states += 16; + list->states = realloc(list->states, sizeof(list->states[0]) * list->max_num_states); + list->move_stacks = realloc(list->move_stacks, sizeof(list->move_stacks[0]) * list->max_num_states); + } + list->states[list->num_states] = state; + list->move_stacks[list->num_states] = move_stack; + list->num_states++; +} +#endif +/* + This function performs a given move on a state + + */ +void freecell_solver_apply_move(fcs_state_with_locations_t * state_with_locations, fcs_move_t move, int freecells_num, int stacks_num, int decks_num) +{ + fcs_state_t * state; + fcs_card_t temp_card; + int a; + int src_stack, dest_stack; + int src_freecell, dest_freecell; + int src_stack_len; + + state = (&(state_with_locations->s)); + + dest_stack = fcs_move_get_dest_stack(move); + src_stack = fcs_move_get_src_stack(move); + dest_freecell = fcs_move_get_dest_freecell(move); + src_freecell = fcs_move_get_src_freecell(move); + + + switch(fcs_move_get_type(move)) + { + case FCS_MOVE_TYPE_STACK_TO_STACK: + { + src_stack_len = fcs_stack_len(*state, src_stack); + for(a=0 ; a<fcs_move_get_num_cards_in_seq(move) ; a++) + { + fcs_push_stack_card_into_stack( + *state, + dest_stack, + src_stack, + src_stack_len - fcs_move_get_num_cards_in_seq(move)+a + ); + } + for(a=0 ; a<fcs_move_get_num_cards_in_seq(move) ; a++) + { + fcs_pop_stack_card( + *state, + src_stack, + temp_card + ); + } + } + break; + case FCS_MOVE_TYPE_FREECELL_TO_STACK: + { + temp_card = fcs_freecell_card(*state, src_freecell); + fcs_push_card_into_stack(*state, dest_stack, temp_card); + fcs_empty_freecell(*state, src_freecell); + } + break; + case FCS_MOVE_TYPE_FREECELL_TO_FREECELL: + { + temp_card = fcs_freecell_card(*state, src_freecell); + fcs_put_card_in_freecell(*state, dest_freecell, temp_card); + fcs_empty_freecell(*state, src_freecell); + } + break; + case FCS_MOVE_TYPE_STACK_TO_FREECELL: + { + fcs_pop_stack_card(*state, src_stack, temp_card); + fcs_put_card_in_freecell(*state, dest_freecell, temp_card); + } + break; + case FCS_MOVE_TYPE_STACK_TO_FOUNDATION: + { + fcs_pop_stack_card(*state, src_stack, temp_card); + fcs_increment_foundation(*state, fcs_move_get_foundation(move)); + } + break; + case FCS_MOVE_TYPE_FREECELL_TO_FOUNDATION: + { + fcs_empty_freecell(*state, src_freecell); + fcs_increment_foundation(*state, fcs_move_get_foundation(move)); + } + break; + case FCS_MOVE_TYPE_SEQ_TO_FOUNDATION: + { + for(a=0;a<13;a++) + { + fcs_pop_stack_card(*state, src_stack, temp_card); + fcs_increment_foundation(*state, fcs_move_get_foundation(move)); + } + } + break; + + case FCS_MOVE_TYPE_FLIP_CARD: + { + fcs_flip_stack_card(*state, src_stack, fcs_stack_len(*state, src_stack)-1); + } + break; + + case FCS_MOVE_TYPE_CANONIZE: + { + fcs_canonize_state(state_with_locations, freecells_num, stacks_num); + } + break; + + } +} + +/* + The purpose of this function is to convert the moves from using + the canonized positions of the stacks and freecells to their + user positions. +*/ + +void freecell_solver_move_stack_normalize( + fcs_move_stack_t * moves, + fcs_state_with_locations_t * init_state, + int freecells_num, + int stacks_num, + int decks_num + ) +{ + fcs_move_stack_t * temp_moves; + fcs_move_t in_move, out_move; + fcs_state_with_locations_t dynamic_state; +#ifdef INDIRECT_STACK_STATES + char buffer[MAX_NUM_STACKS << 7]; + int a; +#endif + + fcs_move_init(out_move); + fcs_move_stack_alloc_into_var(temp_moves); + + fcs_duplicate_state(dynamic_state, *init_state); +#ifdef INDIRECT_STACK_STATES + for(a=0;a<stacks_num;a++) + { + fcs_copy_stack(dynamic_state, a, buffer); + } +#endif + + while ( + fcs_move_stack_pop( + moves, + &in_move + ) == 0) + { + freecell_solver_apply_move( + &dynamic_state, + in_move, + freecells_num, + stacks_num, + decks_num + ); + if (fcs_move_get_type(in_move) == FCS_MOVE_TYPE_CANONIZE) + { + /* Do Nothing */ + } + else + { + fcs_move_set_type(out_move, fcs_move_get_type(in_move)); + if ((fcs_move_get_type(in_move) == FCS_MOVE_TYPE_STACK_TO_STACK) || + (fcs_move_get_type(in_move) == FCS_MOVE_TYPE_STACK_TO_FREECELL) || + (fcs_move_get_type(in_move) == FCS_MOVE_TYPE_STACK_TO_FOUNDATION) || + (fcs_move_get_type(in_move) == FCS_MOVE_TYPE_SEQ_TO_FOUNDATION) + ) + { + fcs_move_set_src_stack(out_move,dynamic_state.stack_locs[(int)fcs_move_get_src_stack(in_move)]); + } + + if ( + (fcs_move_get_type(in_move) == FCS_MOVE_TYPE_FREECELL_TO_STACK) || + (fcs_move_get_type(in_move) == FCS_MOVE_TYPE_FREECELL_TO_FREECELL) || + (fcs_move_get_type(in_move) == FCS_MOVE_TYPE_FREECELL_TO_FOUNDATION)) + { + fcs_move_set_src_freecell(out_move,dynamic_state.fc_locs[(int)fcs_move_get_src_freecell(in_move)]); + } + + if ( + (fcs_move_get_type(in_move) == FCS_MOVE_TYPE_STACK_TO_STACK) || + (fcs_move_get_type(in_move) == FCS_MOVE_TYPE_FREECELL_TO_STACK) + ) + { + fcs_move_set_dest_stack(out_move,dynamic_state.stack_locs[(int)fcs_move_get_dest_stack(in_move)]); + } + + if ( + (fcs_move_get_type(in_move) == FCS_MOVE_TYPE_STACK_TO_FREECELL) || + (fcs_move_get_type(in_move) == FCS_MOVE_TYPE_FREECELL_TO_FREECELL) + ) + { + fcs_move_set_dest_freecell(out_move,dynamic_state.fc_locs[(int)fcs_move_get_dest_freecell(in_move)]); + } + + if ((fcs_move_get_type(in_move) == FCS_MOVE_TYPE_STACK_TO_FOUNDATION) || + (fcs_move_get_type(in_move) == FCS_MOVE_TYPE_FREECELL_TO_FOUNDATION) || + (fcs_move_get_type(in_move) == FCS_MOVE_TYPE_SEQ_TO_FOUNDATION) + + ) + { + fcs_move_set_foundation(out_move,fcs_move_get_foundation(in_move)); + } + + if ((fcs_move_get_type(in_move) == FCS_MOVE_TYPE_STACK_TO_STACK)) + { + fcs_move_set_num_cards_in_seq(out_move,fcs_move_get_num_cards_in_seq(in_move)); + } + + fcs_move_stack_push(temp_moves, out_move); + } + } + + /* + * temp_moves contain the needed moves in reverse order. So let's use + * swallow_stack to put them in the original in the correct order. + * + * */ + fcs_move_stack_reset(moves); + + freecell_solver_move_stack_swallow_stack(moves, temp_moves); +} + +GCC_INLINE int convert_freecell_num(int fcn) +{ + if (fcn >= 7) + return (fcn+3); + else + return fcn; +} + +char * freecell_solver_move_to_string(fcs_move_t move, int standard_notation) +{ + return + freecell_solver_move_to_string_w_state( + NULL, 4, 8, 1, + move, + (standard_notation == 2)?1:standard_notation + ); +} + +char * freecell_solver_move_to_string_w_state(fcs_state_with_locations_t * state, int freecells_num, int stacks_num, int decks_num, fcs_move_t move, int standard_notation) +{ + char string[256]; + switch(fcs_move_get_type(move)) + { + case FCS_MOVE_TYPE_STACK_TO_STACK: + if ((standard_notation == 2) && + /* More than one card was moved */ + (fcs_move_get_num_cards_in_seq(move) > 1) && + /* It was a move to an empty stack */ + (fcs_stack_len(state->s, fcs_move_get_dest_stack(move)) == + fcs_move_get_num_cards_in_seq(move)) + ) + { + sprintf(string, "%i%iv%x", + 1+fcs_move_get_src_stack(move), + 1+fcs_move_get_dest_stack(move), + fcs_move_get_num_cards_in_seq(move) + ); + } + else if (standard_notation) + { + sprintf(string, "%i%i", + 1+fcs_move_get_src_stack(move), + 1+fcs_move_get_dest_stack(move) + ); + } + else + { + sprintf(string, "Move %i cards from stack %i to stack %i", + fcs_move_get_num_cards_in_seq(move), + fcs_move_get_src_stack(move), + fcs_move_get_dest_stack(move) + ); + } + break; + + case FCS_MOVE_TYPE_FREECELL_TO_STACK: + if (standard_notation) + { + sprintf(string, "%c%i", + ('a'+convert_freecell_num(fcs_move_get_src_freecell(move))), + 1+fcs_move_get_dest_stack(move) + ); + } + else + { + sprintf(string, "Move a card from freecell %i to stack %i", + fcs_move_get_src_freecell(move), + fcs_move_get_dest_stack(move) + ); + } + + break; + + case FCS_MOVE_TYPE_FREECELL_TO_FREECELL: + if (standard_notation) + { + sprintf(string, "%c%c", + ('a'+convert_freecell_num(fcs_move_get_src_freecell(move))), + ('a'+convert_freecell_num(fcs_move_get_dest_freecell(move))) + ); + } + else + { + sprintf(string, "Move a card from freecell %i to freecell %i", + fcs_move_get_src_freecell(move), + fcs_move_get_dest_freecell(move) + ); + } + + break; + + case FCS_MOVE_TYPE_STACK_TO_FREECELL: + if (standard_notation) + { + sprintf(string, "%i%c", + 1+fcs_move_get_src_stack(move), + ('a'+convert_freecell_num(fcs_move_get_dest_freecell(move))) + ); + } + else + { + sprintf(string, "Move a card from stack %i to freecell %i", + fcs_move_get_src_stack(move), + fcs_move_get_dest_freecell(move) + ); + } + + break; + + case FCS_MOVE_TYPE_STACK_TO_FOUNDATION: + if (standard_notation) + { + sprintf(string, "%ih", 1+fcs_move_get_src_stack(move)); + } + else + { + sprintf(string, "Move a card from stack %i to the foundations", + fcs_move_get_src_stack(move) + ); + } + + break; + + + case FCS_MOVE_TYPE_FREECELL_TO_FOUNDATION: + if (standard_notation) + { + sprintf(string, "%ch", ('a'+convert_freecell_num(fcs_move_get_src_freecell(move)))); + } + else + { + sprintf(string, + "Move a card from freecell %i to the foundations", + fcs_move_get_src_freecell(move) + ); + } + + break; + + case FCS_MOVE_TYPE_SEQ_TO_FOUNDATION: + if (standard_notation) + { + sprintf(string, "%ih", fcs_move_get_src_stack(move)); + } + else + { + sprintf(string, + "Move the sequence on top of Stack %i to the foundations", + fcs_move_get_src_stack(move) + ); + } + break; + + default: + string[0] = '\0'; + break; + } + + return strdup(string); +} |