2009-06-13

C#と諸々 10分でコーディング
 １０分でコーディング｜プログラミングに自信があるやつこい！！

乗り遅れた感はあるけど、SQL でやってみた。

WITH
  Input(id, numPlayers, deck) AS (
    SELECT 1, 3, '123123123'
    UNION ALL SELECT 2, 4, '123123123'
    UNION ALL SELECT 3, 6, '012345012345012345'
    UNION ALL SELECT 4, 4, '111122223333'
    UNION ALL SELECT 5, 1, '012345012345012345'
    UNION ALL SELECT 6, 6, '01234'
    UNION ALL SELECT 7, 2, ''
    UNION ALL SELECT 8, 0, ''
    UNION ALL SELECT 9, 0, '123'
  )
, Cards(id, i, card, deck) AS (
    SELECT
        id
      , 0
      , LEFT(deck, 1)
      , SUBSTRING(deck, 2, LEN(deck))
    FROM
        Input
    WHERE
        deck <> ''
    UNION ALL
    SELECT
        id
      , i + 1
      , LEFT(deck, 1)
      , SUBSTRING(deck, 2, LEN(deck))
    FROM
        Cards
    WHERE
        deck <> ''
  )
, Players(id, player, n, total) AS (
    SELECT
        id
      , 1
      , numPlayers
      , numPlayers
    FROM
        Input
    WHERE
        numPlayers <> 0
    UNION ALL
    SELECT
        id
      , player + 1
      , n - 1
      , total
    FROM
        Players
    WHERE
        n <> 1
  )
, DealSrc(id, i, player, card, total) AS (
    SELECT
        Player.id
      , COALESCE(Card.i + 1, Player.player)
      , Player.player
      , COALESCE(Card.card, '')
      , Player.total
    FROM
        Players Player
          LEFT OUTER JOIN Cards Card ON
            Player.id = Card.id AND  Player.player = (Card.i % Player.total + 1)
  )
, Concated(id, i, player, cards) AS (
    SELECT
        id
      , i
      , player
      , CAST(card AS varchar(max))
    FROM
        DealSrc
    WHERE
        i = 1
    UNION ALL
    SELECT
        Concated.id
      , Concated.i + Src.total
      , Concated.player
      , Concated.cards + Src.card
    FROM
        Concated
          INNER JOIN DealSrc Src ON Concated.id = Src.id
                                      AND Concated.player = Src.player
    WHERE
        Concated.i + Src.total = Src.i
  )
, Deal_(id, player, cards) AS (
    SELECT
        id
      , player
      , cards
    FROM
        Concated P
    WHERE
        LEN(cards) = (SELECT MAX(LEN(cards)) FROM Concated C
                      WHERE P.id = C.id AND P.player = C.player)
  )
, Deal(id, player, cards) AS (
    SELECT
        id
      , player
      , LEFT(cards, (SELECT MIN(LEN(cards)) FROM Deal_ C WHERE P.id = C.id))
    FROM
        Deal_ P
  )
SELECT * FROM Deal ORDER BY id, player

あまりに簡単なので制限時間を１０分としてやってみてください。
これ以上かかった人は
自分はかなりプログラミングができない。
とつらい事実を認識しましょう。
１０分でコーディング｜プログラミングに自信があるやつこい！！

がーん。精進します！

追記：
結果張り忘れてたw

id	player	cards
1	1	111
1	2	222
1	3	333
2	1	12
2	2	23
2	3	31
2	4	12
3	1	000
3	2	111
3	3	222
3	4	333
3	5	444
3	6	555
4	1	123
4	2	123
4	3	123
4	4	123
5	1	012345012345012345
6	1
6	2
6	3
6	4
6	5
6	6
7	1
7	2

Brainf*ck in SQL を改造して、BrainCrash in SQL を書いてみました！
BrainCrash については 404 Not Found を参考にしてください。

