pockestrap

Programmer's memo

I18nはユニークではない

I18nはユニークではない。grepしてみよう。

$ grep -E '^i.{18}n$' /usr/share/dict/words
institutionalisation
institutionalization
internationalisation
internationalization

4件引っかかった。このうち2つはszの違いなので無視するにしても、I18nにはinstitutionalisationとinternationalisationの2つの候補があることがわかる。

では、I18nのような表記を行った時にユニークとなるような単語はどれだけ存在するのであろうか?

問題

I18n形式で記述した際に一意となるような単語を出力せよ。なお、単語はcase insensitiveで扱うこと。
単語の一覧は/usr/share/dict/wordsファイルに改行区切りで与えられる。
また、I18n形式とは、以下を全て満たす形式のことを言う。

  • 3文字以上の単語であること
  • ある単語をI18n形式で表した時、以下のようになる
    • I18n形式の最初の文字はその単語の最初の文字
    • I18n形式の最後の文字はその単語の最後の文字
    • 2文字目〜最後から2文字目は、その単語の文字数から2を引いた数の10進数での文字列表現

I18n形式の例

  • internationalisation -> i18n
  • vim -> v1m
  • foobar -> f4r

また、一意であるとは単語をI18n形式で表した時に、その単語意外にそのI18n形式で表される単語が存在しないことを言う。
例えばi18ninstitutionalisation, internationalisationなど複数の単語が該当するため、一意ではない。
また、v1mvimしか該当する単語が存在しないため、一意である1

解答例

以下にRubyでの解答例を示す23

hash = {}
File.read('/usr/share/dict/words').each_line.map(&:chomp).map(&:downcase).uniq.each do |word|
  key = [word[0], word[-1], word.size]
  (hash[key] ||= []) << word
end


w = hash.values.select do |words|
  words.size == 1
end.flatten.select do |word|
  word.size > 2
end

puts(*w)

これを実行すると、非常に多くの単語が表示される。

$ ruby test.rb | wc -l 
1160

どうやらI18n形式で一意となるような単語は1160単語存在するようだ。


  1. なお、e3cという形式で表される単語は複数存在する。

  2. 雑なコードなので、ツッコミどころは色々あると思う。

  3. 英国、米国英語が混ざっているので、その重複を取り除けばより多くの単語がi18n形式でユニークだと言えるだろうが、今回はその差は無視した。