A Star Solver for Zachtronics Solitaire Collection Fortune's Foundation

fortunes-foundation-a-star-solver.js

import assert from 'node:assert';

class HeapQueue {
  constructor(cmp) {
    this.cmp = (cmp || function(a, b){ return a - b; });
    this.length = 0;
    this.data = [];
  }
  size() {
    return this.length;
  }
  byteSize() {
    const objSize = JSON.stringify(this.data[0]).length;
    return this.length * objSize / 1024 / 1024;
  }
  peek() {
    return this.data[0];
  }
  push(value) {
    this.data.push(value);
    let pos = this.data.length - 1,
    parent, x;

    while (pos > 0) {
      parent = (pos - 1) >>> 1;
      if (this.cmp(this.data[pos], this.data[parent]) < 0) {
        x = this.data[parent];
        this.data[parent] = this.data[pos];
        this.data[pos] = x;
        pos = parent;
      } else break;
    }
    return this.length++;
  }
  pop() {
    const last_val = this.data.pop();
    let ret = this.data[0];
    if (this.data.length > 0) {
      this.data[0] = last_val;
      let pos = 0,
      last = this.data.length - 1,
      left, right, minIndex, x;
      while(1){
        left = (pos << 1) + 1;
        right = left + 1;
        minIndex = pos;
        if(left <= last && this.cmp(this.data[left], this.data[minIndex]) < 0) minIndex = left;
        if(right <= last && this.cmp(this.data[right], this.data[minIndex]) < 0) minIndex = right;
        if(minIndex !== pos){
          x = this.data[minIndex];
          this.data[minIndex] = this.data[pos];
          this.data[pos] = x;
          pos = minIndex;
        }else break;
      }
    } else {
      ret = last_val;
    }
    this.length--;
    return ret;
  }
}

// --- Constants and Configuration ---

const NUM_QUEUES = 11;
const SUITS = ['L', 'B', 'R', 'G']; // Green (L), Blue (B), Red (R), Gold (G)
const FACE_VALUES = { A: 1, J: 11, Q: 12, K: 13 };
const VALUE_FACES = { 1: 'A', 11: 'J', 12: 'Q', 13: 'K' };
const debug = false;

// --- Card Parsing and Representation ---

/**
 * Parses a card string (e.g., "K/R", "15", "A/L") into a card object.
 * @param {string | number} cardStr - The card string or number.
 * @returns {object | null} Card object { type: 'minor'/'major', value: number, suit?: string } or null if invalid.
 */
function parseCard(cardStr) {
    if (cardStr === null || cardStr === undefined || cardStr === '_') {
        return null; // Represents an empty slot or invalid input
    }
    const str = String(cardStr);
    const parts = str.split('/');
    if (parts.length === 2) {
        // Minor Arcana (e.g., "K/R", "5/L")
        const valueStr = parts[0].toUpperCase();
        const suit = parts[1].toUpperCase();
        if (!SUITS.includes(suit)) return null; // Invalid suit

        let value;
        if (FACE_VALUES[valueStr]) {
            value = FACE_VALUES[valueStr];
        } else {
            value = parseInt(valueStr, 10);
            if (isNaN(value) || value < 2 || value > 10) return null; // Invalid minor value
        }
        return { type: 'minor', value: value, suit: suit };
    } else if (parts.length === 1) {
        // Major Arcana (e.g., "0", "15", "21")
        const value = parseInt(str, 10);
        if (isNaN(value) || value < 0 || value > 21) return null; // Invalid major value
        return { type: 'major', value: value };
    }
    return null; // Invalid format
}

/**
 * Converts a card object back to its string representation.
 * @param {object | null} card - The card object.
 * @returns {string} String representation (e.g., "K/R", "15") or '_' if null.
 */
function cardToString(card) {
    if (!card) return '_';
    if (card.type === 'major') {
        return String(card.value);
    } else if (card.type === 'minor') {
        const valueStr = VALUE_FACES[card.value] || String(card.value);
        return `${valueStr}/${card.suit}`;
    }
    return '?'; // Should not happen
}

// --- Game State ---

/**
 * Creates the initial game state from the provided setup.
 * @param {object} initialStateConfig - Object containing initial queues and foundations.
 * @returns {object} The initial game state.
 */
