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

// The wordle word list (or at least an approximation to it) is in a flat array,
// but in two sections: the initial words are relatively common words, sorted by
// frequency of use in English.  Those are followed by less common words, in
// alphabetical order (although order is not significant within this section).
// The count of common words is COMMON_COUNT and the total count of all words
// is ALLOWED_MAX.  This partitioning of the words was more space efficient
// than having two separate word lists.

#include "sorted.h"

int MAX_WORDS = ALLOWED_MAX;

enum { WORDLEN = 5, MAXTURNS = 6, SCORE_BUCKETS = 243 };
enum { ABSENT = 0, GREEN = 1, YELLOW = 2 };

#define VERSION "$Id: w.c,v 1.9 2026/08/02 06:11:07 gtoal Exp gtoal $"

typedef struct {
  unsigned int not_pos[WORDLEN];
  int fixed[WORDLEN];
  unsigned char min_count[26];
  unsigned char max_count[26];
} constraint_t;

typedef struct {
  clock_t start;
  clock_t limit;
  int timed_out;
} time_budget_t;

typedef struct {
  int enabled;
  int idx;
  char word[WORDLEN];
} hidden_t;

static int debug_mode = 0;  // enable with --debug
static int tried_words[6];
static int tried_count = 0;

int is_tried_word(int idx) {
  for (int i = 0; i < tried_count; i++) {
    if (idx == tried_words[i]) return 1;
  }
  return 0;
}

static hidden_t hidden = {0, -1, {0}};

static int letter_index(int ch) {
  ch = toupper((unsigned char)ch);
  return ch - 'A';
}

static void upcase5(char dst[WORDLEN], const char *src) {
  int i;
  for (i = 0; i < WORDLEN; i++) dst[i] = (char)toupper((unsigned char)src[i]);
}

static char *upcase(const char *src) {
  static char word[WORDLEN];
  for (int i = 0; i < WORDLEN; i++) word[i] = (char)toupper((unsigned char)src[i]);
  return word;
}

static char *downcase(const char *src) {
  static char word[WORDLEN];
  for (int i = 0; i < WORDLEN; i++) word[i] = (char)tolower((unsigned char)src[i]);
  return word;
}

static int same_word5(const char *a, const char *b) {
  int i;
  for (i = 0; i < WORDLEN; i++) {
    if (toupper((unsigned char)a[i]) != toupper((unsigned char)b[i])) return 0;
  }
  return 1;
}

static int find_allowed_index(const char *w) {
  int i;
  for (i = 0; i < MAX_WORDS; i++) {
    if (same_word5(allowed[i], w)) return i;
  }
  return -1;
}

static void constraint_init(constraint_t *c) {
  int i;
  memset(c, 0, sizeof(*c));
  for (i = 0; i < WORDLEN; i++) c->fixed[i] = -1;
  for (i = 0; i < 26; i++) c->max_count[i] = WORDLEN;
}

static void calculate_score(const char *guess, const char *secret, int score[WORDLEN]) {
  int i;
  int remaining[26];

  memset(remaining, 0, sizeof(remaining));
  for (i = 0; i < WORDLEN; i++) score[i] = ABSENT;

  for (i = 0; i < WORDLEN; i++) {
    int g = letter_index(guess[i]);
    int s = letter_index(secret[i]);
    if (g == s)
      score[i] = GREEN;
    else
      remaining[s]++;
  }

  for (i = 0; i < WORDLEN; i++) {
    int g;
    if (score[i] != ABSENT) continue;
    g = letter_index(guess[i]);
    if (remaining[g] > 0) {
      score[i] = YELLOW;
      remaining[g]--;
    }
  }
}

static void update_constraints(constraint_t *c, const char *guess, const int score[WORDLEN]) {
  int i;
  int hits[26];
  int misses[26];

  memset(hits, 0, sizeof(hits));
  memset(misses, 0, sizeof(misses));

  for (i = 0; i < WORDLEN; i++) {
    int li = letter_index(guess[i]);
    if (score[i] == GREEN) {
      c->fixed[i] = li;
      hits[li]++;
    } else if (score[i] == YELLOW) {
      c->not_pos[i] |= (1u << li);
      hits[li]++;
    } else {
      misses[li]++;
    }
  }

  for (i = 0; i < 26; i++) {
    if (hits[i] > c->min_count[i]) c->min_count[i] = hits[i];
    if (misses[i] > 0 && hits[i] < c->max_count[i]) c->max_count[i] = (unsigned char)hits[i];
  }
}

