Advertisement
aaaaaa123456789

JV programming challenges, season 2, week 1, challenge 2

Jan 21st, 2015
262
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.   This file is hereby released to the public domain.
  3.   ~aaaaaa123456789, 2015-01-21
  4. */
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9.  
  10. #include "common.h"
  11.  
  12. int fill_numbers(unsigned short *, unsigned, char **);
  13. unsigned short validate_row(const unsigned short *, unsigned short);
  14. unsigned short validate_column(const unsigned short *, unsigned short, unsigned short);
  15. void assign(const unsigned short *, unsigned short);
  16. void try_assign(const unsigned short *, unsigned short, unsigned short, unsigned short *, unsigned char *);
  17. void output(const unsigned short *, unsigned short);
  18.  
  19. #define create_map(x) calloc(1, ((x) + 7) >> 3)
  20. #define set_map(map, x) (((x) >> 3)[(char *) (map)] |= 1 << ((x) & 7))
  21. #define clear_map(map, x) (((x) >> 3)[(char *) (map)] &= ~(1 << ((x) & 7)))
  22. #define test_map(map, x) ((((x) >> 3)[(char *) (map)]) & (1 << ((x) & 7)))
  23.  
  24. int main (void) {
  25.   // note: this function doesn't release memory before returning -- terminating handles that
  26.   fputs("Enter data (one row per line, numbers separated by spaces, numbers", stderr);
  27.   fputs("range from 1 to n), end with a blank line or EOF:\n", stderr);
  28.   char ** lines = get_lines(0, "", 0, NULL);
  29.   unsigned count = count_lines(lines);
  30.   if (!count) return 0; // nothing to do here
  31.   if (count > 65534) {
  32.     fputs("Too much data.\n", stderr);
  33.     return 1;
  34.   }
  35.   unsigned short * numbers = malloc(count * count * sizeof(unsigned short));
  36.   if (!numbers) {
  37.     fputs("Out of memory.\n", stderr);
  38.     return 1;
  39.   }
  40.   if (!fill_numbers(numbers, count, lines)) return 1;
  41.   free(lines);
  42.   assign(numbers, count);
  43.   return 0;
  44. }
  45.  
  46. int fill_numbers (unsigned short * numbers, unsigned count, char ** lines) {
  47.   char * errp;
  48.   char ** tokens;
  49.   unsigned long rv;
  50.   unsigned linenumber, colnumber;
  51.   for (linenumber = 0; linenumber < count; lines ++, linenumber ++) {
  52.     tokens = tokenize_string(*lines, " ", 1);
  53.     free(*lines);
  54.     if (count_lines(tokens) != count) {
  55.       fprintf(stderr, "ERROR: line %u does not contain %u numbers\n", linenumber + 1, count);
  56.       return 0;
  57.     }
  58.     for (colnumber = 0; colnumber < count; colnumber ++) {
  59.       rv = strtoul(tokens[colnumber], &errp, 10);
  60.       if (*errp) {
  61.         fprintf(stderr, "ERROR: value at (%u, %u) is not a number\n", linenumber + 1, colnumber + 1);
  62.         return 0;
  63.       } else if ((!rv) || (rv > count)) {
  64.         fprintf(stderr, "ERROR: value at (%u, %u) is out of range (expected: 1..%u, got: %lu)\n", linenumber + 1, colnumber + 1, count, rv);
  65.         return 0;
  66.       }
  67.       numbers[linenumber * count + colnumber] = rv;
  68.     }
  69.     free(tokens);
  70.     if (rv = validate_row(numbers + linenumber * count, count)) {
  71.       fprintf(stderr, "ERROR: row %u repeats value %lu\n", linenumber + 1, rv);
  72.       return 0;
  73.     }
  74.   }
  75.   for (colnumber = 0; colnumber < count; colnumber ++)
  76.     if (rv = validate_column(numbers, count, colnumber)) {
  77.       fprintf(stderr, "ERROR: column %u repeats value %lu\n", colnumber + 1, rv);
  78.       return 0;
  79.     }
  80.   return count;
  81. }
  82.  
  83. void assign (const unsigned short * numbers, unsigned short count) {
  84.   unsigned short * assigned = malloc(sizeof(unsigned short) * count);
  85.   memset(assigned, 0, sizeof(unsigned short) * count);
  86.   unsigned char * available = create_map(count);
  87.   try_assign(numbers, count, 0, assigned, available);
  88. }
  89.  
  90. unsigned short validate_row (const unsigned short * row, unsigned short length) {
  91.   char * values = create_map(length);
  92.   while (length --) {
  93.     if (test_map(values, *row - 1)) {
  94.       free(values);
  95.       return *row;
  96.     }
  97.     set_map(values, *row - 1);
  98.     row ++;
  99.   }
  100.   free(values);
  101.   return 0;
  102. }
  103.  
  104. unsigned short validate_column (const unsigned short * numbers, unsigned short count, unsigned short column) {
  105.   if (column >= count) return 0;
  106.   char * values = create_map(count);
  107.   unsigned short p;
  108.   numbers += column;
  109.   for (p = 0; p < count; p ++, numbers += count) {
  110.     if (test_map(values, *numbers - 1)) {
  111.       free(values);
  112.       return *numbers;
  113.     }
  114.     set_map(values, *numbers - 1);
  115.   }
  116.   free(values);
  117.   return 0;
  118. }
  119.  
  120. void try_assign (const unsigned short * numbers, unsigned short count, unsigned short current, unsigned short * assigned, unsigned char * available) {
  121.   if (current >= count) {
  122.     output(assigned, count);
  123.     return;
  124.   }
  125.   unsigned short attempt;
  126.   const unsigned short * p = numbers + count * current;
  127.   for (attempt = 0; attempt < count; attempt ++, p ++) {
  128.     if (assigned[attempt]) continue;
  129.     if (test_map(available, *p - 1)) continue;
  130.     assigned[attempt] = *p;
  131.     set_map(available, *p - 1);
  132.     try_assign(numbers, count, current + 1, assigned, available);
  133.     clear_map(available, *p - 1);
  134.     assigned[attempt] = 0;
  135.   }
  136. }
  137.  
  138. void output (const unsigned short * assigned, unsigned short count) {
  139.   while (-- count) printf("%hu ", *(assigned ++));
  140.   printf("%hu\n", *assigned);
  141. }
Advertisement
RAW Paste Data Copied
Advertisement