function createInitialState(initialStateConfig) {
    const state = {
        queues: [],
        majorFoundations: [[], []], // [low pile (0->), high pile (21<-)]
        minorFoundations: { L: [], B: [], R: [], G: [] },
        minorBlocked: false, // cards cannot move from queue to minor foundation when it's blocked by dock card
        minorDock: null,
    };

    // Initialize Queues
    for (let i = 0; i < NUM_QUEUES; i++) {
        const queueKey = `queue${i + 1}`;
        if (initialStateConfig.queues[queueKey]) {
            state.queues[i] = initialStateConfig.queues[queueKey]
                .map(parseCard)
                .filter(card => card !== null); // Filter out any parsing errors or empty slots
        } else {
            state.queues[i] = [];
        }
    }

    // Initialize Minor Foundations (Assume Aces start there based on input)
    SUITS.forEach(suit => {
        const ace = parseCard(`A/${suit}`);
        if (ace) {
            state.minorFoundations[suit] = [ace];
        } else {
             console.warn(`Could not parse Ace for suit ${suit}`);
             state.minorFoundations[suit] = []; // Should not happen with valid input
        }
    });

    // Initialize Major Foundations (start empty)
    state.majorFoundations = [[], []];

    return state;
}

function deepCopyState(state) {
    return JSON.parse(JSON.stringify(state));
}

/**
 * Generates a unique string representation (hash) of the game state.
 * Used for the 'visited' set in BFS to avoid cycles and redundant work.
 * The hash must be consistent: the same state always produces the same hash.
 * @param {object} state - The game state.
 * @returns {string} A unique string identifier for the state.
 */
function hashState(state) {
    let hash = '';
    // Hash Queues
    hash += state.queues.map(q => q.map(cardToString).join(',')).join('\n');
    hash += '\n-- MF --\n';
    // Hash Major Foundations
    hash += state.majorFoundations[0].map(cardToString).join(',');
    hash += '\n';
    hash += state.majorFoundations[1].map(cardToString).join(',');
    hash += '\n-- mF --\n';
    // Hash Minor Foundations
    hash += SUITS.map(suit => state.minorFoundations[suit].map(cardToString).join(',')).join('\n');
    hash += '\n-- dock --\n';
    // Hash Minor Dock
    hash += cardToString(state.minorDock);
    return hash;
}

function isGoalState(state) {
    return state.queues.every(queue => queue.length === 0);
}

/**
 * get a score for game state, lower the better
 * @param {*} state
 * @returns {number}
 */
function getStateScore(state) {
  let score = 0;
  state.queues.forEach(queue => {
      score += 0.5 * getQueueScore(queue)
  });
  state.majorFoundations.forEach(foundation => {
      score += getQueueScore(foundation)
  });
  score += getQueueScore(state.minorFoundations['L'])
  score += getQueueScore(state.minorFoundations['B'])
  score += getQueueScore(state.minorFoundations['R'])
  score += getQueueScore(state.minorFoundations['G'])
  score += state.minorBlocked ? -10 : 5
  return -score;
}

function getQueueScore(cards) {
    if (cards.length === 0) return 3; // empty queue == 3 consecutive cards
    if (cards.length === 1) return 2;
    let score = 0;
    let consecutive = 0;
    const lastCard = cards[cards.length - 1];
    const lastType = lastCard.type;
    const lastSuit = lastCard.suit;

    let lastValue = lastCard.value;
    for (let i = cards.length - 2; i >= 0; i--) {
        const card = cards[i];
        const { type, value, suit } = card;
        if (type === lastType && (suit ? suit === lastSuit : true) && Math.abs(value - lastValue) === 1) {
            consecutive++;
        } else {
            break;
        }
        lastValue = value;
    }
    score += consecutive;
    return score;
}

assert.equal(getQueueScore([
    { type: 'minor', value: 1, suit: 'L' },
    { type: 'minor', value: 2, suit: 'L' },
    { type: 'major', value: 0 },
    { type: 'minor', value: 3, suit: 'L' },
    { type: 'minor', value: 4, suit: 'L' },
]), 1, `two consecutive cards`);
assert.equal(getQueueScore([
  { type: 'minor', value: 1, suit: 'R' },
  { type: 'minor', value: 2, suit: 'L' },
  { type: 'minor', value: 3, suit: 'L' },
  { type: 'minor', value: 4, suit: 'L' },
]), 2, `three consecutive cards case 1`);
assert.equal(getQueueScore([
  { type: 'minor', value: 1, suit: 'L' },
  { type: 'minor', value: 2, suit: 'L' },
  { type: 'minor', value: 3, suit: 'L' },
  { type: 'minor', value: 4, suit: 'L' },
]), 3, `four consecutive cards case`);
assert.equal(getQueueScore([]), 3, `empty queue`);
assert.equal(getQueueScore([{ type: 'minor', value: 1, suit: 'L' }]), 2, `one card`);