static int word_matches_constraint(const char *w, const constraint_t *c) {
  int i, counts[26];

  memset(counts, 0, sizeof(counts));

  for (i = 0; i < WORDLEN; i++) {
    int li = letter_index(w[i]);
    if (c->fixed[i] >= 0 && li != c->fixed[i]) return 0;
    if (c->not_pos[i] & (1u << li)) return 0;
    counts[li]++;
  }

  for (i = 0; i < 26; i++) {
    if (counts[i] < c->min_count[i]) return 0;
    if (counts[i] > c->max_count[i]) return 0;
  }

  return 1;
}

static int build_candidates(const constraint_t *c, int *indices/*[ALLOWED_MAX]*/) {
  int n = 0;
  for (int i = 0; i < MAX_WORDS; i++) if (word_matches_constraint(allowed[i], c)) indices[n++] = i;
  return n;
}

static int all_green(const int score[WORDLEN]) {
  for (int i = 0; i < WORDLEN; i++) if (score[i] != GREEN) return 0;
  return 1;
}

static int parse_scored_word(char guess[WORDLEN], int score[WORDLEN]) {
  int c, got = 0, colour = 0, anything = 0;
  for (;;) {
    c = fgetc(stdin);
    if (c == EOF || ferror(stdin)) return 0;
    if (c == ' ' || c == '\t' || c == '\r') continue;

    if (isalpha((unsigned char)c)) {
      if (got >= WORDLEN) {
        fprintf(stderr, "Too many letters.\n");
        return 0;
      }
      guess[got] = (char)toupper((unsigned char)c);
      score[got] = colour;
      got++;
      anything = 1;
      continue;
    }

    if (c == '[') {
      if (colour & YELLOW) {
        fprintf(stderr, "Mismatched '['.\n");
        return 0;
      }
      colour |= GREEN;
      anything = 1;
      continue;
    }

    if (c == '{') {
      if (colour & GREEN) {
        fprintf(stderr, "Mismatched '{'.\n");
        return 0;
      }
      colour |= YELLOW;
      anything = 1;
      continue;
    }

    if (c == ']') {
      colour &= ~GREEN;
      anything = 1;
      continue;
    }

    if (c == '}') {
      colour &= ~YELLOW;
      anything = 1;
      continue;
    }

    if (c == '\n') {
      if (colour != 0) {
        fprintf(stderr, "Unclosed [] or {}.\n");
        return 0;
      }
      if (!anything) continue;
      if (got != WORDLEN) {
        fprintf(stderr, "Need exactly 5 letters.\n");
        return 0;
      }
      return 1;
    }

    fprintf(stderr, "Unexpected character '%c'.\n", c);
    return 0;
  }
}

static void print_scored_guess(const char *guess, const int score[WORDLEN], FILE *out) {
  int i;

  for (i = 0; i < WORDLEN; i++) {
    if (score[i] == GREEN)
      fputc('[', out);
    else if (score[i] == YELLOW)
      fputc('{', out);
    fputc(toupper((unsigned char)guess[i]), out);
    if (score[i] == GREEN)
      fputc(']', out);
    else if (score[i] == YELLOW)
      fputc('}', out);
  }
}

static unsigned int encode_score(const int score[WORDLEN]) {
  unsigned int code = 0;
  int i;
  for (i = 0; i < WORDLEN; i++) code = code * 3u + (unsigned int)score[i];
  return code;
}

static int time_exceeded(time_budget_t *tb) {
  if (tb->timed_out) return 1;
  if ((clock() - tb->start) >= tb->limit) {
    tb->timed_out = 1;
    return 1;
  }
  return 0;
}

