« 2016年03月 | メイン | 2016年06月 »

2016年05月 アーカイブ

2016年05月04日

"Sum and Product Puzzle"をPythonで解いてみた

昔、多分NetNewsのfj.sci.mathかどこかだと思うが、次のような問題が流れていた。

司会と A さん, B さんがいます.
司会 「今から Joker を除いたトランプ 52 枚から無作為に 2 枚を取り出し, A さんにはその二数の積を, B さんには和を教えます. その数から元の二数が何であるかを考えてください」
A, B 「はい」
司会 「(B さんにわからないよう, A さんに積を教える)」
司会 「(A さんにわからないよう, B さんに和を教える)」
A さん 「教えてもらった数からは元の二数はわかりません」
B さん 「私もわかりません. でも, A さんが『わからない』と言うのはわかっていました」
A さん 「それなら私はわかりました」
B さん 「それなら私もわかりました」
さて, A さん, B さんの聞いた数はそれぞれいくつでしょう?
これだけで答えが1つに特定できることが驚きであり、取ってあった。それをたまたま見つけたので、もう一度やってみた(解説は後述)。
一見どこから手を付ければ良いのかわからないが、「A さんが『わからない』と言うのはわかっていました」からBさんの数字を考えてみると、ほぼ答えまで絞られるので、解くのにそれほど時間はかからない。

NetNewsの元の投稿は探せなかったが、その代わりに、この問題の元ネタが見つかった。 元の問題は1969年に発表されたもので、その後に様々なバリエーションが作られ、一連の問題は"Sum and Product Puzzle"と呼ばれているらしい。参考文献[1]によると、1979年にMartin Gardnerが"the Impossible Puzzle"と呼んで紹介した頃の英語版の1つは次のようなものだったらしい。

Two numbers m and n are chosen such that 2 ≤ m ≤ n ≤ 99. Mr. S is told their sum and Mr. P is told their product. The following dialogue ensues:
Mr. P: I don’t know the numbers.
Mr. S: I knew you didn’t know. I don’t know either.
Mr. P: Now I know the numbers.
Mr. S: Now I know them too.

In view of the above dialogue, what are the numbers?
元の2数の範囲が2〜99なだけで、後は全く同じである。おそらく同じようにして解けるのだが、範囲が広い為に格段に面倒である。
どうせ、部分的にヒューリスティックに絞り込んでいるが、しらみ潰しに探しているのと大差無い。おそらく、整数の範囲を制限しているので、しらみ潰しに探す以外に解法は無いと思う。(例えば「2より大きいあらゆる偶数は素数の和で表せる」というゴールドバッハ予想も、整数の範囲を制限しているので、単独では使えない。m+nとしてあり得る188は7+181 = 31+157 = 37+151 = 61+127 = 79+109であり、99以下の素数の和ではないので、m,nが共に素数である組み合わせが無い。)
プログラミングの勘を取り戻す為のリハビリを兼ねて、プログラムを作ってしらみ潰しに探すことにした。

#!/usr/bin/python

MIN = 2
MAX = 99

def good_factors(p):
    """Generates pairs of factors of p"""
    return [(m,n) for m in range(MIN, MAX+1) for n in range(MIN, MAX+1) if m <= n and m*n == p]

def good_summands(s):
    """Generates pairs of summands of s"""
    return [(m,n) for m in range(MIN, MAX+1) for n in range(MIN, MAX+1) if m+n == s and m <= n]

def fact1(m, n):
    """Mr. P: I don't know the numbers."""
    return len(good_factors(m*n)) > 1

def fact2(m, n):
    """Mr. S: I knew you didn't know."""
    for (m_, n_) in good_summands(m+n):
        if not fact1(m_, n_):
            return False
    return True

# This is not necessary but just writing straightforward
def fact3(m, n):
    """Mr. S: I don't know either."""
    return len(good_summands(m+n)) > 1

