ネコのために鐘は鳴る

寺院に住み着くパソコ〇好き

解けない15パズル

15パズルってご存知ですか?

知ってても知らなくても15パズルの話をするんですが。はい。

 

あと、本記事は数学的な厳密な証明はせずに感覚的にエイッヤッ~とやっているので正確じゃないです。

でもたぶんあってる。はい。

これ

f:id:ikorin2:20190615010315g:plain

簡単に言いますと、1マス空いている4×4のマスでセルを移動させながら、 左上から順に数字を並べるパズルです。

アルゴリズムも単純でプログラミング初心者でも割と簡単に実装できるゲームです。

 

 

と思っていた時期が私にもありました。

15パズルの欠陥

というのは半分冗談で、ゲームのアルゴリズム自体は別に難しくないです。 問題はこの15パズルというゲームが持つ本質的な欠陥についてです。

端的に言うと、絶対に完成できない形が存在します。

f:id:ikorin2:20190615013108p:plain

これが完成形です。

そして、次が完成不可能な形の一例です。

f:id:ikorin2:20190615014449p:plain

このように完成形から1つだけ入れ替えた形は、どれだけパズルをグルグルまわしても 絶対に完成形にはならないことが知られています。

証明とかは省略します、というより私が知りません。昔の偉い人がそう言ったので信じます。

これをベースに、完成できる条件とは何かを考えていきます。

完成可能条件

先ほどの、完成形から隣接する2つのセルを1度だけ入れ替えたものを、完成形からの距離D=1と呼ぶことにします。

D=1状態が完成不可能なので、D=2の形について考えます。

D=2D=1からもう一度隣接するセルを入れ替えた形の集合です。

D=2D=1のところと同じ2セルを入れ替えた形も含むので、つまり完成形もD=2に含まれます。

 

ということは再帰的にD=2nは完成形を含むため、距離が偶数なら完成可能、奇数なら完成不能です。

(数学徒からは全然証明になってないので受精卵から人生やりなおせと言われそうですが、私は厳密な証明できないのでこの記事執筆後、受精卵からやり直します)

 

では次のような斜めの2つを入れ替えた形に距離を考えます。

f:id:ikorin2:20190615022117p:plain

完成形から順に入れ替えを手順を追っていきます。

# D=0
 9 10 11 12
13 14 15 __

↓ 14, 15を入れ替え

# D=1
 9 10 11 12
13 15 14 __

↓ 10, 15を入れ替え

# D=2
 9 15 11 12
13 10 14 __

↓ 14, 10を入れ替え

# D=3
 9 15 11 12
13 14 10 __

つまり、斜めのセルの入れ替えはD=3です。つまり完成形からは奇数距離です。

このように拡張していくと、任意の2つのセルの入れ替えは奇数距離であることが分かります。

 

ここから分かることは、任意の入れ替えが奇数距離であるため、入れ替え回数が偶数回なら偶数距離を保てるということです。

つまり、解ける15パズルとは、完成形から偶数回の「任意の2セル入れ替え」で得られる集合に含まれる形です。

なので、ランダムに初期状態を生成すると1/2の確率で完成不能なパズルができるということですね。。。。

 

おしまい


