A_country_leader.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Country leaderに挑戦"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Google APAC university test 2017 round AのA問題[country leader](https://code.google.com/codejam/contest/11274486/dashboard#s=p0)に挑戦する．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "この問題は，\n",
    "\n",
    "- 入力: 名前の集合\n",
    "- 出力: 使われている文字の種類数が最大の名前（ただし最大の名前が複数あるならば，その中で辞書順に最初の名前）\n",
    "\n",
    "である．\n",
    "なお，空白文字は文字の種類数に含めない．\n",
    "また，この問題では使われている文字の種類数が最大の名前を「リーダー」としている．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "入力と，それに対する正しい出力の例は\n",
    "\n",
    "- 入力が{\"ADAM\", \"BOB\", \"JOHNSON\"}ならば，出力は\"JOHNSON\"\n",
    "- 入力が{\"A AB C\", \"DEF\"}ならば，出力は\"A AB C\"\n",
    "\n",
    "である．\n",
    "\n",
    "\"ADAM\"に使われている文字は3種類，\"BOB\"に使われている文字は2種類，\"JOHNSON\"に使われている文字は5種類であるからである．\n",
    "\n",
    "\"A AB C\"に使われている文字は3種類，\"DEF\"に使われている文字も3種類であるが，辞書順では\"A AB C\"の方が\"DEF\"よりも先だからである．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解答例として，名前を引数として文字の種類数を返す関数をdifferent letters，その関数を用いて問題を解く関数をsolveとして以下に定義する．\n",
    "このdifferent_lettersでは，名前に使われている文字の種類数を数えるために辞書を用いる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def different_letters(name):\n",
    "    used_alphabets = {} # 文字の種類数を数えるための辞書を用意する．\n",
    "    for char in name: # 名前のそれぞれの文字に関して以下を繰り返す．\n",
    "        if char == ' ': # （問題の仮定より）空白文字ならば，\n",
    "            continue # 何も処理しない．\n",
    "        else: # そうでない（空白文字でない）ならば，\n",
    "            used_alphabets[char] = 1 # その文字が使われているしるしとして辞書の値を1にする．\n",
    "    return len(used_alphabets.keys()) # 辞書のキーの個数が，名前で使われている文字の種類数のはずである．\n",
    "\n",
    "\n",
    "def solve(names):\n",
    "    max_letters = 0 # 最大文字種類数の最大値を覚えるための変数を用意する．\n",
    "    leader = '' # リーダーの名前を覚えるための変数を用意する．\n",
    "    for name in names: # すべての名前に関して以下を繰り返す．\n",
    "        diff_letters = different_letters(name) # まず，その名前で使われている文字の種類数を数える．\n",
    "        if max_letters < diff_letters: # その名前の文字の種類数が，それまでの最大値よりも大きいならば，\n",
    "            max_letters = diff_letters # その種類数を最大値として覚え直し，\n",
    "            leader = name # その名前をリーダーとする．\n",
    "        elif max_letters == diff_letters: # そうでなくて，その名前の種類数がそれまでの最大値と同じで，\n",
    "            if name < leader: # かつ，現時点でのリーダーの名前よりも辞書順で先ならば，\n",
    "                leader = name # その名前をリーダーとする．\n",
    "    return leader"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pythonでは，文字列を比較することは，辞書順の大小を比べることである．\n",
    "よって，このように簡潔に書ける．\n",
    "\n",
    "実際にサンプルの入力を与えて，出力を確かめてみる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'JOHNSON'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve(['ADAM', 'BOB', 'JOHNSON'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'A AB C'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve(['A AB C', 'DEF'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "これだけのサンプルで判断するのは早計かも知れないが，とりあえず良さそうである．\n",
    "\n",
    "続けて，上記の関数solveを用いて，入力のファイルを読み込み，出力のファイルを書き出す関数answerを以下に定義する"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def answer(input_file_name, output_file_name):\n",
    "    input_file = open(input_file_name)\n",
    "    output_file = open(output_file_name, 'w')\n",
    "    T = int(input_file.readline())\n",
    "    for case_number in range(1, T + 1):\n",
    "        N = int(input_file.readline())\n",
    "        names = []\n",
    "        for n in range(N):\n",
    "            names += [input_file.readline().rstrip()]\n",
    "        output_file.write('Case #{0}: {1}\\n'.format(case_number, solve(names)))\n",
    "    input_file.close()\n",
    "    output_file.close()\n",
    "    return # このreturnは必要ないが，お行儀よく一応付けておく．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Small datasetの入力ファイルをA-small-practice.in，large datasetの入力ファイルをA-large-practice.inとして以下を実行してみる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "answer('A-small-practice.in', 'A-small-practice.out')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "answer('A-large-practice.in', 'A-large-practice.out')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "出力ファイルA-small-practice.out，A-large-practice.outのいずれも正しいようだ．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 集合の利用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上で定義した，名前（あるいは文字列）に含まれる文字の種類数を数える関数different_lettersでは辞書を使った．\n",
    "\n",
    "しかし一方で，何かが「ある」か「ない」かを処理するだけならばPythonのデータ構造である集合も便利である．\n",
    "ここでは集合を紹介する．\n",
    "\n",
    "Pythonの集合は，そのまま数学の集合を使えるデータ構造である．\n",
    "以下に使用例を示す．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "list_PP = ['pen', 'pineapple'] # まず，準備として文字列を要素とするリストを作る．\n",
    "list_AP = ['apple', 'pen']\n",
    "list_PPAP = ['pen', 'pineapple', 'apple', 'pen']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "set_PP = set(list_PP) # 組込み関数setはリストを元に集合を作る．\n",
    "set_AP = set(list_AP)\n",
    "set_PPAP = set(list_PPAP)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'pen', 'pineapple'}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set_PP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'apple', 'pen'}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set_AP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'apple', 'pen', 'pineapple'}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set_PPAP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "set_PPAPは集合なので，要素'pen'は1つだけ残る．\n",
    "\n",
    "そして，Pythonの集合は順番を区別しないので，要素はアルファベット順に並べ替えられて表示されている．\n",
    "\n",
    "以下に幾つか集合の演算の例を示す．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'apple', 'pen', 'pineapple'}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set_PP | set_AP # 和集合の計算"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'pen'}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set_PP & set_AP # 共通部分の計算"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'apple', 'pineapple'}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set_PP ^ set_AP # どちらかだけに含まれる要素の計算"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'pineapple'}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set_PP - set_AP # set_PPに含まれ，set_APに含まれない要素の計算"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(set_PPAP) # リストと同様に要素数は組込み関数lenでわかる．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "他にも集合の演算はあるが，より詳しくはネットなどで調べていただきたい．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "この集合を用いると，上記のdifferent_lettersはもっと簡潔に定義できる．\n",
    "\n",
    "以下にdifferent_lettersを再定義する．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def different_letters(name):\n",
    "    return len(set(name) - set([' ']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一行で書けてしまうので，実は関数として定義する必要はなかったかもしれない．\n",
    "\n",
    "一応解説すると，\n",
    "\n",
    "- set(name)で，文字列nameに含まれる文字からなる集合が作られる．文字列は（ほぼ）文字のリストという扱いだからである．\n",
    "- set([' '])で，空白文字だけを含む集合が作られる．\n",
    "- よってset(name) - set([' '])で「空白文字を除く，nameに含まれる文字の集合」が作られる．\n",
    "- その要素数は「nameに含まれる文字の種類数」である．\n",
    "\n",
    "solveとanswerを再定義して動作を試してみる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def solve(names): # 上での定義と全く同じである．\n",
    "    max_letters = 0 # 最大文字種類数の最大値を覚えるための変数を用意する．\n",
    "    leader = '' # リーダーの名前を覚えるための変数を用意する．\n",
    "    for name in names: # すべての名前に関して以下を繰り返す．\n",
    "        diff_letters = different_letters(name) # まず，その名前で使われている文字の種類数を数える．\n",
    "        if max_letters < diff_letters: # その名前の文字の種類数が，それまでの最大値よりも大きいならば，\n",
    "            max_letters = diff_letters # その種類数を最大値として覚え直し，\n",
    "            leader = name # その名前をリーダーとする．\n",
    "        elif max_letters == diff_letters: # そうでなくて，その名前の種類数がそれまでの最大値と同じで，\n",
    "            if name < leader: # かつ，現時点でのリーダーの名前よりも辞書順で先ならば，\n",
    "                leader = name # その名前をリーダーとする．\n",
    "    return leader\n",
    "\n",
    "def answer(input_file_name, output_file_name): # 上での定義と全く同じである．\n",
    "    input_file = open(input_file_name)\n",
    "    output_file = open(output_file_name, 'w')\n",
    "    T = int(input_file.readline())\n",
    "    for case_number in range(1, T + 1):\n",
    "        N = int(input_file.readline())\n",
    "        names = []\n",
    "        for n in range(N):\n",
    "            names += [input_file.readline().rstrip()]\n",
    "        output_file.write('Case #{0}: {1}\\n'.format(case_number, solve(names)))\n",
    "    input_file.close()\n",
    "    output_file.close()\n",
    "    return # このreturnは必要ないが，お行儀よく一応付けておく．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "answer('A-small-practice.in', 'A-small-practice.out')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "answer('A-large-practice.in', 'A-large-practice.out')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ファイルA-small-practice.out，A-large-practice.outのいずれも正しく出力される．"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}