static long int evaluate_guess_letters(int guess_idx, const constraint_t *c) {
  unsigned int seen = 0;
  long int score = 0;
  int k;

  for (k = 0; k < WORDLEN; k++) {
    int li = letter_index(allowed[guess_idx][k]);
    unsigned int bit = 1u << li;

    if ((seen & bit) == 0) {
      seen |= bit;
      if (c->min_count[li] == c->max_count[li] && c->max_count[li] > 0)
        score -= 3;
      else
        score += 4;
    } else {
      score -= 2;
    }

    if (c->fixed[k] == -1 && (c->not_pos[k] & bit) == 0) score += 1;
  }

  return score;
}

static long int evaluate_guess_partition(int guess_idx, const int *candidates, int candidate_count,
                                         const constraint_t *c) {
  unsigned int buckets[SCORE_BUCKETS];
  int score[WORDLEN];
  int i;
  long int sumsq = 0;
  unsigned int max_bucket = 0;
  long int tie;

  memset(buckets, 0, sizeof(buckets));
  for (i = 0; i < candidate_count; i++) {
    calculate_score(allowed[guess_idx], allowed[candidates[i]], score);
    buckets[encode_score(score)]++;
  }

  for (i = 0; i < SCORE_BUCKETS; i++) {
    unsigned int b = buckets[i];
    if (b > max_bucket) max_bucket = b;
    sumsq += (long int)b * (long int)b;
  }

  tie = evaluate_guess_letters(guess_idx, c);
  if (guess_idx < COMMON_COUNT) tie += 500;

  return -(sumsq * 1000L + (long int)max_bucket) * 1000L + tie;
}

static void sort_guess_order(int *order, int count, const int *candidates, int candidate_count,
                             const constraint_t *c) {
  int i, j;
  long int *values = malloc((size_t)count * sizeof(long int));

  if (!values) exit(1);

  for (i = 0; i < count; i++) {
    values[i] = evaluate_guess_partition(order[i], candidates, candidate_count, c);
  }

  for (i = 0; i < count - 1; i++) {
    for (j = i + 1; j < count; j++) {
      if (values[j] > values[i]) {
        long int tv = values[i];
        int ti = order[i];
        values[i] = values[j];
        values[j] = tv;
        order[i] = order[j];
        order[j] = ti;
      }
    }
  }

  free(values);
}

static int build_order_list(int *order, const constraint_t *c, const int *candidates, int candidate_count,
                            int hard_mode, int probe_all) {
  unsigned char seen[ALLOWED_MAX];
  int i, n = 0;

  memset(seen, 0, sizeof(seen));

  for (i = 0; i < candidate_count; i++) {
    int idx = candidates[i];
    if (!seen[idx]) {
      seen[idx] = 1;
      order[n++] = idx;
    }
  }

  if (!hard_mode) {
    for (i = 0; i < MAX_WORDS; i++) {
      if (!seen[i] && word_matches_constraint(allowed[i], c) && !is_tried_word(i)) {
        seen[i] = 1;
        order[n++] = i;
      }
    }
  }

  return n;
}

