Technically Impossible

Lets look at the weak link in your statement. Anything "Technically Impossible" basically means we haven't figured out how yet.

42 SILICON VALLEY Piscine 2017 match/nmatchを考える(後編) 最後は力業

42 SILICON VALLEY Piscineの個人プロジェクト、2つ目はmatch/nmatch。2つの課題で構成されるプロジェクトだ。問題文には明記されていないが、再帰構造の理解と実装が求められている。

再帰はややこしく、理解し難いと言われる。実際その通りだと思う。しかし再帰を用いずにロジックを組むと、さらに複雑になるだろう。再帰の流れを理解するのは難しくとも、ロジックの「見た目」は、それを用いない場合に比べて、非常にシンプルになる。

今回の投稿では二つ目の課題、nmatchを採り上げる。一つ目の課題であるmatchについては、前回の投稿を参照してほしい。

題材は文字列比較だがmatchとは求められていることが異なる。単純な比較結果を出力するのではなく、合致するパターン数を出力しなければならない。前回同様、これまで考えもしなかったロジックで、かなり手間取った。

前回同様、サンプル・コードはPythonで記述したが、Piscine受講生に配慮して、C言語的な記述になるよう配慮した。

  • 準備
  • nmatch
    • 文字列比較再訪
    • matchの答え合わせ
  • 参照
  • サンプル・コード
    • code - pattern A
    • code - pattern B
続きを読む

42 SILICON VALLEY Piscine 2017 match/nmatchを考える(前編) 再帰とバックトラック法の実践

42 SILICON VALLEY Piscineの個人プロジェクト、2つ目はmatch/nmatch。2つの課題で構成されるプロジェクトだ。問題文には明記されていないが、再帰構造の理解と実装が求められている。加えてDay04の話題で触れたバックトラック法の実践だ。

再帰はややこしく、理解し難いと言われる。実際その通りだと思う。しかし再帰を用いずにロジックを組むと、さらに複雑になるだろう。再帰の流れを理解するのは難しくとも、ロジックの「見た目」は、それを用いない場合に比べて、非常にシンプルになる。

題材は文字列比較だ。C言語の練習プログラムの定番の一つだが、難易度を上げているのがワイルドカードの存在だ。私自身、ワイルドカードを含む文字列比較は、正規表現などの与えられた関数を、当然のごとく用いるばかりだったので、このロジックを考えるのは少々手間取った。

今回の投稿では一つ目の課題、matchだけを採り上げる。サンプル・コードはPythonで記述したが、Piscine受講生に配慮して、C言語的な記述になるよう配慮した。

  • 準備
  • match
    • 文字列比較
  • ワイルドカードを考える
    • s1を1文字進める。s2はそのまま「*」を参照する。
    • s1、s2の両方を1文字進める。不一致の場合、s2だけを戻す(「*」を再参照する)。
    • s2を1文字進める。s1はそのまま。不一致の場合、s2を戻し、s1を1文字進める。
    • どちらが正解なのか?
  • 参照
  • サンプル・コード
    • code - pattern A
    • code - pattern B
続きを読む

42 SILICON VALLEY Piscine 2017 Sastantuaを考える Pythonの場合

42 Tokyoでは課題のことをプロジェクトと呼ぶらしい。ここでは日々の課題とは別に課される、特別な課題をプロジェクトとする。プロジェクト資料を読み解くと、Piscineには3種類のプロジェクトが存在するようだ。

  • 個人プロジェクト
  • グループ・プロジェクト
  • 最終プロジェクト

今回、採り上げるSastantuaは、どうやら最初の個人プロジェクトのようだ。問題の形式はロジック問題だが、その詳細を示さない。プログラム上定める必要のある仕様策定を受講生に委ねている節がある。

