C言語でcsvファイル内のデータを用いて「しりとり」を行う

Question

Ｃ言語でしりとりのようなことを行うプログラムを作成しています。

以下のようなCSVファイルがあったとします。

Parts,Input,Output
A,a,b
B,a,c
C,a,a
D,a,h
E,b,c
F,b,e
H,b,f
I,c,d
J,c,h
K,d,i
L,e,a
M,f,a
N,g,b
O,f,c
P,h,c
Q,i,a

ユーザはしりとりの最初の文字（開始文字）と最後の文字（終了文字）を入力させます。そうすると、

その開始文字から始まり終了文字に辿り着く経路を全て表示する　といったものです。

例えば、ユーザが開始文字:a 終了文字:b　を入力すると，

経路1: A

経路2: B→I→K→Q→A

経路3: D→P→I→K→Q→A

・・・

といったような経路を得ることが出来ます。

 

現在、csvデータを行ごとに配列に格納し，終了文字から開始文字に辿り着くようにプログラムを組んでいます。

 

kakuno[100][3] に取得した行を全て格納し、

    int c=0;
    for(int b=0; b<=20;b++)
    {
        if(kakuno[b][2]==”入力された終了文字”) //kakuno[b][2]=配列の3列目=csvファイル上でのOutput列
        {
            firstoutput[c][0]=kakuno[b][0];
            firstoutput[c][1]=kakuno[b][1];
            firstoutput[c][2]=kakuno[b][2];
            c++;
        }
    }   

というように，終了文字をoutputに持つ物を取得する　さらにこれを繰り返すことで経路を得る。

という流れです。

しかし、現在のプログラムでは経路の長さがあらかじめわかっているため、自動的に作業をループし、開始文字に辿り着いたら終了する、というものではありません。（そのようなプログラムを組めていない）

実際にやる事は、

『ＩｎｐｕｔをＯｕｔｐｕｔに持つPartsを検索し、さらにそのPartsのInputをOutputに持つPartsを検索し、もしPartsのInput=開始文字となった場合に終了する』

という事なのですが、スマートに汎用性のある記述を行うためにはどのようにしたら良いのでしょうか・・・？

わかりにくい説明で申し訳ありませんが、よろしくお願いします。

 

Answer 1

外池と申します。非常に興味深いご質問なんですが、あまりに高度な（難易度が高い）内容なので回答できるかどうかわかりませんが・・・、少しコメントを。

まず、これはプログラミング言語に依存したものではなく、もっと一般的にアルゴリズムをどうするか、知恵を絞らないといけない問題だと思います。

次に、前提条件として、明確でない点をいくつか指摘しておきます。

１）与えられるCSVファイルですが、開始文字と終了文字の種類の数は、固定されている（aからh、とか、aからｚとか）のでしょうか？

2)同じく、与えられるCSVファイルですが、どのような開始文字と終了文字の指定がなされても、必ず答えが見つかることが保証されているCSVファイルが与えられるのでしょうか？

3)見つけるべきものは、少なくとも1つの答えでしょうか？　見つけるべき答えの条件はなんでしょう？（最短経路？　かなり最短に近い経路？　すべての可能な経路というのは不可能だと思われます。同じ経路をループすることを許せばいくらでも長い経路を作れるハズなので）

ほんと、すいません、私が回答できるわけではないのですが、気付いた点です。

 

---

（ホームページを再開しました）

Answer 2

char Ass(char Input, char Output)
{
   while(1){
     if(Input == Kakuno[i][2]){
        return kakuno[i][0];
     }else if(Output == Kakuno[i][3]){
        printf("%c", Ass(Input, Kakuno[i][2]));
        return Kakuno[i][0];
     }
     i++;
   }
   return null;
}


