Skip to content

Instantly share code, notes, and snippets.

@ochaochaocha3
Last active Sep 6, 2021
Embed
What would you like to do?
オークの問題C言語版
orcs: orcs.c
$(CC) -std=gnu11 -o $@ $^
/*
* 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;
}
C->A->B->E->D
C->A->E->B->D
B->C->D->E->A
C->B->D->E->A
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment