Posted at

C#でパズルを解く - 覆銭問題(Penny Flipping Problem)

More than 1 year has passed since last update.


覆銭問題とは

覆銭問題とは、積み上げたコインを以下の手順でひっくり返すと何回目で初期状態に戻るかというものです。


  1. n枚のコインを全部表にして積み上げる

  2. 最初に、上の1枚を裏返す。次に上から2枚目をまとめてひっくり返す。次に3枚、4枚とひっくり返す。

  3. n枚全体をひっくり返したら、また1枚に戻る。

  4. この手順を繰り返す。

英語では、Penny Flipping Problem というらしいです。


C#のコード

まずは作成したコードを載せます。その後簡単なコードの解説をしています。

using System;

using System.Linq;
using System.Collections.Generic;

namespace PennyFlippingProblemApp {

public class PennyFlipping {
private int _number;
// falseが表
private bool[] _disks;

public PennyFlipping(int n) {
_number = n;
_disks = new bool[n];
}

// 問題を解く
public IEnumerable<(int, bool[])> Solve() {
int count = 0;
foreach (var n in Repeat(Enumerable.Range(1, _number))) {
Turn(n);
yield return (n, _disks.ToArray());
count++;
if (IsFin())
break;
}
}

// 1,2,3,...n,1,2,3,...n,1,2,3,...nを永遠に繰り返す
private IEnumerable<int> Repeat(IEnumerable<int> nums) {
while (true) {
foreach (var n in nums)
yield return n;
}
}

// 先頭N枚のコインをひっくり返す。
public void Turn(int n) {
var r = _disks.Take(n).Reverse().ToArray();
for (int i = 0; i < n; i++) {
_disks[i] = !r[i];
}
}

// 終了したかどうか
public bool IsFin() {
return _disks.All(d => d == false);
}
}
}

using System;

using System.Linq;

namespace PennyFlippingProblemApp {
class Program {
static void Main(string[] args) {
var line = Console.ReadLine();
if (int.TryParse(line, out var number)) {
number = Math.Max(3, Math.Min(20, number));
var pf = new PennyFlipping(number);
var result = pf.Solve().ToArray();
foreach ((var n, var coins) in result) {
PrintDisks(n, coins);
}
Console.WriteLine($"{result.Length}手で元に戻る");
}
}

private static void PrintDisks(int count, bool[] coins) {
string s = string.Format("({0,2}枚) : ", count);
foreach (var d in coins) {
s += (d ? "1 " : "0 ");
}
Console.WriteLine(s);;
}
}
}


コードの解説

コインの枚数を入力できるようにしていますが、3~20に制限しています。

初期設定のコードを省略するために、コインの表を false, 裏を trueで表しています。回数を求めるのにどちらが表面でも同じですから。

配列にセットしたコイン(bool型)を実際にひっくり返していって、元の状態(すべてがfalse)に戻るまで、処理を繰り返しています。

PennyFlippingクラスには、IEnumerable<int>を戻り値として無限に繰り返すRepeatメソッドを定義しています。

事前に何回繰り返したら良いかわからない問題では、こういったメソッドを定義すると、すっきりしたコードが書けますね。

PennyFlippingクラスのSolveメソッドの内部で、コインをひっくり返す処理をしていて、その経過を列挙しています。こうすれば、途中結果も表示できます。そして、この列挙した回数を数えれば、答えが見つかります。

コードを見てもらえばわかりますが、intとbool[]のタプルを列挙しています。最新のC#はタプルが言語機能として備わっているのでとても便利です。


実行結果

実行結果です。初期状態は示していません。()の中はひっくり返した枚数を示しています。右側がひっくり返したあとの状態です。左が上を示し、一番右が底を示しています。

4

( 1枚) : 1 0 0 0
( 2枚) : 1 0 0 0
( 3枚) : 1 1 0 0
( 4枚) : 1 1 0 0
( 1枚) : 0 1 0 0
( 2枚) : 0 1 0 0
( 3枚) : 1 0 1 0
( 4枚) : 1 0 1 0
( 1枚) : 0 0 1 0
( 2枚) : 1 1 1 0
( 3枚) : 0 0 0 0
11手で元に戻る


補足

ちなみに、途中経過を表示するコードは、以下のようにも書けます。

変更したメソッドだけ示します。

    // 問題を解く 

public int Solve(Action<int, bool[]> progress) {
int count = 0;
foreach (var n in Repeat(Enumerable.Range(1, _number))) {
Turn(n);
progress(n, _disks.ToArray());
count++;
if (IsFin())
break;
}
return count;
}

   static void Main(string[] args) {

var line = Console.ReadLine();
if (int.TryParse(line, out var number)) {
number = Math.Max(3, Math.Min(20, number));
var pf = new PennyFlipping(number);
var result = pf.Solve(PrintDisks);
Console.WriteLine($"{result}手で元に戻る");
}
}

途中経過を示すのに、IObservable<T>IObserver<T> を使う方法もありますが、それはまた別のプログラムの時に紹介したいと思います。


この記事は、Gushwell's C# Programming Pageで公開したものをに大幅に加筆・修正したものです。