第27回オフラインリアルタイムどう書く「分岐と行き止まり」の C言語による実装 #C

問題 http://nabetani.sakura.ne.jp/hena/ord27raswi/
解答リンク集 http://qiita.com/Nabetani/items/23ebddb44f0234e7fb15
イベント http://yhpg.doorkeeper.jp/events/16017

で。

当日お見せした実装。

出題者の気分としては、かなり簡単な問題のつもり。

ruby で事前に実装しておいたんだけど、当日その場で C99 に移植した。

// clang -std=c99 -Wall solve.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

struct ans{  char m[ 3*9 ]; };

bool can_go( char from, char to, char const * src )
{
  if ( strchr( src, from ) ){
    return false;
  }
  if ( from==to ){
    return true;
  }
  char * ways[] = {
    "1ag", "ab", "bc5", "c46",
    "2dh", "dec", "e5",
    "3bf", "fg", "gceh", "h4i", "i6", 0
  };
  for( int i=0 ; ways[i] ; ++i ){
    char const * way = ways[i];
    if ( from==way[0] ){
      for( int j=1 ; way[j] ; ++j ){
        if ( can_go( way[j], to, src )){
          return true;
        }
      }
    }
  }
  return false;
}

struct ans solve( char const * src )
{
  struct ans ans={{0}};
  for( char from='1' ; from<='3' ; ++from ){
    for( char to='4' ; to<='6' ; ++to ){
      if ( can_go( from, to, src ) ){
        if ( ans.m[0]!=0 ){
          strcat( ans.m, "," );
        }
        char path[3]={ from, to };
        strcat( ans.m, path );
      }
    }
  }
  if ( ans.m[0]==0 ){
    ans.m[0]='-';
  }
  return ans;
}

void test( char const * src, char const * expected )
{
  struct ans ans = solve( src );
  bool ok = strcmp( ans.m, expected )==0;
  printf( "%s : %s->%s ( %s )\n", 
    ( ok ? "ok" : "***NG***"),
    src, ans.m, expected );
}

int main()
{
/*0*/ test( "befi", "14,16,24,26" );
/* 中略 */
/*44*/ test( "bdefgi", "24" );
}

地図をどうコードに表現するかで幾つか選択肢がある。

分岐情報を持つ ( https://github.com/keqh/doukaku/blob/master/answers/27/main.coffee など )
1→4 なら ab, gc, gh のいずれかを通る、という情報をソースに書く( http://qiita.com/nidouchi/items/8222ee1eae3bd1375a4a など)
分岐情報をソースコードの条件という形で書ききる( http://qiita.com/Nabetani/items/23ebddb44f0234e7fb15#comment-9c1790c190d3c38f8fb3 )

の３つの選択肢があるんだけど（他にもあるかも）、これは最初に挙げた「分岐情報を持つ」という戦略。

で。
計算量へのケアが全然なく、いろいろひどい感じではある。

ways から way を引くところは hash か二分探索にすべきだし、道をたどる際には重複して探さないようにメモ化すべき。strcat を使うと無駄な計算が生じるので、末尾へのポインタを持っておくべき。

最初は switch〜case を書いていたんだけど、途中で飽きて、こういう形になった。

とはいえ、地図のサイズは決まっているので、今回はこれで十分。

計算量という点では十分だけど、ソースコード出来という観点で見ると、solve が複雑すぎるなとは思う。文字列処理を別の関数に出すべきだね。

struct ans{ char m[ 3*9 ]; }; は、C言語で長さの上限がわかっている文字列を使う際のイディオム。このように構造体の中に配列を入れておくと返戻値としてそのまま使えるし、バッファオーバーランしにくいので便利。