今回はアプローチ、考え方を示すのにサンプル・コードを併記した説明が分かりやすいだろうと考えた。サンプル・コードはPythonで記述している。Piscine受講生はアプローチからロジックまでを真似することはできるが、コードは自分で考えて書き直す必要がある。
ちなみにライブラリは使用していない。自動的にFloatになってしまう箇所だけ、intのキャスト関数を用いた。それ以外には、関数も用いていない。

  • 準備
  • Sastantua
    • ピラミッドを考える
    • 段数を考慮する-段数から行数を考える
    • 段数を考慮する-Sastantuaを描画する
    • ドアを描画する
  • 余談
  • 参照
  • サンプル・コード
    • コード1
    • コード2
    • コード3
    • コード4
続きを読む

スッキリ分かるC言語入門

スッキリわかるC言語入門
プログラム言語の習得において、どの言語から勉強を始めるのか、はあまり意識されることがないのだが、かなりの重要事項だ。最初の言語学習を通じて養われた知見、認識が、2つ目以降の言語を学ぶ際の橋渡しをしてくれる。さらに異なる言語の学習を続けると、言語間の共通概念、ある言語独自の機能や概念が体系的に構成、認識され、学習効率は向上する。
一方、最初に学ぶ言語、2つ目以降に学ぶ言語のコンセプトが違い過ぎる場合、その橋渡しが良好に機能せず、2つ目の言語習得に要する負担は、一つ目のときと変わらないこともあり得る。

英語学習を想像してみるとよい。日本人が英語を苦手とするのは、日常生活で英語を用いない、学校教育云々、色々言われるのだが、原理原則で考えてみてほしい。日本語はウラル・アルタイ語族に、英語はインド・ヨーロッパ語族に分類されている。両言語系統は、分類上、最も遠くに位置している。つまり全く特性の違う言語ということだ。原理原則として、タイプの異なる言語を学ぶのは難しい。プログラム言語も一緒だ。

この観点から、プログラムの初学者が初めて学ぶ言語としてC言語は、かなり良好なポジションにある。C言語を用いた場合の制約や問題をきっかけに、後発の言語へ派生している経緯もあり、C言語で学んだ概念は他の言語でも通じやすい。
学習範囲が広がれば、結局のところC言語に限らず、どの言語でも構文には、それ程変わりがないことを知る。言語特有の機能や概念を学ぶことを重視するようになる。
初学者は、まず構文を学び、加えて特有の要素を学ぶ必要があるため、最初だけは学習負荷が大きいのだ。

『スッキリ分かるC言語入門』(以下、スッキリ~)はタイトル通り、C言語の入門書だ。特にC言語特有の機能であるポインタの紹介を工夫しており、初学者にお勧めの書籍だ。

続きを読む

作って理解するOS x86系コンピュータを動かす理論と実装

作って理解するOS  x86系コンピュータを動かす理論と実装
今年やり残したことを消化する時期がやってきた。今回紹介する書籍に目を通すことも、そのようなやり残しの一つだった。本書は9月に頂いたものだ。せっかくの頂きものなので、年内に目を通して、何らかの記録を残しておこうと考えていた。頂きものだからと言って、ステマに類する投稿ではないことを前置きしておく。

OS、並びにその作成については好奇心以上の関心があるものではなく、そのテーマについての読書は、10年以上前に読んだ『30日でできる!OS自作入門』以来だった。同書の著者であり、『作って理解する~』の監修者でもある川合秀実氏は、本書を次のように評している。

  • 効率よくたくさんの知識を教えてくれ、効率よく学ぶことができる。
  • OSの作り方を紹介した本ではない
  • PCの仕組みを深く説明している本

本書は「作って理解する」と謳うものの、読んで理解する部分が多い。実際のところ、700ページ超の半分はx86アーキテクチャの説明に割かれている。そして、この部分が私にとっては大変得るものが大きかった。同時に、この部分が本書を特徴づけている部分でもあると感じた。それは著者自らが言うところの、

  • OSの入門書であると同時にコンピュータの入門書
  • コンピュータの基礎からOSの基礎までを体系的に理解する

を多分に反映している箇所でもあるからだ。

続きを読む