// --- Move Logic ---

/**
 * Applies a move to a *copy* of the state and returns the new state.
 * @param {object} state - The current game state (will be copied).
 * @param {object} move - The move object { fromType, fromIndex/Suit, toType, toIndex/Suit, card }.
 * @returns {object} The new game state after the move.
 */
function applyMove(state, move) {
    const newState = deepCopyState(state);
    const cardToMove = move.card; // The card being moved

    // Remove card from source
    if (move.fromType === 'queue') {
        if (newState.queues[move.fromIndex].length > 0) {
            newState.queues[move.fromIndex].pop(); // Remove from tail
        } else {
             console.error("Error applying move: Source queue empty", move, hashState(state));
             throw new Error('Error applying move: Source queue empty')
        }
    } else if (move.fromType === 'minor_dock') {
        newState.minorDock = null;
    }

    // Add card to destination
    switch (move.toType) {
        case 'queue':
            newState.queues[move.toIndex].push(cardToMove);
            break;
        case 'major':
            newState.majorFoundations[move.toIndex].push(cardToMove);
            // Keep major foundations sorted implicitly by how we add
            break;
        case 'minor':
            newState.minorFoundations[move.toSuit].push(cardToMove);
            break;
        case 'minor_dock':
            newState.minorDock = cardToMove;
            newState.minorBlocked = true;
            break;
        default:
            console.error("Error applying move: Invalid move type", move);
    }

    return newState;
}

/**
 * Find cards in queues that can be collected to major or minor fountains.
 * @param {object} currentState - The current game state.
 * @returns {object} game state after cards collected to fountains.
 */
function collectFountains(state) {
    let moves = [];
    let currentState = state;
    while (true) {
      const availableCards = currentState.queues.map((queue, index) => {
        if (queue.length === 0) return null;
        return {
          queueIndex: index,
          card: queue[queue.length - 1]
        };
      }).filter(card => card !== null);
      Object.entries(currentState.minorFoundations).forEach(([suit, foundation]) => {
          if (currentState.minorBlocked) { return; } // Can't collect
          if (foundation.length === 0) return; // nothing to collect
          const targetSuit = suit;
          const targetVal = foundation[foundation.length - 1].value + 1;
          const found = availableCards.find(card => card.card.type === 'minor' && card.card.suit === targetSuit && card.card.value === targetVal);
          if (found) {
            moves.push({
              fromType: 'queue', fromIndex: found.queueIndex,
              toType: 'minor', toSuit: targetSuit,
              card: found.card,
              description: `Move ${cardToString(found.card)} from queue ${found.queueIndex + 1} to Minor Arcana (${targetSuit})`
            });
            availableCards.splice(availableCards.indexOf(found), 1);
          }
      });
      // major left and right
      const targetLeftVal = currentState.majorFoundations[0].length === 0 ? 0 : currentState.majorFoundations[0][currentState.majorFoundations[0].length - 1].value + 1;
      const targetRightVal = currentState.majorFoundations[1].length === 0 ? 21 : currentState.majorFoundations[1][currentState.majorFoundations[1].length - 1].value - 1;
      const foundLeft = availableCards.find(card => card.card.type === 'major' && card.card.value === targetLeftVal);
      if (foundLeft) {
        moves.push({
          fromType: 'queue', fromIndex: foundLeft.queueIndex,
          toType: 'major', toIndex: 0,
          card: foundLeft.card,
          description: `Move ${cardToString(foundLeft.card)} from queue ${foundLeft.queueIndex + 1} to Major Arcana (Low)`
        });
        availableCards.splice(availableCards.indexOf(foundLeft), 1);
      }
      const foundRight = availableCards.find(card => card.card.type === 'major' && card.card.value === targetRightVal);
      if (foundRight) {
        moves.push({
          fromType: 'queue', fromIndex: foundRight.queueIndex,
          toType: 'major', toIndex: 1,
          card: foundRight.card,
          description: `Move ${cardToString(foundRight.card)} from queue ${foundRight.queueIndex + 1} to Major Arcana (High)`
        });
        availableCards.splice(availableCards.indexOf(foundRight), 1);
      }

      if (moves.length === 0) break;

      moves.forEach(move => {
        currentState = applyMove(currentState, move);
      });
      moves = [];
    }
    return currentState;
}