def fact4(m, n):
    """Mr. P: Now I know the numbers."""
    fact2_compliers = [(m,n) for (m,n) in good_factors(m*n) if fact2(m,n)]
    return len(fact2_compliers) == 1

def fact5(m, n):
    """Mr. S: Now I know them too."""
    fact4_compliers = [(m,n) for (m,n) in good_summands(m+n) if fact4(m,n)]
    return len(fact4_compliers) == 1

result = [(m,n) for m in range(MIN, MAX+1) for n in range(MIN, MAX+1) if m <= n and fact1(m,n) and fact2(m,n) and fact3(m,n) and fact4(m,n) and fact5(m,n)]

print "result =", result

これを実行すると、(m,n)の正解である(4,13)が出力される。
MIN = 1, MAX = 13にすると、冒頭のトランプの問題の元の2数も計算できる。

但し、心持ち関数型プログラミングっぽくしてみたが、これだととても時間がかかる(Intel Core i5 1.6GHzのCPUでも2分以上)。次のように、good_factors()とgood_summands()が計算結果をキャッシュするように書き換えると、20倍くらい速くなった。

good_factors_dict = {}
def good_factors(p):
    """Generates pairs of factors of p"""
    if not good_factors_dict.has_key(p):
        good_factors_dict[p] = [(m,n) for m in range(MIN, MAX+1) for n in range(MIN, MAX+1) if m <= n and m*n == p]
    return good_factors_dict[p]

good_summands_dict = {}
def good_summands(s):
    """Generates pairs of summands of s"""
    if not good_summands_dict.has_key(s):
        good_summands_dict[s] = [(m,n) for m in range(MIN, MAX+1) for n in range(MIN, MAX+1) if m+n == s and m <= n]
    return good_summands_dict[s]

◆参考文献
[1] "Sum and Product in Dynamic Epistemic Logic"
H. P. van Ditmarsch, et al.
J Logic Computation (2008) 18 (4): 563-588
First published online: December 21, 2007
http://www.cs.otago.ac.nz/staffpriv/hans/sumpro/sumandproduct06.pdf

続きを読む ""Sum and Product Puzzle"をPythonで解いてみた" »

2016年05月29日

CppUTestでテスト駆動開発(1)

図書館で、「テスト駆動開発による組み込みプログラミング」という本に目を引かれ、流し読みしたら結構面白かったので、借りて帰ったのだが、筆者はこの所公私共に多忙で、ほとんど読めないまま返却期限を迎えてしまった。
とりあえず、その本で推薦されていた、CppUTestというユニットテストフレームワークを使ってみた。

筆者は、凄まじく高コストで生産性の低い日本企業のソフトウェア開発を数年間目の当たりにした後、21世紀に入った頃にテストファーストを含むExtreme Programmingの考え方に全面的に共感し、その時にCUnitというユニットテストフレームワークを使ったことがあるのだが、その価値がわからなかった。わざわざそんなのを使わなくても、ユニットテストを駆動する短いテストドライバを自分で書けば事足りると思ったし、実際、これまでそのようにしてきて困ったことが無い。

しかし、今回、この本でUnityやCppUTestの話を読むと、ユニットテストフレームワークには最先端の考え方が反映されており、この枠に嵌められてユニットテストを書いたりTDDをすれば、手軽に世界のトップクラスのインテリジェンスに触れられるような気がして、面白そうだと思った。

そこで、CppUTestを使ってみることにした。

書籍の第3章のLEDドライバの例を題材に、TDD(テスト駆動開発)方式で、まずは未実装のエラーが出る実行可能なテストを作ってみる。

LedDriver/LedDriverTest.cpp
#include "CppUTest/TestHarness.h"

TEST_GROUP(LedDriver)
{
  void setup()
  {
  }
  void teardown()
  {
  }
};

TEST(LedDriver, LedsOffAfterCreate)
{
  FAIL("Start here");
}
test_main.cpp
//from README.md
#include <CppUTest/CommandLineTestRunner.h>

int main(int ac, char** av)
{
   return CommandLineTestRunner::RunAllTests(ac, av);
}
Makefile
CXX = g++
CPPUTEST_HOME := $(HOME)/tmp/cpputest

#from README.md
CPPFLAGS += -I$(CPPUTEST_HOME)/include
CXXFLAGS += -include $(CPPUTEST_HOME)/include/CppUTest/MemoryLeakDetectorNewMacros.h
CFLAGS += -include $(CPPUTEST_HOME)/include/CppUTest/MemoryLeakDetectorMallocMacros.h
LD_LIBRARIES = -L$(CPPUTEST_HOME)/lib -lCppUTest -lCppUTestExt

TARGET = test_main
SRCS = test_main.cpp LedDriver/LedDriverTest.cpp
OBJS = $(SRCS:.cpp=.o)

all: $(TARGET)

$(TARGET): $(OBJS)
	$(CXX) -o $@ $^ $(CXXFLAGS) $(LD_LIBRARIES)

%.o: %.cpp
#	GNU make implicit rule + "-o $@"
	$(CXX) $(CPPFLAGS) $(CXXFLAGS) -c $< -o $@

.PHONY: check
check: $(TARGET)
	./$(TARGET) -v

.PHONY: clean
clean:
	rm -f $(TARGET) $(OBJS) *.gcno *.gcov *~ */*~
	find . -name "*.gcda" | xargs rm -f

これでmake checkとすると、1つのテストが失敗し、"Start here"と表示される。
筆者は普段、テストの実行はmake testであるが、make checkが多数派らしいので、今後はそれに倣うことにした。(make testはPerlの世界に多い?)

MakefileにLedDriver.cのコンパイルが無いのは、TDDの、エラーにならない限りは作らない原則に従っているからである。

次に、LedDriver/LedDriverTest.cppにテストを追加し、それがpassするようにLedDriver.cを開発するのを繰り返す。
途中と詳細説明を省略するが、例えば途中段階では次のようになった。

LedDriver/LedDriverTest.cpp
#include "CppUTest/TestHarness.h"
extern "C" {
#include "LedDriver.h"
}

static uint16_t virtualLeds;

TEST_GROUP(LedDriver)
{
  void setup()
  {
    LedDriver_Create(&virtualLeds);
  }
  void teardown()
  {
  }
};

TEST(LedDriver, LedsOffAfterCreate)
{
	uint16_t virtualLeds = 0xffff;
	LedDriver_Create(&virtualLeds);
	LONGS_EQUAL(0, virtualLeds);
}

TEST(LedDriver, TurnOnLedOne)
{
	LedDriver_TurnOn(1);
	LONGS_EQUAL(1, virtualLeds);
}

TEST(LedDriver, TurnOffLedOne)
{
	LedDriver_TurnOn(1);
	LedDriver_TurnOff(1);
	LONGS_EQUAL(0, virtualLeds);
}

TEST(LedDriver, TurnOnMultipleLeds)
{
	LedDriver_TurnOn(9);
	LedDriver_TurnOn(8);
	LONGS_EQUAL(0x0180, virtualLeds);
}

TEST(LedDriver, AllOn)
{
	LedDriver_TurnAllOn();
	LONGS_EQUAL(0xffff, virtualLeds);
}
	
TEST(LedDriver, TurnOffAnyLed)
{
	LedDriver_TurnAllOn();
	LedDriver_TurnOff(8);
	LONGS_EQUAL(0xff7f, virtualLeds);
}

IGNORE_TEST(LedDriver, LedMemoryIsNotReadable)
{
	// TODO: let LED state read-only
}
LedDriver/LedDriver.h
#pragma once
#include <stdint.h>

extern void LedDriver_Create(uint16_t *address);
extern void LedDriver_Destroy(void);
extern void LedDriver_TurnOn(int ledNumber);
extern void LedDriver_TurnOff(int ledNumber);
extern void LedDriver_TurnAllOn(void);
LedDriver/LedDriver.c
#include "LedDriver.h"

enum {ALL_LEDS_ON = ~0, ALL_LEDS_OFF = ~ALL_LEDS_ON};

static uint16_t *ledsAddress;

static uint16_t convertLedNumberToBit(int ledNumber)
{
	return 1 << (ledNumber - 1);
}

void LedDriver_Create(uint16_t *address)
{
	ledsAddress = address;
	*ledsAddress = ALL_LEDS_OFF;
}

void LedDriver_Destroy(void)
{
}

void LedDriver_TurnOn(int ledNumber)
{
	*ledsAddress |= convertLedNumberToBit(ledNumber);
}

void LedDriver_TurnOff(int ledNumber)
{
	*ledsAddress &= ~convertLedNumberToBit(ledNumber);
}

void LedDriver_TurnAllOn(void)
{
	*ledsAddress = ALL_LEDS_ON;
}
Makefile
CXX = g++
CC = gcc
CPPUTEST_HOME := $(HOME)/tmp/cpputest

#from README.md
CPPFLAGS += -I$(CPPUTEST_HOME)/include
CXXFLAGS += -include $(CPPUTEST_HOME)/include/CppUTest/MemoryLeakDetectorNewMacros.h
CFLAGS += -include $(CPPUTEST_HOME)/include/CppUTest/MemoryLeakDetectorMallocMacros.h
LD_LIBRARIES = -L$(CPPUTEST_HOME)/lib -lCppUTest -lCppUTestExt

TARGET = test_main
SRCS = test_main.cpp LedDriver/LedDriverTest.cpp
CSRCS = LedDriver/LedDriver.c
OBJS = $(SRCS:.cpp=.o) $(CSRCS:.c=.o)

all: $(TARGET)

$(TARGET): $(OBJS)
	$(CXX) -o $@ $^ $(CXXFLAGS) $(LD_LIBRARIES)

%.o: %.cpp
#	GNU make implicit rule + "-o $@"
	$(CXX) $(CPPFLAGS) $(CXXFLAGS) -c $< -o $@

%.o: %.c
#	GNU make implicit rule + "-o $@"
	$(CC) $(CPPFLAGS) $(CFLAGS) -c $< -o $@

.PHONY: check
check: $(TARGET)
	./$(TARGET) -v

.PHONY: clean
clean:
	rm -f $(TARGET) $(OBJS) *.gcno *.gcov *~ */*~
	find . -name "*.gcda" | xargs rm -f

