LL Golf Hole 4 - 文章から単語の索引を作る DouKaku?

GNU GENERAL PUBLIC LICENSE Version 3に登場する単語について、単語が登場する行を示した索引を作成してください。

与えられる文章についてはリテラルで表記する、標準入力で与えられる、引数でファイル名が与えられるなどは自由とします。

余力のあるものはこのプログラムを短くしてみたり、短くしてみたり、短くしてください。

※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。

see: open-uri - Rubyリファレンスマニュアル

#!/usr/bin/env ruby
require 'open-uri'
lines = open('http://www.gnu.org/licenses/gpl.txt').readlines
dic = {}
lines.each_with_index do |line, index|
    line.scan(/\w+/).each do |word|
        dic[word] = dic[word] ? dic[word] << index + 1 : [index + 1]
    end
end
p dic

普通に解いてみました(294 bytes)。ファイル名を引数で与えます。

ハッシュテーブルのままだと分からないので最後に alist に変換して出力しています。また、大文字小文字は無視して、かつインデックスのリストを作るときに同一行番号が重複することは避けています。

実行例:

% gosh gpl.txt
... 略 ...

(use util.list)(use srfi-13)(let1 t(hash-table'equal?)(call-with-input-file(car *argv*)(#0=lambda(i)(port-fold(#0#(s n)(for-each(#0#(w)(hash-table-update! t(string-downcase w)(#0#(l)(if(memq n l)l(cons n l)))'()))(string-split s #[\W]))(+ n 1))1(cut read-line i))))(print(hash-table->alist t)))

with-input-from-fileを使えばもっと短くなりました (284 bytes)。

(use util.list)(use srfi-13)(let1 t(hash-table'equal?)(with-input-from-file(car *argv*)(cut port-fold(#0=lambda(s n)(for-each(#0#(w)(hash-table-update! t(string-downcase w)(#0#(l)(if(memq n l)l(cons n l)))'()))(string-split s #[\W]))(+ n 1))1|read-line|))(print(hash-table->alist t)))

まだ無駄があった (277 bytes)。

(use util.list)(use srfi-13)(let1 t(hash-table'equal?)(with-input-from-file(car *argv*)(cut port-fold(#0=lambda(s n)(map(#0#(w)(hash-table-update! t(string-downcase w)(#0#(l)(if(memq n l)l(cons n l)))()))(string-split s #[\W]))(+ n 1))1 read-line))(print(hash-table->alist t)))

空気読まずに、普通にGO

url = "http://www.gnu.org/licenses/gpl.txt"
dic = {}
for index, line in enumerate(urllib.urlopen(url)):
    for word in re.findall('\w+', line):
        dic.setdefault(word, []).append(index + 1)
print dic

コード内にURLが出るかでないかで長さがだいぶ違ってくるのでは・・・。

とりあえず普通に。

1 2	f <- 'http://www.gnu.org/licenses/gpl.txt' sapply(names(table(unlist(strsplit((l<-readLines(f)),"\\W+")))), function(s) grep(s,l))

もっと素直にやっても結構短くなるみたいですよ(262bytes)。

(use file.util)(use util.list)(use srfi-13)(do((t(make-hash-table 'string=?))(ls(file->string-list(car *argv*))(cdr ls))(n 1 (+ n 1)))((null? ls)(print(hash-table->alist t)))(dolist(w(string-split(car ls)#[\W]))(hash-table-push! t (string-downcase w) n)))

Squeak Smalltalk で。

| dict stream delimiters lineCount |
dict := Dictionary new.
stream := HTTPSocket httpGet: 'http://www.gnu.org/licenses/gpl.txt'.
delimiters := Character allCharacters reject: [:each | each isLetter].
lineCount := 0.
[stream atEnd] whileFalse: [
    lineCount := lineCount + 1.
    ((stream upTo: Character lf) subStrings: delimiters) do: [:word | 
        | lines |
        lines := dict at: word ifAbsentPut: [OrderedCollection new].
        lines add: lineCount]].
^dict

文書データを取得するのも問題に含まれるのでしょうか？

文章はコンパイル時に文字列リテラルとして取り込むので、dmdの-Jオプションでgpl.txtのあるディレクトリを指定してください。

private import std.stdio, std.string, std.regexp;

auto text = import("gpl.txt");

void main() {
    int[][string] dict;
    auto re = RegExp(r"[\w-]+");
    foreach(i, line; text.splitlines()) {
        foreach(m; re.search(line)) {
            dict[m[0].tolower()] ~= i + 1;
        }
    }
    writeln(dict);
}

どうやっても短くならないです。

using System;using System.Collections.Generic;using System.IO;using System.Net;class P{static void Main(){char[]c=new char[]{' ',',','.','\'',';',':','-','?','\n','\r','(',')','/','\\','<','>','\"'};Dictionary<string,List<int>>d=new Dictionary<string,List<int>>();StreamReader s=new StreamReader(WebRequest.Create("http://www.gnu.org/licenses/gpl.txt").GetResponse().GetResponseStream());for(int l=1;!s.EndOfStream;l++){foreach(string t in s.ReadLine().Split(c)){string w=t.Trim().ToLower();if(w!="")if(d.ContainsKey(w)){if(!d[w].Contains(l))d[w].Add(l);}else d.Add(w,new List<int>(new int[]{l}));}}List<string>k=new List<string>(d.Keys);k.Sort((x,y)=>{int r=d[y].Count-d[x].Count;if(r==0){r=d[x][0]-d[y][0];}return r;});foreach(string m in k){Console.WriteLine("<<"+m+">>"+" "+d[m].Count+"回");foreach(int u in d[m]){Console.Write(u.ToString()+", ");}Console.WriteLine("\n");}Console.ReadLine();}}

「g」がファイル名の場合 107 bytes です。

1	<?php foreach(file(g)as$l=>$d){preg_match_all('/\w+/',$d,$m);foreach($m[0]as$w)$D[$w][]=$l+1;}print_r($D);

単語の定義は、正規表現で w+ としています。大文字小文字を区別しません（小文字に変換しています）。同じ行に同じ単語が複数出現する場合でも、行番号は1つのみ出力します。

import java.io.*;
import java.net.*;
import java.util.regex.*;
import java.util.*;

public class Sample {
    private final static Pattern WORD = Pattern.compile("(\\w+)");

    public static Map<String, Set<Integer>> indexWords(LineNumberReader r) throws IOException {
        TreeMap<String, Set<Integer>> ref = new TreeMap<String, Set<Integer>>();
        String line;
        while ((line = r.readLine()) != null) {
            Matcher m = WORD.matcher(line);
            while (m.find()) {
                String w = m.group().toLowerCase();
                if (ref.get(w) == null)
                    ref.put(w, new TreeSet<Integer>());
                ref.get(w).add(r.getLineNumber());
            }
        }
        return ref;
    }
    
    public static void main(String[] args) throws IOException {
        URL u = new URL("http://www.gnu.org/licenses/gpl.txt");
        LineNumberReader r = new LineNumberReader(new InputStreamReader(u.openStream()));
        Map<String, Set<Integer>> ref = indexWords(r);
        for (String key: ref.keySet()) {
            System.out.println(key + ref.get(key));
        }
    }
}

ちょっと短くしました。

1 2	f <- 'http://www.gnu.org/licenses/gpl.txt' sapply(unique(unlist(strsplit((l<-readLines(f)),"\\W+"))),grep,l)

ゴルフじゃないけど汚くならない程度に短くした版。

(loop with table = (make-hash-table :test 'equal)
  for i from 1 while (listen) do
  (loop with a = 0 and b = 0 and s = (read-line)
    while (and (setf a (position-if #'alpha-char-p s :start b))
               (setf b (position-if-not #'alpha-char-p s :start a)))
    do (push i (gethash (subseq s a b) table)))
  finally
  (loop for k being each hash-key of table using (hash-value v)
    do (format t "~A: ~{~D~^, ~}~%" k (nreverse v))))

sh + nl + sed + sort。標準入力。

1	nl -ba\|sed 's/[^[:alnum:]#]\+\\|$/#/g;:a;s/^$#\([0-9]$#.\)#/\1\t\2\n/;ta;s/.#//'\|sort -u -k 1,1 -k 2n\|sed 'h;:a;$b;N;/^$.\t$$.$\n\1$.$$/{s//\1\2,\3/;ba};$b;P;D'

標準入力から読み込み。スペース・改行を省いたら363byte。
そういえば C#ってカンマ演算子使えないんですね。短くならないわけだ。

using System;
using System.Text.RegularExpressions;
class P
{
    static void Main()
    {
        var d = new System.Collections.Generic.Dictionary<String, int>();
        var n = 1;
        for (var s = "" ; (s = Console.ReadLine()) != null ; n++)
            new Regex("\\w+").Replace(s, delegate(Match m)
            {
                var k = m.ToString();
                if (!d.ContainsKey(k)) d[k] = n;
                return k;
            });
        foreach (var k in d)
            Console.Write("{0}: {1}\n", k.Key, k.Value);
    }
}

pure bashで。標準入力。

shopt -s extglob
while read s;do
  ((++i))
  for w in ${s//+([^[:alnum:]])/ };do
    eval _X_$w=\${_X_$w}$i,
  done
done
for w in ${!_X_*};do
  echo ${w#_X_}: ${!w}
done

SWI-Prologで。大文字は小文字に変換しました。次のようにして、参照できます。
?- index('future', N).
N = 58 ;
N = 579.

:- use_module(library('http/http_open')).

assert_word(_, '') :- !.
assert_word(In, W) :- downcase_atom(W, WL), line_count(In, N), assert(index(WL, N)).

make_index(In, W) :- at_end_of_stream(In), assert_word(In, W), !.
make_index(In, W) :- peek_char(In, C), (char_type(C, csym) -> atom_concat(W, C, W1);
     assert_word(In, W), W1 = ''), get_char(In, _), make_index(In, W1).

:- http_open('http://www.gnu.org/licenses/gpl.txt', In, []), make_index(In, ''), close(In).

gawk 一行野郎で。文章は標準入力、出力は標準出力です。

1	gawk -F'\\W' '{ for (i=1; i<= NF; i++) { if ($i != ""){h[$i, NR] = NR; }}} END { for (k in h){split(k,s,SUBSEP);print s[1], h[k];}}'

覚えたてのmap使ってみました。文章は標準入力で。83byte。

1 2	map{map{push@{$w{lc$_}},$l+1}/\w+/gi;$l++}<>; map{print"$_ @{$w{$_}}\n"}sort keys%w;

stdin → stderrで76B。
URLから読む場合は「System.in」を「new URL('http://..')」に。

i=0
m=[:]
System.in.eachLine{++i;(it=~/\w+/).each{m[it]=(m[it]?:[])<<i}}
0|m

素直にstdinから読んで146B。

1	(let([t(hash-table'equal?)][n 1])(guard,,(hash-table-map t print)(while(map(cut hash-table-push! t <> n)(string-split(read-line)#[\W]))(inc! n))))

また、Javaで頑張ってGolfしてみました。改行とTabを除いて、283byteでした。

import java.util.*;
class P{
    public static void main(String[]a){
        Map m=new TreeMap();
        Scanner i=new Scanner(System.in);
        for(int l=0;i.hasNext();l++)
            for(String w:i.nextLine().split("\\W")){
                if(m.get(w)==null)
                    m.put(w,new TreeSet());
                ((Set)m.get(w)).add(l);
            }
        System.out.println(m.entrySet());
    }
}

Boost(1.35.0)を使ってどうにかこうにか。

もはやGolfではないです。

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <iterator>
#include <algorithm>
#include <boost/asio.hpp>
#include <boost/regex.hpp>

using namespace std;
using namespace boost;
using namespace boost::asio;

typedef vector<string>            Strings;
typedef map<string, vector<int> > Dic;

int main()
{
    ip::tcp::iostream src( "www.gnu.org", "http" );

    src << "GET /licenses/gpl.txt HTTP/1.0\r\n"
        << "Host: www.gnu.org\r\n"
        << "\r\n"
        << flush;

    // 読み込み
    Strings lines;
    string  s;
    bool    body = false;
    while(getline(src, s))
    {
        if(body) lines.push_back(s);
        if(s == "\r") body = true;
    }

    // 解析
    regex re("¥¥w+");
    Dic   dic;
    int   lineno = 1;
    for(Strings::const_iterator i = lines.begin(); i != lines.end(); ++i)
    {
        sregex_iterator ri(i->begin(), i->end(), re);
        sregex_iterator end;
        for(; ri != end; ++ri)
        {
            dic[ri->str()].push_back(lineno);
        }
        ++lineno;
    }

    // 書き出し
    for(Dic::const_iterator i = dic.begin(); i != dic.end(); ++i)
    {
        cout << i->first << ":";
        copy(i->second.begin(), i->second.end(), ostream_iterator<int>(cout, ","));
        cout << endl;
    }

    return 0;
}

JavaScript(Rhino)で。入力は標準入力から。 225byte。

r=new java.io.BufferedReader(new java.io.InputStreamReader(java.lang.System["in"]));
d={};
for(i=1;l=r.readLine();i++)for(a=l.match(/\w+/g);w=a&&a.pop();)(d[w]=d[w]||[]).push(i);
for(w in d)println(w+":"+d[w].join(" "));

たぶん狐限定114B。

1	javascript:for(d={},i=1;l=/.+/g(document.body.textContent);++i)for(;w=/\w+/g(l);)(d[w]=d[w]\|\|[]).push(i);uneval(d)

マイナスモデもらったので、sed 3丁がけで再投稿。時間がかかります。

1	sed =\|sed 'N;s/[^[:alnum:]]\+\\|$/#/g;:a;s/^$\([0-9]$#.\)#/\1\t\2\n/;ta;s/.#//'\|sed ':a;$b;N;/\n$/{s///;ba};:b;/$[[:alnum:]]\t$$[0-9,]$$\n.$\n\1$[0-9]*$$/{s//\1\2,\4\3/;bb};ba'

標準入力からで63Byte。

1	d=Hash.new [];$<.map{\|l\|l.scan(/\w+/){d[$&]+=[$<.lineno]}};p d

　お世辞にも短いとは言い難いですが...。

import scala.io._
import java.net._
import scala.collection.mutable._
import scala.util.matching._
object M extends Application{
    Source.fromURL(new URL("http://www.gnu.org/licenses/gpl.txt")).getLines.toList.zipWithIndex.foldLeft(new HashMap[String,List[Int]]){(h,d) =>
        (new Regex("\\w+")).findAllIn(d._1).foreach{w=>if(h.isDefinedAt(w))h.update(w,h.apply(w)+(d._2+1))else h.update(w,List(d._2+1))};h
    }.elements.toList.sort{(a,b)=>a._1<b._1}.foreach{e=>
        printf("%s\t%s\n",e._1,e._2.tail.foldLeft(e._2.head.toString){(j,i)=>j+","+i.toString})
    }
}

awk -f word.awk gpl.txt

1 2	{gsub(/[^a-zA-Z0-9]/, " ");for(i=1;i<=NF;i++)t[$i]=t[$i]":"NR} END{for(k in t)print k t[k]}

前回の、数え間違えてました。ついでなので少し改良して、55byte。

1	d=Hash.new [];$<.map{\|l\|l.scan(/\w+/){d[$&]+=[$.]}};p d

ナイーブに。全然短くない

module Main where

import Control.Arrow
import Data.Char
import Data.Function
import Data.List

main :: IO ()
main = print
     . map (first head . unzip)
     . groupBy ((==) `on` fst)
     . sortBy (compare `on` fst)
     . concat
     . zipWith (map . flip (,)) [1..]
     . map (map head . group . sort . map (map toLower) . words')
     . lines =<< getContents

ws :: [Char]
ws = '_':concat [['0'..'9'],['a'..'z'],['A'..'Z']]

words' :: String -> [String]
words' = unfoldr phi
  where phi ss = case dropWhile (flip notElem ws) ss of 
                   ""  -> Nothing
                   ss' -> Just $ span (flip elem ws) ss'

seriesとcl-ppcreとdrakmaを使ってみました。

(require :cl-ppcre)
(defpackage :doukaku-198 (:use :cl :drakma :series))
(in-package :doukaku-198)

(let* ((text (http-request "http://www.gnu.org/licenses/gpl.txt"))
       (ht (collect-hash (scan (ppcre:all-matches-as-strings "\\w+" text)) 
                         (series () )
                         :test #'equalp)))
  (iterate ((line (scan (ppcre:split "\\n" text)))
            (num (scan-range :from 1)))
    (dolist (w (ppcre:all-matches-as-strings "\\w+" line))
      (push num (gethash w ht))))
  (iterate (((k v) (scan-hash ht)))
    (format t "~A => ~A~%" k (nreverse v))))

苦し紛れに少し短くしてみました。出力がイマイチ (;<>;)な71バイト。文章はstdin、出力はstderrで。

1 2	use Data::Dumper; for(;<>;){map{push@{$w{lc$_}},$.}/\w+/gi}warn Dumper%w

DouKaku?

LL Golf Hole 4 - 文章から単語の索引を作る

Posted feedbacks - Flatten