assert.equal(hashState(collectFountains({
    queues: [
      [],
      [],
      [],
      [],
      [],
      [], // Empty
      [],
      [],
      [],
      [],
      [9, 20, 7, 'J/R', 13, 10, '2/B'].map(parseCard)
    ],
    majorFoundations: [[], []],
    minorFoundations: { L: ['A/L'].map(parseCard), B: ['A/B'].map(parseCard), R: ['A/R'].map(parseCard), G: ['A/G'].map(parseCard) },
    minorBlocked: false,
    minorDock: null,
})), hashState({
    queues: [
      [],
      [],
      [],
      [],
      [],
      [], // Empty
      [],
      [],
      [],
      [],
      [9, 20, 7, 'J/R', 13, 10].map(parseCard)
    ],
    majorFoundations: [[], []],
    minorFoundations: { L: ['A/L'].map(parseCard), B: ['A/B', '2/B'].map(parseCard), R: ['A/R'].map(parseCard), G: ['A/G'].map(parseCard) },
    minorBlocked: false,
    minorDock: null,
}), 'collect minor fountains');

/**
 * Generates all valid moves from the current game state.
 * @param {object} state - The current game state.
 * @returns {Array<object>} A list of valid move objects.
 */
function getValidMoves(state) {
    const moves = [];
    const numQueues = state.queues.length;

    // --- 1. Moves between Queues ---
    for (let i = 0; i < numQueues; i++) {
        if (state.queues[i].length === 0) continue; // Can't move from empty queue

        const sourceCard = state.queues[i][state.queues[i].length - 1];

        for (let j = 0; j < numQueues; j++) {
            if (i === j) continue; // Can't move to the same queue

            const destQueue = state.queues[j];

            if (destQueue.length === 0) {
                // Can always move to an empty queue
                moves.push({
                    fromType: 'queue', fromIndex: i,
                    toType: 'queue', toIndex: j,
                    card: sourceCard,
                    description: `Move ${cardToString(sourceCard)} from queue ${i + 1} to empty queue ${j + 1}`
                });
            } else {
                // Can move to a non-empty queue if cards stack
                const destCard = destQueue[destQueue.length - 1];

                // Stacking Rule: Minor cards, same suit, value differs by 1
                if (sourceCard.type === 'minor' && destCard.type === 'minor' &&
                    sourceCard.suit === destCard.suit &&
                    Math.abs(sourceCard.value - destCard.value) === 1)
                {
                    moves.push({
                        fromType: 'queue', fromIndex: i,
                        toType: 'queue', toIndex: j,
                        card: sourceCard,
                        description: `Move ${cardToString(sourceCard)} from queue ${i + 1} onto ${cardToString(destCard)} in queue ${j + 1}`
                    });
                } else if (sourceCard.type === 'major' && destCard.type === 'major' &&
                    Math.abs(sourceCard.value - destCard.value) === 1)
                {
                    moves.push({
                        fromType: 'queue', fromIndex: i,
                        toType: 'queue', toIndex: j,
                        card: sourceCard,
                        description: `Move ${cardToString(sourceCard)} from queue ${i + 1} onto ${cardToString(destCard)} in queue ${j + 1}`
                    });
                }
            }
        }
    }

    // --- 2. Minor docker to queue
    if (state.minorDock) {
        const sourceCard = state.minorDock;
        for (let i = 0; i < numQueues; i++) {
            const destQueue = state.queues[i];
            if (destQueue.length === 0) {
                // Can always move
                moves.push({
                    fromType: 'minor_dock',
                    toType: 'queue', toIndex: i,
                    card: sourceCard,
                    description: `Move ${cardToString(sourceCard)} from Minor Arcana (Dock) to queue ${i + 1}`
                });
            } else {
                // Can move to a non-empty queue if cards stack
                const destCard = destQueue[destQueue.length - 1];
                if (sourceCard.type === destCard.type && Math.abs(sourceCard.value - destCard.value) === 1) {
                    moves.push({
                        fromType: 'minor_dock',
                        toType: 'queue', toIndex: i,
                        card: sourceCard,
                        description: `Move ${cardToString(sourceCard)} from Minor Arcana (Dock) to queue ${i + 1}`
                    });
                }
            }
        }
    }

    // --- 3. Moves from Queue to Minor Dock
    for (let i = 0; i < numQueues; i++) {
        if (state.queues[i].length === 0) continue
        const sourceCard = state.queues[i][state.queues[i].length - 1];
        if (state.minorDock === null) {
            moves.push({
                fromType: 'queue', fromIndex: i,
                toType: 'minor_dock',
                card: sourceCard,
                description: `Move ${cardToString(sourceCard)} from queue ${i + 1} to Minor Arcana (Dock)`
            });
        }
    }

    if (moves.length > 0 && debug === true)
      console.log('valid moves:', moves.map(m => m.description).join('\n'))
    return moves;
}