42 SILICON VALLEY Piscine 2017 Day04を考える アルゴリズム問題の手引き。

先日、ロジック問題に対する一つのアプローチを紹介した。アプローチ手法は異なれども、自分で考えることはロジック問題に限らず、何かにつけ共通する活動の一つだ。

42 SILICON VALLEY Piscine 2017 Day02を考える 私なりのアプローチ。 - Technically Impossible

しかし考え過ぎるのは良くない。時には考える必要がない、あるいは考えない方が良い場面もある。それは、いわゆる定石が適用できる、あるいはそれを積極的に適用すべき場面だ。特にプログラミングにおいては、そのような定石となる「アルゴリズム」が存在する場合だ。

Day02のロジック問題を、一から自分で考える問題とするならば、アルゴリズム問題は知識を活用し、適用するための問題だ。加えて、提供された限られた学習機会を通じて、どれだけのことを学び、実践適用できるかを試している問題にも見える。
ただし課題にアルゴリズム問題と明記されているわけではなく、受講者が判別、判断する必要がある。Day04 Exercise 08、09はその典型例だ。

42SV、2017年PiscineのDay04の課題を題材に、その取り組み方を説明してみよう。対象の課題はExercise 08~09だ。この投稿がPiscine受講生の一助になれば、と思う。

続きを読む

42 SILICON VALLEY Piscine 2017 Day02を考える 私なりのアプローチ。

先日投稿した42に関する投稿が、このブログにしてはアクセスを稼いでいる。その投稿の内容よりも、42の話題性、その関心に起因するものだろう。

42 SILICON VALLEY Piscine 2017資料を読み解く 印象、考察、そして余談。 - Technically Impossible
42 SILICON VALLEY Piscine 2017プロジェクト資料を読み解く 印象、考察、そして余談。 - Technically Impossible

学期末で、些か暇を持て余している。せっかくPiscine受講者の方々がアクセスしてくれているのだから、先日の投稿に加えて、何か「お持ち帰り」感のある情報を提供できないだろうか、と考えた。

Piscineの特性を考えると、公開されている課題について、そのプログラムを示しても有意義ではないだろう。ダミー・コードが含まれている場合もあるとはいえ、コードはGitHubに公開されている。何よりPeer learningを伴うため、コードだけを見たところで、受講者が自分自身でそのロジックを説明できなければ意味がない。
Peer learnngのパートナーはランダムに選別されるのだという。課題を理解している者が、理解していない者へ教えるという構図が常に成り立つとは限らない。課題を理解していないものが、理解している者へ教える場面もあり得るのだ。そのような場面で、いきなりプログラムを提示することなど無理だろう。むしろ課題を解くための考え方、アプローチを示すことを求められているのではないだろうか。

受講者の中には、C言語そのものよりも、プログラミング自体についての初学者もいるようだ。課題の回答に通じるプログラムを直接的に示すよりも、課題を題材にして、ロジックを見出す考え方、解法に至るアプローチを伝えることの方が、プログラム自体を示すよりも汎用的で有用ではないかと考えた。

ここでは42SV、2017年PiscineのDay02の課題を題材に、私なりのアプローチを説明してみようと思う。対象の課題はExercise 04~07(06は除外)だ。特に次の事柄を伝えることに焦点を絞った。

  1. 力技による真正面からの正攻法でも良いが、より効率的なアプローチを見出すこと。
  2. Piscineの課題には関連があり、後に続く課題を解くには、前の課題のアプローチが応用できること。

この投稿がPiscine受講生の一助になれば、と思う。
間違っていたらゴメン。

  • Exercise 04
  • Exercise 05
    • 懸念事項
  • Exercise 07
  • 余談-力技のトレードオフ
  • 参照
続きを読む

42 SILICON VALLEY Piscine 2017プロジェクト資料を読み解く 印象、考察、そして余談。