make checkすると、"OK (7 tests, 6 ran, 6 checks, 1 ignored, ...)"となる。
ignoredなのは「実行可能なリマインダ」である。

ところで、CppUTestには簡単なメモリリーク検出機能がある。各TEST()の実行前にTEST_GROUPのsetup()が、実行後にteardown()が呼び出されるが、そのsetup()前とteardown()後とでメモリ確保状態を比較するようである。
試しに、LedDriver/LedDriver.cのLedDriver_TurnAllOn()を

#include <stdlib.h>
void LedDriver_TurnAllOn(void)
{
	void *p = malloc(1);
	*ledsAddress = ALL_LEDS_ON;
}
に変えてmake checkとすると、次のエラーメッセージが出た。
TEST(LedDriver, AllOn)
LedDriver/LedDriverTest.cpp:46: error: Failure in TEST(LedDriver, AllOn)
	Memory leak(s) found.
Alloc num (6) Leak size: 1 Allocated at: LedDriver/LedDriver.c and line: 35. Type: "malloc"

うまく使えば便利そうである。
CppUTestに触れてみて、TDDをきちんと勉強しようと思った。

続きを読む "CppUTestでテスト駆動開発(1)" »

About 2016年05月

2016年05月にブログ「Weblog on mebius.tokaichiba.jp」に投稿されたすべてのエントリーです。過去のものから新しいものへ順番に並んでいます。

前のアーカイブは2016年03月です。

次のアーカイブは2016年06月です。

他にも多くのエントリーがあります。メインページアーカイブページも見てください。

Powered by
Movable Type 3.35