DouKaku? Language detail: SQL

SQLiteで。2,3,5の11乗まで計算し、その直積をとるだけ。
SQLiteで100行だけ取り出す方法がわからなかったので結果テーブルに一度格納してます。Oracleだとwhere rowno<=100が使えたような

-- 数字テーブル
create table d (
  n   integer,
  p2  integer,
  p3  integer,
  p5  integer
);
insert into d values (0,1,1,1);
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
-- 結果テーブル
create table result (
  id  integer primary key,
  i   integer,
  j   integer,
  k   integer,
  val integer
);
insert into result (i, j, k, val)
  select a.n, b.n, c.n, a.p2 * b.p3 * c.p5 val from d a, d b, d c order by val;
select val,'2^'||i||' * 3^'||j||' * 5^'||k from result where id <= 100;

バージョン 2.7.3の頃に使ったのでちょっと自信がありませんが、先頭から 100件という
ことであれば、

  e.g.
    select ... from ... limit 100;

のように limit句で、Oracleのrownumと同等のことを実現できたと思います。

# 先頭の位置(オフセット)はoffset句で調節します。

see: SQL As Understood By SQLite

LL Golf Hole 7 - バイト数を読みやすくする (Nested Flatten)

それ、PostgreSQLで。8.2で確認。174byte。
ところで、SQLはLLですか？

1	select substring(c from 1 for l%3)\|\|'.'\|\|substring(c from l%3+1 for 1)\|\|substring(' kMGTPE' from l/3+1 for 1)from(select column1 as c,length(column1)as l from(values('12345'))s)s;

LL Golf Hole 5 - 最上位の桁を数え上げる (Nested Flatten)

MySQL と oracle で動作を確認しました。

SELECT DISTINCT t.x*v.y count_up
FROM (
SELECT 0 x FROM DUAL UNION
SELECT 1 FROM dual UNION
SELECT 2 FROM dual UNION
SELECT 3 FROM dual UNION
SELECT 4 FROM dual UNION
SELECT 5 FROM dual UNION
SELECT 6 FROM dual UNION
SELECT 7 FROM dual UNION
SELECT 8 FROM dual UNION
SELECT 9 FROM dual) t
, (SELECT 1 y FROM dual UNION
SELECT 10 FROM dual UNION
SELECT 100 FROM dual UNION
SELECT 1000 FROM dual UNION
SELECT 10000 FROM dual UNION
SELECT 100000 FROM dual UNION
SELECT 1000000 FROM dual UNION
SELECT 10000000 FROM dual UNION
SELECT 100000000 FROM dual UNION
SELECT 1000000000 FROM dual UNION
SELECT 10000000000 FROM dual UNION
SELECT 100000000000 FROM dual UNION
SELECT 1000000000000 FROM dual) v
WHERE t.x*v.y <= 300
ORDER BY t.x*v.y;

LL Golf Hole 2 - 文字列に含まれる単語の最初の文字を大文字にする (Nested Flatten)

PostgreSQL 8.3以降です

1
2
3

SELECT array_to_string(ARRAY(
  SELECT upper(substr(s, 1, 1)) || substr(s, 2) 
    FROM (SELECT regexp_split_to_table('LL day and night', E'\\s')) r(s)), ' ');

擬似lsの実装 (Nested Flatten)

SQLは文字列操作が苦手だけど、無理してやってみました。おそらくMySQL以外では動きません。他のDBでは関数等を読み替えてください。

インデックスを張ってやれば、件数が増えてもパフォーマンスが期待できるところが強みです。検索はSQLを使い、文字列の加工などは呼び元の高級言語（CとかJavaとか）で行うというのが王道かと。

-- パス一覧の作成
create table fs(path char(80) primary key);
insert into fs values("aaa/bbb");
insert into fs values("aaa/ccc");
insert into fs values("aaa/ddd/eee");
insert into fs values("aaa/ddd/fff");
insert into fs values("bbb/ddd/eee");
-- "aaa/" の検索
select distinct substr(
           path, length(dir) + 1,
           case instr(path, "/") when 0 then 80 else (instr(path, "/")) end
       ) ls
  from fs, (select "aaa/" dir) _dir
 where path like concat(dir, "%");
-- "aaa/ddd/" の検索
select distinct substr(
           path, length(dir) + 1,
           case instr(path, "/") when 0 then 80 else (instr(path, "/")) end
       ) ls
  from fs, (select "aaa/ddd/" dir) _dir
 where path like concat(dir, "%");

変形Fizz-Buzz問題 (Nested Flatten)

if もループも使っていません！
いや、ループはあるなら使いたかったけど、ストアドよく知らないし。