先日の投稿では42 Silicon valleyの2017年度Piscine資料を読み解いた。この資料は14日分の課題で構成されているのだが、Piscineは4週間開催される。残り2週間、あるいは14日の課題と並行して、志願者は複数のプロジェクトに参加する必要がある。今回の資料に基づくならば、

  • 3つの個人プロジェクト
  • 3つのグループ・プロジェクト
  • 最終プロジェクト

今回は、これらプロジェクトの資料を元に、印象的だった部分を紹介する。

ちなみに、ここで紹介する情報が東京校のPiscineに通用する保証はなく、内容の正しさを保証するものでもないことを申し添えておく。
関連サイトのハイパーリンクは投稿末尾にまとめている。

  • 個人プロジェクト
  • グループ・プロジェクト
  • 最終プロジェクト
  • 余談
  • 参照
続きを読む

数式なしのクラスター分析-Rでの最適なクラスタ数の予測から分析までの手順

何らかの形でデータを分類しなければならないとしよう。例えばドラクエのようなRPGに登場するモンスターをタイプごとに分類するならば、

  • HP、MP
  • ゴールド
  • 経験値
  • つよさ、すばやさ

などなど。どのような項目、特徴で分類されるのか、最終的に何種類に分類されるのか定かではないデータを、何らかの形で分類する方法の一つがクラスター分析だ。

クラスター分析は機械学習で言うところの、教師なし学習に相当する。何らかの特徴を見出し、その特徴に基づいて分類していく。何通りのクラスターに分類されるのかは予想できないが、見当をつけることはできる。

この投稿では最適なクラスター数の特定から、クラスター分析結果の検討まで、Rを用いた一連の手順を紹介する。分析対象データはRに含まれているものを用いるので、RStudioだけで手順を再現することができる。ここでは次の環境を用いている。

  • R 3.6.1
  • RStudio 1.2.5001

ちなみに現時点でのR、最新版は3.6.2だ。RStudioと共に参照先は、この投稿末尾にまとめている。

  • 豆知識
    • エルボー法
    • シルエット分析法
    • ギャップ統計法
  • ライブラリとデータの準備
  • 最適なクラスタ数の特定
  • クラスター分析
    • k = 2の場合
    • k = 6の場合
    • k = 15の場合
  • 参照
  • コード
続きを読む

42 SILICON VALLEY Piscine 2017資料を読み解く 印象、考察、そして余談。

42 Tokyoというエンジニア養成機関が話題だ。私は42 Tokyoを受験しないのだが、選抜方法とその内容に関心があり調べていた。シリコンバレー校の資料がGitHubで公開されている。資料は2017年のものだ。オンライン・テストを通過した志願者は、Piscineと呼ばれる4週間の入学試験を経て選抜される。このPiscineの内容が関心の的だ。

試験日ごとにPDFが用意され、該当日の課題が掲載されている。一通り確認したところ、良問に通じる雰囲気を感じた。
今時のwebプログラミングや、データベースの要素はかけらも含まれていない。課題の成果物はプログラムなのだが、プログラミング・スキルを評価するものではなく、コーディングの巧拙以外の何か、例えばロジックの組み立て、情報に基づいて実装する理解、作業の丁寧さ、繊細さ、根気強さなどを評価しようとしている意図を感じた。

Day00~Day13の資料を基に、いくつか印象的だった部分を紹介する。その他のプロジェクト資料、特にBSQという最終プロジェクトの資料には気になる箇所もあるのだが、この投稿では話題として取り上げない。これは次回の話題だ。
GitHub上にはC++版Piscineも掲載されているのだが、内容は確認していない。リポジトリには、他にも42関連と思われるファイルがアップロードされている。

ちなみに、ここで紹介する情報が東京校のPiscineに通用する保証はなく、内容の正しさを保証するものでもないことを申し添えておく。
関連サイトのハイパーリンクは投稿末尾にまとめている。

  • 印象的な仕掛け
  • コーディング規則
  • カリキュラム
    • Day09について
  • 余談
    • 初学者に向けて
    • 負荷、負担の予測
  • 参照
続きを読む