COMP1721 - Higher Computing 1B

1. 
   void
   print_word_as_16bit_binary(int word) {
       int divisor;
       assert(sizeof (int) > 2);
       assert(word >= 0 && word <= 65535);
       for (divisor = 32768; divisor > 0; divisor /= 2) {
           printf("%d", word/divisor);
           word = word % divisor;
       }
   }
   

2. 
   int
   hex_digit_to_int(char c) {
        if (c >= '0' && c <= '9')
           return c - '0';
       else if (c >= 'A' && c <= 'F')
           return c - 'A' + 10;
       else if (c >= 'a' && c <= 'f')
           return c - 'a' + 10;
       else
           return 0; // could print error message here
   }
   

3. 
   int
   hex_digit_array_to_int0(char c[], int n_digits) {
       int i, value = 0;
       for ( i = 0; i < n_digits; i++)
           value = value*16 + hex_digit_to_int(c[i]);
       return value;
   }
   int
   hex_digit_array_to_int(char c[], int offset, int n_digits) {
       int i, value = 0;
       for (i = 0; i < n_digits; i++)
           value = value*16 + hex_digit_to_int(c[offset+i]);
       return value;
   }
   

4. 
   void
   convert_bytes_to_little_endian_words(int bytes[], int n_bytes, int words[]) {
       int i;
       assert(n_bytes % 2 == 0);
       for (i = 0; i < n_bytes; i += 2)
           words[i/2] = bytes[i+1]*256+bytes[i];
   }
   

5. 
   int
   read_ihex_line(FILE *f, int bytes[], int bytes_array_size) {
       char line[4096];
       if (fgets(line, sizeof line, f) == NULL)
           return  -1;
       if (strlen(line) < 6 || line[0] != ':') // shouldn't happen
           return 0;
       int byte_count = hex_digit_array_to_int(line, 1, 2);
       int address = hex_digit_array_to_int(line, 3, 4);
       int type = hex_digit_array_to_int(line, 7, 2);
       if (type != 0)
           return 0;
       assert(address+byte_count <= bytes_array_size);
       int i;
       for (i = 0; i < byte_count; i++)
           bytes[address+i] = hex_digit_array_to_int(line, 9 + i*2, 2);
       return byte_count;
   }
   

6. 
   #include <stdio.h>
   #include <string.h>
   #include <assert.h>
   
   int
   hex_digit_to_int(char c) {
        if (c >= '0' && c <= '9')
           return c - '0';
       else if (c >= 'A' && c <= 'F')
           return c - 'A' + 10;
       else if (c >= 'a' && c <= 'f')
           return c - 'a' + 10;
       else
           return 0; // could print error message here
   }
   
   int
   hex_digit_array_to_int(char c[], int offset, int n_digits) {
       int i, value = 0;
       for (i = 0; i < n_digits; i++)
           value = value*16 + hex_digit_to_int(c[offset+i]);
       return value;
   }
   
   int
   read_ihex_line(FILE *f, int bytes[], int bytes_array_size) {
       char line[4096];
       if (fgets(line, sizeof line, f) == NULL)
           return  -1;
       if (strlen(line) < 6 || line[0] != ':') // shouldn't happen
           return 0;
       int byte_count = hex_digit_array_to_int(line, 1, 2);
       int address = hex_digit_array_to_int(line, 3, 4);
       int type = hex_digit_array_to_int(line, 7, 2);
       if (type != 0)
           return 0;
       assert(address+byte_count <= bytes_array_size);
       int i;
       for (i = 0; i < byte_count; i++)
           bytes[address+i] = hex_digit_array_to_int(line, 9 + i*2, 2);
       return byte_count;
   }
   
   int
   read_ihex_file(char *filename, int bytes[], int bytes_array_size) {
       FILE *f = fopen(filename, "r");
       if (f == NULL) {
           fprintf(stderr, "Can not open %s:", filename);
           perror("");
           return 0;
       }
       int bytes_read = 0;
       while (1) {
           int line_bytes = read_ihex_line(f, bytes, bytes_array_size);
           if (line_bytes < 0)
               break;
           bytes_read += line_bytes;
       }
       return bytes_read;      
   }
   
   void
   convert_bytes_to_little_endian_words(int bytes[], int n_bytes, int words[]) {
       int i;
       assert(n_bytes % 2 == 0);
       for (i = 0; i < n_bytes; i += 2)
           words[i/2] = bytes[i+1]*256+bytes[i];
   }
   
   void
   print_word_as_16bit_binary(int word) {
       int divisor;
       assert(sizeof (int) > 2);
       assert(word >= 0 && word <= 65535);
       for (divisor = 32768; divisor > 0; divisor /= 2) {
           printf("%d", word/divisor);
           word = word % divisor;
       }
   }
   
   int
   main(int argc, char* argv[]) {
       const int n_bytes = 65536;
       int bytes[n_bytes];
   
       if (argc != 2) {
           fprintf(stderr,  "A single ihex file must be give as argument]\n");
           return 1;
       }
       int bytes_read = read_ihex_file(argv[1], bytes, n_bytes);
       int words[n_bytes/2];
       convert_bytes_to_little_endian_words(bytes, n_bytes, words);
       
       // assume words read were palced at the start of the address space
       // rather than print the entire address space
       int i;
       for (i = 0; i < bytes_read/2; i++) {
           printf("%5d ", i);
           print_word_as_16bit_binary(words[i]);
           printf("\n");
       }
       return 0;
   }
   