--出力テーブル
drop table OUTPUT;
create table OUTPUT (
  LINE integer,
  MSG varchar(10)
);
--以下を２０回実行してください
-->>>ここから
insert into OUTPUT select coalesce(max(LINE),0)+1, 'hoge' from OUTPUT;
--<<<ここまで
--今回のキモ
update OUTPUT set MSG = 'Fizz' where (LINE % 3) = 0;
update OUTPUT set MSG = 'Buzz' where (LINE % 5) = 0;
update OUTPUT set MSG = 'FizzBuzz' where (LINE % 15) = 0;
--出力
select LINE || '：' || MSG from OUTPUT order by LINE;

変数の初期値 (Nested Flatten)

coalesce はSQL標準の関数で、リスト中の NULL じゃない初めの値を返します。
読み方はコゥァレスみたいな感じで、後ろのほうにアクセントを。
お題の意味からはちょっと外れてるかも。

SQLでは初期値は NULL です。
三値論理とかいう独特のルールを持つため、初心者が苦しみます。

1	SELECT id, COALESCE(name, '名無しさん') name FROM namelist ;

ライフゲーム (Nested Flatten)

すごい。もっと評価されるべき。

ということで２次元に表示するSQLを作ってみました。
グライダーが実際に動いているのを見ると鳥肌モノです。sqliteのみでしか確認していませんが、caseの辺りを直せばどこでも動くと思います。

ちなみにsqliteはALLを使えないらしく、#5459 の28行目を max(G)に変えて問題なく動きました。

create table LG_ROWS ( Y integer );
insert into LG_ROWS values (0);
insert into LG_ROWS values (1);
insert into LG_ROWS values (2);
insert into LG_ROWS values (3);
insert into LG_ROWS values (4);

select 0 SEDAI
     , case (CM3.G isnull) when 0 then "o" else " " end
     , case (CM2.G isnull) when 0 then "o" else " " end
     , case (CM1.G isnull) when 0 then "o" else " " end
     , case (CZ0.G isnull) when 0 then "o" else " " end
     , case (CP1.G isnull) when 0 then "o" else " " end
     , case (CP2.G isnull) when 0 then "o" else " " end
     , case (CP3.G isnull) when 0 then "o" else " " end
from LG_ROWS R
left join life CM3 on R.Y = CM3.Y and CM3.X = -3 and CM3.G = SEDAI
left join life CM2 on R.Y = CM2.Y and CM2.X = -2 and CM2.G = SEDAI
left join life CM1 on R.Y = CM1.Y and CM1.X = -1 and CM1.G = SEDAI
left join life CZ0 on R.Y = CZ0.Y and CZ0.X =  0 and CZ0.G = SEDAI
left join life CP1 on R.Y = CP1.Y and CP1.X =  1 and CP1.G = SEDAI
left join life CP2 on R.Y = CP2.Y and CP2.X =  2 and CP2.G = SEDAI
left join life CP3 on R.Y = CP3.Y and CP3.X =  3 and CP3.G = SEDAI
order by R.Y;

データの整列 (Nested Flatten)

#5889 の答えとほとんど変わらないけど。

--テーブル：POINTS
create table POINTS (
  X number(10),
  Y number(10)
);
--データ
insert into POINTS values (-2, 2);
insert into POINTS values (3, 2);
insert into POINTS values (1, -5);
insert into POINTS values (4, 5);
insert into POINTS values (1, -2);
--辞書順
select * from POINTS order by X, Y;
--距離順
select * from POINTS order by x*x + y*y;

年間カレンダー (Nested Flatten)

365行(or 366行)をだらーっと出力しますが、年間のカレンダーには一応なっています。

+------------------------+
| date                   |
+------------------------+
| 2008/1/1 (Tuesday)     | 
| 2008/1/2 (Wednesday)   | 
| 2008/1/3 (Thursday)    | 
(略)
| 2008/12/29 (Monday)    | 
| 2008/12/30 (Tuesday)   | 
| 2008/12/31 (Wednesday) | 
+------------------------+

-- いつものように数字を用意しておく
DROP TABLE if exists num_chars;
CREATE TABLE num_chars(id int not null);
INSERT INTO num_chars VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9);
DROP TABLE if exists nums;
CREATE TABLE nums as (
  SELECT n1.id + (n2.id * 10) + (n3.id * 100) as id
    FROM num_chars n1, num_chars n2, num_chars n3);

-- 2008年を指定
SET @ycalendar = 2008;
SELECT date_format(makedate(@ycalendar, id), '%Y/%c/%e (%W)') as date
  FROM nums
 WHERE nums.id between 1 and (365 + day(last_day(concat(@ycalendar, '-2-1'))) - 28);

ライフゲーム (Nested Flatten)

まだ投稿されていないようなのでSQLで書いてみました。
Microsoft SQL Server 2005 で確認しています。

/* 生存セルを格納する表: G=世代 */
CREATE TABLE LIFE (G INT, X INT, Y INT)