static int exact_solve(const int *candidates, int candidate_count, int moves_left, int allow_probe,
                       const constraint_t *c, time_budget_t *tb, int *best_guess, int hard_mode) {
  int *order;
  int order_count = 0;
  int i;

  if (time_exceeded(tb)) return 0;
  if (candidate_count <= 0) return 0;
  if (candidate_count == 1) {
    if (best_guess) *best_guess = candidates[0];
    return 1;
  }
  if (moves_left <= 1) return 0;
  if (candidate_count > moves_left * moves_left * 4 && !allow_probe) return 0;

  order = malloc((size_t)MAX_WORDS * sizeof(int));
  if (!order) exit(1);

  order_count = build_order_list(order, c, candidates, candidate_count, hard_mode, allow_probe);
  sort_guess_order(order, order_count, candidates, candidate_count, c);
  if (order_count > 24) order_count = 24;

  for (i = 0; i < order_count; i++) {
    int guess_idx = order[i];
    int bucket_count[SCORE_BUCKETS];
    int bucket_offset[SCORE_BUCKETS];
    int bucket_fill[SCORE_BUCKETS];
    int *bucketed;
    int ok = 1;
    int bucket;
    int pos;
    int cidx;

    if (time_exceeded(tb)) {
      free(order);
      return 0;
    }

    memset(bucket_count, 0, sizeof(bucket_count));
    bucketed = malloc((size_t)candidate_count * sizeof(int));
    if (!bucketed) exit(1);

    for (cidx = 0; cidx < candidate_count; cidx++) {
      int sc[WORDLEN];
      unsigned int key;
      calculate_score(allowed[guess_idx], allowed[candidates[cidx]], sc);
      key = encode_score(sc);
      bucket_count[key]++;
    }

    pos = 0;
    for (bucket = 0; bucket < SCORE_BUCKETS; bucket++) {
      bucket_offset[bucket] = pos;
      bucket_fill[bucket] = 0;
      pos += bucket_count[bucket];
    }

    for (cidx = 0; cidx < candidate_count; cidx++) {
      int sc[WORDLEN];
      unsigned int key;
      int dst;
      calculate_score(allowed[guess_idx], allowed[candidates[cidx]], sc);
      key = encode_score(sc);
      dst = bucket_offset[key] + bucket_fill[key]++;
      bucketed[dst] = candidates[cidx];
    }

    for (bucket = 0; bucket < SCORE_BUCKETS; bucket++) {
      int next_best;
      int count = bucket_count[bucket];

      if (count == 0) continue;
      if (count == candidate_count) {
        ok = 0;
        break;
      }
      if (count == 1) continue;

      if (!exact_solve(&bucketed[bucket_offset[bucket]], count, moves_left - 1, allow_probe, c, tb, &next_best,
                       hard_mode)) {
        ok = 0;
        break;
      }

      if (time_exceeded(tb)) {
        free(bucketed);
        free(order);
        return 0;
      }
    }

    free(bucketed);

    if (ok) {
      if (best_guess) *best_guess = guess_idx;
      free(order);
      return 1;
    }
  }

  free(order);
  return 0;
}

static int choose_best_guess_hybrid(constraint_t *c,
                                    const int *candidates, int n_all,
                                    int moves_left, int hard_mode,
                                    clock_t limit_ticks, int *used_exact, int *timed_out) {
  int best;
  int *order;
  int order_count;
  time_budget_t tb;
  int exact_count;
  const int *exact_candidates;

  *used_exact = 0;
  *timed_out = 0;

  if (n_all <= 0) return -1; else if (n_all == 1) return candidates[0];

  exact_candidates = candidates; exact_count = n_all;

  if (exact_count <= 18 && moves_left >= 2) {
    tb.start = clock();
    tb.limit = limit_ticks;
    tb.timed_out = 0;
    if (exact_solve(exact_candidates, exact_count, moves_left, !hard_mode /*allow_probe*/, c, &tb, &best, hard_mode)) {
      *used_exact = 1; *timed_out = tb.timed_out;
      return best;
    }
    *used_exact = 1;
    *timed_out = tb.timed_out;
  }

  order = malloc((size_t)MAX_WORDS * sizeof(int));
  if (!order) exit(1);

  order_count = build_order_list(order, c, candidates, n_all, hard_mode, !hard_mode /*allow_probe*/);
  if (order_count <= 0) {
    free(order);
    return -1;
  }

  sort_guess_order(order, order_count, candidates, n_all, c);
  best = order[0];
  free(order);
  return best;
}