// --- BFS A* Solver ---

/**
 * Solves the card game using Breadth-First Search.
 * @param {object} initialState - The starting state of the game.
 * @param {number} maxStates - Maximum number of states to explore (to prevent infinite loops or excessive memory usage).
 * @returns {Array<object> | null} An array of move description strings if a solution is found, null otherwise.
 */
function solveBFS(initialState, maxStates = 100000) {
    let queue = new HeapQueue(([a1, a2], [b1, b2]) => a1 - b1 || a2 - b2);
    queue.push([getStateScore(initialState), 0, initialState, []])
    const visited = new Set();

    let exploredStates = 0;

    console.log("Starting BFS...", queue.size());
    while (queue.size() > 0) {
        if (exploredStates >= maxStates) {
            console.warn(`BFS stopped: Reached maximum state limit (${maxStates}) or Reach max queue size (${queue.size()})`);
            return null; // Limit reached
        }

        let [f, g, currentState, currentPath] = queue.pop();
        if (visited.has(hashState(currentState))) {
          continue;
        }
        exploredStates++;
        visited.add(hashState(currentState));

        currentState = collectFountains(currentState);

        if (exploredStates % 10000 === 0) {
          console.log(`Explored ${exploredStates} states, queue size: ${queue.size()}, byte size: ${queue.byteSize()}\n`, hashState(currentState));
          const qLimit = new HeapQueue(([a1, a2], [b1, b2]) => a1 - b1 || a2 - b2);
          for (let i = 0; i < 1000; i++) {
            qLimit.push(queue.pop());
          }
          queue = qLimit;
        }

        // --- Goal Check ---
        if (isGoalState(currentState)) {
          console.log(`Solution found after exploring ${exploredStates} states! Path length: ${currentPath.length}`);
          // Return the descriptions for readability
          return currentPath;
        }

        // --- Explore Neighbors ---
        const validMoves = getValidMoves(currentState);

        for (const move of validMoves) {
            const nextState = applyMove(currentState, move);
            const nextStateHash = hashState(nextState);

            if (!visited.has(nextStateHash)) {
                const nextg = g + 1;
                const newPath = [...currentPath, `${move.fromType},${move.fromIndex}:${move.toType},${move.toIndex}`]; // Add current move to the path
                queue.push([nextg + getStateScore(nextState), nextg, nextState, newPath]);
            }
        }
    }

    console.log(`No solution found after exploring ${exploredStates} states. Remaining in queue: `, queue.size());
    return null; // No solution found
}

// --- Example Usage ---

// Define the initial game setup based on your input
const initialGameSetup = {
    queues: {
        queue1: ['5/R', 15, 'Q/R', 21, '2/G', 19, 8],
        queue2: [0, '6/L', '9/L', 'J/B', '8/L', 'K/L', 4],
        queue3: ['8/R', '10/R', 3, 5, '4/R', 16, 12],
        queue4: ['3/R', '3/G', '2/L', '5/G', 'J/G', '7/L', 14],
        queue5: ['3/L', '10/B', '10/G', 'K/R', '4/B', 17, '5/L'],
        queue6: [], // Empty
        queue7: ['8/B', '4/G', '5/B', '7/G', '6/G', 'Q/G', 11],
        queue8: ['J/L', 1, '4/L', '7/R', 'Q/L', '3/B', 18],
        queue9: ['8/G', 'Q/B', 6, '9/B', '6/R', '9/G', '7/B'],
        queue10: ['6/B', '2/R', 2, 'K/G', 'K/B', '10/L', '9/R'],
        queue11: [9, 20, 7, 'J/R', 13, '2/B', 10]
    },
    // Minor foundations start with Aces according to rules/notation provided
    // Major foundations start empty
};


function main() {
  // Create the initial state object
  const startGameState = createInitialState(initialGameSetup);

  console.log("Initial State Hash:", hashState(startGameState));
  console.log("Initial State Object:", startGameState); // For debugging

  // Run the solver
  const solutionPath = solveBFS(startGameState, 2000000); // Increased limit a bit

  // Display the result
  if (solutionPath) {
      console.log("\n--- Solution Found ---");
      solutionPath.forEach((step, index) => {
          console.log(`Step ${index + 1}: ${step}`);
      });
  } else {
      console.log("\n--- No solution found within the state limit. ---");
  }
}

main();