WITH
  -- 入力
  Input(id, bc_program, stdin) AS (
    -- Hello, World!と標準出力に出力するプログラム
    SELECT 0, '', ''
    
    -- OR計算
    UNION ALL SELECT 1, '|', ''
    -- OR計算2
    UNION ALL SELECT 2, '|<', ''
    
    -- AND計算
    UNION ALL SELECT 3, '&', ''
    -- AND計算2
    UNION ALL SELECT 4, '&<', ''
    
    -- NOT計算
    UNION ALL SELECT 5, '[>]++++++++++[-<<<<<<<<<<<<<+++++++++++>>>>>>>>>>>>>]<<<<<<<<<<<<<+~', ''
    
    -- XOR計算
    UNION ALL SELECT 6, '^', ''
    -- XOR計算2
    UNION ALL SELECT 7, '^<', ''
    
    -- 入力された文字+world!
    UNION ALL SELECT 8, ',+[-.,+]>>>>>>', 'Hoge'
    
    -- worldのwを大文字にする
    UNION ALL SELECT 9, '>>>>>>^<<<<<<<', ''
  )
, Input_(id, bc_program, stdin) AS (
    SELECT id, bc_program + '[.>]', stdin + NCHAR(255) FROM Input
  )
, BracketTableSrc(id, open_bracket_pos, close_bracket_pos, stack, src, crnt) AS (
    -- 括弧の対応表の元データ
    -- スタックに開き括弧のインデックスをpushし、
    -- 閉じカッコを見つけ次第そのインデックスとスタックに積まれているインデックスを取り出して、
    -- open_bracket_posとclose_bracket_posに格納する。
    -- 後戻りが発生しないので、文字列消費型(srcがどんどん減っていく)で構成。
    SELECT
        id
      , 0
      , 0
      , CAST('' AS nvarchar(max))
      , bc_program
      , 1
    FROM
        Input_
    UNION ALL
    SELECT
        id
        -- スタックのtopにあるインデックスを設定
      , CASE LEFT(src, 1)
        WHEN ']' THEN CAST(LEFT(stack, CHARINDEX(' ', stack, 1)) AS int)
                 ELSE 0
        END
        -- 閉じカッコのインデックスを設定
      , CASE LEFT(src, 1)
        WHEN ']' THEN crnt
                 ELSE 0
        END
        -- 開き括弧ならスタックにインデックスをpushし、
        -- 閉じカッコならスタックからpopする
      , CASE LEFT(src, 1)
        WHEN '[' THEN CAST(crnt AS nvarchar(4)) + ' ' + stack
        WHEN ']' THEN SUBSTRING(stack, CHARINDEX(' ', stack, 1) + 1, LEN(stack))
                 ELSE stack
        END
        -- 消費した文字列を取り除いたものが次のsrcになる
      , SUBSTRING(src, 2, LEN(src))
      , crnt + 1
    FROM
        BracketTableSrc
    WHERE
        src <> ''
  )
, BracketTable(id, open_bracket_pos, close_bracket_pos) AS (
    -- open_bracket_posとclose_bracket_posがどちらも格納されているデータのみ抜き出す
    -- このテーブルをひくことで対応括弧のインデックスが取得できる
    SELECT
        id
      , open_bracket_pos
      , close_bracket_pos
    FROM
        BracketTableSrc
    WHERE
        open_bracket_pos <> 0
          AND close_bracket_pos <> 0
  )