ソースコード(C#版/VB版)

github.com

二度とVBなんか書かねぇ

(C#) コレクションのカプセル化

コレクションの保護

クラスの不十分なカプセル化としてよく見られるのがコレクションです。 以下の例は、カプセル化されていないコレクションの例です。

public static class Database
{
    public static Person[] People { get; private set; }
}

public class Person
{
    public int Age { get; private set; }
    public string Name { get; private set; }
}

問題があるのは、DatabaseクラスのPeopleプロパティです。 一見、setterはprivateであるため、クラス外部からの変更は不可能なように見えますが、これはコレクションにありがちなミスです。

コレクションそのもののインスタンスは書き換え不可ですが、以下のように各要素については書き換えができてしまいます。

// これはsetterがprivateなので不可
Database.Person = new Person[5];

// これは可能
Database.Person[3] = new Person();

外部に対してforeachPersonを回すことだけを想定している場合、外部からの要素の書き換えは危険です。これはArrayに限らずList<T>である場合も当然同様です。

public static class Database
{
    public static List<Person> People { get; private set; }
}
// -----------------------------------------------

// 想定外の要素の追加が可能
Database.People.Add(new Person());

foreachによる列挙を許可したい場合、適切な実装は以下のようにIEnumerable<T>を使うのが正しいです。

public static class Database
{
    public static IEnumerable<Person> People { get; private set; }
}

これで、外部からはイテレート以外の操作は受け付けません。 しかし、この場合、内部からの操作もIEnumerable<T>でしか操作できず、大変不便です。 以下のように実装すると内部では柔軟な操作が可能になります。

public static class Database
{
    private static readonly List<Person> _people = new List<Person>();
    public static IEnumerable<Person> People => _people;
}

これで外部からはイテレートしかできず、内部からは自由な操作が可能になります。

しかし、IEnumerable<T>は意外と不便で、index操作が使えない、要素数が取れない等の不便さが生じます。インデクサを定義しているのはIList、要素数を定義しているのはICollectionだからです。(IEnumerable<T>から要素数取得やインデックス指定可能な方法はありますが後述。)

なおIEnumerableICollectionIListおよびそのジェネリック版の関係は以下の図の通りです。

f:id:ikorin2:20190414041214p:plain

そこで、コレクションのカプセル化を実現しつつ、インデクサと要素数を利用できるのがSystem.Collections.ObjectModel.ReadOnlyCollection<T>です。

[2020/06/21 追記] .net standard 2.0 以降の環境では、保護したいものが配列の場合はReadOnlyMemory<T>ReadOnlySpan<T>を使った方が色々とパフォーマンスが良いです。Listとかの場合はReadOnlyCollection<T>を使わざるを得ませんが。

public static class Database
{
    private static readonly List<Person> _people = new List<Person>();
    public static ReadOnlyCollection<Person> People { get; } = _people.AsReadOnly();
}
// --------------------------------------------------------

// インデクサのsetterはないためこれは不可
Database.People[3] = new Person();

// getは可能
var person = Database.People[3];
// 要素数も取得可能
var count = Database.People.Count;

これで、インデクサ操作や要素数の要件を満たしつつ、適切なコレクションのカプセル化ができました。

インデクサ操作や要素数の取得が不要な場合、IEnumerable<T>でもReadOnlyCollection<T>でも外部から保護されている点では十分なのでどちらを用いてもよいでしょう。

補足1

ReadOnlyCollection<T>を用いた実装例で、

public static ReadOnlyCollection<Person> People => _people.AsReadOnly();

ではなく、

public static ReadOnlyCollection<Person> People { get; } = _people.AsReadOnly();

としています。2つの違いは、前者の実装ではgetterが呼ばれるたびにReadOnlyCollection<Person>インスタンスが生成されますが、後者は最初の1回インスタンスが生成されるのみです。当然、後者の方がメモリ的には良いでしょう。(微々たる差ではありますが)

が、これは一見不思議な実装です。次の例を見てください。

public static class Database
{
    private static readonly List<Person> _people = new List<Person>();
    public static ReadOnlyCollection<Person> People { get; } = _people.AsReadOnly();

    public static Add(Person person) => _people.Add(person);
}
// --------------------------------------------------------

// ここで0が出力されるとする
Console.WriteLine(Database.People.Count);

// 要素追加
Database.Add(new Person());
// ここでは何が出力される?
Console.WriteLine(Database.People.Count);

さて問題です。最後の出力では何が出力されるでしょう?

ReadOnlyCollection<Person>インスタンスが生成されるのがDatabaseクラス初期化時のみなので、一見0が出力されるように思えます。

が、実際は1がちゃんと出力されます。アラ不思議。

これはReadOnlyCollection<T>List<T>のラッパーであるため、内部で元になったList<T>インスタンスを持っているために起こります。参照型万歳。

補足2

IEnumerable<T>を使った隠蔽実装では要素数およびインデクサ操作ができないと前述しました。 しかし、実際はLINQIEnumerable<T>.Count()IEnumerable<T>.ElementAt(int)を使うことで可能です。

しかし、IEnumerable<T>は列挙可能であることを定義するだけのインターフェースであるため、Count()は先頭から順に全要素の数え上げを行いO(n)かかります。ElementAt(int)も同様です。

が、実はMicrosoftの公開しているLINQの実装を見てみると、Count()は実際のインスタンスICollectionである場合はICollectionにキャスト後、ICollection.Countを返しています。同様に、ElementAt(int)IListである場合はキャスト後にIList[int]を返しています。

本文で上げたIEnumerable<T>を用いた隠蔽実装の実体はList<T>であるため、ともにO(1)で返ります。つまり、要素数もインデクサ操作も実は何の不都合も存在せず使用可能なのです。

しかし、ここでもう一度否定します。

例で挙げたDatabaseクラスを外部から見ると、内部の実態がList<T>であることなど知る由もありません。IEnumerable<T>.Count()と使えばO(n)だと考えるのが自然です。実際はO(1)で返るのだとしても、そのような利用法を外部に公開するのはフレンドリーとはあまり言えないでしょう。

よって、要素数やインデクサを使わせたいのであれば素直にReadOnlyCollection<T>で公開すべきでしょう。

カプセル化とは何か

カプセル化とはオブジェクト指向の根幹をなす考え方です。カプセル化について考えて見ましょう。(本記事はC#をベースに考えていますが、カプセル化自体はオブジェクト指向言語全般に関して共通することでしょう)

カプセル化API

自販機を例に考えてみましょう。

オブジェクト指向なのですから、当然まずは自販機クラスを作ります。

オブジェクト(自販機)を外から使う人(飲み物の購入者)の視点から見て、必要な入力と出力は、

  • お金を入れる
  • 飲みたいジュースを選ぶ
  • 選択したジュースが出てくる
  • お釣りがある場合はお釣りも出てくる

これだけです。つまり必要なAPIはこれだけです。

当たり前のように感じますが、これ以外のAPIは公開する必要がありません。

むしろ公開してはいけません。

当たり前のようなことを書きますが、以下は公開してはいけないAPIの例です。

  • 自動販売機が製造された工場の名前
  • 自販機内に溜まっているお金の総量
  • 投入されたコインが500円玉か100円玉かを判別する方法
  • ジュースの缶を押し出す機構に使われているバネの種類
  • etc...

まず1つ目。自動販売機が製造された工場の名前。

こんなものはジュースの購入者にとってはどうでもいいことです。公開されるAPIは少なければ少ないほどいいので、こんなものを公開する意味がないです。

2つ目。販機内に溜まっているお金の総量

これも1つ目と同様、利用者にとっては関係ないです。むしろ、セキュリティの観点から見て、公開することにデメリットしかないです。泥棒に盗んで欲しいのでしょうか。

3つ目と4つ目。投入されたコインが500円玉か100円玉かを判別する方法、ジュースの缶を押し出す機構に使われているバネの種類

これは利用者側から見れば上記の2つ同様不要な情報です。しかし、自販機内部にとっては必要な情報です。つまりこれはpublicで公開すべきAPIではなく、privateで実装されるべき内容です。特に500円玉と100円玉の判別方法など外部に公開するのはセキュリティ的にもまずいでしょう。


つまり、ユーザーにとって自販機とはお金とジュース名を入力したら、ジュースとお釣りを出力するだけの装置にすぎません。自動販売機の中でどのようにジュースが保管されており、投入したコインの金額をどのように数え、どのようにジュースを取り出し口まで運んでいるかなど、内部の仕組みについて一切考える必要がないのです。

自販機内のジュースが5℃以上で保存されている場合はジュースのボタンを3回押さなければならない、などという仕様の自動販売機があるとすれば、それは明らかに欠陥品だとは思いませんか?

こんな当たり前のことなのに、ソフトウェア開発の現場ではこのような意味不明なオブジェクトが横行しています。キレそう

.NET CoreでNugetパッケージのdllをビルド出力する

.NET CoreでNugetのパッケージのdllはデフォルトではビルド出力にコピーされないし、 Visual Studio上から設定で出力するように設定変更もできない(たぶん)(何故)

[2020/6/29 追記] この記事の内容は.net core 2.x 時代の話で、.net core 3.0 からはdllがデフォルトでビルド出力にコピーされます。 なのでこの記事の内容自体が今は不要です。。。

.csprojファイルに以下の設定を直接書き足す。

<PropertyGroup>
  <CopyLocalLockFileAssemblies>true</CopyLocalLockFileAssemblies>
</PropertyGroup>

はい。

よかったですねぇ~

参考文献

NuGet を使用したパッケージ管理 - マイクロソフト系技術情報 Wiki

.NETとマルチプラットフォーム

C#マルチプラットフォームなアプリケーションを作りたかった時に、調べたことを自分用メモとしてまとめました。

たまには違う言語も書いたら?

C#の実行環境

C#はIL(中間言語;Intermediate Language)にコンパイルされ、仮想環境上で動くコンパイル系言語です。概念的にはJavaと同じです。 JavaJRE(Java Runtime Environment)上で動いているように、C#は.NET上で動いています。 たまに勘違いをしている人がいますが、スクリプト系言語ではありません。1

もともとC#Microsoftが作った言語なので.NET FrameworkWindowsでしか動きません。ですが、JavaWindowsでもlinuxでも動くのと同様、原理的には他OS向けの.NET Framework互換のものがあれば、C#はどこでも動きます。

そこでMonoという.NET framework互換のものをlinuxmac向けにどこかの偉い人が作りました。なのでMonoさえインストールすればWindowsで動いていたC#のコードがそのままmacでも動きます。すごい。

マルチプラットフォームを謳っているUnityもC#の実行にMonoを使ってます。(Unity はIL2CPPだとか多少特殊ですが)

.NET Frameworkと.NET Core

.NET FrameworkというのはCLI(共通言語基盤;Common Language Infrastructure)、GC(ガベージコレクション)、JIT(just in time compiler)、標準ライブラリ等を全部あわせた環境全体のことを言います。(で本当にあってるんでしょうか?私はそういう認識してますが正しいのか微妙)

コンソールアプリケーションなら前述の通り、Monoを使うとlinuxでも動くんですが、さすがにWindows formとかWPFなんかのウィンドウズアプリケーションは動かないんですよね。彼らは内部でwin32 APIやDirextXとかを呼んでいるのでそれはまあ当たり前です。

そこで.NET FrameworkのうちWindows/Mac/LInuxの共通部分だけをとりだして、いい感じにまとめた.NET Coreというのが登場します。 そういうわけで、.NET Coreはクロスプラットフォームで動作します。

.NET Coreの実行ファイルは全てWindows PEファイル形式の.dllで作成されます。 それは、色々とその方が都合がいいからだそうです。 詳しくはこの辺参照

実行ファイル(app.dll)に対して、コマンドで

dotnet app.dll

というように実行できます。 dotnetコマンドからの実行じゃなくて、直接実行可能ファイル(Windowsでいうexeファイル)で欲しいという場合も、実行可能ファイルを出力できます。 .NETのランタイムエンジンそのものも一緒に出力されるため、.NETのランタイムがインストールされていないマシンでもそのまま実行できます。

やり方はこのサイトに書いてあるので。

kagasu.hatenablog.com

Xamarin, .NET Standard

XamarinはC#Mac/Android/iOSを開発するための.NETです。触ったことないので詳しくはわかりません。UIはxamlベースでいい感じに開発できるそうです。 いつか触ってみたい。

もう一つ、.NETの種類で.NET Standardというのがあります。これは、.NET Framework/ .NET Core/ Xamarinの全てで使用可能なライブラリを作成するための.NETです。いわば各種.NETの汎用部分のAPIを定義したAPI仕様です。

つまり、.NET Standardを対象に作成されたライブラリは.NET Framework/ .NET Core/ Xamarinの全てから使用可能ということです。 逆に言うと、特定のフレームワークでしか実行できないようなライブラリは、.NET Standard 向けのライブラリとして提供してはダメということです。

まあ実際のところ、行儀のいい(?)ピュアC#なコードしか使っていないライブラリの場合は だいたい.NET Standard 向けでビルドして提供して問題ないはずです。(行儀の良い、という説明が説明になっていない気がするがどう言えばいいんだろう。。。)

まとめ

C#Windowsはもちろん、MaclinuxAndroidiOSアプリケーションも開発できるのはすごい。

あと、本記事はMSDNこのページとかその他いろいろを参考に自分なりに噛み砕いたものです。

https://msdn.microsoft.com/ja-jp/magazine/mt842506.aspxmsdn.microsoft.com

おしまい

あと結果的に本記事より、下のこのページの方が簡潔で分かりやすかった

よかったですねぇ~

qiita.com


  1. 実はRoslynというVisual Studio 2015から使われているコンパイラの機能によって、C#スクリプト実行できたりpythonとかrubyみたいに1行ずつ対話実行できたりするようになった。なにそのチート……

(備忘録)C++でOpenGL使う時に調べた用語まとめ

C++素人がC++OpenGLで遊びたいなと思った時に出てきた用語をまとめた。

知っていた単語、聞いたことはあるが理解していなかった単語、知らなかった単語もあるが、 備忘録として関連してそうなワードを独断と偏見でまとめてみた。

間違いや勘違いがあれば教えてください。

調べた単語

  • Cmake

    cppプロジェクトのコンパイルを自動化するためのツール。コンパイラ非依存。 様々なOSで利用可能。最小限の依存関係のみを持つ設計で、コンパイラ自体は別に必要。 makefileと同じような物だがmakefileの方がレガシー(たぶん)。

  • Clang

    GCCに代わるC系言語のコンパイラ。C, C++, Objective-Cなどで使える。 2019年現在もオープンソース開発は積極的に行われている。「クラン」と読むらしい

  • Boost

    C++の代表的なライブラリ。 データ構造から入出力処理、メモリ操作など多岐にわたる便利機能を提供している。 pythonにとってのnumpyと同じぐらいC++erにとっては当たり前に使うライブラリっぽい。

  • OpenGL

    OSに依存しない2D/3Dグラフィック処理を提供するライブラリ。 APIC/C++。Open Graphics Libraryの略らしい。OS非依存なのでスマホでも動くよ。 もちろんOS非依存だが、グラフィックを表示するためのウィンドウ生成自体は 各OSの機能(WindowsAPI/X Window System等)にお願いせざるを得ないので、初期化部分でOSに依存してしまうかわいそうな子(?)。 その辺のOS差を吸収してくれるGLUKやGLFWといったOpenGL補助ライブラリも存在する。

  • GLFW

    OpenGLの補助ライブラリ。色々とOpenGLを扱うのが簡単になる。 昔([要出典] いつ?)はGLUKというのがよく使われていたらしいが、 2016年に開発が止まっているので、今はGLFWを使うのが主流らしい。

  • OpenCL

    Open Computing Language。 名前が似ているOpenGLと混同されがちだが別物。 こちらはGPUに計算処理をさせるためのフレームワーク

  • 静的ライブラリ・共有ライブラリ (C/C++)

    静的ライブラリは、単にC言語のオブジェクトファイル(拡張子 .o)を複数まとめただけのアーカイブ。 リンカがリンク時に使用しコンパイルする。 Windowsでの拡張子は.lib、unix系は.a

    共有ライブラリは呼び出し時に動的に呼び出されるバイナリ。 Windowsでの拡張子は.dll、unix系は.so

  • X Window System

    Unix系OSGUIのウィンドウを表示するためのシステム。

  • DirectX

    Microsoftが開発しているWindows向け2D/3Dグラフィック処理API群。 Windowsでゲームなどで高速にグラフィックを扱うために作られた。もちろんMac/Linuxでは使えない。

(C#)Enumの要素に表示名をつける ~ローカライズ編~

前回の記事の続きです

前回はEnumDisplayName属性に定数リテラル文字列を与えることはできましたが、 リソースから値を割りつけることができませんでした。これでは多言語化する時に困ります。

[AttributeUsage(AttributeTargets.Field)]
public class EnumDisplayNameAttribute : Attribute
{
    /// <summary>表示名</summary>
    public string Name { get; set; }

    /// <summary>enum表示名属性</summary>
    /// <param name="name">表示名</param>
    public EnumDisplayNameAttribute(string name)
    {
        Name = name;
    }
}
public enum Sushi
{
   [EnumDisplayName("タコ")]    // リテラルを割り付けることはできる
   Tako,
   [EnumDisplayName("イカ")]
   Ika,
   [EnumDisplayName(Resources.SushiEbi)]  // リソース値はコンパイルエラーになる
   Ebi
}

そこで以下のようにEnumDisplayNameAttributeクラスを修正します。

using System.Reflection;

[AttributeUsage(AttributeTargets.Field)]
public class EnumDisplayNameAttribute : Attribute
{
    /// <summary>表示名</summary>
    public string Name { get; set; }

    /// <summary>リソース名</summary>
    public string Resource
    {
        get { return _resource; }
        set { _resource = value; SetNameFromResource(); }
    }
    private string _resource;

    /// <summary>リソースの型</summary>
    public Type ResourceType
    {
        get { return _resourceType; }
        set { _resourceType = value; SetNameFromResource(); }
    }
    private Type _resourceType;

    /// <summary>enum表示名属性</summary>
    public EnumDisplayNameAttribute() { }

    /// <summary>enum表示名属性</summary>
    /// <param name="name">表示名</param>
    public EnumDisplayNameAttribute(string name)
    {
        Name = name;
    }

    /// <summary>リソース型とリソース名から表示名をセットします</summary>
    private void SetNameFromResource()
    {
        if(_resourceType == null || _resource == null) { return; }
        var propertyInfo = _resourceType.GetProperty(_resource);
        Name = propertyInfo?.GetValue(_resourceType) as string;
    }
}

そしてEnumに次のように属性を与えます

public enum Sushi
{
    [EnumDisplayName(Resource = "SushiTako", ResourceType = typeof(Resources))]
    Tako,
    [EnumDisplayName(Resource = "SushiIka", ResourceType = typeof(Resources))]
    Ika,
    [EnumDisplayName(Resource = "SushiEbi", ResourceType = typeof(Resources))]
    Ebi,
}

Resources.SushiEbi等がリソース値です。これで無事リソースから表示名を割り付けることができたので 多言語にローカライズできます。