static void self_test_solver(const char *start_word, int hard_mode) {
  int secret;
  char start[WORDLEN];

  upcase5(start, start_word);

  for (secret = 0; secret < COMMON_COUNT; secret++) {
    int secret_idx = find_allowed_index(allowed[secret]);
    constraint_t c;
    int score[WORDLEN];
    int candidates[ALLOWED_MAX];
    char guess[WORDLEN];
    char linebuf[1024];
    size_t used = 0;
    int solved = 0;
    int turn;
    int len;
    time_budget_t game_tb;

    if (secret_idx < 0) continue;

    tried_count = 0;
    constraint_init(&c);
    memcpy(guess, start, WORDLEN);
    linebuf[0] = '\0';
    game_tb.start = clock();
    game_tb.limit = CLOCKS_PER_SEC * 3;  // 3 sec
    game_tb.timed_out = 0;

    for (turn = 1; turn <= MAXTURNS; turn++) {
      int n_all, used_exact = 0, timed_out = 0;
      int best;
      int guess_idx = find_allowed_index(guess);

      if (guess_idx >= 0) {
        if (tried_count == 0 || tried_words[tried_count-1] != guess_idx) tried_words[tried_count++] = guess_idx;
      }
      if (used + WORDLEN + 2 < sizeof(linebuf)) {
        if (used != 0) linebuf[used++] = ' ';
        memcpy(&linebuf[used], guess, WORDLEN);
        used += WORDLEN;
        linebuf[used] = '\0';
      }

      calculate_score(guess, allowed[secret_idx], score);
      if (all_green(score)) {
        solved = 1;
        break;
      }

      if (time_exceeded(&game_tb)) break;

      update_constraints(&c, guess, score);
      n_all = build_candidates(&c, candidates);
      if (n_all <= 0) break;

      best = choose_best_guess_hybrid(&c,
                                      candidates, n_all,
                                      MAXTURNS - turn,
                                      hard_mode, CLOCKS_PER_SEC / 10, &used_exact, &timed_out);
      if (best < 0) break;
      if (time_exceeded(&game_tb)) break;

      memcpy(guess, allowed[best], WORDLEN);
    }

    len = (int)strlen(linebuf);
    if (!solved) {
      snprintf(linebuf + len, sizeof(linebuf) - (size_t)len, " ******** FAILURE **********");
    }
    printf("%.5s: %s\n", allowed[secret_idx], linebuf);
    fflush(stdout);
  }
}

static void usage(const char *argv0) {
  fprintf(stderr,
          "usage: %s [--debug] [--hard] [--hidden WORD] starting-word\n"
          "       %s [--debug] [--hard] [--hidden WORD] --selftest [starting-word]\n",
          argv0, argv0);
}