, Eval(id, array, ptr, input_pgm, crnt, stdout, stdin) AS (
    -- BrainCrashの評価エンジン
    -- ループが存在するので、文字列消費型ではなく、
    -- オリジナル文字列とインデックスによる方法(input_pgmは変わらず、crntが変わる)を使用している。
    SELECT
        id
        -- BrainCrashが使用する配列は2000に制限
        -- SQL Serverに限らず、一行のサイズが制限されていることは多いので一応。
        -- 初期状態はHello, world!の後が全て0
      , CAST('Hello, world!' + REPLICATE(NCHAR(0), 2000 - LEN('Hello, world!')) AS nchar(2000))
      , 1   -- ポインタの初期状態はSQLの文字列のインデックスが1からなので1
      , bc_program
      , 1
      , CAST('' AS nvarchar(max))   -- 標準出力は最初空
      , stdin                       -- 標準出力はInputのものをそのまま使う
    FROM
        Input_
    UNION ALL
    SELECT
        id
      , CAST(
          -- 現在見ている文字が+、-、|、&、^、~、,のいずれかなら配列を操作する
          CASE SUBSTRING(input_pgm, crnt, 1)
          WHEN '+' THEN CASE UNICODE(SUBSTRING(array, ptr, 1))
                        WHEN 255 THEN STUFF(array, ptr, 1, NCHAR(0))
                                 ELSE STUFF(array, ptr, 1, NCHAR(UNICODE(SUBSTRING(array, ptr, 1)) + 1))
                        END
          WHEN '-' THEN CASE UNICODE(SUBSTRING(array, ptr, 1))
                        WHEN 0 THEN STUFF(array, ptr, 1, NCHAR(255))
                               ELSE STUFF(array, ptr, 1, NCHAR(UNICODE(SUBSTRING(array, ptr, 1)) - 1))
                        END
          WHEN '|' THEN STUFF(
                          array,
                          ptr + 1,
                          1,
                          NCHAR(
                            UNICODE(SUBSTRING(array, ptr, 1))
                              | UNICODE(SUBSTRING(array, ptr + 1, 1))
                          )
                        )
          WHEN '&' THEN STUFF(
                          array,
                          ptr + 1,
                          1,
                          NCHAR(
                            UNICODE(SUBSTRING(array, ptr, 1))
                              & UNICODE(SUBSTRING(array, ptr + 1, 1))
                          )
                        )
          WHEN '^' THEN STUFF(
                          array,
                          ptr + 1,
                          1,
                          NCHAR(
                            UNICODE(SUBSTRING(array, ptr, 1))
                              ^ UNICODE(SUBSTRING(array, ptr + 1, 1))
                          )
                        )
          WHEN '~' THEN STUFF(array, ptr, 1, NCHAR(~CAST(UNICODE(SUBSTRING(array, ptr, 1)) AS tinyint)))
          -- 標準入力にも一応対応。標準入力を一番最初に与えておかなければいけないのはSQLの限界ですね
          WHEN ',' THEN STUFF(array, ptr, 1, LEFT(stdin, 1))
                   ELSE array
          END
        AS nchar(2000))
        -- 現在見ている文字が>か<か|か&か^ならポインタを操作する
      , CASE
        WHEN SUBSTRING(input_pgm, crnt, 1) IN ('>', '|', '&', '^')
          THEN ptr + 1
        WHEN SUBSTRING(input_pgm, crnt, 1) = '<' AND ptr <> 1
          THEN ptr - 1
          ELSE ptr
        END
      , input_pgm
        -- 現在見ている文字が[か]ならインデックスを操作する
      , CASE SUBSTRING(input_pgm, crnt, 1)
        WHEN '[' THEN CASE UNICODE(SUBSTRING(array, ptr, 1))
                      WHEN 0 THEN (SELECT close_bracket_pos FROM BracketTable
                                   WHERE Eval.id = BracketTable.id AND open_bracket_pos = crnt) + 1
                             ELSE crnt + 1
                      END
        WHEN ']' THEN (SELECT open_bracket_pos FROM BracketTable
                       WHERE Eval.id = BracketTable.id AND close_bracket_pos = crnt)
                 ELSE crnt + 1
        END
        -- 現在見ている文字が.なら標準出力に追記する
      , CASE SUBSTRING(input_pgm, crnt, 1)
        WHEN '.' THEN stdout + SUBSTRING(array, ptr, 1)
                 ELSE stdout
        END
        -- 現在見ている文字が,なら標準入力から消費する
      , CASE SUBSTRING(input_pgm, crnt, 1)
        WHEN ',' THEN SUBSTRING(stdin, 2, LEN(stdin))
                 ELSE stdin
        END
    FROM
        Eval
    WHERE
        crnt <= LEN(input_pgm)
  )
, Result(id, stdout) AS (
    SELECT
        id
      , stdout
    FROM
        Eval P
    WHERE
        crnt = (SELECT MAX(crnt) FROM Eval C WHERE P.id = C.id)
  )
SELECT * FROM Result ORDER BY id
OPTION (MAXRECURSION 32767)

実行結果はこんな感じ。

id	stdout
0	Hello, world!
1	mllo, world!
2	Hmllo, world!
3	@llo, world!
4	H@llo, world!
5	Hello, world!
6	-llo, world!
7	H-llo, world!
8	Hoge world!
9	Hello, World!

実はこれ組んでるときに Brainf*ck in SQL のバグを見つけてしまった・・・後で直します！

ぐるぐる～

10 分間コーディングで 30 分かかった・・・

BrainCrash in SQL