/* 周囲9セルを求めるための補助的な表 */
CREATE TABLE NEAR (X INT, Y INT)
INSERT INTO NEAR VALUES (-1, -1)
INSERT INTO NEAR VALUES ( 0, -1)
INSERT INTO NEAR VALUES ( 1, -1)
INSERT INTO NEAR VALUES (-1,  0)
INSERT INTO NEAR VALUES ( 0,  0)
INSERT INTO NEAR VALUES ( 1,  0)
INSERT INTO NEAR VALUES (-1,  1)
INSERT INTO NEAR VALUES ( 0,  1)
INSERT INTO NEAR VALUES ( 1,  1)

/* 初期配置 (グライダー) */
INSERT INTO LIFE VALUES (0, 1, 0)
INSERT INTO LIFE VALUES (0, 0, 1)
INSERT INTO LIFE VALUES (0, 0, 2)
INSERT INTO LIFE VALUES (0, 1, 2)
INSERT INTO LIFE VALUES (0, 2, 2)

/* 処理本体: 実行するたびにLIFE表に次世代を挿入します */
INSERT INTO LIFE
SELECT L1.G + 1, L1.X, L1.Y
FROM (SELECT L.G AS G, L.X + N.X AS X, L.Y + N.Y AS Y, COUNT(*) AS C
      FROM LIFE L, NEAR N
      WHERE L.G >= ALL(SELECT G FROM LIFE)
      GROUP BY L.G, L.X + N.X, L.Y + N.Y) L1
      LEFT JOIN LIFE L2 ON L2.G = L1.G AND L2.X = L1.X AND L2.Y = L1.Y
WHERE L1.C = 3 OR L2.G IS NOT NULL AND L1.C = 4

除算・余剰を使わずに閏年 (Nested Flatten)

SQLで書いてみました。十分な行数をもつテーブルT_DUMMYがあるものとします。

SELECT CASE WHEN TB_FORE.Y IS NULL
           THEN '平年'
            ELSE CASE WHEN TB_FOREHANDRED.Y IS NOT NULL
                      THEN '閏年'
                      WHEN TB_HANDRED.Y IS NOT NULL
                      THEN '平年'
                 ELSE '閏年'
            END
       END AS RESULT 
FROM (SELECT ABS(:ARG) AS Y FROM DUAL) TB_ARG
LEFT JOIN (SELECT ROWNUM *   4 AS Y FROM T_DUMMY ) TB_FORE 
     ON TB_ARG.Y = TB_FORE.Y
LEFT JOIN (SELECT ROWNUM * 100 AS Y FROM T_DUMMY ) TB_HANDRED
     ON TB_ARG.Y = TB_HANDRED.Y
LEFT JOIN (SELECT ROWNUM * 400 AS Y FROM T_DUMMY ) TB_FOREHANDRED
     ON TB_ARG.Y = TB_FOREHANDRED.Y

続・ファイル内の重複行削除 (Nested Flatten)

使い方：sh uniq.sh input.txt

http://unicode.org/にあるUnihan.txtを37個連結した、
約4000万行（約1GB）のファイルの処理に、
Core2 6700, メモリ2GB、MySQL 5.0.45（設定ファイルはmy-huge.cnf）で、
約23分かかりました（消費メモリは約400MB）

uniq.shは下に

mysql -uroot -N -r test << EOF

DROP TABLE IF EXISTS tmp;
CREATE TABLE tmp (
  id INT PRIMARY KEY AUTO_INCREMENT,
  line LONGTEXT NOT NULL,
  INDEX (line(10))
) CHARACTER SET UTF8;

LOAD DATA LOCAL INFILE "$1" INTO TABLE tmp FIELDS TERMINATED BY '\n' (line);

SELECT line FROM tmp GROUP BY line ORDER BY max(id);

EOF

ファイル内の重複行削除(後優先) (Nested Flatten)

使い方: sh uniq.sh input.txt

「シビア」な場合に想定される「DBMSの再発名」の準備です。#3のメモリは主記憶と解釈しました。
キャッシュで済んでしまうくらい小さいデータセットの場合にはこの解釈でも問題になるわけですが、
そのことを明示しているわけではないということで

uniq.shの内容は下に

mysql -uroot -p -N test << EOF

DROP TABLE IF EXISTS tmp;
CREATE TABLE tmp (
  id INT PRIMARY KEY AUTO_INCREMENT,
  line LONGTEXT NOT NULL
) CHARACTER SET UTF8;

LOAD DATA LOCAL INFILE "$1" INTO TABLE tmp FIELDS TERMINATED BY '\n' (line);

SELECT line FROM tmp GROUP BY line ORDER BY MAX(id);

EOF

格子点の列挙 (Nested Flatten)

MySQL 限定。
最初に整数の組み合わせを作ってしまってから、
それをソートしています。

