Small programming challenges

flip_region.cc

// Given a boolean matrix, and a point (x, y) you need to
// change the values for all the adjacent (x1, y1) such that |x-x1| + |y-y1| = 1
// (neighbors with adjacent side)

#define flip!(x, y) matrix[x][y] = !matrix[x][y]

int xs = {-1, 0, 1, 0};
int ys = {0, 1, 0, -1};

bool visited[D+1][D+1];
bool matrix[D+1][D+1];

bool inside(x, y){
  return (x >= 0) && (x < D) && (y >= 0) && (y < D);
}

void flip_it(int x, int y){
  visited[x][y] = true;

  for(int i=0; i<4;++i){
    int nx = x + xs[i];
    int ny = y + ys[i];
    if(inside(nx, ny) && a[x][y] == a[nx][ny] && !visited[nx][ny]){
      flip_it(nx, ny);
    }
  }
  flip!(x, y);
}

merge_sort.cc

template<typename T>

void combine(vector<T> &s, int low, int middle, int high){
  queue<int> left, right;
  for(int i=low; i <= middle; ++i) left.push(s[i]);
  for(int i=middle + 1; i <= high; ++i) right.push(s[i]);
  int index = low;
  while(left.size() && right.size()){
    if(left.front() < right.front()){
      s[index++] = left.front();
      left.pop();
    }else{
      s[index++] = right.front();
      right.pop();
    }
  }
  while(left.size()) { s[index++] = left.front();  left.pop(); }
  while(right.size()){ s[index++] = right.front(); right.pop();}
}

void merge_sort(vector<T> &s, int low, int high){
  int middle = (low + high) / 2;
  if(low >= high) return;
  merge_sort(s, low, middle);
  merge_sort(s, middle + 1, high);
  combine(s, low, middle, high);
}

quick_sort.cc

template <typename T>

void dutch_flag_partition(vector<T> &A, int from, int to){
  /**
   * bottom group: A[0..smaller - 1]
   * middle group: A[smaller..equal - 1]
   * unclassified: A[equal..larger - 1]
   * top group:    A[larger..A.size - 1]
   **/
  int pivot_index = (from + to) / 2;
  int pivot = A[pivot_index];

  if(from >= to) return;

  int smaller = from, equal = from, larger = to - 1;
  while(equal <= larger){
    int element = A[equal];
    if(element < pivot){
      swap(A[equal++], A[smaller++]);
    }else if(element == pivot){
      equal++;
    }else{
      swap(A[equal], A[larger--]);
    }
  }
  dutch_flag_partition(A, from, smaller);
  dutch_flag_partition(A, equal, to);
}

spiral_matrix.cc

// Print a matrix in spiral order
vector<vector<int> > a(7, vector<int>(7, 0));

void do_ring(int ring, int n){
  int i, j;
  i = j = ring;
  for(j = ring; j < n - ring ; ++j) cout << a[i][j] << " ";

  j = n - ring - 1;
  for(i = ring + 1; i < n - ring; ++i) cout << a[i][j] << " ";

  i = n - ring - 1;
  for(j = n - ring - 2; j >= ring; --j) cout << a[i][j] << " ";
  
  j = ring;
  for(i = n - ring - 2; i > ring; --i) cout << a[i][j] << " ";
}


int main(){
  for(int ring=0;ring < ceil(a.size() / 2.0); ++ring)
    do_ring(ring, a.size());
}