オークの問題C言語版

Makefile

orcs: orcs.c
	$(CC) -std=gnu11 -o $@ $^

orcs.c

/*
 * https://twitter.com/MomiRaccoon/status/1434402973627531267
 *
 * 女騎士「わ、私に性感度3000倍もさせて一体何をさせるんだ…」
 * オーク「ククク…」
 *
 * オークA「感度を半分にするクスリだ」
 * オークB「感度を900マイナスにするクスリだ」
 * オークC「感度を2000プラスにするクスリだ」
 * オークD「感度を5倍するクスリだ」
 * オークE「感度を500プラスにするクスリだ」
 *
 * 女騎士「はじめの感度の値が0であった場合、感度の値を3000にするためにオーク達はどんな順序でクスリを飲ませることになるんだ…！？」
 */

#include <stdio.h>

/** オークを表す構造体。 */
typedef struct Orc_t {
  /** 名前。 */
  char name;
  /** クスリを投与する。投与後の感度を返す。 */
  int (*medicate)(int sensitivity);
} Orc;

/** 順列に対する処理の関数の型。 */
typedef void (*EachPermutationProc)(Orc * const *, size_t);

/**
 * @brief すべての順列をイテレートする。
 * @param orcs オークへのポインタの配列。
 * @param n 要素数。
 * @param proc 順列に対する処理。
 */
void each_permutation(Orc** orcs, size_t n, EachPermutationProc proc);

/**
 * @brief Heapのアルゴリズムですべての順列をイテレートする（再帰処理）。
 * @param orcs オークへのポインタの配列。
 * @param n 要素数。
 * @param k カウンタ。最初はnとすること。
 * @param proc 順列に対する処理。
 */
void each_permutation_iter(Orc** orcs, size_t n, size_t k, EachPermutationProc proc);

/** 2つのオークへのポインタを交換する。 */
void swap_orcs(Orc** a, Orc** b);

/**
 * @brief 感度の計算結果が3000となったときに順序を出力する。
 * @param orcs オークへのポインタの配列。
 * @param n 要素数。
 */
void output_order_if_sensitivity_gets_3000(Orc * const * orcs, size_t n);

/** オークA「感度を半分にするクスリだ」 */
int orc_a_medicate(int sensitivity) { return sensitivity / 2; }

/** オークB「感度を900マイナスにするクスリだ」 */
int orc_b_medicate(int sensitivity) { return sensitivity - 900; }

/** オークC「感度を2000プラスにするクスリだ」 */
int orc_c_medicate(int sensitivity) { return sensitivity + 2000; }

/** オークD「感度を5倍するクスリだ」 */
int orc_d_medicate(int sensitivity) { return 5 * sensitivity; }

/** オークE「感度を500プラスにするクスリだ」 */
int orc_e_medicate(int sensitivity) { return sensitivity + 500; }

int main(void) {
  Orc orc_a = {'A', orc_a_medicate};
  Orc orc_b = {'B', orc_b_medicate};
  Orc orc_c = {'C', orc_c_medicate};
  Orc orc_d = {'D', orc_d_medicate};
  Orc orc_e = {'E', orc_e_medicate};

  Orc* orcs[] = {&orc_a, &orc_b, &orc_c, &orc_d, &orc_e};
  const size_t n = sizeof(orcs) / sizeof(orcs[0]);

  each_permutation(orcs, n, output_order_if_sensitivity_gets_3000);

  return 0;
}

void output_order_if_sensitivity_gets_3000(Orc * const * orcs, size_t n) {
  int sensitivity = 0;

  for (size_t i = 0; i < n; i++) {
    sensitivity = orcs[i]->medicate(sensitivity);
  }

  if (sensitivity != 3000) {
    return;
  }

  for (size_t i = 0; i < n; i++) {
    if (i > 0) {
      fputs("->", stdout);
    }

    putchar(orcs[i]->name);
  }

  putchar('\n');
}

void each_permutation(Orc** orcs, size_t n, EachPermutationProc proc) {
  each_permutation_iter(orcs, n, n, proc);
}

void each_permutation_iter(Orc** orcs, size_t n, size_t k, EachPermutationProc proc) {
  if (k == 1) {
    proc(orcs, n);
    return;
  }

  for (size_t i = 0; i < k; i++) {
    each_permutation_iter(orcs, n, k - 1, proc);

    if (k & 1) {
      swap_orcs(&orcs[0], &orcs[k - 1]);
    } else {
      swap_orcs(&orcs[i], &orcs[k - 1]);
    }
  }
}

void swap_orcs(Orc** a, Orc** b) {
  Orc* temp = *a;
  *a = *b;
  *b = temp;
}

output.txt

C->A->B->E->D
C->A->E->B->D
B->C->D->E->A
C->B->D->E->A