void main(int argc, char *argv[]){
{
   Ass(argv[1], argv[2]);
   exit(0);
}

『ＩｎｐｕｔをＯｕｔｐｕｔに持つPartsを検索し、さらにそのPartsのInputをOutputに持つPartsを検索し、もしPartsのInput=開始文字となった場合に終了する』

要はこういうことでいいのでしょうか?

無限ループに陥るとか、

一本しか経路見つけてないとかいろいろ問題ありますが、

上記の『』をそのままソースにするとこうなります。

 

外池様も申しておられましたが、

アルゴリズムをどうするか、知恵を絞らないといけない問題だと思います。

 

テクニックの問題ではなく、アルゴリズムがどうにかなればソースは自然に書けると思います。

Answer 3

返信ありがとうございます。

まず前提条件に関する回答を・・・

1)現在は本文に載せたもので全てですが，最終的にはInput/Outputには名詞が代入される予定です。なので種類の数は固定されていません。

2)必ず答えが見つかる訳ではないと思います。最終的にも経路見がつからない　という場合も想定しています。

3)見つける経路は2)で述べたように，0以上という事になります。見つけるべき答えの条件は，『ﾙｰﾌﾟがない』　というだけです。本文中に載せたように，Input a，Output b　の場合，

最短である経路１も経路２も同様に回答となります。

 

 

Answer 4

返信ありがとうございます。

 

アルゴリズムに関しては外池様への返答に追加致しました。

要するに『考えられる経路をﾙｰﾌﾟを除いて全て検索し，最終的にはパーツ名を用いて経路を表示する(例． B→I→K→Q→A)』

ということになります．

 

Answer 5

そういった話であればいろいろ方法論があると思いますが、

簡単なのは語の関係の有効グラフを構築して、

幅優先探索とか深さ優先探索で探索するのが良いと思います。

Answer 6

　「有効グラフ」は、「有向グラフ」の変換ミスのようです。

　「最終文字から開始文字にたどり着く」としているのには、何か理由があるのでしょうか。というのも、2011年5月25日 5:51の例で行くと...終端が「b」であるルートは「A, N」ですが、「A」の始端が「a」であるため、ここで探索が終わってしまうのです。

　先頭から探すと、
a が始端であるパーツ：A, B, C, D
A から行けるパーツ：終わり
B から行けるパーツ：I
　I から行けるパーツ：K
　　K から行けるパーツ：Q
　　　Q から行けるパーツ：A
　　　　A から行けるパーツ：終わり
C から行けるパーツ：A, B, D, （C）
　A から行けるパーツ：終わり
　B から行けるパーツ：I
　　I から行けるパーツ：K
　　　K から行けるパーツ：Q
　　　　Q から行けるパーツ：A
　　　　　A から行けるパーツ：終わり
　D から行けるパーツ：P
　　P から行けるパーツ：I
　　　I から行けるパーツ：K
　　　　K から行けるパーツ：Q
　　　　　Q から行けるパーツ：A
　　　　　　A から行けるパーツ：終わり
D から行けるパーツ：P
　P から行けるパーツ：I
　　I から行けるパーツ：K
　　　K から行けるパーツ：Q
　　　　Q から行けるパーツ：A
　　　　　A から行けるパーツ：終わり
と、こんな感じですね。これが、「幅優先探索」です。

　で、これをするためには、容量を動的に変更できる入れ物が必要ですが、それの書き方はわかるでしょうか。

---

Jitta＠わんくま同盟

Answer 7

返信ありがとうございます。

終点から開始したのには特に深い訳はありません。。。

ので、最終的にはどちらでも良いです。

 

「容量を動的に変更できる入れ物」については，探索の結果で検索される経路の数が「未定」であるため、

必要ではないかと探していたのですが、結局は分かりませんでした。

よろしければご教授願います。

Answer 8

ああ書いておいて何ですが、別に動的に容量を増やせなくてもいいんですよ。

たとえば、「経路に使うパーツの最大数」を考えたとき、ループはしないようにするのですから、CSV ファイルの行数が最大になります。従って、動的に容量を増やさなくても、まず CSV ファイルを読んで、行数を調べれば、最大限必要な数がわかります。

また、今回の場合、realloc でもことが足りそうです。

あるいは、C 言語でなければならいのでしょうか。C# であれば List 等のコンテナクラスがありますし、C++ でも、STL にコンテナクラスがあります。

