Nonogram Solver

Greedy Alogrithm

How to measure the number of segments?

• Fills on the edge doesn't count

|Line|# Segments|Fills|Holes| |---|---|---|---|---| |[0,0,0,0]|0|[]|[1,2,3,4]| |[1,0,0,0]|1|[0]|[2,3,4]| |[1,1,0,0]|1|[0,1]|[2,3]| |[0,0,1,0]|1|[2]|[0,1,3]| |[1,0,1,0]|2|[0,2]|[1,3]| |[0,1,1,0]|1|[1,2]|[0,3]| |[1,1,1,0]|1|[0,1,2]|[3]| |[0,0,0,1]|1|[3]|[0,1,2]| |[1,0,0,1]|2|[0,3]|[1,2]| |[0,1,0,1]|2|[1,3]|[0,2]| |[1,1,0,1]|2|[0,1,3]|[2]| |[0,0,1,1]|1|[2,3]|[0,1]| |[1,0,1,1]|2|[0,2,3]|[1]| |[0,1,1,1]|1|[1,2,3]|[0]| |[1,1,1,1]|1|[0,1,2,3]|[]|

• Need a function that f(arrFills) = # of segments
  • idea ON-OFF flip flop
    • Add one when 0->1 occurs; reset when 1->0
    • Time complexity: O(n)

#Julia
function seg_conunt(arr)
  count = 0 
  n_seg = 0
  for i in arr
    if count == 0
      if i == 1
        count = 1
        n_seg += 1
      end
    else
      if i == 0
        count = 0
      end
    end
  end

  return n_seg
end

Create 2D array with double pointer and one malloc call

#include<stdio.h> 
#include<stdlib.h> 
  
int main() 
{ 
    int r=3, c=4, len=0; 
    int *ptr, **arr; 
    int count = 0,i,j; 
  
    len = sizeof(int *) * r + sizeof(int) * c * r; 
    arr = (int **)malloc(len); 
  
    // ptr is now pointing to the first element in of 2D array 
    ptr = (int *)(arr + r); 
  
    // for loop to point rows pointer to appropriate location in 2D array 
    for(i = 0; i < r; i++) 
        arr[i] = (ptr + c * i); 
  
    for (i = 0; i < r; i++) 
        for (j = 0; j < c; j++) 
            arr[i][j] = ++count; // OR *(*(arr+i)+j) = ++count 
  
    for (i = 0; i < r; i++) 
        for (j = 0; j < c; j++) 
            printf("%d ", arr[i][j]); 
  
    return 0; 
} 

Git tag

• Add tag

  git tag -a v0.0.1 -m "my version 1.4"

• Push tag

  git push origin v0.0.1

Header files

It is not recommended to put function definitions in a header file. Ideally there should be only function declarations. Purpose of this code is to only demonstrate working of header files.

Implementation of dynamic 1D array

typedef struct {
  int *array;
  size_t used;
  size_t size;
} Array;

void initArray(Array *a, size_t initialSize) {
  a->array = malloc(initialSize * sizeof(int));
  a->used = 0;
  a->size = initialSize;
}

void insertArray(Array *a, int element) {
  // a->used is the number of used entries, because a->array[a->used++] updates a->used only *after* the array has been accessed.
  // Therefore a->used can go up to a->size 
  if (a->used == a->size) {
    a->size *= 2;
    a->array = realloc(a->array, a->size * sizeof(int));
  }
  a->array[a->used++] = element;
}

void freeArray(Array *a) {
  free(a->array);
  a->array = NULL;
  a->used = a->size = 0;
}

Usage

Array a;
int i;

initArray(&a, 5);  // initially 5 elements
for (i = 0; i < 100; i++)
  insertArray(&a, i);  // automatically resizes as necessary
printf("%d\n", a.array[9]);  // print 10th element
printf("%d\n", a.used);  // print number of elements
freeArray(&a);

https://stackoverflow.com/questions/3536153/c-dynamically-growing-array

Use realloc to increase or shrink the size.

How to read line in a file

void read_file(void){

    FILE *stream = fopen("test/data/output_1.txt", "r");
    char line[80];

    while ((fscanf(stream, "%[^\n]", line))!= EOF)
    {
        fgetc(stream); // Reads in '\n' character and moves file
        // stream past delimiting character
        printf("%s \n", line);
    }

    fclose(stream);
}

Add test file

'input_3.txt'

Reference

1. 2D array construction. [GreekforGeek]
2. Git tag. [Blog]
3. Integer to string: itoa. [Blog]
4. Compare with memcpy [Tutorial]
   • 不能用於 struct [reason]
5. Memory management in C [tutorial]
6. fscanf: reading file in C. [greekforgeek]
7. How to pass 2D array. [GreekforGeek]