#include <iostream> #include <vector> #include <array> #include <tuple> #include…
- User
#include #include #include #include #include #include #include #include #include
// Requested constants const int m = 4, n = 4; const int cnt_monsters = 2; const int antiverbosity = 100;
const int board_size = m * n; const int cnt_states = std::pow(board_size, cnt_monsters) + .5; int directions[5][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {0, 0}}; const int max_threads = 24;
const double monster_move_prob = std::pow(0.2, cnt_monsters); const int threads_to_use = std::min(max_threads, cnt_states);
int get_state_index(const std::array<int, cnt_monsters>& state) { int index = 0; for (int i = 0; i < cnt_monsters; ++i) { index = index * board_size + state[i]; } return index; }
std::array<int, cnt_monsters> get_state_from_index(int index) { std::array<int, cnt_monsters> state; for (int i = cnt_monsters - 1; i >= 0; --i) { state[i] = index % board_size; index /= board_size; } return state; }
void update_dp_by_state(int state_start, int state_end, const std::vector<std::vector>& dp, std::vector<std::vector>& new_dp, std::vector<std::vector>& next_move) { for (int state_idx = state_start; state_idx < state_end; ++state_idx) { // OPTIMIZATION: Calculate monster outcomes once, as they only depend on state_idx. std::vector<std::array<int, cnt_monsters>> monster_outcomes; monster_outcomes.push_back(get_state_from_index(state_idx));
for (int i = 0; i < cnt_monsters; ++i) { std::vector<std::array<int, cnt_monsters>> generated_states; generated_states.reserve(monster_outcomes.size() * 5); for (const auto& current_state : monster_outcomes) { int monster_x = current_state[i] / n, monster_y = current_state[i] % n; for (int monster_d = 0; monster_d < 5; ++monster_d) { auto [mdx, mdy] = directions[monster_d]; auto next_state = current_state; int new_monster_x = monster_x + mdx; int new_monster_y = monster_y + mdy; if (0 <= new_monster_x && new_monster_x < m && 0 <= new_monster_y && new_monster_y < n) { next_state[i] = new_monster_x * n + new_monster_y; } generated_states.push_back(next_state); } } monster_outcomes.swap(generated_states); } // Inner loop over man positions. for (int man_pos = 0; man_pos < board_size; ++man_pos) { if (dp[man_pos][state_idx] == -1) continue; int mx = man_pos / n, my = man_pos % n; std::array<double, 5> expected_scores{}; for (int d = 0; d < 5; ++d) { auto [dx, dy] = directions[d]; int new_mx = mx + dx, new_my = my + dy; if (new_mx < 0 || new_mx >= m || new_my < 0 || new_my >= n) { expected_scores[d] = -1.0; continue; } int new_man_pos = new_mx * n + new_my; double total_score = 0; for (const auto& new_monster_state : monster_outcomes) { int new_state_idx = get_state_index(new_monster_state); if (dp[new_man_pos][new_state_idx] != -1) { total_score += monster_move_prob * (1 + dp[new_man_pos][new_state_idx]); } } expected_scores[d] = total_score; } int best_move = std::distance(expected_scores.begin(), std::max_element(expected_scores.begin(), expected_scores.end())); new_dp[man_pos][state_idx] = expected_scores[best_move]; next_move[man_pos][state_idx] = best_move; }} }
void compute_divergence_by_state(int state_start, int state_end, const std::vector<std::vector>& old_dp, const std::vector<std::vector>& current_dp, double& partial_divergence, double& partial_avg_sum, int& partial_valid_count) {
double div = 0, avg_sum = 0; int count = 0; for (int state_idx = state_start; state_idx < state_end; ++state_idx) { for (int man_pos = 0; man_pos < board_size; ++man_pos) { if (old_dp[man_pos][state_idx] != -1) { double val1 = old_dp[man_pos][state_idx]; double val2 = current_dp[man_pos][state_idx]; div += (val1 > val2) ? (val1 - val2) : (val2 - val1); avg_sum += current_dp[man_pos][state_idx]; count++; } } } partial_divergence = div; partial_avg_sum = avg_sum; partial_valid_count = count; }
int main() { std::cout << "Board: " << m << "x" << n << ", Monsters: " << cnt_monsters << ", Threads: " << threads_to_use << std::endl; std::cout << "State space size: " << board_size * cnt_states << std::endl;
auto dp = std::make_unique<std::vector<std::vector>>(board_size, std::vector(cnt_states, 0)); auto new_dp = std::make_unique<std::vector<std::vector>>(board_size, std::vector(cnt_states, 0)); auto next_move = std::make_unique<std::vector<std::vector>>(board_size, std::vector(cnt_states, 0));
for (int man_pos = 0; man_pos < board_size; ++man_pos) { for (int state_idx = 0; state_idx < cnt_states; ++state_idx) { auto monster_state = get_state_from_index(state_idx); for (int pos : monster_state) { if (pos == man_pos) { (*dp)[man_pos][state_idx] = -1; (*new_dp)[man_pos][state_idx] = -1; break; } } } }
for (int t = 0;; ++t) { if (t % antiverbosity == 0) { std::cout << "Iteration " << t << std::endl; }
int chunk_size = cnt_states / threads_to_use; std::vector<std::thread> threads; for (int i = 0; i < threads_to_use; ++i) { int start = i * chunk_size; int end = (i == threads_to_use - 1) ? cnt_states : (i + 1) * chunk_size; threads.emplace_back(update_dp_by_state, start, end, std::cref(*dp), std::ref(*new_dp), std::ref(*next_move)); } for (auto& thread : threads) { thread.join(); } std::vector<std::thread> div_threads; std::vector<double> partial_divergences(threads_to_use); std::vector<double> partial_avg_sums(threads_to_use); std::vector<int> partial_valid_counts(threads_to_use); for (int i = 0; i < threads_to_use; ++i) { int start = i * chunk_size; int end = (i == threads_to_use - 1) ? cnt_states : (i + 1) * chunk_size; div_threads.emplace_back(compute_divergence_by_state, start, end, std::cref(*dp), std::cref(*new_dp), std::ref(partial_divergences[i]), std::ref(partial_avg_sums[i]), std::ref(partial_valid_counts[i])); } for (auto& thread : div_threads) { thread.join(); } double divergence = std::accumulate(partial_divergences.begin(), partial_divergences.end(), 0.0); double avg_sum = std::accumulate(partial_avg_sums.begin(), partial_avg_sums.end(), 0.0); int valid_states_count = std::accumulate(partial_valid_counts.begin(), partial_valid_counts.end(), 0); double avg = (valid_states_count > 0) ? avg_sum / valid_states_count : 0; if (t % antiverbosity == 0) { std::cout << "Divergence " << divergence << ", average survival time " << avg << std::endl; } if (divergence < 1e-1) break; dp.swap(new_dp);}
// Example: man at (3,3) [index 15], monsters at (0,0) [0] and (0,1) [4] // state_index = 0 * 16 + 4 = 4 double value = (*dp)[15][4]; std::cout << "Expected survival time from man at (3,3), monsters at (0,0) & (0,1): " << value << std::endl;
return 0; }
rewrite to PURE C, and also, remove excessive comments and one-line functions
Assistant
#include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #include <pthread.h> const int m = 4, n = 4; const int cnt_monsters = 2; const int antiverbosity = 100; const int board_size = 16; const int cnt_states = 256; int directions[5][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {0, 0}}; const int max_threads = 24; const double monster_move_prob = 0.04; const int threads_to_use = 24; int get_state_index(const int* state) { int index = 0; for (int i = 0; i < cnt_monsters; ++i) { index = index * board_size + state[i]; } return index; } void get_state_from_index(int index, int* state) { for (int i = cnt_monsters - 1; i >= 0; --i) { state[i] = index % board_size; index /= board_size; } } typedef struct { int state_start; int state_end; double** dp; double** new_dp; int** next_move; } ThreadData; typedef struct { int state_start; int state_end; double** old_dp; double** current_dp; double* partial_divergence; double* partial_avg_sum; int* partial_valid_count; } DivergenceData; void* update_dp_by_state(void* arg) { ThreadData* data = (ThreadData*)arg; int state_start = data->state_start; int state_end = data->state_end; double** dp = data->dp; double** new_dp = data->new_dp; int** next_move = data->next_move; int* current_state = malloc(cnt_monsters * sizeof(int)); int* next_state = malloc(cnt_monsters * sizeof(int)); for (int state_idx = state_start; state_idx < state_end; ++state_idx) { int monster_outcomes_size = 1; int max_outcomes = pow(5, cnt_monsters); int** monster_outcomes = malloc(max_outcomes * sizeof(int*)); for (int i = 0; i < max_outcomes; i++) { monster_outcomes[i] = malloc(cnt_monsters * sizeof(int)); } get_state_from_index(state_idx, current_state); memcpy(monster_outcomes[0], current_state, cnt_monsters * sizeof(int)); for (int i = 0; i < cnt_monsters; ++i) { int new_size = 0; int** new_outcomes = malloc(monster_outcomes_size * 5 * sizeof(int*)); for (int j = 0; j < monster_outcomes_size * 5; j++) { new_outcomes[j] = malloc(cnt_monsters * sizeof(int)); } for (int j = 0; j < monster_outcomes_size; ++j) { int monster_x = monster_outcomes[j][i] / n; int monster_y = monster_outcomes[j][i] % n; for (int monster_d = 0; monster_d < 5; ++monster_d) { int mdx = directions[monster_d][0]; int mdy = directions[monster_d][1]; int new_monster_x = monster_x + mdx; int new_monster_y = monster_y + mdy; if (0 <= new_monster_x && new_monster_x < m && 0 <= new_monster_y && new_monster_y < n) { memcpy(new_outcomes[new_size], monster_outcomes[j], cnt_monsters * sizeof(int)); new_outcomes[new_size][i] = new_monster_x * n + new_monster_y; new_size++; } else { memcpy(new_outcomes[new_size], monster_outcomes[j], cnt_monsters * sizeof(int)); new_size++; } } } for (int j = 0; j < monster_outcomes_size; j++) { free(monster_outcomes[j]); } free(monster_outcomes); monster_outcomes = new_outcomes; monster_outcomes_size = new_size; } for (int man_pos = 0; man_pos < board_size; ++man_pos) { if (dp[man_pos][state_idx] == -1) continue; int mx = man_pos / n, my = man_pos % n; double expected_scores[5] = {0}; for (int d = 0; d < 5; ++d) { int dx = directions[d][0], dy = directions[d][1]; int new_mx = mx + dx, new_my = my + dy; if (new_mx < 0 || new_mx >= m || new_my < 0 || new_my >= n) { expected_scores[d] = -1.0; continue; } int new_man_pos = new_mx * n + new_my; double total_score = 0; for (int j = 0; j < monster_outcomes_size; ++j) { int new_state_idx = get_state_index(monster_outcomes[j]); if (dp[new_man_pos][new_state_idx] != -1) { total_score += monster_move_prob * (1 + dp[new_man_pos][new_state_idx]); } } expected_scores[d] = total_score; } int best_move = 0; for (int d = 1; d < 5; ++d) { if (expected_scores[d] > expected_scores[best_move]) { best_move = d; } } new_dp[man_pos][state_idx] = expected_scores[best_move]; next_move[man_pos][state_idx] = best_move; } for (int i = 0; i < monster_outcomes_size; i++) { free(monster_outcomes[i]); } free(monster_outcomes); } free(current_state); free(next_state); return NULL; } void* compute_divergence_by_state(void* arg) { DivergenceData* data = (DivergenceData*)arg; int state_start = data->state_start; int state_end = data->state_end; double** old_dp = data->old_dp; double** current_dp = data->current_dp; double div = 0, avg_sum = 0; int count = 0; for (int state_idx = state_start; state_idx < state_end; ++state_idx) { for (int man_pos = 0; man_pos < board_size; ++man_pos) { if (old_dp[man_pos][state_idx] != -1) { double val1 = old_dp[man_pos][state_idx]; double val2 = current_dp[man_pos][state_idx]; div += (val1 > val2) ? (val1 - val2) : (val2 - val1); avg_sum += current_dp[man_pos][state_idx]; count++; } } } *(data->partial_divergence) = div; *(data->partial_avg_sum) = avg_sum; *(data->partial_valid_count) = count; return NULL; } int main() { printf("Board: %dx%d, Monsters: %d, Threads: %d\n", m, n, cnt_monsters, threads_to_use); printf("State space size: %d\n", board_size * cnt_states); double** dp = malloc(board_size * sizeof(double*)); double** new_dp = malloc(board_size * sizeof(double*)); int** next_move = malloc(board_size * sizeof(int*)); for (int i = 0; i < board_size; i++) { dp[i] = malloc(cnt_states * sizeof(double)); new_dp[i] = malloc(cnt_states * sizeof(double)); next_move[i] = malloc(cnt_states * sizeof(int)); for (int j = 0; j < cnt_states; j++) { dp[i][j] = 0; new_dp[i][j] = 0; next_move[i][j] = 0; } } int* monster_state = malloc(cnt_monsters * sizeof(int)); for (int man_pos = 0; man_pos < board_size; ++man_pos) { for (int state_idx = 0; state_idx < cnt_states; ++state_idx) { get_state_from_index(state_idx, monster_state); for (int i = 0; i < cnt_monsters; ++i) { if (monster_state[i] == man_pos) { dp[man_pos][state_idx] = -1; new_dp[man_pos][state_idx] = -1; break; } } } } free(monster_state); for (int t = 0;; ++t) { if (t % antiverbosity == 0) { printf("Iteration %d\n", t); } int chunk_size = cnt_states / threads_to_use; pthread_t threads[threads_to_use]; ThreadData thread_data[threads_to_use]; for (int i = 0; i < threads_to_use; ++i) { thread_data[i].state_start = i * chunk_size; thread_data[i].state_end = (i == threads_to_use - 1) ? cnt_states : (i + 1) * chunk_size; thread_data[i].dp = dp; thread_data[i].new_dp = new_dp; thread_data[i].next_move = next_move; pthread_create(&threads[i], NULL, update_dp_by_state, &thread_data[i]); } for (int i = 0; i < threads_to_use; ++i) { pthread_join(threads[i], NULL); } pthread_t div_threads[threads_to_use]; DivergenceData div_data[threads_to_use]; double partial_divergences[threads_to_use]; double partial_avg_sums[threads_to_use]; int partial_valid_counts[threads_to_use]; for (int i = 0; i < threads_to_use; ++i) { div_data[i].state_start = i * chunk_size; div_data[i].state_end = (i == threads_to_use - 1) ? cnt_states : (i + 1) * chunk_size; div_data[i].old_dp = dp; div_data[i].current_dp = new_dp; div_data[i].partial_divergence = &partial_divergences[i]; div_data[i].partial_avg_sum = &partial_avg_sums[i]; div_data[i].partial_valid_count = &partial_valid_counts[i]; pthread_create(&div_threads[i], NULL, compute_divergence_by_state, &div_data[i]); } for (int i = 0; i < threads_to_use; ++i) { pthread_join(div_threads[i], NULL); } double divergence = 0; double avg_sum = 0; int valid_states_count = 0; for (int i = 0; i < threads_to_use; ++i) { divergence += partial_divergences[i]; avg_sum += partial_avg_sums[i]; valid_states_count += partial_valid_counts[i]; } double avg = (valid_states_count > 0) ? avg_sum / valid_states_count : 0; if (t % antiverbosity == 0) { printf("Divergence %f, average survival time %f\n", divergence, avg); } if (divergence < 1e-1) break; double** temp = dp; dp = new_dp; new_dp = temp; } double value = dp[15][4]; printf("Expected survival time from man at (3,3), monsters at (0,0) & (0,1): %f\n", value); for (int i = 0; i < board_size; i++) { free(dp[i]); free(new_dp[i]); free(next_move[i]); } free(dp); free(new_dp); free(next_move); return 0; }Would you like me to explain or break down this code?
- User
KEEP 2 SPACES INDENTATION also, REMOVE THREADS, make it single-threaded for simplicity
Assistant
#include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> const int m = 4, n = 4; const int cnt_monsters = 2; const int antiverbosity = 100; const int board_size = 16; const int cnt_states = 256; int directions[5][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {0, 0}}; const double monster_move_prob = 0.04; int get_state_index(const int* state) { int index = 0; for (int i = 0; i < cnt_monsters; ++i) { index = index * board_size + state[i]; } return index; } void get_state_from_index(int index, int* state) { for (int i = cnt_monsters - 1; i >= 0; --i) { state[i] = index % board_size; index /= board_size; } } void update_dp_by_state(double** dp, double** new_dp, int** next_move) { int* current_state = malloc(cnt_monsters * sizeof(int)); int* next_state = malloc(cnt_monsters * sizeof(int)); for (int state_idx = 0; state_idx < cnt_states; ++state_idx) { int monster_outcomes_size = 1; int max_outcomes = pow(5, cnt_monsters); int** monster_outcomes = malloc(max_outcomes * sizeof(int*)); for (int i = 0; i < max_outcomes; i++) { monster_outcomes[i] = malloc(cnt_monsters * sizeof(int)); } get_state_from_index(state_idx, current_state); memcpy(monster_outcomes[0], current_state, cnt_monsters * sizeof(int)); for (int i = 0; i < cnt_monsters; ++i) { int new_size = 0; int** new_outcomes = malloc(monster_outcomes_size * 5 * sizeof(int*)); for (int j = 0; j < monster_outcomes_size * 5; j++) { new_outcomes[j] = malloc(cnt_monsters * sizeof(int)); } for (int j = 0; j < monster_outcomes_size; ++j) { int monster_x = monster_outcomes[j][i] / n; int monster_y = monster_outcomes[j][i] % n; for (int monster_d = 0; monster_d < 5; ++monster_d) { int mdx = directions[monster_d][0]; int mdy = directions[monster_d][1]; int new_monster_x = monster_x + mdx; int new_monster_y = monster_y + mdy; if (0 <= new_monster_x && new_monster_x < m && 0 <= new_monster_y && new_monster_y < n) { memcpy(new_outcomes[new_size], monster_outcomes[j], cnt_monsters * sizeof(int)); new_outcomes[new_size][i] = new_monster_x * n + new_monster_y; new_size++; } else { memcpy(new_outcomes[new_size], monster_outcomes[j], cnt_monsters * sizeof(int)); new_size++; } } } for (int j = 0; j < monster_outcomes_size; j++) { free(monster_outcomes[j]); } free(monster_outcomes); monster_outcomes = new_outcomes; monster_outcomes_size = new_size; } for (int man_pos = 0; man_pos < board_size; ++man_pos) { if (dp[man_pos][state_idx] == -1) continue; int mx = man_pos / n, my = man_pos % n; double expected_scores[5] = {0}; for (int d = 0; d < 5; ++d) { int dx = directions[d][0], dy = directions[d][1]; int new_mx = mx + dx, new_my = my + dy; if (new_mx < 0 || new_mx >= m || new_my < 0 || new_my >= n) { expected_scores[d] = -1.0; continue; } int new_man_pos = new_mx * n + new_my; double total_score = 0; for (int j = 0; j < monster_outcomes_size; ++j) { int new_state_idx = get_state_index(monster_outcomes[j]); if (dp[new_man_pos][new_state_idx] != -1) { total_score += monster_move_prob * (1 + dp[new_man_pos][new_state_idx]); } } expected_scores[d] = total_score; } int best_move = 0; for (int d = 1; d < 5; ++d) { if (expected_scores[d] > expected_scores[best_move]) { best_move = d; } } new_dp[man_pos][state_idx] = expected_scores[best_move]; next_move[man_pos][state_idx] = best_move; } for (int i = 0; i < monster_outcomes_size; i++) { free(monster_outcomes[i]); } free(monster_outcomes); } free(current_state); free(next_state); } double compute_divergence(double** old_dp, double** current_dp, double* avg) { double div = 0, avg_sum = 0; int count = 0; for (int state_idx = 0; state_idx < cnt_states; ++state_idx) { for (int man_pos = 0; man_pos < board_size; ++man_pos) { if (old_dp[man_pos][state_idx] != -1) { double val1 = old_dp[man_pos][state_idx]; double val2 = current_dp[man_pos][state_idx]; div += (val1 > val2) ? (val1 - val2) : (val2 - val1); avg_sum += current_dp[man_pos][state_idx]; count++; } } } *avg = (count > 0) ? avg_sum / count : 0; return div; } int main() { printf("Board: %dx%d, Monsters: %d\n", m, n, cnt_monsters); printf("State space size: %d\n", board_size * cnt_states); double** dp = malloc(board_size * sizeof(double*)); double** new_dp = malloc(board_size * sizeof(double*)); int** next_move = malloc(board_size * sizeof(int*)); for (int i = 0; i < board_size; i++) { dp[i] = malloc(cnt_states * sizeof(double)); new_dp[i] = malloc(cnt_states * sizeof(double)); next_move[i] = malloc(cnt_states * sizeof(int)); for (int j = 0; j < cnt_states; j++) { dp[i][j] = 0; new_dp[i][j] = 0; next_move[i][j] = 0; } } int* monster_state = malloc(cnt_monsters * sizeof(int)); for (int man_pos = 0; man_pos < board_size; ++man_pos) { for (int state_idx = 0; state_idx < cnt_states; ++state_idx) { get_state_from_index(state_idx, monster_state); for (int i = 0; i < cnt_monsters; ++i) { if (monster_state[i] == man_pos) { dp[man_pos][state_idx] = -1; new_dp[man_pos][state_idx] = -1; break; } } } } free(monster_state); for (int t = 0;; ++t) { if (t % antiverbosity == 0) { printf("Iteration %d\n", t); } update_dp_by_state(dp, new_dp, next_move); double avg; double divergence = compute_divergence(dp, new_dp, &avg); if (t % antiverbosity == 0) { printf("Divergence %f, average survival time %f\n", divergence, avg); } if (divergence < 1e-1) break; double** temp = dp; dp = new_dp; new_dp = temp; } double value = dp[15][4]; printf("Expected survival time from man at (3,3), monsters at (0,0) & (0,1): %f\n", value); for (int i = 0; i < board_size; i++) { free(dp[i]); free(new_dp[i]); free(next_move[i]); } free(dp); free(new_dp); free(next_move); return 0; }
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.