問題は、経路の確定に必要な行程がすべて明らかになっているか、というところだと思います。自分で探す行程を、日本語で箇条書きにして説明できますか？

---

Jitta＠わんくま同盟

Answer 9

jitta様、

 

たとえば、「経路に使うパーツの最大数」を考えたとき、ループはしないようにするのですから、CSV ファイルの行数が最大になります。従って、動的に容量を増やさなくても、まず CSV ファイルを読んで、行数を調べれば、最大限必要な数がわかります。


たしかにその通りですね。。。行数は現在数えられていますので、経路の最大長は17ということになりますね。

あるいは、C 言語でなければならいのでしょうか。C# であれば List 等のコンテナクラスがありますし、C++ でも、STL にコンテナクラスがあります。

C++も可能です。

問題は、経路の確定に必要な行程がすべて明らかになっているか、というところだと思います。自分で探す行程を、日本語で箇条書きにして説明できますか？

今回質問文に載せたｃｓｖを例に箇条書きにしてみます。ユーザの入力はInput:a Output:bと仮定しています。

また、具体的なメソッドがわからないので、一時的に「経路を格納する箱」という表現を用いています。

１．Input=aであるパーツを全て取得し、「経路を格納する箱n」の先頭に入れる。nは該当Inputを持つパーツ数で、　

Input=aなら，箱1~4が用意される

２．もし、それらの箱の最後尾で、Output=bであるものがあれば、その箱はクローズし、中身を出力する

３．さらに、箱1~4に対し、箱の最後尾に置かれているパーツのOutputをInputにもつパーツを全て取得する。

４．その際、箱１の最後尾に置かれているパーツのOutputをInputに持つパーツが2つ存在した場合、別々の箱1-1と箱

1-2を作成し、格納する

５．２を行う

６．もし、箱の最後尾のパーツ名が、それ以前に格納されたパーツの名前と同じなら、その箱を破棄する

７．３．に戻り、作成したすべての箱が出力された場合、終了

という感じになります。うまく説明できていないのですが…

作業自体はループしているのですが、取得したパーツの個数によってループ回数が変わる、という事が自分の中ではネックとなっています。また不明な点があれば細くしていきますので、どうかよろしくお願いします。

Answer 10

　なかなかいい線行ってますよ。

　C ということなので、とりあえず、『プログラミング言語 C』という本が、“バイブル”と言われている本になります。ただ、この本の出版後、C の規格が変わっています。新しい C については、『C リファレンス マニュアル』という本が、詳しく書いてあります。この2冊、特に『C リファレンス マニュアル』の方は、必読と言っていいでしょう。これらの本は、言語リファレンスとしてだけではなく、アルゴリズムの理解を深めるためのことも書いてあります。今回の問題を解くのに必要な“仕組み”も、書いてあります。

　あと、柔軟な発想も必要かと思います。「経路を格納する箱」とは、どんなものを考えていらっしゃるでしょうか。たとえば、このスレッドで提示されている内容では、“パーツ名”は「1文字」です。これが変わらないのなら、この「経路を格納する箱」は、「文字配列」でもいいわけですよね？そしてその容量は、「CSV の行数 + 1」を超えることはありません。すると、経路が path という変数に入っているとすると、「箱の最後尾」のパーツ名は path[strlen(path) - 1] で取り出せます。「箱の最後尾のパーツ名が、それ以前に格納されたパーツの名前と同じなら」は、 strchr(path, path[strlen(path) - 1]) となります。これで、かなり楽になりませんか？

---

Jitta＠わんくま同盟

Answer 11

Jitta様

 

『Ｃリファレンス　マニュアル』、探してみようと思います。

 

最終的にパーツ名は単語になる予定です。。。

返信を待つ間、似たようなプログラムを発見し、それを改良することで頑張っていました・・・

スタックを利用したもので、元のプログラムは

#include <stdio.h>

