Diff in C

diff.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct list {
  int x, y;
  struct list *tail;
};

void main(void) {
  int i, j, k;
  
  char *s1 = "xthe cat jumped gracefully on the counter";
  char *s2 = "ythe dog jumped clumsily on the couch";

  int w = strlen(s1);
  int h = strlen(s2);

  int *cost = malloc((w+1)*(h+1)*sizeof(int));
  for(j = 0; j < h+1; j++) {
    for(i = 0; i < w+1; i++) {
      cost[i+(w+1)*j] = -1;
    }
  }

#define PRINT_GRID()                            \
  for(j = 0; j < h+1; j++) {                    \
    for(i = 0; i < w+1; i++) {                  \
      printf("%3d ", cost[i+(w+1)*j]);          \
    }                                           \
    printf("\n");                               \
  }                                             \
  printf("\n");
  
  PRINT_GRID();

  struct list* crest = malloc((w+1)*(h+1)*sizeof(struct list));
  int next = 0;
  crest[next].x = w;
  crest[next].y = h;
  crest[next].tail = NULL;
  cost[crest[0].x+(w+1)*crest[0].y] = 0;
  next++;

  PRINT_GRID();

  struct list* l;
  struct list* mytail = &(crest[next-1]);

  int done = 0;
  while(!done) {
    l = mytail;
    mytail = NULL;
    
    while(l) {
      if(l->x == 0 && l->y == 0) {
        done = 1;
        break;
      }

      if(l->x > 0) {
        if(cost[l->x-1+(w+1)*l->y] == -1) {
          crest[next].x = l->x-1;
          crest[next].y = l->y;
          crest[next].tail = mytail;
          mytail = &(crest[next]);
          cost[crest[next].x+(w+1)*crest[next].y] = 1+cost[l->x+(w+1)*l->y];
          next++;
        }
        else if(cost[l->x-1+(w+1)*l->y] > 1+cost[l->x+(w+1)*l->y]) {
          cost[l->x-1+(w+1)*l->y] = 1+cost[l->x+(w+1)*l->y];
        }
      }

      if(l->y > 0) {
        if(cost[l->x+(w+1)*(l->y-1)] == -1) {
          crest[next].x = l->x;
          crest[next].y = l->y-1;
          crest[next].tail = mytail;
          mytail = &(crest[next]);
          cost[crest[next].x+(w+1)*crest[next].y] = 1+cost[l->x+(w+1)*l->y];
          next++;
        }
        else if(cost[l->x+(w+1)*(l->y-1)] > 1+cost[l->x+(w+1)*l->y]) {
          cost[l->x+(w+1)*(l->y-1)] = 1+cost[l->x+(w+1)*l->y];
        }
      }

      if(l->x > 0 && l->y > 0 && s1[l->x-1] == s2[l->y-1]) {
        if(cost[l->x-1+(w+1)*(l->y-1)] == -1) {
          crest[next].x = l->x-1;
          crest[next].y = l->y-1;
          crest[next].tail = mytail;
          mytail = &(crest[next]);
          cost[crest[next].x+(w+1)*crest[next].y] = 1+cost[l->x+(w+1)*l->y];
          next++;
        }
        else if(cost[l->x-1+(w+1)*(l->y-1)] > 1+cost[l->x+(w+1)*(l->y)]) {
          cost[l->x-1+(w+1)*(l->y-1)] = 1+cost[l->x+(w+1)*(l->y)];
        }
      }
      
      l = l->tail;
    }
    
    PRINT_GRID();
  }
  
  int x = 0, y = 0;
  int best, this_cost;
  int move;

  int mode = 0;
  int mode_same = 1;
  
  while(x != w || y != h) {
    best = -1;
    
    if(x < w) {
      // consider going right
      this_cost = cost[(x+1)+(w+1)*y];
      
      if(best == -1 || this_cost <= best) {
        best = this_cost;
        move = 0;
      }
    }
    
    if(y < h) {
      // consider going down
      this_cost = cost[x+(w+1)*(y+1)];
      
      if(best == -1 || this_cost <= best) {
        best = this_cost;
        move = 1;
      }
    }
    
    if(x > 0 && y > 0 && x < w && y < h && s1[x] == s2[y]) {
      // consider going diagonally
      this_cost = cost[(x+1)+(w+1)*(y+1)];
      
      if(best == -1 || this_cost <= best) {
        best = this_cost;
        move = 2;
      }
    }
    
    mode_same = move == mode;
    mode = move;
    switch(move) {
    case 0:
      if (!mode_same) { printf("\n+"); }
      printf("%c", s1[x]);
      x++;
      break;
    case 1:
      if (!mode_same) { printf("\n-"); }
      printf("%c", s2[y]);
      y++;
      break;
    case 2:
      if (!mode_same) { printf("\n"); }
      printf("%c", s1[x]);
      x++;
      y++;
      break;
    }
    /*
    switch(move) {
    case 0:
      printf("+ %c \n", s1[x]);
      x++;
      break;
    case 1:
      printf("- %c \n", s2[y]);
      y++;
      break;
    case 2:
      printf("  %c %c\n", s1[x], s2[y]);
      x++;
      y++;
      break;
    }
    */
  }
  puts("");
  
  printf("survived\n");
}

