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

#define MAX_LEN 10000 /* 対応できる文字列の長さの上限 */

void swap_pointers(int **p2p1, int **p2p2) {
    /* ２つのポインタが指すアドレスを交換する */
    int *temp = *p2p1;
    *p2p1 = *p2p2;
    *p2p2 = temp;
}

int lowest(int values[], int n) { /* 整数の配列の中から最小値を返す */
    int lowest = values[0];
    int i = 0;
    for (i = 1; i < n; i++) {
        if (values[i] < lowest) {
            lowest = values[i];
        }
    }
    return lowest;
}

int eddist_iter(char *str1, char *str2, int len1, int len2) {
    /* （再帰呼び出しを使わずに）編集距離（レーベンシュタイン距離）を計算する関数
    str1, str2 は対象の文字列
    len1, len2 は文字列の長さ */
    int row1[MAX_LEN+1] = {0};
    int row2[MAX_LEN+1] = {0};
    int *prev = row1; /* 直前の行 */
    int *current = row2; /* 今見ている行 */
    int i, j;
    int opt[3];

    for (i = 0; i <= len1; i++) {
        for (j = 0; j <= len2; j++) {
            /* str1の終端に到達した場合、str2の残りの文字数を返す */
            if (i == 0) {
                current[j] = j;
            /* str2の終端に到達した場合、str1の残りの文字数を返す */
            } else if (j == 0) {
                current[j] = i;
            /* 両方の文字列が対象の位置に同じ文字を持つ場合、編集距離は増えない */
            } else if (str1[i-1] == str2[j-1]) {
                current[j] = prev[j-1];
            /* 対象の位置にある文字が異なる場合、可能な編集を全て検討し
            最小値を求める */
            } else {
                opt[0] = current[j-1]; /* str1に1文字を挿入することと同じ */
                opt[1] = prev[j]; /* str1から1文字を削除することと同じ */
                opt[2] = prev[j-1]; /* str1の1文字を置き換えることと同じ */
                current[j] = 1 + lowest(opt, 3);
            }
        }
        swap_pointers(&prev, &current); /* 今回調べた行（current）が今度 prev になる */
    }
    /* 処理が終わったら prev の最後の要素に最小距離が入っているのでそれを返す */
    return prev[len2];
}



int main() {
  
  char *lv1[] = {"anthem", "addicted", "crazy", "cassette", "curtain", "double", "everlasting", "gangster", "hoodstar", "hysteria", "imitation", "interlude", "lemonade", "louder", "legend", "navigator", "ordinary", "papercut", "perfect", "rollin", "rosy", "special", "strawberry", "telephone", "uncrushable"};

  char *lv2[] = {"Life_is_not_fair", "Whenever_you_call", "No_matter_the_time", "There's_nothing_in_this_world", "I_never_said_it_would_be_easy", "I'm_still_writing_all_this_love_for_you", "I_don't_know_what_I_have_done_to_you", "Cause_you_don't_wanna_talk", "But_it's_so_hard_to_tell_you_with_my_words", "Keep_going_my_way", "Just_do_it_believe_yourself"};

  char *lv3[] = {"The_odds_are_against_me._But_here_to_win_it._Oh_girl,_I'm_all_in_for_you._I_can't_stop_thinking_about_you._Can't_hide_it._Baby,_come_all_in_for_me.", "Girl,_you_slay_the_night_away._Put_me_in_a_daze._But_you're_with_another_man.", "Everyday_I_wake_up,_See_the_world_that's_brand_new._Some_places_I_can_never_go_back_for_good.", "Right,_Nothing_lasts_forever,_Yeah,_Nothing_but_our_love._I_wanna_build_a_brighter_future_for_the_world_to_come.", "Every_single_day,_The_world_just_keeps_on_changing._And_I_pray_that_we're_headed_for_the_happy_ending."};

  char line[100];
  char answer[100];
  int i, rv, level, dist;
  int sum=0;
  float total_len1=0;
  float total_len2=0;

  puts("---タイピングゲーム---");
  puts("難易度を選んでください");

  puts("1:初級");
  puts("2:中級");
  puts("3:上級");
  
  fgets(line, sizeof line, stdin);
  level = atoi(line);

  printf("\n");

  time_t start = time(0);
  srand(start);
  
  switch(level) {
  case 1:
    for (i=0; i<10; i++) {
      rv = rand() % 25;
      while(1) {
	printf("第%d問: %s\n", i+1, lv1[rv]);
	scanf("%s", answer);
	printf("\n");
	total_len1 += strlen(lv1[rv]);
        total_len2 += strlen(answer);
	dist = eddist_iter(lv1[rv], answer, strlen(lv1[rv]), strlen(answer));
        sum += dist;
	break;
      }
    }
    printf("正答率: %.2f %%\n", (total_len2 - sum) / total_len1 * 100);
    printf("時間: %d 秒\n", time(0)-start);
    break;
  case 2:
    for (i=0; i<5; i++) {
      rv = rand() % 11;
      while(1) {
	printf("第%d問: %s\n", i+1, lv2[rv]);
	scanf("%s", answer);
	printf("\n");
	total_len1 += strlen(lv2[rv]);
        total_len2 += strlen(answer);
	dist = eddist_iter(lv2[rv], answer, strlen(lv2[rv]), strlen(answer));
	sum += dist;
	break;
      }
    }
    printf("正答率: %.2f %%\n", (total_len2 - sum) / total_len1 * 100);
    printf("時間: %d 秒\n", time(0)-start);
    break;
  case 3:
    for (i=0; i<3; i++) {
      rv = rand() % 5;
      while(1) {
	printf("第%d問: %s\n", i+1, lv3[rv]);
	scanf("%s", answer);
	printf("\n");
	total_len1 += strlen(lv3[rv]);
        total_len2 += strlen(answer);
	dist = eddist_iter(lv3[rv], answer, strlen(lv3[rv]), strlen(answer));
	sum += dist;
	break;
      }
    }
    printf("正答率: %.2f %%\n", (total_len2 - sum) / total_len1 * 100);
    printf("時間: %d 秒\n", time(0)-start);
    break;
  default:
    printf("1〜3の数字をで入力してください\n");
  }
  return 0;
}