7. It takes 5 C statements to accomplish this by normal means;

        int myArray[4];
        myArray[0] = 7;
        myArray[1] = 22;
        myArray[2] = 31;
        myArray[3] = -44;
   

   Because the above is common sequence of operations, a shorthand exists in C:

        int myArray[] = { 7, 22, 31, 44 };
   

8.         int min = nums[0];
           for (int i = 1; i < N; i++) {
               if (nums[i] < min)
                   min = nums[i];
           }
           printf("min = %d\n", min);
   

9. int
   magic(int square[SIZE][SIZE]) {
       int firstColumnSum, i, j;
       int diagonal1Sum, diagonal2Sum;
       int columnSum, rowSum;
      
       firstColumnSum = 0;
       for (i = 0; i < SIZE; i++)
           firstColumnSum += square[i][0];
           
       for (i = 0; i < SIZE; i++) {
           columnSum = 0;
           rowSum = 0;
           
           for (j = 0; j < SIZE; j++) {
               rowSum +=  square[i][j];
               columnSum +=  square[j][i];
           }     
           if (rowSum != firstColumnSum || columnSum != firstColumnSum)
               return 0;
       }
       
       diagonal1Sum = 0;
       diagonal2Sum = 0;
       for (i = 0; i < SIZE; i++) {
              diagonal1Sum +=  square[i][i];
              diagonal2Sum +=  square[i][(SIZE - i) - 1];
       }
       
       return diagonal1Sum == firstColumnSum && diagonal2Sum == firstColumnSum;
   }
   

10. Points to note:

    • The method here is relatively complicatd, so it's essential to design it properly. Start with pseudo-code before moving on to write C code.

    • The main trick is the idea of putting a mark in place of matched elements so that they don't get counted more than once.

    • The rest of the algorithm deals with scanning across the sequences, either together or one-at-a-time.

    • The C version also has to attend to such house-keeping details as making copies of the arrays, so as not to destroy the originals with the markers. It also has to make sure that the return values are placed into the result arguments, since they're initially computed in local variables.

    Here's the pseudo-code design:

    count bulls and cows:
            initially no bulls and no cows
            scan for bulls, marking any matches
            scan for cows, marking any matches
    
    scan for bulls:
            FOR each element in first array DO
                    check whether it is same as
                            corresponding element in second array
                    if it is, note one more bull and
                            mark the matching element in each arrays
            END
    
    scan for cows:
            FOR each element in first array DO
                    scan second array looking for a match
                    if find one, note one more cow and
                            mark the matching element in each array
            END
    
    scan second array looking for a match:
            FOR each element in second array DO
                    check whether it matches the given element
                    if it does, stop scanning across the array and
                            remember where the match was found
            END
    

    Here is C code, based on this design:

    Here's a C function, based on this design:
    void
    BullsCows(int nums1[N], int nums2[N], int *nbulls, int *ncows) {
    	int	n1[N], n2[N];  /* local copies of nums1 and nums2 */
    	int	nb, nc;  /* local counters for *nbulls and *ncows */
    	int	i, j;    /* loop index variables */
    
    	/* Make local copies of the NumLists, so we can scribble on them */
    	for (i = 0; i < N; ++i) {
    		n1[i] = nums1[i];
    		n2[i] = nums2[i];
    	}
    
    	/* How many bulls and cows so far? */
    	nb = 0;  nc = 0;
    
    	/* First scan - look for Bulls */
    	/* Bull = matching value in corresponding positions */
    
    	for (i = 0; i < N; ++i) {
    		if (n1[i] == n2[i]) {
    			++nb;
    			n1[i] = Mark;
    			n2[i] = Mark;
    		}
    	}
    
    	/* Second scan - look for Cows */
    	/* Cow = matching value in any position in other array */
    	/* Note: won't re-count Bulls because of Mark          */
    
    	for (i = 0; i < N; ++i) {
    		if (n1[i] != Mark) {
    			for (j = 0; j < N; ++j) {
    				if (n1[i] == n2[j] && n2[j] != Mark) {
    					++nc;
    					/* ensure cow is not rematched */
    					n2[j] = Mark;
    					break;
    				}
    			}
    		}
    	}
    
    	/* Return the results */
    
    	*nbulls = nb;  *ncows = nc;
    }
    
    
    Here is an interesting solution but it only handles odd numbers.
    #include <stdio.h>
    
    enum {
    	MAXIMUM_SIZE = 100
    };
    	
    int
    main(void) {
        int square[MAXIMUM_SIZE][MAXIMUM_SIZE];
        int x,y,i,j,size;
        
        printf("Enter the size of the magic square you wish to create: ");
        scanf("%d", &size);
        
        if (size >= MAXIMUM_SIZE) {
            printf("Sorry the size has to be smaller than %d\n", MAXIMUM_SIZE);
            return 1;
        }
        
        if (size % 2 != 1) {
            printf("Sorry the size has to be an odd number.\n");
            return 1;
        }
        
        x = size*size + size/2;
        y = size*size;
        
        for (i = 1; i <= size*size; i++) {
            square[x % size][y % size] = i;
            if (i % size == 0) {
                y++;
            } else {
                x--;
                y--;
            }
        }
        
        for (i = 0; i < size; i++) {
            for (j = 0; j < size; j++)
                printf("%4d ", square[j][i]);
            printf("\n");   
        }
        
        return 0;
    }