char table[][2] = {
        {'A','B'}, // A->B
        {'A','G'}, // A->G
        {'B','C'}, // B->C
        {'B','E'}, // B->E
        {'C','D'}, // C->D
        {'E','F'}, // E->F
        {'G','H'}, // G->H
        {'H','I'}, // H->I
        {'H','J'}, // H->J
        {'J','K'}, // J->K
        {'_','?'}, // terminator
};

char stack[26]; //Ａ－Ｚなので最大で２６
int  sp=-1;     //stack pointer

void route(char x){
        int i;
        char c;

        stack[++sp]= x ;
        for(i=0;(c=table[i][0])!=x && c!='_';i++); //頭出し

        if(c!='_')
                for(;table[i][0]==x;i++)
                        route(table[i][1]);
        else {
                for(i=0;i<sp;i++){
                        putchar(stack[i]);putchar('-');
                }
                putchar(stack[sp]);putchar('\n');
        }
        --sp;
}

void main(void){
        route('A');
}


となっています。tableで有向グラフ状にアルファベットを定義しています。
質問文に掲載したcsvを同様の形式に書き換え、同様のプログラムを実行すると、当然ループが発生するため暴走します。
（上のプログラムではループが発生しないようにtableを定義しています。）
正直そのまま引っ張ってきたので、内部で何が起こっているのかは理解できていません…
elseの中のfor文をうまくbreakする必要があるとは思うのですが…
このプログラムを改良することで、所期の目的は達成できないでしょうか・・・？

Answer 12

　2011年5月26日 2:30の外池さん「もっと一般的にアルゴリズムをどうするか、知恵を絞らないといけない問題だと思います。」、2011年5月26日 5:10のKistymynordさん「テクニックの問題ではなく、アルゴリズムがどうにかなればソースは自然に書けると思います。」の言葉の意味を、理解されているでしょうか。それを踏まえて、2011年5月31日 12:30で私が「自分で探す行程を、日本語で箇条書きにして説明できますか？」と尋ねた意味を、理解していただけているでしょうか。

　プログラムを「書く」と言いますが、プログラム「に翻訳する」という言い方をした方が、これからプログラムを作ろうとする人には、目的が明確になるんじゃないかと思います。プログラムに、翻訳するのです。何を？やりたいことを、です。何から？思考から、です。その為に「アルゴリズムを考えて」というアドバイスがあり、「日本語で箇条書きにして説明できますか」と尋ねました。2011年6月1日 10:22の箇条書きを（多少追加修正して）C のコードに翻訳すると、下のようになります。箇条書き1つが、ほぼ1行に対応しています。だから、「なかなかいい線行ってますよ。」なのです。

　なお、新しい方のコードが動かないのは、終了条件が明示されていないからです。

#include "stdafx.h"
#include <memory.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

// char kakunou[][3] から定義を変更。
// 「文字3つ」ではなく、文字ひとつひとつの定義が違うため。
typedef struct {
  char  パーツ名;
  char  始点;
  char  終点;
} パーツ;

パーツ 元データ[] = {
  {'A', 'a', 'b'},
  {'B', 'a', 'c'},
  {'C', 'a', 'a'},
  {'D', 'a', 'h'},
  {'E', 'b', 'c'},
  {'F', 'b', 'e'},
  {'H', 'b', 'f'},
  {'I', 'c', 'd'},
  {'J', 'c', 'h'},
  {'K', 'd', 'i'},
  {'L', 'e', 'a'},
  {'M', 'f', 'a'},
  {'N', 'g', 'b'},
  {'O', 'f', 'c'},
  {'P', 'h', 'c'},
  {'Q', 'i', 'a'},
  { 0 , 0 , 0 },  // 終了マーク
};

typedef struct _パーツチェーン {
  struct _パーツチェーン *next;
  パーツ パーツ;
} パーツチェーン;

void パーツチェーンを解放(パーツチェーン *p)
{
  while (p != NULL) {
    パーツチェーン *n = p->next;
    free(p);
    p = n;
  }
}

