fork download
copy 
  1. #include <unistd.h>
  2. #define MAX_SOLUTIONS 100 // Define a maximum number of solutions to store
  3.  
  4. typedef struct {
  5.     int solutions[100][4];
  6.     int count;
  7. } SolutionTable;
  8.  
  9. // Initialize the solution table
  10. void initialize_solution_table(SolutionTable *table) {
  11.     table->count = 0; 
  12. }
  13.  
  14. // Store a valid configuration in the SolutionTable
  15. void store_solution(SolutionTable *table, int *input) {
  16.     if (table->count < MAX_SOLUTIONS) {
  17.         for (int i = 0; i < 4; i++) {
  18.             table->solutions[table->count][i] = input[i];
  19.         }
  20.         table->count++;
  21.     }
  22. }
  23.  
  24. void initialize_grid(int result[4][4]) {
  25.     int i = 0;
  26.     int j;
  27.     while (i < 4) {
  28.         j = 0;
  29.         while (j < 4) {
  30.             result[i][j] = 0;
  31.             j++;
  32.         }
  33.         i++;
  34.     }
  35. }
  36.  
  37. void print_result(int result[4][4]) {
  38.     int i = 0;
  39.     int j;
  40.     char num;
  41.  
  42.     while (i < 4) {
  43.         j = 0;
  44.         while (j < 4) {
  45.             num = result[i][j] + '0';
  46.             write(1, &num, 1);
  47.             if (j < 3) {
  48.                 write(1, " ", 1);
  49.             }
  50.             j++;
  51.         }
  52.         write(1, "\n", 1);
  53.         i++;
  54.     }
  55. }
  56.  
  57. // Modified print_final_combinations function that prints only the valid combinations
  58. void print_final_combinations(int final_tables[MAX_SOLUTIONS][4][4], int final_count) {
  59.     char newline = '\n';
  60.     if (final_count == 0) {
  61.         write(1, "No valid combinations found.\n", 29);
  62.         return;
  63.     }
  64.  
  65.     for (int i = 0; i < final_count; i++) {
  66.         write(1, "Combination:\n", 13);
  67.         print_result(final_tables[i]);
  68.         write(1, &newline, 1); // Print a newline between tables for better readability
  69.     }
  70. }
  71.  
  72.  
  73. void fill_easy_cases_rows(int *left_clues, int *right_clues, int result[4][4]) {
  74.     int i, j;
  75.     for (i = 0; i < 4; i++) {
  76.         if (left_clues[i] == 4) {
  77.             for (j = 0; j < 4; j++) {
  78.                 result[i][j] = j + 1;
  79.             }
  80.         } else if (left_clues[i] == 1) {
  81.             result[i][0] = 4;
  82.         }
  83.  
  84.         if (right_clues[i] == 4) {
  85.             for (j = 0; j < 4; j++) {
  86.                 result[i][j] = 4 - j;
  87.             }
  88.         } else if (right_clues[i] == 1) {
  89.             result[i][3] = 4;
  90.         }
  91.         if (left_clues[i] == 2 && right_clues[i] == 1)
  92.             result[i][0] = 3;
  93.         if (left_clues[i] == 1 && right_clues[i] == 2)
  94.             result[i][3] = 3;
  95.     }
  96. }
  97.  
  98. void fill_easy_cases_cols(int *up_clues, int *down_clues, int result[4][4]) {
  99.     int i, j;
  100.     for (i = 0; i < 4; i++) {
  101.         if (up_clues[i] == 4) {
  102.             for (j = 0; j < 4; j++) {
  103.                 result[j][i] = j + 1;
  104.             }
  105.         } else if (up_clues[i] == 1) {
  106.             result[0][i] = 4;
  107.         }
  108.  
  109.         if (down_clues[i] == 4) {
  110.             for (j = 0; j < 4; j++) {
  111.                 result[j][i] = 4 - j;
  112.             }
  113.         } else if (down_clues[i] == 1) {
  114.             result[3][i] = 4;
  115.         }
  116.         if (up_clues[i] == 2 && down_clues[i] == 1)
  117.             result[0][i] = 3;
  118.         if (up_clues[i] == 1 && down_clues[i] == 2)
  119.             result[3][i] = 3;
  120.     }
  121. }
  122.  
  123. // Checks if a row satisfies the left and right clues
  124. int is_valid_view(int *tab, int l_clue, int r_clue) {
  125.     int count = 0, max_height = 0;
  126.     int i = 0;
  127.     // Check left view
  128.     while (i < 4) {
  129.         if (tab[i] > max_height) {
  130.             count++;
  131.             max_height = tab[i];
  132.         }
  133.         i++;
  134.     }
  135.     if (count != l_clue) {
  136.         return 0;
  137.     }
  138.     // Check right view
  139.     count = 0;
  140.     max_height = 0;
  141.     i = 3;
  142.     while (i >= 0) {
  143.         if (tab[i] > max_height) {
  144.             count++;
  145.             max_height = tab[i];
  146.         }
  147.         i--;
  148.     }
  149.     return count == r_clue;
  150. }
  151.  
  152. // Finds missing numbers in a row or column
  153. void find_missing_numbers(int *input, int *missing, int *missing_count) {
  154.     int used[5] = {0}, i = 0;
  155.     while (i < 4) {
  156.         if (input[i] > 0 && input[i] <= 4) {
  157.             used[input[i]] = 1;
  158.         }
  159.         i++;
  160.     }
  161.     *missing_count = 0;
  162.     i = 1;
  163.     while (i <= 4) {
  164.         if (!used[i]) {
  165.             missing[(*missing_count)++] = i;
  166.         }
  167.         i++;
  168.     }
  169. }
  170.  
  171. // Generates permutations for rows/columns and checks validity
  172. void generate_permutations(int *input, int *missing, int missing_count, int index, int l_clue, int r_clue, SolutionTable *table) {
  173.     if (index == 4) {
  174.         if (is_valid_view(input, l_clue, r_clue)) {
  175.             store_solution(table, input); // Store the valid configuration
  176.         }
  177.         return;
  178.     }
  179.     if (input[index] != 0) {
  180.         generate_permutations(input, missing, missing_count, index + 1, l_clue, r_clue, table);
  181.     } else {
  182.         for (int i = 0; i < missing_count; i++) {
  183.             int current_value = missing[i];
  184.             int already_used = 0;
  185.             for (int j = 0; j < index; j++) {
  186.                 if (input[j] == current_value) {
  187.                     already_used = 1;
  188.                     break;
  189.                 }
  190.             }
  191.             if (!already_used) {
  192.                 input[index] = current_value;
  193.                 generate_permutations(input, missing, missing_count, index + 1, l_clue, r_clue, table);
  194.                 input[index] = 0;
  195.             }
  196.         }
  197.     }
  198. }
  199.  
  200. void compare_solutions(SolutionTable *rows, SolutionTable *colms, SolutionTable better_solutions[4]) {
  201.     // Initialize better_solutions counts to zero
  202.     for (int i = 0; i < 4; i++) {
  203.         better_solutions[i].count = 0; // Set count to zero for each SolutionTable
  204.     }
  205.  
  206.     // Iterate through each row table
  207.     for (int k = 0; k < 4; k++) {
  208.         // Initialize c for each row
  209.         for (int c = 0; c < rows[k].count; c++) {
  210.             int verifier = 0; // Reset verifier for each combination
  211.  
  212.             // Check each solution against the columns
  213.             for (int j = 0; j < 4; j++) { // Loop through all columns (0 to 3)
  214.                 int d = 0;
  215.                 while (d < colms[j].count) {
  216.                     // Compare solutions in rows and columns
  217.                     if (rows[k].solutions[c][j] == colms[j].solutions[d][k]) {
  218.                         verifier++; // Increment verifier on match
  219.                         break; // Stop checking other column entries once a match is found
  220.                     }
  221.                     d++;
  222.                 }
  223.             }
  224.             // If all four elements matched, add the solution to better_solutions
  225.             if (verifier == 4) {
  226.                 // Copy the solution into better_solutions
  227.                 for (int m = 0; m < 4; m++) {
  228.                     better_solutions[k].solutions[better_solutions[k].count][m] = rows[k].solutions[c][m];
  229.                 }
  230.                 better_solutions[k].count++; // Increment count of better solutions
  231.             }
  232.         }
  233.     }
  234. }
  235.  
  236. // Function to check if any row in better_solutions is empty
  237. int check_empty_rows(SolutionTable better_solutions[4]) {
  238.     for (int i = 0; i < 4; i++) {
  239.         if (better_solutions[i].count == 0) {
  240.             return 1; // Return 1 if any row is empty
  241.         }
  242.     }
  243.     return 0; // Return 0 if all rows have at least one solution
  244. }
  245. // Function to check if a column has unique elements (no duplicates)
  246. int is_column_unique(int final_table[4][4], int col_index) {
  247.     int seen[5] = {0}; // Array to track which numbers (1 to 4) have been seen
  248.     for (int i = 0; i < 4; i++) {
  249.         int value = final_table[i][col_index];
  250.         if (seen[value]) {
  251.             return 0; // Duplicate found, return false
  252.         }
  253.         seen[value] = 1; // Mark the number as seen
  254.     }
  255.     return 1; // All elements are unique
  256. }
  257.  
  258. // Function to validate all columns and check for uniqueness and view correctness
  259. int are_columns_valid(int final_table[4][4], int *up_clues, int *down_clues) {
  260.     for (int col = 0; col < 4; col++) {
  261.         // Check if the column has unique elements
  262.         if (!is_column_unique(final_table, col)) {
  263.             return 0; // Column has duplicates, return false
  264.         }
  265.         // Extract the column into a temporary array to check the views
  266.         int column[4];
  267.         for (int row = 0; row < 4; row++) {
  268.             column[row] = final_table[row][col];
  269.         }
  270.         // Check if the column satisfies the up and down clues
  271.         if (!is_valid_view(column, up_clues[col], down_clues[col])) {
  272.             return 0; // Column does not satisfy the view clues, return false
  273.         }
  274.     }
  275.     return 1; // All columns are valid
  276. }
  277. // Modified function to generate and validate combinations
  278. void generate_combinations(SolutionTable better_solutions[4], int final_tables[MAX_SOLUTIONS][4][4], int *final_count, int *up_clues, int *down_clues) {
  279.     *final_count = 0; // Initialize final count to 0
  280.  
  281.     for (int i = 0; i < better_solutions[0].count; i++) {
  282.         for (int j = 0; j < better_solutions[1].count; j++) {
  283.             for (int k = 0; k < better_solutions[2].count; k++) {
  284.                 for (int l = 0; l < better_solutions[3].count; l++) {
  285.                     // Copy the current row configurations into the final table
  286.                     for (int col = 0; col < 4; col++) {
  287.                         final_tables[*final_count][0][col] = better_solutions[0].solutions[i][col];
  288.                         final_tables[*final_count][1][col] = better_solutions[1].solutions[j][col];
  289.                         final_tables[*final_count][2][col] = better_solutions[2].solutions[k][col];
  290.                         final_tables[*final_count][3][col] = better_solutions[3].solutions[l][col];
  291.                     }
  292.  
  293.                     // Validate columns: check for duplicates and view correctness
  294.                     if (are_columns_valid(final_tables[*final_count], up_clues, down_clues)) {
  295.                         (*final_count)++; // Increment the count of valid combinations
  296.                     }
  297.                 }
  298.             }
  299.         }
  300.     }
  301. }
  302. void solvesky(char *input) {
  303.     int result[4][4];
  304.     int data[4][4];
  305.     int i = 0;
  306.     SolutionTable rows_posiblets[4];
  307.     SolutionTable colms_posiblets[4];
  308.     int missing[4];
  309.     int missing_count;
  310.     SolutionTable better_solutions[4]; // Declare better_solutions array
  311.  
  312.     initialize_grid(result);
  313.  
  314.     // Parse the input clues (up, down, left, right)
  315.     while (i < 4) {
  316.         data[0][i] = input[2 * i] - '0';         // up clues
  317.         data[1][i] = input[2 * (i + 4)] - '0';   // down clues
  318.         data[2][i] = input[2 * (i + 8)] - '0';   // left clues
  319.         data[3][i] = input[2 * (i + 12)] - '0';  // right clues
  320.         i++;
  321.     }
  322.  
  323.     // Initialize the possible solution tables
  324.     for (i = 0; i < 4; i++) {
  325.         initialize_solution_table(&rows_posiblets[i]);
  326.         initialize_solution_table(&colms_posiblets[i]);
  327.     }
  328.  
  329.     // Fill easy cases
  330.     fill_easy_cases_rows(data[2], data[3], result);  // Process rows
  331.     fill_easy_cases_cols(data[0], data[1], result);  // Process columns
  332.  
  333.     // Generate permutations for rows and columns
  334.     for (i = 0; i < 4; i++) {
  335.         find_missing_numbers(result[i], missing, &missing_count);
  336.         generate_permutations(result[i], missing, missing_count, 0, data[2][i], data[3][i], &rows_posiblets[i]);
  337.  
  338.         find_missing_numbers(result[i], missing, &missing_count);
  339.         generate_permutations(result[i], missing, missing_count, 0, data[0][i], data[1][i], &colms_posiblets[i]);
  340.     }
  341.  
  342.     // Compare solutions and store the best ones
  343.     compare_solutions(rows_posiblets, colms_posiblets, better_solutions);
  344.  
  345.     // Check if any row is empty
  346.     if (check_empty_rows(better_solutions)) {
  347.         write(1, "Error: impossible selution \n", 33);
  348.         return;
  349.     }
  350.  
  351.     int final_tables[100][4][4]; // 3D array to store all combinations
  352.     int final_count = 0; // Total number of 2D tables generated
  353.  
  354.     // Generate combinations and store them in final_tables
  355.     generate_combinations(better_solutions, final_tables, &final_count,data[0], data[1]);
  356.  
  357.     // Print all final combinations
  358.     print_final_combinations(final_tables, final_count);
  359. }
  360.  
  361. int main(int argc, char **argv) {
  362.     if (argc == 2) {
  363.         solvesky("3 1 2 3 1 3 3 2 2 3 2 1 3 2 1 2");
  364.     } else {
  365.         write(1, "Error\n", 6);
  366.     }
  367.     return 0;
  368. }
  369.  
  370.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
45
stdout
copy 
Error
https://ideone.com/XFx4tF
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!