run.txt

$ gcc diff.c -o diff && ./diff
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 

 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1   0 

 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1   1 
 -1  -1  -1  -1  -1  -1   1   0 

 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1   2   2 
 -1  -1  -1  -1  -1  -1   2   1 
 -1  -1  -1  -1  -1   2   1   0 

 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1   3   3   3 
 -1  -1  -1  -1  -1   3   2   2 
 -1  -1  -1  -1  -1   3   2   1 
 -1  -1  -1  -1   3   2   1   0 

 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1  -1   4   4   4 
 -1  -1  -1  -1   4   3   3   3 
 -1  -1  -1  -1   4   3   2   2 
 -1  -1  -1  -1   4   3   2   1 
 -1  -1  -1   4   3   2   1   0 

 -1  -1  -1  -1  -1  -1  -1  -1 
 -1  -1  -1  -1   5   5   5   5 
 -1  -1  -1   5   5   4   4   4 
 -1  -1  -1   5   4   3   3   3 
 -1  -1  -1   5   4   3   2   2 
 -1  -1   5   5   4   3   2   1 
 -1  -1   5   4   3   2   1   0 

 -1  -1  -1  -1   6   6   6   6 
 -1  -1  -1   6   5   5   5   5 
 -1  -1   6   5   5   4   4   4 
 -1  -1   6   5   4   3   3   3 
 -1  -1   6   5   4   3   2   2 
 -1   6   5   5   4   3   2   1 
 -1   6   5   4   3   2   1   0 

 -1  -1   7   7   6   6   6   6 
 -1   7   7   6   5   5   5   5 
 -1   7   6   5   5   4   4   4 
 -1   7   6   5   4   3   3   3 
  7   7   6   5   4   3   2   2 
  7   6   5   5   4   3   2   1 
  7   6   5   4   3   2   1   0 

 -1   8   7   7   6   6   6   6 
  8   7   7   6   5   5   5   5 
  8   7   6   5   5   4   4   4 
  8   7   6   5   4   3   3   3 
  7   7   6   5   4   3   2   2 
  7   6   5   5   4   3   2   1 
  7   6   5   4   3   2   1   0 

  9   8   7   7   6   6   6   6 
  8   7   7   6   5   5   5   5 
  8   7   6   5   5   4   4   4 
  8   7   6   5   4   3   3   3 
  7   7   6   5   4   3   2   2 
  7   6   5   5   4   3   2   1 
  7   6   5   4   3   2   1   0 

  9   8   7   7   6   6   6   6 
  8   7   7   6   5   5   5   5 
  8   7   6   5   5   4   4   4 
  8   7   6   5   4   3   3   3 
  7   7   6   5   4   3   2   2 
  7   6   5   5   4   3   2   1 
  7   6   5   4   3   2   1   0 

- c 
+ a 
  b b
+ c 
  a a
  b b
+ b 
  a a
- c 
survived

zzzz

$ cat t1.txt 
c
b
a
b
a
c

$ cat t2.txt 
a
b
c
a
b
b
a

$ diff t1.txt t2.txt 
1c1
< c
---
> a
2a3
> c
4a6
> b
6d7
< c



the cat jumped gracefu   lly on the cou  nter
    ^^^        ^^^ ^^ xxx              xx
the dog jumped    c lumsil y on the couch

the
-dog
+cat
 jumped 
+gra
c
-l
+ef
u
-msi
l
+l
y on the cou
-ch
+nter
survived