#include <stdio.h>

#define MIN(a,b) (((a)<(b))?(a):(b))

struct dictionary{
  int value;
  int count;
  struct dictionary* next;

};
typedef struct dictionary item;


item* hash(item* head,int index){
  item* iterator = head;
  while(iterator->next){
    if(iterator->value == index){
      return iterator;
    }
    iterator = iterator->next;
  }
  return NULL;
}

item* push(int v,int c,item* curr){
  curr->value = v;
  curr->count = c;
  curr->next = (item*)malloc(sizeof(item));
  return curr->next;
}



static int scores(int src[],int tgt[],int ax,int ay){
  int i,j,k;
  int scores[ax+1][ay+1];
  item *head,*curr,*temp;
  head = (item*)malloc(sizeof(item));
  curr = head;

  int INF = ax + ay;
  scores[0][0] = INF;

  /* handle blank strings */
  if(ax == 0){
    return ay;
  }else if(ay == 0){
   return ax;
  }

  /* setup scoring matrix */
  for(i=0;i<=ax;i++){
    scores[i+1][1] = i;
    scores[i+1][0] = INF;

    if(hash(head,src[i]) == NULL){
      curr = push(src[i],0,curr);
    }
  }
  for(j=0;j<=ay;j++){
    scores[1][j+1] = j;
    scores[0][j+1] = INF;

    if(hash(head,tgt[j]) == NULL){
      curr = push(tgt[j],0,curr);
    }
  }


  /* work loop */
  int db,i1,j1;
  for(i=1;i<=ax;i++){
    db = 0;
    for(j=1;j<=ay;j++){
      i1 = hash(head,tgt[j-1])->count;
      j1 = db;

      if(src[i-1] == tgt[j-1]){
        scores[i+1][j+1] = scores[i][j];
        db = j;
      }else{
        scores[i+1][j+1] = MIN(scores[i][j], MIN(scores[i+1][j], scores[i][j+1])) + 1;
      }

      scores[i+1][j+1] = MIN(scores[i+1][j+1], scores[i1][j1] + i - i1 - 1 + j - j1);
    }

    hash(head,src[i-1])->count = i;
  }

  return scores[ax+1][ay+1];
}



int main(void) {
    // Same code as cxs_distance
    // Left for ease of compiling outside of perl

    int arrSourcex[4];
    int arrTargetx[4];

    arrSourcex[0] = 1;
    arrSourcex[1] = 2;
    arrSourcex[2] = 3;
    arrSourcex[3] = 4;

    arrTargetx[0] = 1;
    arrTargetx[1] = 3;
    arrTargetx[2] = 2;
    arrTargetx[3] = 4;


    int lenSourcex2 = 4;
    int lenTargetx2 = 4;

    int x = scores(arrSourcex,arrTargetx,lenSourcex2,lenTargetx2);
    printf("%i\n",x);

    return x;
}