1000番目は (-8, 16) と出ました。

DROP TABLE IF EXISTS digits;
CREATE TABLE digits(n INTEGER PRIMARY KEY);
INSERT INTO digits VALUES(0), (1), (2), (3), (4), (5), (6), (7), (8), (9);

DROP TABLE IF EXISTS integers;
CREATE TABLE integers
SELECT n 
FROM ( SELECT a.n + (b.n * 10) AS n FROM digits a, digits b
        UNION
       SELECT - (a.n + (b.n * 10)) AS n FROM digits a, digits b) a;

SET @r = 0;
SELECT x, y
  FROM ( SELECT a.n AS x
              , b.n AS y
              , a.n * a.n + b.n * b.n AS magnitude
              , atan(b.n, a.n) + CASE WHEN atan(b.n, a.n) < 0
                                      THEN 2 * pi()
                                      ELSE 0 END AS angle
              , (@r := @r + 1) AS row   
           FROM integers a, integers b
       ORDER BY magnitude, angle) c
 WHERE row <= 1000;

九九の表示 (Nested Flatten)

確認してませんが、PostgreSQL でも動くはずです。
MySQL には、TO_CHAR が無いので、どうやって整形したらいいんだろう？

DROP TABLE digits;
CREATE TABLE digits(n INTEGER PRIMARY KEY);
INSERT INTO digits VALUES(1);
INSERT INTO digits VALUES(2);
INSERT INTO digits VALUES(3);
INSERT INTO digits VALUES(4);
INSERT INTO digits VALUES(5);
INSERT INTO digits VALUES(6);
INSERT INTO digits VALUES(7);
INSERT INTO digits VALUES(8);
INSERT INTO digits VALUES(9);

  SELECT a.n || ' * ' || b.n || ' = ' || TO_CHAR(a.n * b.n , '99') AS kuku
    FROM digits a, digits b
ORDER BY b.n, a.n ;

重複する要素を取り除く (Nested Flatten)

'3, 1, 4, 1, 5, 9, 2, 6, 5'という「配列のような文字列」をカンマで区切って重複を調べます。

set @xs = '3, 1, 4, 1, 5, 9, 2, 6, 5';

drop table if exists num_chars;
create table num_chars(id int not null);
insert into num_chars values (0), (1), (2), (3), (4), (5), (6), (7), (8), (9);

drop table if exists nums;
create table nums as (
  select n1.id + (n2.id * 10) + (n3.id * 100) as id
  from num_chars n1, num_chars n2, num_chars n3);

select
  x
from (
  select
    num
  , trim(substring_index(substring_index(@xs, ',', num), ',', -1)) as x
  from (
    select id as num from nums
    where id >= 1
      and id <= (length(@xs) - length(replace(@xs, ',', '')) + 1)
    ) as nums
  ) as xs
group by x having count(x) < 2
order by min(num);

SQLで「配列のようなもの」をどう考えるかで悩んだ時間の方が長かったです。
テーブルを使うのは都合良すぎで、お題から外れるような気がするのですが。

drop table if exists xs;
create table xs(id int not null auto_increment primary key, x int not null);
insert into xs(x) values (3), (1), (4), (1), (5), (9), (2), (6), (5);

select
  x
from xs
group by x having count(x) < 2
order by min(id);

長方形の交差判定 (Nested Flatten)

可能ならCHECK制約つけたいところ。

重なりあっていればtrueが、そうでなければfalseが表示されるはずです。

-- CREATE TABLEしなくてもできる
select 
  (case
    when b2.xleft >= b1.xright
      or b2.ytop >= b1.ybottom
      or b1.xleft >= b2.xright
      or b1.ytop >= b2.ybottom
      then 'false'
    else 'true' end) as overlap
from
  (select 0 xleft, 0 ytop, 100 xright, 100 ybottom) b1
, (select 100 xleft, 0 ytop, 200 xright, 100 ybottom) b2;

-- 個人的にはCREATE TABLEする方が好み
drop table if exists box;
create table box(
    id int auto_increment primary key
  , xleft int not null
  , ytop int not null
  , xright int not null
  , ybottom int not null
);

insert into
  box(xleft, ytop, xright, ybottom)
values
  (0, 0, 100, 100)
, (100, 0, 200, 100)
, (0, 50, 100, 150)
, (0, 100, 100, 200)
, (100, 100, 400, 400)
, (200, 200, 500, 500);

select 
  (case
    when b2.xleft >= b1.xright
      or b2.ytop >= b1.ybottom
      or b1.xleft >= b2.xright
      or b1.ytop >= b2.ybottom
      then 'false'
    else 'true' end) as overlap
from
  (select * from box where id = 1) b1
, (select * from box where id = 2) b2;

DouKaku?

Language detail: SQL

Unsolved challenges

codes