<commit_before>// This file is part of Black Hole Solitaire Solver. It is subject to the
// license terms in the COPYING file found in the top-level directory of this
// distribution and at
// https://www.shlomifish.org/open-source/projects/black-hole-solitaire-solver/
// . No part of Black Hole Solitaire Solver, including this file, may be
// copied, modified, propagated, or distributed except according to the terms
// contained in the COPYING file.
//
// Copyright (c) 2010 <NAME>

// black_hole_solver.c - a solver for Black Hole Solitaire.

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

#include "config.h"
#include <black-hole-solver/black_hole_solver.h>
#include "can_move.h"
#include "rinutils/likely.h"
#include "state.h"
#include "bit_rw.h"
#include "rinutils/typeof_wrap.h"

#if (BHS_STATE_STORAGE == BHS_STATE_STORAGE_TOKYO_CAB_HASH)
#include "tokyo_cab_hash.h"
#elif (BHS_STATE_STORAGE == BHS_STATE_STORAGE_INTERNAL_HASH)
#include "fcs_hash.h"
#elif (BHS_STATE_STORAGE == BHS_STATE_STORAGE_GOOGLE_SPARSE_HASH)
#include "google_hash.h"
#else
#error Unknown state storage.
#endif

#include "rank_reach_prune.h"

#define NUM_SUITS 4
enum BHS_SUITS
{
    SUIT_H,
    SUIT_C,
    SUIT_D,
    SUIT_S,
    INVALID_SUIT = -1
};

static int suit_char_to_index(char suit)
{
    switch (suit)
    {
    case 'H':
        return SUIT_H;
    case 'C':
        return SUIT_C;
    case 'D':
        return SUIT_D;
    case 'S':
        return SUIT_S;
    default:
        return INVALID_SUIT;
    }
}

typedef struct
{
    bhs_state_key_value_pair_t packed;
} bhs_solution_state_t;

typedef struct
{
    bhs_solution_state_t s;
    bhs_rank_counts rank_counts;
} bhs_queue_item_t;

#define TALON_MAX_SIZE (NUM_RANKS * NUM_SUITS)
#define QUEUE_MAX_SIZE (1 + (BHS__MAX_NUM_COLUMNS + 1) * NUM_RANKS * NUM_SUITS)

typedef const bool can_move__row[NUM_RANKS];
typedef struct
{
    uint_fast16_t talon_len;
    bh_solve_hash_t positions;
    meta_allocator meta_alloc;
    uint_fast16_t initial_lens[BHS__MAX_NUM_COLUMNS];
    uint_fast32_t num_states_in_solution, current_state_in_solution_idx;
    unsigned long iterations_num, num_states_in_collection, max_iters_limit;
    uint_fast32_t num_columns;
    uint_fast32_t bits_per_column;
    uint_fast32_t queue_len;
    int_fast32_t sol_foundations_card_rank, sol_foundations_card_suit;
    // This is the ranks of the cards in the columns. It remains constant
    // for the duration of the game.
    bhs_rank_t board_ranks[BHS__MAX_NUM_COLUMNS][BHS__MAX_NUM_CARDS_IN_COL];

    bhs_rank_t initial_foundation;
    bhs_rank_t talon_values[TALON_MAX_SIZE];

    bhs_card_string_t initial_foundation_string;
    bhs_card_string_t initial_board_card_strings[BHS__MAX_NUM_COLUMNS]
                                                [BHS__MAX_NUM_CARDS_IN_COL];
    bhs_card_string_t initial_talon_card_strings[TALON_MAX_SIZE];

    bhs_state_key_value_pair_t init_state;
    bhs_state_key_value_pair_t final_state;

    bool is_rank_reachability_prune_enabled;
    bool effective_is_rank_reachability_prune_enabled;
    bool place_queens_on_kings;
    bool wrap_ranks;
    bool effective_place_queens_on_kings;
    can_move__row *can_move;
    bhs_queue_item_t queue[QUEUE_MAX_SIZE];
#define MAX_NUM_STATES (NUM_SUITS * NUM_RANKS + 1)
    bhs_solution_state_t states_in_solution[MAX_NUM_STATES];
} bhs_solver_t;

#define TALON_PTR_BITS 6