int main(int argc, char **argv) {
  constraint_t c;
  int score[WORDLEN];
  char guess[WORDLEN];
  int moves_used = 1;
  int argi = 1;
  int hard_mode = 0;
  int selftest = 0;
  int n_common = 0;
  const char *start_word = NULL;

  while (argi < argc && argv[argi][0] == '-') {
    if (strcmp(argv[argi], "--hard") == 0) {
      hard_mode = 1;
    } else if (strcmp(argv[argi], "--selftest") == 0) {
      selftest = 1;
    } else if (strcmp(argv[argi], "--common") == 0) {   // Common-only words
      MAX_WORDS = COMMON_COUNT;
    } else if (strcmp(argv[argi], "--debug") == 0) {
      debug_mode = 1;
    } else if (strcmp(argv[argi], "--hidden") == 0) {
      if (argi + 1 >= argc) {
        usage(argv[0]);
        return 1;
      }
      hidden.enabled = 1;
      upcase5(hidden.word, argv[++argi]);
      hidden.idx = find_allowed_index(hidden.word);
      if (hidden.idx < 0) {
        fprintf(stderr, "Hidden word %.5s is not in sorted.h\n", hidden.word);
        return 1;
      }
    } else if (*argv[argi] != '-') {
      start_word = argv[argi++];
    } else {
      fprintf(stderr, "Unknown option: %s\n", argv[argi]);
      usage(argv[0]);
      return 1;
    }
    argi++;
  }

  if (debug_mode) printf("Version: %s\n", VERSION);

  if (start_word == NULL && (argi < argc)) start_word = argv[argi++];
  if (start_word == NULL) {
    //start_word = "SLATE";
    //start_word = "CRANE";
    start_word = "TRACE";
    if (hard_mode) start_word = "TARPS";
  }
  if (argi != argc) {
    usage(argv[0]);
    return 1;
  }

  if (strlen(start_word) != WORDLEN) {
    fprintf(stderr, "Starting word must be 5 letters.\n");
    return 1;
  }

  if (find_allowed_index(start_word) < 0) {
    fprintf(stderr, "Starting word %.5s is not in sorted.h\n", start_word);
    return 1;
  }

  if (selftest) {
    self_test_solver(start_word, hard_mode);
    return 0;
  }

  tried_count = 0;
  constraint_init(&c);
  memset(score, 0, sizeof(score));
  upcase5(guess, start_word);

  fprintf(stderr, "Play %.5s and enter scored guesses using [] for green and {} for yellow.\n", start_word);
  if (hard_mode) fprintf(stderr, "Hard mode enabled.\n");
  if (debug_mode) fprintf(stderr, "Debug enabled.\n");
  if (hidden.enabled) fprintf(stderr, "Hidden scoring enabled for %.5s.\n", hidden.word);

  while (moves_used <= MAXTURNS) {
    int candidates[ALLOWED_MAX];
    int n_all, used_exact = 0, timed_out = 0;
    int best;
    int blank_score[WORDLEN] = {0, 0, 0, 0, 0};
    int moves_left;
    int guess_idx;

    fprintf(stderr, "> ");

    if (hidden.enabled) {
      int sc[WORDLEN];
      calculate_score(guess, hidden.word, sc);
      memcpy(score, sc, sizeof(score));
      print_scored_guess(guess, score, stderr);
      fprintf(stderr, "\n");
    } else {
      if (!parse_scored_word(guess, score)) return 1;
    }

    guess_idx = find_allowed_index(guess);
    if (guess_idx >= 0) {
      if (tried_count == 0 || tried_words[tried_count-1] != guess_idx) tried_words[tried_count++] = guess_idx;
    }

    if (all_green(score)) {
      printf("Solved.\n");
      return 0;
    }

    if (moves_used >= MAXTURNS) {
      printf("Failed to solve within %d guesses.\n", MAXTURNS);
      return 0;
    }

    update_constraints(&c, guess, score);
    n_all = build_candidates(&c, candidates);
    n_common = 0;
    for (int i = 0; i < n_all; i++) {
      if (candidates[i] < COMMON_COUNT) n_common += 1;
    }

    printf("%d valid candidates remain, of which %d are common words\n", n_all, n_common);

    if (debug_mode && hard_mode && n_all > 0 && n_all <= 5) {
      fprintf(stderr, "DEBUG candidates:");
      for (int i = 0; i < n_all; i++) {
        fprintf(stderr, " %.5s", (candidates[i] >= COMMON_COUNT ? downcase(allowed[candidates[i]]) : upcase(allowed[candidates[i]])));
      }
      fprintf(stderr, "\n");
    }

    if (n_all <= 0) {
      printf("No valid candidates remain.\n");
      return 0;
    }

    if (n_all == 1) {
      best = -1;
      for (int i = 0; i < MAX_WORDS; i++) {
        if (candidates[i] != 0) {
          best = candidates[i];
          break;
        }
      }
      if (best < 0) {
        fprintf(stderr, "* Internal error at line %d\n", __LINE__);
        exit(1);
      }
    } else {
      moves_left = MAXTURNS - moves_used;
      if (moves_left == 1) {
        best = candidates[0];
      } else {
        best = choose_best_guess_hybrid(&c,
                                        candidates, n_all,
                                        moves_left, hard_mode,
                                        CLOCKS_PER_SEC / 5, &used_exact, &timed_out);
      }
    }
    if (best < 0) {
      fprintf(stderr, "* No valid candidates remain? - n_all=%d\n", n_all);
      exit(1);
    }

    printf("Suggested next guess: ");
    print_scored_guess(allowed[best], blank_score, stdout);
    if (used_exact && timed_out)  printf(" [exact search timed out; heuristic fallback]");
    if (moves_used >= 4 || n_common < 12) {
      printf(n_all == 1 ? " (No other remaining words" : " (Other remaining words:");
      for (int i = 0; i < n_all; i++) {
        if (candidates[i] != best) printf(" %.5s", (candidates[i] >= COMMON_COUNT ? downcase(allowed[candidates[i]]) : upcase(allowed[candidates[i]])));
      }
      printf(")");
    }
    printf("\n");
    memcpy(guess, allowed[best], WORDLEN);
    if (tried_count == 0 || tried_words[tried_count-1] != best) tried_words[tried_count++] = best;
    moves_used++;
  }
}