パーツ *パーツ名からパーツを探す(char パーツ名)
{
  for (int i = 0; 元データ[i].パーツ名 != 0; ++i) {
    if (元データ[i].パーツ名 == パーツ名) {
      return &元データ[i];
    }
  }
  return NULL;
}

パーツチェーン *始点を指定してパーツを探す(char 始点)
{
  パーツチェーン *見つけたパーツ = NULL, *p = NULL;
  for (int idx = 0; 元データ[idx].パーツ名 != 0; ++idx) {
    if (元データ[idx].始点 == 始点) {
      if (p == NULL) {
        p = (パーツチェーン*)malloc(sizeof(パーツチェーン));
        見つけたパーツ = p;
      } else {
        パーツチェーン *q = (パーツチェーン*)malloc(sizeof(パーツチェーン));
        p->next = q;
        p = q;
      }
      p->next = NULL;
      memcpy(&p->パーツ, &元データ[idx], sizeof(パーツ));
    }
  }
  return 見つけたパーツ;
}

char *パスを伸ばす(char *パス, パーツ パーツ)
{
  int 新しいパスの長さ = strlen(パス) + 2;  // NULL も含めるので
  char *新しいパス = (char*) malloc(sizeof(char) * 新しいパスの長さ);
  memset(新しいパス, 0, 新しいパスの長さ);
  sprintf_s(新しいパス, sizeof(char) * 新しいパスの長さ, "%s%c", パス, パーツ.パーツ名);
  return 新しいパス;
}

void パスを探す(char *パス, char 終点)
{
  // ２．もし、それらの箱の最後尾で、Output=bであるものがあれば、その箱はクローズし、中身を出力する
  // ５．２を行う
  パーツ *パスの最後のパーツ = パーツ名からパーツを探す(パス[strlen(パス) - 1]);
  if (パスの最後のパーツ->終点 == 終点) {
    printf("見つかったパス：[%s]\n", パス);
    return;
  }

  // ３．さらに、箱1~4に対し、箱の最後尾に置かれているパーツのOutputをInputにもつパーツを全て取得する。
  パーツチェーン *見つけたパーツ = 始点を指定してパーツを探す(パスの最後のパーツ->終点);

  for (パーツチェーン *p = 見つけたパーツ; p != NULL; p = p->next) {
    // ６．もし、箱の最後尾のパーツ名が、それ以前に格納されたパーツの名前と同じなら、その箱を破棄する
    if (strchr(パス, p->パーツ.パーツ名) != NULL) { continue; }

    // ４．その際、箱１の最後尾に置かれているパーツのOutputをInputに持つパーツが2つ存在した場合、
    //   別々の箱1-1と箱1-2を作成し、格納する
    char *新しいパス = パスを伸ばす(パス, p->パーツ);

    // ７．３．に戻り、作成したすべての箱が出力された場合、終了
    パスを探す(新しいパス, 終点);

    free(新しいパス);
  }

  パーツチェーンを解放(見つけたパーツ);
  return;
}

int main(int argc, char **argv)
{
  if (argc != 3) { return -1; }

  // １．Input=aであるパーツを全て取得し、「経路を格納する箱n」の先頭に入れる。
  //   nは該当Inputを持つパーツ数で、Input=aなら，箱1~4が用意される
  パーツチェーン *p, *パーツ = 始点を指定してパーツを探す(argv[1][0]);
  for (p = パーツ; p != NULL; p = p->next) {
    char path[2];
    sprintf_s(path, sizeof(path), "%c", p->パーツ.パーツ名);
    パスを探す(path, argv[2][0]);
  }
  パーツチェーンを解放(パーツ);
  return 0;
}

---

Jitta＠わんくま同盟

Answer 13

すでに解決したかもしれませんが、

ここに書いたことを思い出したので一応見に来てみました。

 

あと直接は関係ないですが、参考書籍を一つ

河西朝雄著

「C言語による（はじめての）アルゴリズム入門」

 

学生のときにアルゴリズムの授業の参考書として利用していましたが、

基本的な様々なアルゴリズムを非常に平易な説明で書いていて、

初心者にも分かりやすいです。