static void write_talon(bhs_state_key_t *key, uint_fast32_t n)
{
    fc_solve_bit_writer_t bit_w;
    fc_solve_bit_writer_init_bare(&bit_w, key->data);
    fc_solve_bit_writer_overwrite(&bit_w, TALON_PTR_BITS, n);
}
static uint_fast32_t read_talon(bhs_state_key_t key)
{
    return key.data[0] & ((1 << TALON_PTR_BITS) - 1);
}
static void write_col(bhs_state_key_t *key, uint_fast32_t col_idx,
    uint_fast32_t bits_per_column, uint_fast32_t n)
{
    fc_solve_bit_writer_t w;
    fc_solve_bit_writer_init_bare(&w, key->data);
    fc_solve_bit_writer_skip(&w, TALON_PTR_BITS + col_idx * bits_per_column);

    fc_solve_bit_writer_overwrite(&w, bits_per_column, n);
}
static uint_fast32_t read_col(
    bhs_state_key_t key, uint_fast32_t col_idx, uint_fast32_t bits_per_column)
{
    fc_solve_bit_reader_t r;
    fc_solve_bit_reader_init(&r, key.data);
    fc_solve_bit_reader_skip(&r, TALON_PTR_BITS + col_idx * bits_per_column);

    return fc_solve_bit_reader_read(&r, bits_per_column);<commit_msg>optimization<commit_after>// This file is part of Black Hole Solitaire Solver. It is subject to the
// license terms in the COPYING file found in the top-level directory of this
// distribution and at
// https://www.shlomifish.org/open-source/projects/black-hole-solitaire-solver/
// . No part of Black Hole Solitaire Solver, including this file, may be
// copied, modified, propagated, or distributed except according to the terms
// contained in the COPYING file.
//
// Copyright (c) 2010 <NAME>

// black_hole_solver.c - a solver for Black Hole Solitaire.

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

#include "config.h"
#include <black-hole-solver/black_hole_solver.h>
#include "can_move.h"
#include "rinutils/likely.h"
#include "state.h"
#include "bit_rw.h"
#include "rinutils/typeof_wrap.h"

#if (BHS_STATE_STORAGE == BHS_STATE_STORAGE_TOKYO_CAB_HASH)
#include "tokyo_cab_hash.h"
#elif (BHS_STATE_STORAGE == BHS_STATE_STORAGE_INTERNAL_HASH)
#include "fcs_hash.h"
#elif (BHS_STATE_STORAGE == BHS_STATE_STORAGE_GOOGLE_SPARSE_HASH)
#include "google_hash.h"
#else
#error Unknown state storage.
#endif

#include "rank_reach_prune.h"

#define NUM_SUITS 4
enum BHS_SUITS
{
    SUIT_H,
    SUIT_C,
    SUIT_D,
    SUIT_S,
    INVALID_SUIT = -1
};

static int suit_char_to_index(char suit)
{
    switch (suit)
    {
    case 'H':
        return SUIT_H;
    case 'C':
        return SUIT_C;
    case 'D':
        return SUIT_D;
    case 'S':
        return SUIT_S;
    default:
        return INVALID_SUIT;
    }
}

typedef struct
{
    bhs_state_key_value_pair_t packed;
} bhs_solution_state_t;

typedef struct
{
    bhs_solution_state_t s;
    bhs_rank_counts rank_counts;
} bhs_queue_item_t;

#define TALON_MAX_SIZE (NUM_RANKS * NUM_SUITS)
#define QUEUE_MAX_SIZE (1 + (BHS__MAX_NUM_COLUMNS + 1) * NUM_RANKS * NUM_SUITS)

typedef const bool can_move__row[NUM_RANKS];
typedef struct
{
    uint_fast16_t talon_len;
    bh_solve_hash_t positions;
    meta_allocator meta_alloc;
    uint_fast16_t initial_lens[BHS__MAX_NUM_COLUMNS];
    uint_fast32_t num_states_in_solution, current_state_in_solution_idx;
    unsigned long iterations_num, num_states_in_collection, max_iters_limit;
    uint_fast32_t num_columns;
    uint_fast32_t bits_per_column;
    uint_fast32_t queue_len;
    int_fast32_t sol_foundations_card_rank, sol_foundations_card_suit;
    // This is the ranks of the cards in the columns. It remains constant
    // for the duration of the game.
    bhs_rank_t board_ranks[BHS__MAX_NUM_COLUMNS][BHS__MAX_NUM_CARDS_IN_COL];

    bhs_rank_t initial_foundation;
    bhs_rank_t talon_values[TALON_MAX_SIZE];

    bhs_card_string_t initial_foundation_string;
    bhs_card_string_t initial_board_card_strings[BHS__MAX_NUM_COLUMNS]
                                                [BHS__MAX_NUM_CARDS_IN_COL];
    bhs_card_string_t initial_talon_card_strings[TALON_MAX_SIZE];

    bhs_state_key_value_pair_t init_state;
    bhs_state_key_value_pair_t final_state;

    bool is_rank_reachability_prune_enabled;
    bool effective_is_rank_reachability_prune_enabled;
    bool place_queens_on_kings;
    bool wrap_ranks;
    bool effective_place_queens_on_kings;
    can_move__row *can_move;
    bhs_queue_item_t queue[QUEUE_MAX_SIZE];
#define MAX_NUM_STATES (NUM_SUITS * NUM_RANKS + 1)
    bhs_solution_state_t states_in_solution[MAX_NUM_STATES];
} bhs_solver_t;

#define TALON_PTR_BITS 6

static inline void write_talon(
    bhs_state_key_t *key, const fc_solve_bit_data_t n)
{
    fc_solve_bit_writer_t bit_w;
    fc_solve_bit_writer_init_bare(&bit_w, key->data);
    fc_solve_bit_writer_overwrite(&bit_w, TALON_PTR_BITS, n);
}
static inline uint_fast32_t read_talon(const bhs_state_key_t key)
{
    return key.data[0] & ((1 << TALON_PTR_BITS) - 1);
}
static inline void write_col(bhs_state_key_t *const key,
    const uint_fast32_t col_idx, const uint_fast32_t bits_per_column,
    fc_solve_bit_data_t n)
{
    fc_solve_bit_writer_t w;
    fc_solve_bit_writer_init_bare(&w, key->data);
    fc_solve_bit_writer_skip(&w, TALON_PTR_BITS + col_idx * bits_per_column);

    fc_solve_bit_writer_overwrite(&w, bits_per_column, n);
}
static inline fc_solve_bit_data_t read_col(const bhs_state_key_t key,
    const uint_fast32_t col_idx, const uint_fast32_t bits_per_column)
{
    fc_solve_bit_reader_t r;
    fc_solve_bit_reader_init(&r, key.data);
    fc_solve_bit_reader_skip(&r, TALON_PTR_BITS + col_idx * bits_per_column);

    return fc_solve_bit_reader_read(&r, bits_per_column);
{'fraction_non_alphanumeric': 0.08055463849455266, 'fraction_numerical': 0.008803785627819962, 'mean_word_length': 4.59950708564387, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 27, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3728021', 'n_tokens_mistral': 3718, 'n_tokens_neox': 3577, 'n_words': 685}