speaking_in_tongue_2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Speaking in tonguesに挑戦（解答編）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Google code jam 2012 qualification round A. [Speaking in tongues](https://code.google.com/codejam/contest/1460488/dashboard)に挑戦する．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "この問題を入力と出力で定義すると，\n",
    "\n",
    "- 入力: 小文字アルファベットと空白からなるGoogle語の文字列$G$\n",
    "- 出力: Google語の文字列$G$を英語に変換した文字列$S$\n",
    "\n",
    "である．\n",
    "\n",
    "なお，Google語は英語のアルファベットを入れ替えただけである．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "これだけだと，Google語がなんだかわからないので，解きようがない．\n",
    "\n",
    "しかし，入力と出力の例が以下の通り与えられている．\n",
    "\n",
    "- 入力がejp mysljylc kd kxveddknmc re jsicpdrysiならば，出力はour language is impossible to understandである．\n",
    "- 入力がrbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd ならば，出力はthere are twenty six factorial possibilitiesである．\n",
    "- 入力がde kr kd eoya kw aej tysr re ujdr lkgc jvならば，出力はso it is okay if you want to just give upである．\n",
    "\n",
    "よって，この例からGoogle語と英語の辞書（略してグー英辞書）を作る．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "手作業でもグー英辞書は作れるが，できればプログラミングでどうにかしたい．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 入出力例から辞書を作る"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "これまでとは異なり，いきなり入力データを読み込んで，グー英辞書を作ることにする．\n",
    "\n",
    "グー英辞書を返す関数google_english_dictionaryを以下に定義する．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def google_english_dictionary(input_file_name, output_file_name):\n",
    "    input_file = open(input_file_name)\n",
    "    input_data = input_file.readlines()\n",
    "    input_file.close()\n",
    "    \n",
    "    output_file = open(output_file_name)\n",
    "    output_data = output_file.readlines()\n",
    "    output_file.close()\n",
    "    \n",
    "    T = int(input_data.pop(0))\n",
    "    \n",
    "    ge_dic = {}\n",
    "    for t in range(T):\n",
    "        google_string = input_data.pop(0).rstrip()\n",
    "        english_string = output_data.pop(0).split(':')[1]\n",
    "        english_string = english_string.strip()\n",
    "        for i in range(len(google_string)):\n",
    "            ge_dic[google_string[i]] = english_string[i]\n",
    "    return ge_dic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "早速，問題のページの入力サンプルをファイルA-sample.inとして，出力サンプルをファイルA-sample.outとして用意し，make_google_english_dictionaryを実行する．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ge_dic = google_english_dictionary('A-sample.in', 'A-sample.out')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "そして，出来上がったグー英辞書を確認する"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'e': 'o',\n",
       " 'j': 'u',\n",
       " 'p': 'r',\n",
       " ' ': ' ',\n",
       " 'm': 'l',\n",
       " 'y': 'a',\n",
       " 's': 'n',\n",
       " 'l': 'g',\n",
       " 'c': 'e',\n",
       " 'k': 'i',\n",
       " 'd': 's',\n",
       " 'x': 'm',\n",
       " 'v': 'p',\n",
       " 'n': 'b',\n",
       " 'r': 't',\n",
       " 'i': 'd',\n",
       " 'b': 'h',\n",
       " 't': 'w',\n",
       " 'a': 'y',\n",
       " 'h': 'x',\n",
       " 'w': 'f',\n",
       " 'f': 'c',\n",
       " 'o': 'k',\n",
       " 'u': 'j',\n",
       " 'g': 'v'}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ge_dic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "アルファベット順に並んでいる方が見やすいので，アルファベット順に表示する．\n",
    "\n",
    "アルファベット順に表示するために辞書のメソッドと組み込み関数を新たに紹介する．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "辞書のメソッドkeys()を使うと，辞書のキーの一覧を得られる．\n",
    "戻り値はdict_keysという型である．\n",
    "dict_keysはリストのように扱える型である．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_keys(['e', 'j', 'p', ' ', 'm', 'y', 's', 'l', 'c', 'k', 'd', 'x', 'v', 'n', 'r', 'i', 'b', 't', 'a', 'h', 'w', 'f', 'o', 'u', 'g'])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ge_dic.keys()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "組み込み関数sorted()を使うと，引数のリスト（あるいはそれっぽいもの）を昇順に並べ替えたリストが返される．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[' ',\n",
       " 'a',\n",
       " 'b',\n",
       " 'c',\n",
       " 'd',\n",
       " 'e',\n",
       " 'f',\n",
       " 'g',\n",
       " 'h',\n",
       " 'i',\n",
       " 'j',\n",
       " 'k',\n",
       " 'l',\n",
       " 'm',\n",
       " 'n',\n",
       " 'o',\n",
       " 'p',\n",
       " 'r',\n",
       " 's',\n",
       " 't',\n",
       " 'u',\n",
       " 'v',\n",
       " 'w',\n",
       " 'x',\n",
       " 'y']"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(ge_dic.keys())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "keys()とsorted()を使って，ge_dicの内容を表示してみる．\n",
    "以下ではフォーマット済み文字列リテラルの中でシングルクォーテーションを使っているので，一番外側はダブルクォーテーションで囲っている．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "' ': ' '\n",
      "'a': 'y'\n",
      "'b': 'h'\n",
      "'c': 'e'\n",
      "'d': 's'\n",
      "'e': 'o'\n",
      "'f': 'c'\n",
      "'g': 'v'\n",
      "'h': 'x'\n",
      "'i': 'd'\n",
      "'j': 'u'\n",
      "'k': 'i'\n",
      "'l': 'g'\n",
      "'m': 'l'\n",
      "'n': 'b'\n",
      "'o': 'k'\n",
      "'p': 'r'\n",
      "'r': 't'\n",
      "'s': 'n'\n",
      "'t': 'w'\n",
      "'u': 'j'\n",
      "'v': 'p'\n",
      "'w': 'f'\n",
      "'x': 'm'\n",
      "'y': 'a'\n"
     ]
    }
   ],
   "source": [
    "for k in sorted(ge_dic.keys()):\n",
    "    print(f\"'{k}': '{ge_dic[k]}'\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "このグー英辞書にはqとzがない．\n",
    "改めてサンプル入力とサンプル出力を見ると，確かにqとzがない．\n",
    "\n",
    "これではグー英辞書を完成できないと思われる．\n",
    "しかし，問題をよく読むと「例えば……'z'->'q'」と書いてある．\n",
    "\n",
    "残りの'q'は'z'しか割り当てる先がないので，合わせて辞書に加える．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ge_dic['z'] = 'q'\n",
    "ge_dic['q'] = 'z'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "' ': ' '\n",
      "'a': 'y'\n",
      "'b': 'h'\n",
      "'c': 'e'\n",
      "'d': 's'\n",
      "'e': 'o'\n",
      "'f': 'c'\n",
      "'g': 'v'\n",
      "'h': 'x'\n",
      "'i': 'd'\n",
      "'j': 'u'\n",
      "'k': 'i'\n",
      "'l': 'g'\n",
      "'m': 'l'\n",
      "'n': 'b'\n",
      "'o': 'k'\n",
      "'p': 'r'\n",
      "'q': 'z'\n",
      "'r': 't'\n",
      "'s': 'n'\n",
      "'t': 'w'\n",
      "'u': 'j'\n",
      "'v': 'p'\n",
      "'w': 'f'\n",
      "'x': 'm'\n",
      "'y': 'a'\n",
      "'z': 'q'\n"
     ]
    }
   ],
   "source": [
    "for k in sorted(ge_dic.keys()):\n",
    "    print(f\"'{k}': '{ge_dic[k]}'\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "これで辞書が完成したので，問題の入力をファイルとして読み込んで，正しい出力をファイルに出力する関数answerを定義する．\n",
    "この関数answerは，グー英辞書も引数として使うことにする．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def answer(input_file_name, ge_dic, output_file_name):\n",
    "    input_file = open(input_file_name)\n",
    "    input_data = input_file.readlines()\n",
    "    input_file.close()\n",
    "    \n",
    "    output_file = open(output_file_name, 'w')\n",
    "    T = int(input_data.pop(0))\n",
    "    \n",
    "    for t in range(T):\n",
    "        google_string = input_data.pop(0).rstrip()\n",
    "        english_string = ''\n",
    "        for g in google_string:\n",
    "            english_string += ge_dic[g]\n",
    "        output_file.write(f'Case #{t+1}: {english_string}\\n')\n",
    "    \n",
    "    output_file.close()\n",
    "    return\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "データが書き込まれているテキストファイルA-sample.inを用意して，それを読み込み，A-sample.outというファイルに出力を書き込んでみる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "answer('A-small-practice.in', ge_dic, 'A-small-practice.out')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "望みどおりの文字列がA-sample.outに書き出されているか，テキストエディターで見てみよう．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 場合によっては反復を便利にする関数zip"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上記の関数make_google_english_dictionaryでは，入力データと出力データを同時に見比べてグー英辞書を作っている．\n",
    "それぞれ同じ長さの文字列であることがわかっているので添字iで反復したが，もっとスマートにコードを書く方法がある．\n",
    "\n",
    "それは組み込み関数zipを使う方法である．\n",
    "まず，以下に組み込み関数zipの使用例を挙げる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "X = [1, 2, 3]\n",
    "Y = [100, 1000, 10000]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "101\n",
      "1002\n",
      "10003\n"
     ]
    }
   ],
   "source": [
    "for x, y in zip(X, Y):\n",
    "    print(x + y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ここから想像がつくと思うが，zipは複数のリストを引数として，反復などにおいてそれぞれの値を同時に返す関数である．\n",
    "\n",
    "今一度，zipの使用例を挙げる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 100), (2, 1000), (3, 10000)]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(zip(X, Y))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "これでさらに雰囲気がわかったと思う．\n",
    "\n",
    "リストの中の()はタプルである．\n",
    "タブルはリストとほどんど同じである．\n",
    "異なるのは「要素を変更できない」ということだけである．\n",
    "タプルに関しては，いずれ改めて説明する．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "組み込み関数zipを用いて，google_english_dictionaryを再定義する．\n",
    "ついでに，'z'と'q'も予めコードに入れておく．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def google_english_dictionary(input_file_name, output_file_name):\n",
    "    input_file = open(input_file_name)\n",
    "    input_data = input_file.readlines()\n",
    "    input_file.close()\n",
    "    \n",
    "    output_file = open(output_file_name)\n",
    "    output_data = output_file.readlines()\n",
    "    output_file.close()\n",
    "    \n",
    "    T = int(input_data.pop(0))\n",
    "    \n",
    "    ge_dic = {}\n",
    "    for t in range(T):\n",
    "        google_string = input_data.pop(0).rstrip()\n",
    "        english_string = output_data.pop(0).split(':')[1]\n",
    "        english_string = english_string.strip()\n",
    "        for g, e in zip(google_string, english_string): # ここがzipを使っている行\n",
    "            ge_dic[g] = e # zipの利用によって，繰り返し文の中がスッキリしている．\n",
    "    ge_dic['z'] = 'q'\n",
    "    ge_dic['q'] = 'z'\n",
    "    \n",
    "    return ge_dic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "' ': ' '\n",
      "'a': 'y'\n",
      "'b': 'h'\n",
      "'c': 'e'\n",
      "'d': 's'\n",
      "'e': 'o'\n",
      "'f': 'c'\n",
      "'g': 'v'\n",
      "'h': 'x'\n",
      "'i': 'd'\n",
      "'j': 'u'\n",
      "'k': 'i'\n",
      "'l': 'g'\n",
      "'m': 'l'\n",
      "'n': 'b'\n",
      "'o': 'k'\n",
      "'p': 'r'\n",
      "'q': 'z'\n",
      "'r': 't'\n",
      "'s': 'n'\n",
      "'t': 'w'\n",
      "'u': 'j'\n",
      "'v': 'p'\n",
      "'w': 'f'\n",
      "'x': 'm'\n",
      "'y': 'a'\n",
      "'z': 'q'\n"
     ]
    }
   ],
   "source": [
    "ge_dic = google_english_dictionary('A-sample.in', 'A-sample.out')\n",
    "for k in sorted(ge_dic.keys()):\n",
    "    print(f\"'{k}': '{ge_dic[k]}'\")"
   ]
  }
 ],
 "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.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}