Language detail: Erlang - 's unsolved challenges

文字列で+を表示する (Nested Flatten)
与えられた文字列で+のかたちを表示するプログラムをかいてください。
サンプル入力:
doukaku

サンプル出力:
       doukakud
       u      o
       k      u
       a      k
       k      a
       u      k
       o      u
doukakud      doukakud
u                    o
k                    u
a                    k
k                    a
u                    k
o                    u
dukakuod      dukakuod
       u      o
       k      u
       a      k
       k      a
       u      k
       o      u
       dukakuod
年賀はがきの当せん番号 (Nested Flatten)

年賀はがきの当せん番号について確認する方法をはがき(番号)の整理の仕方も含めて考えよ

箱詰めパズルの判定 (Nested Flatten)
以下の積み木のうち4つを、
重複を含めてランダムに選びます。
このとき、それらを4×4の箱に
詰められるかどうかを判定してください。

1.
■■■■

2.
■■
■■

3.
■■■
 ■

4.
■■■
■

5.
■■
 ■■

例えば、{ 1, 1, 1, 1 }, { 2, 2, 2, 2 } は箱につめることができますが、
{ 1, 2, 2, 3 } は箱につめることができません。

余力のある方は、以下の値を求めてみてください。
・箱につめることができる積み木の組み合わせの総数
・上記総数を、異なる詰め方の個数別にカウント
 (箱の回転・裏返しで一致するものは同一視します)
関数やメソッドのソースの平均行数 (Nested Flatten)

イントロスペクションおよびメトリックスのお題です。

アジャイル界隈などでは、あまり長くだらだらと書いてはいけない…と言われている 関数 and/or メソッド ですが、ならば実際のところ、洗練された既存のライブラリにおいて、関数 and/or メソッド は平均すると何行くらいで記述されているのか…といった情報を具体的に把握しておきたいと思ったことはありませんか?

そこで、みなさんイチオシの言語それ自身で書かれているライブラリを、それなりの規模になるように集めてきて、1)集めたライブラリ群内に定義されている全 関数 and/or メソッド の合計数(母集団の確認のため)、と 2)関数 or メソッドのソースの平均の行数、を求めるコードと、その結果を示してください。

なお、関数 and/or メソッドに帰属するものであれば、コメント行やアノテーションのたぐいも行数のカウントに含めてください(コードが必要以上に複雑にならない範囲で結構です)。また、関数内関数定義やメソッド内クラス定義(ひいてはその中でのメソッド定義)といった入れ子になったコードの行数をどう解釈するかの判断はお任せします。関数とメソッドが共存する言語では両者を区別してカウントする必要はありません(しても構いません)。平均値を求めるコードを、対象言語で記述することが技術的に困難な場合は、UNIX的なツールを組み合わせたり、IDEなどが提供するメトリックス機能を活用して算出した結果を示すのでもよいと思います。

このお題は、平均行数が 8.4 行(Squeak Smalltalk の組み込みライブラリ+αより、調査メソッド総数 4万)と、一般に簡潔さが美徳とされている Smalltalk からの挑戦(?)でもあります。

コレクションの実装 (Nested Flatten)

コレクションフレームワークに則ってコレクションクラスを実装して下さい.

具体的にどのようなコレクションを実装しても構いませんが,コレクションフレームワークで用意された基本的なメソッドは一通り呼べるようにして下さい. foreach系の構文があれば,それでも使えるとよいです.

例えば,Rubyであれば以下のようなコードで(mapを直接定義することなく)要素を列挙できる必要があるでしょう.

1
2
3
4
5
6
p MyCollection.new.map {|i| i }

# for でも使える
for i in MyCollection.new
  p i
end
居眠り床屋問題 (Nested Flatten)

並行処理のお題です。ある床屋の亭主は、客がいないときまって居眠りを始めます。床屋店内には三台の散髪兼順番待ち用の椅子があり、客は来店時に椅子に空きがあれば、いずれかに勝手に座って自分の番が来るのを待ち、散髪を終えてから店を出ます。空席が無ければそのまま何もせずに立ち去ります。居眠り中の亭主は、客の入店時に起こされると待ち客すべてをひとりずつ順に散髪しますが、誰もいなくなればまた居眠りを始めます。

この床屋店に16人の客が訪れた日のシミュレーションを行なうコードと、その結果(下に例として示したログ形式。「[スレッドのIDなど] イベント描写」の一覧と終了後の総括)を出力して示してください。なお、散髪には一人当たり100~400ミリ秒の時間(この範囲でランダムに変化)を要し、客は通常 0~200ミリ秒(同)の間隔で訪れます。ただし例外として9番目の客だけは前の客から1200ミリ秒程度の間隔(すなわち、最大三名の待ち客全員を散髪し終えるのに十分な時間)をあけて訪れるものとします。

実装に際し、実行時のデッドロックの回避はもちろんですが、そのほかにも、競合状態(席の空きを確認して座ろうとしたら、もう別の客が座っていた…というような事態)などの不整合も生じないよう配慮し、必要であればそのための対策を講じてください。たとえば来客の間隔が仮に0ミリ秒で固定の場合(つまり、客が一斉に来店した場合)でも、コードが正常に動作するかどうか試してみるのもよいかもしれません。

 

 

出力例:

[7302088] 床屋、眠る

[7012360] 来店 1

[7302088] 床屋、目覚める

[7302088] 散髪開始 1

[7012360] 来店 2

[7012360] 来店 3

[7302088] 散髪完了 1

[7302088] 散髪開始 2

[7012360] 来店 4

[7012360] 来店 5

[7012360] 満席で立ち去る 5

[7302088] 散髪完了 2

[7302088] 散髪開始 3

[7012360] 来店 6

[7012360] 来店 7

[7012360] 満席で立ち去る 7

[7012360] 来店 8

[7012360] 満席で立ち去る 8

[7302088] 散髪完了 3

[7302088] 散髪開始 4

[7302088] 散髪完了 4

[7302088] 散髪開始 6

[7302088] 散髪完了 6

[7302088] 床屋、眠る

[7012360] 来店 9

[7302088] 床屋、目覚める

[7302088] 散髪開始 9

[7012360] 来店 10

[7012360] 来店 11

[7012360] 来店 12

[7012360] 満席で立ち去る 12

[7302088] 散髪完了 9

[7302088] 散髪開始 10

[7012360] 来店 13

[7012360] 来店 14

[7012360] 満席で立ち去る 14

[7012360] 来店 15

[7012360] 満席で立ち去る 15

[7302088] 散髪完了 10

[7302088] 散髪開始 11

[7012360] 来店 16

[7302088] 散髪完了 11

[7302088] 散髪開始 13

[7302088] 散髪完了 13

[7302088] 散髪開始 16

[7302088] 散髪完了 16

[7302088] 床屋、眠る

※ 16人のうち 10人を散髪

 

化学反応式の完成 (Nested Flatten)

整数の係数を持つ化学反応式を完成してください。反応前の物質と反応後の物質は与えられる物とします。例えば、

(前) Mg, O 2 (後) Mg O

(答) 2Mg + O 2 -> 2MgO

(前) C 2, H 2, O 2 (後) CO 2 , H 2 O

(答) 2C 2 H 2 + 5O 2 -> 4CO 2 + 2H 2 O

こんな感じです。以前anarchy golf に出題させて貰ったんですが、埋め込み解で解かれてしまったので、今回は埋め込み解はなし、と云うことでおねがいします。

復活 (Nested Flatten)
現在のプロセスが終了後、一定時間経過したのち再起動するプログラムを作成してください。一時的にスリープするのではなく、プロセスAが一度終了しアンロードされてから別のプロセスA'が動き出す感じです。AとA'が時間的に重ならないことを要件とします。

プロセスが作成できない言語では、スレッドやオブジェクトなど適当に読み替えてください。

以下のどちらでもかまいません。下のほうが難しいと思います。
 <レベル1> 自分から終了して再起動する。
 <レベル2> タスクマネージャーや kill などでいきなり殺されたのち、再起動する。
UTF-16をUTF-8に変換 (Nested Flatten)

UTF-16の文字コードを16進(1オクテットごとにスペース区切り)の形で入力します。入力した文字コードを、2進数の形(1オクテットごとにスペース区切り)で出力してください。

入力する文字コードはUCS-2の範囲(サロゲートペアを使わなくてもよい範囲)のみに限定しても構いませんが、可能ならばサロゲートペアにも対応したものに挑戦してください。

  • 例1: abc(U+0041 U+0042 U+0043)
    • 入力 00 41 00 42 00 43
    • 出力 01000001 01000010 01000011
  • 例2: あいう(U+3042 U+3044 U+3046)
    • 入力 30 42 30 44 30 46
    • 出力 11100011 10000001 10000010 11100011 10000001 10000100 11100011 10000001 10000110

正攻法からトリッキーな手段まで、いろいろお待ちしております。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>                  
#include <stdlib.h>                 
#include <string.h>                 

typedef unsigned short utf16char; /* sizeof(short) >= 2 octets */
#define UTF8_MAXOCTETS 3 /* UCS-2ではutf-8にしたとき3 octets以内に収まる */
typedef struct{                                                           
        int len;                                                          
        char data[UTF8_MAXOCTETS];                                        
} Utf8char;                                                               

void encode(Utf8char *utf8, utf16char utf16){
        int i, len;                          

        if(!(utf16 & (~0x7f))) len = 1;
        else if(!(utf16 & (~0x7ff))) len = 2;
        else len = 3;                        

        switch(len){
        case 1:     
                utf8->data[0] = utf16 & 0x7f;
                break;                       
        case 2:                              
                utf8->data[0] = (utf16>>6 & 0x1f) | 0xc0;
                utf8->data[1] = (utf16 & 0x3f) | 0x80;   
                break;                                   
        case 3:                                          
                utf8->data[0] = (utf16>>12 & 0xf) | 0xe0;
                utf8->data[1] = (utf16>>6 & 0x3f) | 0x80;
                utf8->data[2] = (utf16 & 0x3f) | 0x80;   
                break;                                   
        }                                                
        utf8->len = len;                                 
}                                                        

void print_bin(char c){
        printf("%d%d%d%d%d%d%d%d ", c>>7&1, c>>6&1, c>>5&1, c>>4&1, c>>3&1, c>>2&1, c>>1&1, c&1);
}                                                                                                

int main(int argc, char **argv){
        int bytes = argc-1, len = bytes / 2;
        int i, j;
        utf16char *utf16;
        char *utf8;
        int u8len = 0;
        Utf8char u8char;

        if(!bytes) return 0;
        if(bytes % 2){
                printf("Invalid input.\n");
                return 1;
        }
        utf16 = malloc(sizeof(utf16char)*len);
        utf8 = malloc(len*UTF8_MAXOCTETS);

        for(i=0,j=1;i<len;i++,j+=2) utf16[i] = strtol(argv[j], NULL, 16)<<8 | strtol(argv[j+1], NULL, 16);

        for(i=0;i<len;i++){
                encode(&u8char, utf16[i]);
                memcpy(utf8 + u8len, u8char.data, u8char.len);
                u8len += u8char.len;
        }
        for(i=0;i<u8len;i++) print_bin(utf8[i]);
        putchar('\n');

        free(utf16);
        free(utf8);
}
シードを固定した乱数 (Nested Flatten)
シードを固定した疑似乱数を出力してください。
数回実行して、常に同じ結果が出力されることを確認してください。
Twitterへの投稿 (Nested Flatten)
Twitter(http://twitter.com/)につぶやきを投稿してください。

APIに関しては
http://watcher.moe-nifty.com/memo/2007/04/twitter_api.html
に日本語訳があるようです。
「update」に投稿の仕様が説明されています。
いちばん長いしりとり (Nested Flatten)
単語のリストを読み込んで、そのリストにある単語で「しりとり」をします。
一番長くしりとりを続けるためのプログラムを書いてください。
また、単語数に対して、計算量がどのように増えていくかも考えて下さい。

なお、単語リストの一例として
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/index-j.htmlで公開されている
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/fam55_40.txtがあります。

ただし、
・一度使った単語は使わないこと(リストに重複がある可能性は考えなくてよい)
・「ん」で終わる単語を使用するか、リスト内にしりとりを続けられる単語がなくなったときに、しりとりは終了する
・一番最初は、好きな単語から初めてもよい
・「一番長くしりとりを続ける」とは、しりとりが終了するまでに使用する単語数が最大になるよう、しりとりの単語を選ぶことをいう
ラングトンのアリの描画 (Nested Flatten)
ラングトンのアリを描画してください。ラングトンのアリは、以下のような動きをする、セル・オートマトンです。(Wikipediaより引用)
- 黒いマスにアリがいた場合、90°右に方向転換し、そのマスの色を反転させ、1マス前進する。
- 白いマスにアリがいた場合、90°左に方向転換し、そのマスの色を反転させ、1マス前進する。
詳しくはWikipedia等で調べるか、参考ページに拙作のデモがありますのでご覧下さい。
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html lang="ja">
<head>
       <meta http-equiv="content-type" content="text/html;charset=utf-8">
       <meta http-equiv="content-script-type" content="text/javascript">
       <meta http-equiv="content-style-type" content="text/css">
       <title>ラングトンの蟻</title>
<style type="text/css">
#canvas{
       border: 1px solid #999;
       width: 300px;
       height: 300px;
}
#canvas div{
       width: 3px;
       height: 3px;
       float: left;
}
</style>
<script>
var earth = [];
var WORLD_SIZE = 100;
var lang_ant;

function Ant(){}
Ant.prototype = {
    age : 0,
    ageDisplay : undefined,
    id : undefined,
    speed: 200,
    direction: [0,-1],//向き。x y軸。最初は上に動く
    position: [60,40],//初期位置
    world: [],
    start: function(){
        var self = this;
        this.id = setInterval(function(){self.move()}, 1000/this.speed);
    },
    move: function(){
        this.ageDisplay.innerHTML = ++this.age;
        this.moveNextCell();
        var cell = this.getCellInfo();
        var color = cell.getAndToggleColor();
        this.setNextDirection(color);
    },
    moveNextCell: function(){
        this.position[0] += this.direction[0];
        this.position[1] += this.direction[1];
        if(this.position[0] < 0 || this.position[1] < 0 ||
           this.position[0] >= WORLD_SIZE || this.position[1] >= WORLD_SIZE){
            clearInterval(this.id);
            this.die();
        }
    },
    getCellInfo: function(){
        var idx = this.position[0] + this.position[1] * WORLD_SIZE;
        return this.world[idx];
    },
    setNextDirection: function(bool){//colorがfalse(白)なら右へ、true(黒)なら左へ転回
        if(bool){//黒
            var tmp = this.direction[0];
            this.direction[0] = this.direction[1];
            this.direction[1] = -tmp;
        }
        else{//白
            var tmp = this.direction[0];
            this.direction[0] = -this.direction[1];
            this.direction[1] = tmp;
        }
    },
    die: function(){
        alert('Langton\'s ant is dead.');
        throw true;
    }
};

function Cell(elm){
    this.elm = elm;
}
Cell.prototype = {
    elm: undefined,
    color: false, //colorは2値なのでbooleanで表す
    colorList: ['#FFF','#000'],
    getAndToggleColor: function(){
        this.color = !this.color;
        var i = this.color ? 1 : 0;
        this.elm.style.backgroundColor = this.colorList[i];
        return !this.color;
    }
}
window.onload = function(){
    var canvas = document.getElementById('canvas');
    var div = '<div></div>';
    var inner_canvas = "";
    for(var i=0; i< WORLD_SIZE*WORLD_SIZE; i++){
        inner_canvas += div;
    }
    canvas.innerHTML = inner_canvas;
    
    var cells = canvas.childNodes;
    for(var i=0; i<cells.length; i++){//世界の誕生
        earth[i] = new Cell(cells[i]);
    }
    lang_ant = new Ant();//蟻の誕生
    lang_ant.world = earth;//地球に降り立つ
    lang_ant.ageDisplay = document.getElementById('step');
    
    document.getElementById('run').disabled = false;
}
</script>
</head>
<body>
<p><input type="button" value="run" onclick="lang_ant.start();this.disabled=true;" id="run" disabled="disabled"> <span id="step"></span>
 <input type="button" value="stop &amp; refresh" onclick="location.reload();"></p>
<div id="canvas"></div>
バイナリクロック (Nested Flatten)
 時刻を二進数相当の表現で出力する時計アプリケーションを書いてください。
 20:18の場合,例えば以下の様な出力をするイメージです。

出力例:
 ■□■□□
□■□□■□
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#! c:\ruby\bin\ruby.exe -Ks

String.class_eval do |string|
    def words
        self.split(//)
    end
    def fix_width(width, padding)
        (self.words.size > width) ? self : (padding * (width - self.words.size) + self)
    end
end

Fixnum.class_eval do |fixnum|
    alias :to_s_orig :to_s
    def to_s(base, width)
        binary = self.to_s_orig(base).fix_width(width, "0")
    end
end

class BinaryClock
    attr_accessor :now
    def initialize
        self.now = Time.now
    end
    def print
        output(self.now.hour.to_s(2, 5))
        output(self.now.min.to_s(2, 6))
    end
private
    def output(binary)
        puts binary.words.map { |f| f == "0" ? "□" : "■" }.join.fix_width(6, " ")
    end
end

BinaryClock.new.print
リングノードベンチマーク (Nested Flatten)

N個のノードを作り、1番目のノードに送られたメッセージは2番目のノードに、2番目のノードに送られたメッセージは3番目のノードに、・・・、N番目のノードに送られたメッセージは1番目のノードに送られるようにリングを形成し、そのリング上を一つのメッセージがM回まわるのにかかる時間を計測してください。

メソッド数の多い組み込みクラスを列挙 (Nested Flatten)

言語処理系に組み込みの全クラスについて、それぞれに定義されているメソッド数が多い順に上位10番目までのクラス名とメソッド数を出力するコードを書いてください。全クラス数も示してください。

なお、「組み込み」「クラス」「メソッド」などについては、必要であれば、その言語にふさわしい対象や機能に適宜読み替えてください。(たとえば、組み込み→標準添付、クラス→型・モジュール・パッケージ…、メソッド→関数・プロシージャ…といった具合に)

初期設定の読み書き (Nested Flatten)

 初期設定を読み書きするプログラムを書いてください。

 保存先や形式は問いませんが,OS,ライブラリ,言語等の環境で標準的なものがあれば,なるべくそちらを用いてください。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package org.doukaku.ja.preference;

import java.util.prefs.Preferences;
import java.util.prefs.BackingStoreException;

public class HelloPreference {
    private static final String MESSAGE_KEY = "message";
    private static final String DEFAULT_MESSAGE = "Hello, Preference.";

    private String message;
    private Preferences pref;

    public HelloPreference() {
        loadPreference();
    }

    public void loadPreference() {
        setPreference(Preferences.userNodeForPackage(this.getClass()));
        setMessage(pref.get(MESSAGE_KEY, DEFAULT_MESSAGE));
    }

    public void setMessage(String message) { this.message = message; }
    public String getMessage() { return this.message; }
    public void setPreference(Preferences pref) { this.pref = pref; }
    public Preferences getPreference() { return this.pref; }

    public void showMessage() {
        System.out.println(getMessage());
    }
    public void storePreference() throws BackingStoreException {
        Preferences pref = getPreference();
        pref.put(MESSAGE_KEY, getMessage());
        pref.flush();
    }

    public static void main(String[] args) {
        try {
            HelloPreference    hello = new HelloPreference();
            if (args.length > 0) {
                hello.setMessage(args[0]);
            }
            hello.showMessage();
            hello.storePreference();
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }
}
printf書式変換 (Nested Flatten)
C言語のprintf書式を、あなたの言語のprintf系書式に変換して下さい。
また、逆変換をして下さい。
loan patternのサンプル (Nested Flatten)
リソースを使うときのパターンloanのサンプルを書いて下さい。
参考
Programming in Scala (P.170 , P.172)
手作業Grep (Nested Flatten)

標準入力を読み込んで、行選択のUIをだし、選択されたものだけを標準出力にだしてください。 標準出力に出力するタイミングは選択終了をユーザーが報告したときです。(完了ボタンを想定してください)

UIライブラリは何をつかってもかまいません。 例えばncursesのようなコンソール上でのUIでもかまいませんし、GtkのようなGUIライブラリでもかまいません。

想定される使い方としては、以下のような感じです。

ps aux | handgrep | xargs kill -9

プロセスの一覧を表示、UI上で選択したものをkill

ストレンジアトラクタの描画 (Nested Flatten)
ストレンジアトラクタの描画をしてください。
ストレンジアトラクタの種類は問いません。
簡単に出力できる言語はその言語の出力機能を使ってもらってかまいません。
また、出力が難しい言語はgnuplotなどのグラフ出力ソフトを使って出力してください。

解答の際はどのタイプのストレンジアトラクタなのかを添えてください。
16進数から10進数の変換 (Nested Flatten)

16進数を10進数に変換してください。

ただし、入出力は文字列とし、次の変換は最低必ずできなければいけないこととします。

  1. 0x12437308CCB6 →20080902065334

2.0x2C9C1227FC6520B →200904012311450123

あわせて、扱える最大の整数も明らかにしてください。

ケブンッリジ関数 (Nested Flatten)

 与えた文章の各単語の最初と最後の文字以外の文字を入れ替えた文章を出力する処理を実装して下さい。元の文章の与え方は特に問いません。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#! c:\ruby\bin\ruby.exe -Ks

class Cmabrigde
    def self.convert(word)
        cs = word.split("")
        (cs.size <= 3) ? word : cs.first + cs[1..-2].sort_by { |c| rand }.join("") + cs.last
    end
end

source = <<EOS
こんにちは みなさん おげんき ですか? わたしは げんき です。
この ぶんしょう は いぎりす の ケンブリッジ だいがく の けんきゅう の けっか
にんげん は もじ を にんしき する とき その さしいょ と さいご の もじさえ あっていれば
じゅんばん は めちゃくちゃ でも ちゃんと よめる という けんきゅう に もとづいて
わざと もじの じゅんばん を いれかえて あります。
どうです? ちゃんと よめちゃう でしょ?
ちゃんと よめたら はんのう よろしく
EOS
source.each_line do |line|
    puts line.chomp.split(/\s+/).map { |word| Cmabrigde.convert(word) }.join(" ")
end
急勾配の判定 (Nested Flatten)

有限の長さの数列で,各要素の値が,その要素の後ろにある残りの列に含まれるすべての要素の和よりも大きい列を「急勾配の列」ということにします(空列の和は0とします).

任意の長さ(ただし有限の長さの)数列を与えられたとき,それが「急勾配の列」であるかどうかを判定する述語関数を定義してください.

必須ではありませんが,効率についてコメントがあれば面白いかもしれませんね.

複素数 (Nested Flatten)
以下の計算をしてください。

1. 加算  ( 3 + i ) + ( 4 - i )
2. 減算  ( 5 - 9i ) - ( 2 + 6i )
3. 乗算  ( 5 + 3i )  * ( 5 + 8i )
4. 除算  ( 9 - 7i )  /  ( 9 - 3i )
5. 絶対値  | 2 + 3i |

複素数計算を行う関数やクラスを定義して答えを求めること。
ライブラリがある場合はそれを利用してかまいません。
割り算の筆算 (Nested Flatten)
整数 n, m を与えれば、 n ÷ m の筆算を出力するような
プロシージャ(関数)を創ってください。

ウィンドウに描画するもよし、
コンソールに出力するもよし、です。
ACLの制御 (Nested Flatten)
通常、作成者以外は、読み書きができないファイルを新規作成してください。
# UNIX的にいうと「0600」のファイルです。

すでに存在していた場合、新しい内容で上書きしてください。

symlinkアタック等を考慮する必要はありません。

余裕のある人はファイルがすでに存在していた場合、
パーミッションを変更してみてください。
外部の実行ファイルを呼び出し (Nested Flatten)
外部の実行ファイルを呼び出して実行してください。
ただし、実行中にプログラムの実行をブロックする版と、しない版の二つを作ってください。
ダブルクリックの取得 (Nested Flatten)
マウスのダブルクリックを取得してください。
ダブルクリックを取得したら、ダブルクリックをした時のマウス座標を表示してください。
キッチンタイマー (Nested Flatten)
キッチンタイマーを作ってください。
要件は以下のとおりです。

・タイマーが鳴るまでの時間を入力可能
・残り時間を表示
・タイマーが切れたら音がなる
ローテートシフト (Nested Flatten)
ローテートシフトを実装してください。

例)
0010 0011 1110 1101
↓右に1ビットローテート
1001 0001 1111 0110

ローテートシフトがある言語がどれ位あるか知りたくなって投稿しました。
ナイツ関数(ボケの方) (Nested Flatten)
入力した文章のところどころを言い間違えて出力する関数を実装してください。
(ナベアツ算を見てて思いつきました)

入出力の方法は標準入出力や引数・戻り値など、扱いやすい方法でかまいません。

文字単位でランダムに間違えても面白くないので、単語のリストから似た単語の候補を探すようにしてください。英単語でもOKです。単語のリストは参考ページからダウンロードしたものを加工して利用すると良いと思います。(4000個あります)

結果がつまらなくても構いませんが、面白いボケをうむ工夫があると良いです。
※人が考えたボケは求めてませんよ!

入力の例として「どう書く?org」の前文をお借りしました。ご自分でヤホーで調べたりして手ごろな文章を見つけて下しあ。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
<入力例>
ドウカク org ヘ ヨウコソ
コノ サイト ハ ダサレタ オダイ ヲ イカニ トクカ キソイアウ
 プログラマ ノ タメノ コロシアム デス
トウコウ ヲ タメシテ ミタイ カタ ハ テスト
トリアエズ ナガメテ ミタイ カタ ハ ゲンゴ ノ イチラン ガ オススメ デス

<出力例>
ドウモク org ヘ ヨウコソ
コノ ザレゴト ハ ダサレタ オダイ ヲ イワハダ トシシタ キソイアウ
 プログラマ ノ タチノミ コロシアム デス
トウコウ ヲ ハナシテ ミチノリ カタ ハ プリント
トリアエズ ナガメテ ミツリン カタ ハ ゲンゴ ノ キンラン ガ オススメ デス
麻雀の和了判定 (Nested Flatten)
麻雀の手牌が和了形か否かを判定するコードを書いてください。

手牌を表すのは、mn+h 枚を表す配列です。フォーマットは A, B の2つから任意に選んだものを受け取ってください。以下の2つは同じものです:
handA = [2,1,1,1,1,2,2,1,3] # 牌1が2個、牌2が1個、牌3が1個、牌4が1個、牌5が1個、牌6が2個、牌7が2個、牌8が1個、牌9が3個
handB = [1,1,2,3,4,5,6,6,7,7,8,9,9,9] # 牌1、牌1、牌2、牌3、牌4、牌5、牌6、牌7、牌7、牌8、牌9、牌9、牌9

ある配列が和了形であるとは、手牌が「刻子」「順子」を合計 n 個と「対子」1 個との和であることをいうものとします。
「刻子」とは1種の牌が m 個あることをいいます。
「順子」とは連続したインデクスを持つ牌が m 種各1個あることをいいます。
「対子」とは1種の牌が h 個あることをいいます。

上の例は、和了形です。なぜなら、当該配列が
Bタイプで表記すると、刻子 [9,9,9], 順子 [2,3,4], [5,6,7], [6,7,8], 対子 [1,1] の、
Aタイプで表記すると、刻子 [0,0,0,0,0,0,0,0,3], 順子 [0,1,1,1,0,0,0,0,0], [0,0,0,0,1,1,1,0,0], [0,0,0,0,0,1,1,1,0], 対子 [2,0,0,0,0,0,0,0,0] の、
和だからです。

・ n は任意のものを受け取れるようにしてください。
・ 牌のインデクスの数 (Aタイプの長さ、Bタイプの要素の最大値) M も任意としてください。
・ 1種の牌の最大個数 (Aタイプの要素の最大値、Bタイプの1種の要素の最大重複度) L も任意としてください。
・ 一般の麻雀の場合は、m=3, n=4, h=2, M=9, L=4 です。この条件に特化した高速化が可能なら行ってもかまいません。

擬似コードで、ごく短い例を示します。
1
2
3
4
5
6
7
8
for 考えられる対子:
    対子を手牌から抜く
    for 考えられる刻子のパターン:
        刻子を手牌から抜く
        手牌が順子の和となっていれば、和了形として抜ける
        刻子を手牌へ戻す
    対子を手牌へ戻す
ここに到達していれば、和了形ではない
17歳教 (Nested Flatten)

誕生日を入力すると、「17歳と何日か」、「17歳と何か月と何日か」を表示するプログラムを作ってください。

文字列を指定されたバイト数で分割 (Nested Flatten)
与えられた文字列を指定されたバイト数以下に分割する関数
splitBytes を書いてください。エンコーディングは実装側の
自由としますが、日本語対応は必須とします。
また、分割した結果の表現方法は、各言語で都合のよいものを
選択して下さい。(リスト,配列,改行区切りなど)

[使用例]
"あいうえおabcdeかきくけこfghij" -> 30バイト (Shift_JIS)
"あいうえおabcdeかきくけこfghij" -> 40バイト (UTF-8)

★Shift_JISで10バイトで分割
splitBytes("あいうえおabcdeかきくけこfghij", 10, "Shift_JIS")
=> ["あいうえお", "abcdeかき", "くけこfghi", "j"]
    (10バイト, 9バイト, 10バイト, 1バイト)

★UTF-8で10バイトで分割
splitBytes("あいうえおabcdeかきくけこfghij", 10, "UTF-8")
=> ["あいう", "えおabcd", "eかきく", "けこfghi", "j"]
    (9バイト, 10バイト, 10バイト, 1バイト)

---補足-------------------------------------------
当処理は文字列をデータベースの
固定長フィールド(2000バイト)に投入できる最大サイズ
ぎりぎりまでに分割する時の利用を考えています。
--------------------------------------------------

●●●
余力のある方は以下も行ってみて下さい。

(1) 以下データを2000バイトずつに分割し、処理時間を計測する。

日本郵便 - 香川県の郵便番号(CSV形式:10,513Byte)
http://www.post.japanpost.jp/zipcode/dl/kogaki/lzh/37kagawa.lzh

※ひとまず香川県が一番サイズが小さいので選びました。
  自信ありの方はさらに大きいサイズのファイルでもチャレンジして
  みて下さい。(全国一括など)
http://www.post.japanpost.jp/zipcode/dl/kogaki.html

(2) 処理速度向上・コード短縮
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// サンプルコード (Groovy版)
def splitBytes(str, len, encode) {
   result = []
   while (str) {
      int stock = 0;
      for (i in 0..<str.size()){
         if (str[0..i].getBytes(encode).size() <= len) stock = i
         else break
      }
      result << str[0..stock]
      str -= str[0..stock]
   }
   return result
}

println splitBytes("あいうえおabcdeかきくけこfghij", 10, "Shift_JIS")
println splitBytes("あいうえおabcdeかきくけこfghij", 10, "UTF-8")
ナベアツ算 (Nested Flatten)

「3の倍数と3がつく数字の時だけアホになる」コードを実装して下さい。

また、余裕のあるかたは更に、

「8の倍数のときに人探しをしてる感じに」「5の倍数のときにナルシストに」なるよう実装して下さい。

自分自身を表示する (Nested Flatten)
いわゆるself-printing programです。
今まで出てなかったっぽいので投稿してみました。

実行すると、そのソースコードの内容をそっくりそのまま表示するコードを書いてください。
ただし、
・空白のみのコードは認めない
・コードそのものを読み込むコードは書いてはいけない
-------->print open('selfprinting.py').read() のようなコード禁止
・コードを複数のファイルに分けたときは、作成あるいは変更したファイルの内容全てを表示すること
-------->foo.pyにprint 'import foo'、main.pyにimport fooのようなコード禁止
・標準入力や引数、あらかじめあるファイルを都合よく想定するの禁止
-------->print argv[1]として引数に'print argv[1]'を指定ってのはなし
・こういったことをしないで真面目に解いてもらうことを目的としているが、目的通りにいかないことは承知しているし、ある意味、楽しみにしている
1
2
3
4
5
6
#!/usr/bin/python
# coding: utf-8
# あんまりpythonらしくないです...

s = "#!/usr/bin/python%c# coding: utf-8%c# あんまりpythonらしくないです...%c%cs = %c%s%c%cprint s %% (10, 10, 10, 10, 34, s, 34, 10)"
print s % (10, 10, 10, 10, 34, s, 34, 10)
指定ファイル名でフォルダツリーごとコピー (Nested Flatten)
コピー元フォルダ、コピー先フォルダ、ファイル名(複数)を指定し、
コピー元フォルダ(配下含む)から、指定したファイル名のファイルを探し出し、
コピー先フォルダにツリーごとコピーする処理を実装して下さい。

[実装に際して]
・複数ファイル名を指定できればどのような形式でも構いません。
   (例: コマンド引数, 外部ファイル)
・指定したファイル名が複数見つかった場合、すべてコピー対象として下さい。
・コピー先に既にファイルやフォルダが存在する場合、削除して下さい。
   (コピー先が指定したファイルのみとなるようにする)
・コピー先フォルダが存在しない場合、新規作成して下さい。

[余裕のある方は]
・除外するファイル名、フォルダ名を指定できるようにして下さい。
・GUIでファイル名の指定やコマンド実行を行えるようにして下さい。

===============================
例) コマンド引数で指定する
(コマンド {コピー元} {コピー先} {コピーファイル名リスト})
>WholeCopy C:\temp C:\temp2 aaa.txt,ddd.txt,ggg.txt,kkk.txt

[フォルダツリーの状態]
C:\temp
|   aaa.txt
|   bbb.txt
|   ccc.txt
|
\---dir1
    |   ddd.txt
    |
    +---dir2
    |   |   eee.txt
    |   |
    |   \---dir3
    |           fff.txt
    |           ggg.txt
    |
    \---dir4
            hhh.txt
            iii.txt
            jjj.txt
            kkk.txt

C:\temp2
|   aaa.txt
|
\---dir1
    |   ddd.txt
    |
    +---dir2
    |   \---dir3
    |           ggg.txt
    |
    \---dir4
            kkk.txt
===============================
作業予定表から週単位で作業量を積み上げる (Nested Flatten)
以下のような期間を表す予定データから、1週間単位での棒グラフになるように作業量を積み上げて表示して下さい。
余裕があれば、土日祝日を休日として、終了日を後ろにずらした表示にすると良いですね。

    開始日    日数
1.2009/1/10 21日間 (#) ←わかり易いように記号を付けています
2.2009/1/15  6日間 (@)
3.2009/1/10  8日間 (*)
4.2009/1/16  1日間 (=)
5.2009/1/16  3日間 (%)
6.2009/1/30  4日間 (=)

結果例:

           %
           %
           %
           =
           *
           *
           *
           *
           *
           *
           @
           @   %
           @   @
           @   @
           #   #   =
           #   #   =
           #   #   #
      *   #   #   #
      *   #   #   #
      #   #   #   #
      #   #   #   #
 1/1  1/5  1/12 1/19 1/26

ルール:
・下から上に向かって積み上げて下さい
・結果の表示は、記号でなくても、テキストでなくても構いませんが個々の予定が判別出来るようにして下さい
・表示範囲は1ヶ月(1/1~1/31)とします
 表示範囲からはみ出した分は無視します
・1週間は月曜から日曜までとします
・予定は1日単位とします

このお題は、以前仕事で作った機能のほんの一部を抜き出して単純化してみました。
プロジェクト管理等でよくあるグラフですね。
IPv6アドレスの短縮 (Nested Flatten)
いろんなところでIPv6の実用化やそれに向けた実験が進められており、今後IPv6のアドレスを見かけることも多くなりそうなので少し触れてみよう、というお題です。

IPv6アドレスは16進表記した2バイトを、コロンで8つつなげて表記します。
例)1230:5670:0000:0000:0123:0000:0000:00ab 

各部分の頭の0は省略できます。上の例はこうなります。
例)1230:5670:0:0:123:0:0:ab 

また、0 が複数続くところは 「::」に置き換えることができます。(ただしアドレス内で1箇所のみ)
例)1230:5670::123:0:0:ab 

この短縮を行う関数を作ってください。
余力のある方は逆変換(伸長)も考えてみてください。
この程度ならライブラリに備わってるかも??
1
2
3
4
5
> ipv6_compress( '1230:5670:0000:0000:0123:0000:0000:00ab' )
1230:5670::123:0:0:ab

> ipv6_compress( '0000:0000:0000:0000:0000:0000:0000:0001' )
::1
エレベータの制御(基本編) (Nested Flatten)
エレベータを制御して、5階建てのビルの各階にいる人たちを、
「効率よく」1階のエントランスまで運んでください。

作成時の条件は次の通りです。
  1. 各階において、人が残っていることはわかるが、
     あと何人残っているかまではわからないものとする。
     # 人が残っているところは常に呼び出しのボタンが押された状態を
     # 仮定して問題ありません。
  2. 稼働しているエレベータは1機のみとする
  3. 降車するたびに、変化がわかるような出力をしてください。
  4. すべての人を運搬終わったら、最後に次の情報を出力してください。
     - 運搬を始めてからの経過時間(ラウンド数)
     - 一番長く放置されていた階の待ち時間(ラウンド数)
     - エレベータの移動距離合計数

エレベータの機能は次の通りです。
  - 搭載人数は最大3人までとする。
  - 移動には、1つの階につき「2」ラウンドかかる。
  - 人の乗降には、1回につき「5」ラウンドかかる。

※ 「ラウンド」は包括された時間だと思ってください。
   単純に「秒」と読み替えてもよいです


各階の人数は次の通りです。
5階  7人
4階 11人
3階  3人
2階  7人
1階  0人

冒頭では、「効率よく」なんて曖昧な表現をしようしましたが、
何について効率よくしたのか、設計についての見解を
コメントしていただけるとうれしいです。

たとえば、
下記のサンプル出力では、各階の待ち時間を最小とすることで
効率よいとしました。(利用者の視点)
ぱっと思いつくところでは、ほかにも2-3種類あるとおもいます。

さて、あなたならどう書く?(笑
// 自分で作ったやつは250L位になってしまいましたorz

INIT --------------------
 [5]th Floor: [ 7] / last_round:[   0]
 [4]th Floor: [11] / last_round:[   0]
 [3]th Floor: [ 3] / last_round:[   0]
 [2]th Floor: [ 7] / last_round:[   0]
 [1]th Floor: [ 0] / last_round:[   0] 

IN(5) [7] → [4] OUT
IN(4) [11] → [8] OUT
IN(3) [3] → [0] OUT
IN(2) [7] → [4] OUT
IN(5) [4] → [1] OUT
IN(4) [8] → [5] OUT
IN(2) [4] → [1] OUT
IN(5) [1] → [0] IN(4) [5] → [3] OUT
IN(2) [1] → [0] OUT
IN(4) [3] → [0] OUT

END --------------------
 [5]th Floor: [ 0] / last_round:[ 174]
 [4]th Floor: [ 0] / last_round:[ 229]
 [3]th Floor: [ 0] / last_round:[  58]
 [2]th Floor: [ 0] / last_round:[ 213]
 [1]th Floor: [ 0] / last_round:[   0] 
       経過時間:[257]
   最大待ち時間:[100]
 移動距離合計数:[52]
データの圧縮と展開 (Nested Flatten)

データを圧縮するcompress、展開するdecompressという関数やメソッドなどを書いてください。データはバイト列でもストリームでもそれ以外の形式でもOKです。

圧縮形式は問いませんが、できるだけ一般的なフォーマット(zip,lzhなど)でお願いします。

また、標準以外のライブラリを使う場合には出典の記載をお願いします。

「○○でも実用的な圧縮/展開プログラムがかけるんだぞ!」というのを、ぜひ示してください。

麻雀ゲーム1 (Nested Flatten)

麻雀ゲームの部分的な作成がお題になります. 以下のメソッド/関数を組み込んで下さい.

  1. n人のプレーヤでゲームをする機能; n = 2--4.
  2. 牌をかき混ぜてから山を作成する機能.
  3. 手牌を理牌する機能.
  4. 山から牌を取る操作.
  5. 手配を切る操作 (ツモ切りで構いません).
  6. 河を保存する機能.
  7. 3--5を繰り返す機能.

ルールとしては,

  1. 配牌は親は14枚, 子は13枚.
  2. 親から順に手牌を切る.
  3. 自分の手番で始めにツモり, その後手牌を切る.
  4. 手牌の数は最大14枚.
  5. 山の牌が残り14枚になったら終了.
  6. 牌全体としては, (3人プレーヤでも) 日本で通常用いられている34種類136枚を使用.

と考えていただければ結構です.

鳴き, あがり, 自風, 場風などは考慮していただかなくて結構です.

テキスト行の正規化 (Nested Flatten)
改行文字を複数個含むテキストデータを格納する文字列を
最大長の行を除く各行末に指定したパディング文字を適切な数だけ追加して、
すべての行が最大長の行と同じ長さに揃う文字列に変換する
手続あるいは関数を書いてください。

元の文字列の最後は改行です。
行の長さはその行に含まれる(行末の改行を除く)文字の数です。

変換前の文字列例
"○○○○\n○○○○○○○\n\n○○○○○\n"

上の文字列例をパディング文字'☆'を指定して変換した文字列
"○○○○☆☆☆\n○○○○○○○\n☆☆☆☆☆☆☆\n○○○○○☆☆\n"

必須ではありませんが、
テキストデータをトラバースする回数を減らす工夫をすると面白いかもしれません。
道順を数える (Nested Flatten)
図.1のような。格子状の経路があるとします。

(1)  このときPからQまでいくのに何通りの経路があるか数えてください。ただし遠回りはせずかならずQに近づく方向に進む(右方向か下方向にだけ進む)とします。

(2)  (1)と条件は同じで、図.2のように経路の一部がない(通れない)場合に、PからQまでいくのに何通りの経路があるか数えてください。

P-+-+-+    P-+-+-+
| | | |    | | | |
+-+-+-+    +-+-+-+
| | | |    |   | |
+-+-+-+    +-+-+ +
| | | |    | | | |
+-+-+-+    +-+ +-+
| | | |    | | | |
+-+-+-Q    +-+-+-Q
  図.1       図.2

経路の表現の仕方、記憶の仕方は自由とします。上記のようなキャラクタでの表現でもよいですし、最初からプログラムで扱いやすいデータとして持っていてもOKです。入力も外部からの入力でもよいですし、プログラム中にコーディングされていてもOKです。


※問題は、野﨑昭弘「離散数学『数え上げ理論』」(講談社 ブルーバックス)「第3章 道順を数える」から拝借させて頂きました。
数独の問題数を数え上げる (Nested Flatten)
4×4のマスを2×2の4ブロックに区切り、いくつかのマスに1~4の数字を配置します。

以下、空白のマスすべてに数字を補い、縦、横、および各ブロックについて1~4の数字が
それぞれ一個ずつ含まれている状態にすることが可能で、かつその方法が一意であるもの、
つまり数独の問題として成立するもののみを考えます。

4 1 | 2           4 1 | 2 3
2   | 4 1         2 3 | 4 1
----+-----  --->  ----+----
  2 | 3 4         1 2 | 3 4
3 4 | 1           3 4 | 1 2

このようなものの総数を「初期配置の数字の個数ごとに」カウントしてください。

余力のある人は、極小な配置に限定してカウントしてみてください。
ただし、極小な配置とは、どの数字を取り除いても数独の問題として
不成立になる配置を指すものとします。


まどろっこしい言い回しになってしまいましたが、
一言で言えば「数独の問題数を数え上げよ」という問題になります。

参考:http://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%AC
島の数をカウントする (Nested Flatten)
m×nの長方形のマス目のうちいくつかを黒く塗りつぶします。
このとき、白の島、黒の島がそれぞれいくつあるかをカウントしてください。

ただし、2つのマスは、同色マスの上下左右の移動で移れるとき、
同じ島にあると定義します。

例:
□■■□
□□■□
□■□□
□■■□
白の島は2つ
黒の島は2つ

例:
□□□□
■□■□
□■□□
□□□□
白の島は1つ
黒の島は3つ
行列式の計算 (Nested Flatten)

n×nの2次元配列を引数にとり、 これを行列とみなして行列式を返す 関数を作成してください。

行列・線形代数のライブラリ等を 使用しないことが条件です。

参考:http://ja.wikipedia.org/wiki/%E8%A1%8C%E5%88%97%E5%BC%8F

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# -*- coding: utf-8 -*-

#   定義に基づく実装例


#   対称群
def symmetric_group(n):
    #   配列 [0, 1, .., (n-1)] を並び替えてできる
    #   すべての配列の組み合わせを返します。

#  置換の符号
def signature(sym):
    #   配列 [0, 1, .., (n-1)] の符号を +1とします。
    #   互換(2つの要素を交換)すると符合が変わります。
    #   配列 [0, 1, .., (n-1)] から
    #   奇数回の互換で得られる配列の符号は -1、
    #   偶数回の互換で得られる配列の符号は +1 になります。

#  行列式
def determinant(mat):
    det = 0;
    deg = len(mat)
    for s in symmetric_group(deg):
        term = signature(s)
        for i in range(deg):
            term *= mat[i][s[i]]
        det += term
    return det
inline/embeded bytecode assembly (Nested Flatten)

Duff's deviceをinline bytecode assemblyを使って実装してください。C言語ではよくあるinline asmのほかの言語バージョンといったところです。copyのsrcとdstは呼び出し側から渡すようにしてください。(要はbytecode側で閉じていてはならない)

Duff's deviceとは、 http://ja.wikipedia.org/wiki/Duff%27s_device に説明がありますが、ループ展開したコピーのコードです。もちろんbytecodeである時点で速度の話をするのはナンセンスです。

bytecodeで速くするとかいう話よりも、ある言語で書かれたcodeの中にその言語で使用されているbytecodeが埋め込めるかどうか、どのようにできるのかが、このお題の意図です。面白い使い道があるならsiteしていただけると幸いです。

また、1言語につき1種のbytecodeとは限りません。たとえば、PythonならCPythonのbytecode, JythonのJavaVMのbytecode, IronPythonのCIL/CLRなどがあります。 もちろん特定アーキテクチャのasmを呼んでもよいです。x86を書くことができるpyasmなんてものもあるらしいです。 http://members.verizon.net/olsongt/usersGuide.pdf

'('と')'の対応 (Nested Flatten)

入力の'('と')'の対応をとってください。

ただし、コード中に'('と')'を含まないでください。

漢字の九九にinspireされました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import sys
start = sys.argv[1]
end = sys.argv[2]
to_test = sys.argv[3]
print start
print end
print to_test

stack = []
while to_test:
  print stack
  head = to_test[0]
  to_test = to_test[1:]
  if head == start:
    stack += [head]
  if head == end:
    if stack:
      stack = stack[:-1]
    else:
      stack = [True]
      break
if stack:
  print False
else:
  print True
世界時計 (Nested Flatten)
プログラムを実行した端末のロケールと、グリニッジ標準時と、ロサンゼルスの現在時刻をそれぞれ表示してください。 時刻の表示はリアルタイムでなく、一回限りで構いません。 時刻のフォーマットは自由とします。
1
2
3
4
出力例
現在の時刻は、2008年10月29日 11時36分21秒です。
グリニッジ標準時刻は、2008年10月29日 2時36分21秒です。
アメリカ・ロサンゼルスの時刻は、2008年10月28日 19時36分21秒です。
漢数字で九九の表 (Nested Flatten)
漢数字で九九の表を作ってください。
ただし以下の条件をつけます。

条件
一.アラビア数字(0~9)禁止。
  プログラムにも出力結果にもアラビア数字を含んではいけない。(全角・半角とも)
二.結果の数字は、「七」とか「一○」(=10)とか「六四」(=64)のような形式とする。
三.九九の結果をそのままプログラム中に書き込んではいけない。

1
2
3
4
5
6
7
8
出力例

 一  二  三  ・・・・
 二  四  六  ・・・・
 三  六  九  ・・・・
 四  八 一二
 ・
 ・
π (Nested Flatten)

円周率を計算してください。

積分を計算するも、素朴な方法も、速さを目指すも、LLで計算する意味を問うもあるでしょう。

http://ja.wikipedia.org/wiki/%E5%86%86%E5%91%A8%E7%8E%87

LL Golf Hole 9 - トラックバックを打つ (Nested Flatten)

LL Golf Hole 9のリリースをアナウンスしているエントリにトラックバックを打ってください(トラックバックURL)。マシンガンのようには打たないでください。ただし、このエントリにはスパムフィルタが搭載されているため、寄せることはできてもカップインできないかもしれません。その場合はtakano32が用意させていただきました打ちっ放し場にてガンガン試し打ちください(トラックバックURL)。

余力のあるものは感想を公式ブログ感想エントリにトラックバックくしてください。 余力がなくても感想をトラックバックしてくれるとスタッフがよろこびます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#!/usr/bin/env ruby
require 'net/http'
require 'uri'
uri = URI.parse('http://ll.jus.or.jp/2008/blog/archives/38/trackback')
Net::HTTP.start(uri.host) do |http|
    ping = "title=LL+Futureに行ってきた!&" +
        "excerpt=参加者としてもLL+Futureおもしろかったよ!¥n" +
        "でも、司会ぐだぐだですみません。次から頑張ります!&" +
        "url=http://ja.doukaku.org/207/&" +
        "blog_name=LL+Golf+Hole+9"
    response, = http.post(uri.path, ping)
    puts response.body
end
起動オプションの解析 (Nested Flatten)
いわゆる、コマンドライン引数の取得(http://ja.doukaku.org/118/)からの派生です。
やっぱ、自分のコマンドってオプションつけたいですよね(笑
タグに「クックブック」なんてつけてみました
長文なのはご容赦ください^^;;
-----
次の起動インタフェースを持つコマンドを作成してください。

書式:cmdopt -o [-q] -d{0|1|2} 文字列 [文字列 ...]

書式を説明すると
- オプション「o」
  必須オプションです。指定されていない場合、異常終了してください。
- オプション「q」
  選択オプションです。
  省略されていても問題有りません。
- オプション「d」
  引数付きオプションです。
  「0」「1」「2」のいずかが続いて指定されます。
- 文字列
  パラメータです。
  1つ以上であればいくつでも指定できます。
  指定されていなかった場合、異常終了してください。

オプションの開始が「-」になっていますが
「+」や「/」でもかまいません。
余力があればロングオプションに対応してもよいです。

起動例:(すべて許容されるのが望ましいです)
1. cmdopt -o AAA
2. cmdopt -o AAA BBB CCC
3. cmdopt -oq AAA
4. cmdopt -o  -q AAA
5. cmdopt -o -s1 AAA
6. cmdopt -o -s 1 AAA
7. cmdopt -q -s2 -o AAA

出力例:
[オプション情報]
o(output): ON|OFF
q(quote): ON|OFF
d(debug): 0|1|2 

[パラメータ情報]
指定数: N
1: 文字列1
2: 文字列2
...
N: 文字列N
文字列型日時ののN秒後時間取得 (Nested Flatten)
日時を表す文字列と時間(秒)を受け取り
指定された日時からN秒となる日時を出力する関数 DateEx() を作成してください。

関数の仕様は次の通りです。
1. 入力となる日時の書式は任意である。
    → プログラムの都合に合わせてよい。
2. 入力となる時間(秒)は、負の値も許容すること。
    また、負の値が指定された場合、指定の日時よりも前の日時を出力すること
3. 出力する日時は入力の日時と同じ書式をとる文字列であること
4. 出力する日時は正規化されていること
5. 出力先は標準出力、または、バッファのいずれでもよい。

たとえば、DateEx("20080827235925",40)ならば
出力は
「20080828000005」です。

余力があれば時間を省略可能とし、
省略された場合は「現在時刻」を利用するようにしてみてください。
LL Golf Hole 4 - 文章から単語の索引を作る (Nested Flatten)

GNU GENERAL PUBLIC LICENSE Version 3に登場する単語について、単語が登場する行を示した索引を作成してください。

与えられる文章についてはリテラルで表記する、標準入力で与えられる、引数でファイル名が与えられるなどは自由とします。

余力のあるものはこのプログラムを短くしてみたり、短くしてみたり、短くしてください。

※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#!/usr/bin/env ruby
require 'open-uri'
lines = open('http://www.gnu.org/licenses/gpl.txt').readlines
dic = {}
lines.each_with_index do |line, index|
    line.scan(/\w+/).each do |word|
        dic[word] = dic[word] ? dic[word] << index + 1 : [index + 1]
    end
end
p dic
tailの実装 (Nested Flatten)

'tail'を実装してください。

巨大なファイルでも効率的に動作するようにしてください。

最低限必要な機能は、

  • 行数指定
  • 「-f」パラメータの対応

です。

lessの実装 (Nested Flatten)

'less'を実装してください。

巨大なファイルでも効率的に動作するようにしてください。

最低限必要な機能は、

  • 上下スクロール
  • 検索

です。

2次元ランダムウォーク (Nested Flatten)

2次元ランダムウォークをつくってみてください。

******

元は3本建てにしようかと思ったけど、上の一本に絞りました。おまけとして、3本とも下に補足しておきます。作れるようでしたら作ってみてください。

1.一次元のランダムウォークを作ってください。

1.1 データファイルに残してください。 フォーマット:時間 位置

おまけ)

可視化が簡単な処理系・プログラミング言語でしたら実際に可視化してみてください。フォーマットしたファイルをスプレッドシートやplotutilitiesなどの可視化ソフトを使って、実際に動きをかくにんしてみましょう。:-)

2.同じように2次元のランダムウォークを作ってください。

2.1 1.1と同じようにしてください。

フォーマット:時間 x位置 y位置

3.凝りたければ、アニメーションにするもよし、3次元の動きをとるもよし、自分の想像力がいかせるところまでやってみてください。

http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%82%A6%E3%82%A9%E3%83%BC%E3%82%AF

分からないというヒトへの分かりにくいヒント:

今の位置から次の時間の位置が決まるのですが、決まりかたが、乱数で一歩後退するか一歩先にいくか?ということをやればよいです。

LL Golf Hole 1 - tinyurl.comを使ってURLを短縮する (Nested Flatten)

tinyurl.com( http://tinyurl.com/ )のサービスを利用し、 http://ll.jus.or.jp/2008/info/xgihyo というURLを短縮しなさい。tinyurl.comのalias機能は使わないものとする。 なお、参考までに短縮したURLは http://tinyurl.com/5mngx8 となる。

余力のあるものはこのプログラムを短くしてみたり、短くしてみたり、短くしてみよ。

※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/env ruby

require 'rubygems'
require 'mechanize'

def tinyurl(url, _alias = nil)
    m = WWW::Mechanize.new
    res = m.get('http://tinyurl.com/')
    form = res.forms[1]
    form['url'] = url
    form['alias'] = _alias if _alias
    res = m.submit(form)
    regexp = Regexp.new('.*(http\:\//tinyurl.com/[a-z0-9-]+).*')
    match = regexp.match(res.body)
    return match[1] if match
end

if __FILE__ == $0 then
    puts tinyurl('http://ll.jus.or.jp/2008/info/xgihyo')
end
コード圧縮 (Nested Flatten)
スペースやインデントなど、本来は必要なく開発効率を上げるために記述が許可されている項目について、
それらを可能な限り減らし、コードを短くするコード書いてください。
また、投稿時に対象とする言語と、実際の処理結果を記載できるとわかり易いかと思います。

以下詳細
・全てを行う必要はありません、どこまで行うかは任意です。
・ローカル宣言など、消しても動作に関係のない構文の削除や置き換えを行っても構いません。
・必ず同じ入力に同じ結果が返るのであれば処理内容を変えることもかまいませんが、推奨・強制はしません。
・コンパイラや実行環境に依存する圧縮は避けてください。
クリップボードへの転送 (Nested Flatten)

クリップボード(や同等の機能)へテキストを転送するプログラムをお願いします。 また可能でしたらクリップボードのデータを取り出すプログラムもお願いします。

システムに依存する内容ですが、応用範囲が広いと思いましたので出題させてもらいました。

設定ファイルから値を取得 (Nested Flatten)
設定ファイルから項目名をキーとして値を取得するコードを書いてください。
設定ファイルのイメージも載せてください。

ここで設定ファイルとは、
 ・項目名と値のペアが書いてあるファイル
 ・フォーマットはその言語で扱いやすいものでよい
 ・コードと分離され、コードに影響を与えずに変更が可能
を条件とします。ファイルが難しければ同等のものでもかまいません(テーブル、環境変数など)。

例)
----
ファイル:ShowPrice.ini
ITEM_NAME=りんご
ITEM_COST=200

> showPrice()
「りんご」は210円(税込み)
----
ITEM_NAME=みかん
ITEM_COST=100

> showPrice()
「みかん」は105円(税込み)
コメントの削除 (Nested Flatten)
ソースコードからコメント部分を削除するプログラム decomment を書いてください.
すくなくとも,decomment を記述したのと同じ言語で書かれているソースコードが
扱えるようにしてください.



α置換 (Nested Flatten)
標準入力から与えられたソースコードの変数名
を置換するプログラムを作ってください。
最近はリファクタリングツールなどの普及でこ
のような需要は少ないかと思われますが、viな
ど貧弱なエディタを使っているときに困る
のが変数名の置換です。さすがに以下の例のよ
うなプログラムは例としてしか書きませんが、
置換しようとしている変数名と同じ綴りの他の
ものがプログラム中に出てくることはまれにあ
ります。そこで、与えられたソースコードに現
れる変数だけを指定された名前に置換してくだ
さい。
置換対象となるソースコードと使用言語は同じ
ものを使ってください。与えられるソースコー
ドは、完全なコンパイル単位、もしくはパース
して意味が通る範囲のものどちらであってもか
まいません。後者の場合、一番外側の変数だけ
置換できるようにしてください。
C言語での解答例をつけたかったのですが、と
ても難しかったためまだ作成できていません。
ご容赦ください。

例
$ cat a.c
/* a */
int foo()
{
        struct a {int a;} a;
#if FOO
        a.a = 1;
#endif
        { int a; }
	return 0;
}
$ alpha -DFOO=1 b a < a.c
/* a */
int foo()
{
        struct a {int a;} b;
#if FOO
        b.a = 1;
#endif
        { int a; }
	return 0;
}
メソッドのフック (Nested Flatten)

例えば、あるクラスのあるメソッドを実行する前に他の処理を呼びたい(例えばログやトランザクション開始など)。 また、そのメソッドの終了後にも何らかの後処理を呼びたい(トランザクション終了など)。

そのような、メソッドに対するフック処理を書いてください。 ライブラリを使用してメソッドのフックを実現した場合は ライブラリの名前を紹介してくれると助かります。

ポリゴンを表示するプログラム (Nested Flatten)
適当なポリゴンを表示させて、描画するプログラムを書いてください。
ポリゴンは回転させてください。

2D処理だけなら、標準ライブラリで大体いけますが、
3D処理は追加でライブラリを利用すると思うので、
何のライブラリを利用したのか書いてください。
変数の初期値 (Nested Flatten)
WEB+DB 43のRecent Perl Worldを読んで知りました。

変数を初期化するに当たってPerlでは
my $var ||= 'foo';
とかきます。この不備を補うためPerlの5.10には
Defined-or演算子が実装されたそうです。
$zero //= 25;
このような変数のデフォルト設定を行う方法を各種言語ではどうかくのでしょうか。


不動点演算子 (Nested Flatten)

不動点演算子とは、関数を引数に取り、その関数の不動点を返すような関数です。 つまり、不動点演算子である関数gが関数fを引数に取るとき、 f(g(f)) = g(f) となります。

お題は不動点演算子を実装することです。(Yコンビネータを実装しても結構ですが、それ以外でも、コンビネータになっていなくてもOKとします)

ライフゲーム (Nested Flatten)
セルオートマトンに関するお題です. 
2次元タイプの'ライフゲーム'を実装して下さい. 
初期値としては10行10列程度の格子上の平面に0.3程度の人口(?)密度を考え, 
末端はループするようにして下さい. (例: 座標[-1, -1] = [10, 10])

それだけだと簡単すぎると思われる方は, 
過密状態で間引きが発生するような機能を組み込んで下さい. 
間引きは, 少なくともその後の1時間ステップにおける死亡率が, 
それをしなかった場合よりも小さくなれば結構です. 
(死亡率の最小化は複雑性が高すぎる感がありますし. )
サンプル:
t = 0
[ ][*][ ][ ][ ][ ][*][*][*][ ]
[ ][ ][ ][ ][*][ ][ ][*][*][ ]
[ ][ ][ ][*][ ][ ][*][ ][*][ ]
[*][ ][*][*][ ][ ][*][ ][ ][ ]
[ ][*][ ][ ][ ][ ][ ][ ][*][ ]
[*][ ][ ][ ][*][ ][*][*][ ][*]
[ ][*][ ][ ][ ][ ][*][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ][ ][*]
[*][ ][ ][ ][ ][ ][*][ ][ ][*]
[ ][ ][ ][ ][*][*][ ][ ][*][ ]
t = 1
[ ][ ][ ][ ][*][ ][ ][ ][ ][*]
[ ][ ][ ][ ][ ][*][ ][ ][ ][*]
[ ][ ][*][ ][*][*][*][ ][*][*]
[ ][*][ ][*][ ][ ][ ][ ][ ][*]
[ ][ ][*][*][ ][*][*][ ][*][ ]
[ ][*][ ][ ][ ][*][*][ ][*][*]
[ ][ ][ ][ ][ ][*][*][*][*][*]
[ ][ ][ ][ ][ ][ ][ ][ ][ ][*]
[*][ ][ ][ ][ ][*][ ][ ][*][ ]
[*][ ][ ][ ][ ][ ][ ][ ][ ][ ]
必ず解ける迷路 (Nested Flatten)
以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。

1. 格子状の迷路であること。
2. 経路の幅は均等であること。
3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。
   ループも認めません。
4. 出力の度にランダムな迷路であること。
   ランダムシードが同じ時に同じ迷路になってしまうのはよいです。

たとえば、n=4, m=5の迷路の出力は以下のようになります。

 |1|2|3|4|
―■■■■■■■■■
1■   ■   ■
―■■■ ■■■ ■
2■   ■   ■
―■ ■■■ ■ ■
3■     ■ ■
―■ ■■■ ■ ■
4■ ■   ■ ■
―■ ■ ■■■ ■
5■ ■   ■ ■
―■■■■■■■■■

こう言うのは、×の部分が3のルールに違反するのでダメです。
 |1|2|3|4|
―■■■■■■■■■
1■   ■×■ ■
―■■■ ■■■ ■
2■   ■   ■
―■ ■■■ ■ ■
3■     ■ ■
―■ ■■■■■ ■
4■ ■×××■ ■
―■ ■×■■■ ■
5■ ■×××■ ■
―■■■■■■■■■

このようなループも2のルールに違反するのでダメです。
 |1|2|3|4|
―■■■■■■■■■
1■     ■ ■
―■■■ ■ ■ ■
2■   ■   ■
―■ ■■■ ■ ■
3■     ■ ■
―■ ■■■ ■ ■
4■ ■   ■ ■
―■ ■ ■■■ ■
5■     ■ ■
―■■■■■■■■■

できたプログラムを使って n=1024, m=1024 の迷路を作るのにかかった時間を教えてください。


難易度高めです。限られたメモリを使って縦方向に無限に広い迷路を
どうやって作るのかを考えると答えが見えてくると思います。
ソースコードはJavaで150行程度になりました。
西暦 to 和暦 (Nested Flatten)
西暦を和暦に変換するプログラムを書いてください。元号の切り替わる日など、複数の表記が可能な場合には両方表示し、西暦が無効な日付の場合には「範囲外」と表示するようにしてください。対応すべき日付は明治元年以降とします。

>a.py 1868/12/2
明治1年12月2日

>a.py 1926/12/24
大正15年12月24日

>a.py 2007/12/01
平成19年12月1日

>a.py 1926/12/25
大正15年12月25日 昭和1年12月25日

>a.py 1868/1/2
範囲外

>a.py 1868/100/2
範囲外
ポーカーの役判定 (Nested Flatten)

引数に手札を与えると、ポーカーの役を表示するプログラムを作ってください。

条件:

  • スートはS,D,H,C、ランクはA,2~9,T,J,Q,Kのそれぞれ一文字で表します。
  • 手札は S2D5H3CQS9 のように10文字で指定されます。特にソートはされていません。
  • 手札にジョーカーは含まれません。
  • ストレートで取りうるランクの種類はA2345, 23456 ... 9TJQK, TJQKAの10種類で、JQKA2のようにK-A-2をまたぐものはストレートではありません。

実行例:

% ./poker SQSJSASKST
Royal flush

% ./poker D9D7D6D5D8
Straight flush

% ./poker C2D2S2H3H2
Four of a kind

% ./poker C2D3S2H3H2
Full house

% ./poker S9S4S8STSJ
Flush

% ./poker C4H7D5S6H3
Straight

% ./poker S6H6C5DQC6
Three of a kind

% ./poker S6HQC5DQC6
Two pair

% ./poker S6H4C5DQC6
One pair

% ./poker SJSQSKSAC2
No pair
法演算 (Nested Flatten)

ここでいう法演算とは,与えられた数(ここでは「法」と言います)で剰余をとりながら行う計算のことです.たとえば,法が10である場合,以下のように計算します.

  • 足し算
    • 1 + 2 = 3
    • 7 + 3 = 0 (10を10で割った余りは0)
    • 11 + 12 = 1 + 2 = 3
  • 引き算
    • 3 - 2 = 1
    • 2 - 3 = 9
  • 掛け算
    • 2 * 3 = 6
    • 11 * 12 = 1 * 2 = 2
    • 18 * 39 = 8 * 9 = 2

式と法を与えたときに,このような法演算を行い,計算結果を表示するプログラムを作成してください.

注意点

  • プログラムの入力には,式と法が与えられます.
    • 式に現れる数は,整数のみと仮定してかまいません.しかし,法より大きな数が与えられるかもしれませんし,負の数が与えられるかもしれません.
    • 法は2以上の正整数のみが与えられます.
    • 式と法は,プログラムにとって都合のよい形式で与えられると仮定してかまいません.ソースコード中に埋め込んでしまってもかまいません.
  • 足し算,引き算,掛け算に対応してください.
    • 法10の世界においては,1 - 2 と 1 + 8 は同じ意味です.引き算の計算においては,この性質を使い,足し算に変換してから計算してもかまいません.
  • プログラムの出力として,計算結果を表示して下さい.

  • 与えられた式の中に,範囲外の数(負の数や,法の数以上の数)が現れた時には,必ず一度,式全体を正規化し,その結果を表示してから計算を行って下さい.
    • ここでいう「正規化」とは,式の中のすべての項をいったん法で剰余をとり,0以上,法-1以下の範囲になるようにする,ということです
    • 正規化をする際に,引き算を足し算へ変換する処理を一緒に行ってもかまいません.
    • 計算過程で範囲外の数が現れたときには,正規化を行うことが望ましいですが,必ずしも行う必要はありません.(最終的な計算結果が正しければよしとします)
Meertens数 (Nested Flatten)

お題#100「正整数のゲーデル数化?」で定義した goedel を適用すると自分自身になるような数,すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください.

このような数のことをMeertens数と言うそうです.

32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください.また,その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません).

与えられた並べ替えを実現するあみだくじの生成 (Nested Flatten)

お題#4476を見て思いつきました。

0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。

与えられたリストが (3 5 2 4 0 1) の場合、出力の1例を示します:

 0 1 2 3 4 5
 | | |-| |-|
 | |-| |-| |
 |-| |-| | |
 | |-| |-| |
 | | |-| |-|
 | | | |-| |
 3 5 2 4 0 1

一応、制約条件を示しておきます。

  • あみだの横棒は縦棒をまたぐことはできません。常に隣接する縦棒同士の交換となります 。
  • 同じ行に複数の横棒があっても良いですが、ひとつの縦棒の同じ点からふたつ横棒が出ることはありません。

一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。

魔方分割数 (Nested Flatten)
1 .. N^2までの数をN個の数字の和が等しいN個のグループに分けたいと思います。

たとえば、N=3のときは、
(1) { 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 } 
(2) { 1, 6, 8 }, { 2, 4, 9 }, { 3, 5, 7 }
の2通りの方法があります。

ここで指定されたNに対して、何通りのグループ分けの方法があるかを数えるプログラムを作ってください。
(何通りかという値だけが出力されればよいのですが、予め計算してある結果を返すのはダメですよ。)
また、N=5を指定したときの実行時間もあわせて教えてください。

なお、数え上げるときの注意として、

・{ 1, 5, 9 } と { 1, 9, 5 }は同じもの

・{ 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }と
 { 1, 5, 9 }, { 3, 4, 8 }, { 2, 6, 7 }は同じもの
とすることに注意してください。
最大公約数(除算禁止) (Nested Flatten)

あなたが使っている言語で除算と剰余が使えなくなりました。

以下の条件のもと最大公約数を求めるプログラムを書いてください。

条件

  • 除算および剰余の使用禁止
  • 加算や乗算から除算・剰余を単純に定義することも禁止とする
  • ただし, ビットシフトが面倒な場合には引数を2で割った商を返す関数を実装しても構わない
  • 多倍長演算をサポートすること(各言語のライブラリ状況を見たいので)
  • 引数は2つの正整数と仮定して構わない
  • F_1=1, F_2=1のフィボナッチ数列で2000番目と1999番目の最大公約数を求めたときのループ回数を教えてください
小町算 (Nested Flatten)

古典的なパズルである小町算を解くプログラムを作成してください。

小町算とは:

1□2□3□4□5□6□7□8□9=100

四角の中に、空白、+、-、×、÷のいずれかを一つ入れ、等式が成り立つようにするパズルです。

解答例:

1-2-3+4×56÷7+8×9=100

1+234×5÷6-7-89=100

参考: http://ja.wikipedia.org/wiki/%E5%B0%8F%E7%94%BA%E7%AE%97

  • evalやそれに類するものを使うか否かは自由です。
  • 割り算の際には小数点以下の切捨てが起こらないのが望ましいです。(必須ではない)
    • 切捨てが起こる場合の解答例:1÷2÷3+4+5÷6+7+89=100
  • 余裕があれば括弧を含むようにしてもいいかもしれません。

手元で20数行ほどのPythonスクリプトを書いてみたところ、101個の解答が得られました。

あみだくじ (Nested Flatten)
次のような書式で与えられた「あみだくじ」があります。
(あみだくじはコード中に埋め込んでも、標準入力や
外部ファイルから読み込んでも、書きやすい方法でかまいません)

A B C D E
| | |-| |
|-| | |-|
| |-| |-|
|-| |-| |
|-| | | |

このあみだくじをたどって
A B C D E
| | |-| |
|-| | |-|
| |-| |-|
|-| |-| |
|-| | | |
B D C A E
のように結果を表示させるプログラムを作ってください。
文字列の八方向検索 (Nested Flatten)
与えられた矩形状の文字列中に存在する文字列"ウオリ"の位置を全て出力するプログラムを
書いてください。
文字列の検索方向は八方全てで、また連続している(左右や上下の境界をまたがない)ものを
対象とします。出力は起点"ウ"の座標と方向のリストにしてください。

サンプル入力:

リオウウリウ
ウオリウオリ
オリリオリウ
リリオオウオ

サンプル出力:

(2, 0), 左
(0, 1), 右
(0, 1), 下
(3, 1), 右
(4, 3), 左上

--
より一般には、任意の検索文字列への対応も考えてみてください。
自然数の分割(別表現) (Nested Flatten)
正整数の分割といったとき,同じ組み合わせのもの同じ分割とみなし,
0 を除いて降順に並べたものを指すことも多いのではないかと思います.

たとえば,

partitions 1  ⇒ [[1]]
partitions 2  ⇒ [[2],[1,1]]
partitions 3  ⇒ [[3],[2,1],[1,1,1]]
partitions 4  ⇒ [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]
partitions 5  ⇒ [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]
partitions 6  ⇒ [[6],[5,1],[4,2],[3,3],[4,1,1],[3,2,1],[2,2,2],[3,1,1,1]
                 ,[2,2,1,1],[2,1,1,1,1],[1,1,1,1,1,1]]

すなわち,

- 1つの分割は非増加列
- 分割は長さが短いものが先
- 同じ長さの分割では辞書順で大きいものが先

という規則でならべたものです.一つの分割に一つのヤング図形が対応します.
たとえば、5 の分割に対応するヤング図形を列挙すると以下 7 つのようになります.

□□□□□
               
□□□□
□

□□□
□□

□□□
□
□

□□
□□
□

□□
□
□
□

□
□
□
□
□

お題:
正整数を与えられたとき上の意味での分割に対応するヤング図形をすべて
標準出力に印字する関数 young を定義してください.ヤング図形の出力は
上の例のように文字'□'を並べてください.

young 50 の出力をファイルにリダイレクトしたときの処理時間はどの程度
かかったかもCPUスペックとあわせt教えてください.
printfの自作 (Nested Flatten)
printf関数を自作してください。
printfの説明は不要だと思います。とりあえずWikiPediaのリンクをはっておきます。

実際にはsprintf関数を作ってください。
注意事項
  • 標準でついているprintf系関数の使用禁止
  • 標準でついているライブラリ以外の使用禁止
  • 引数・返り値等の仕様はできるだけ似せればよい

可変長引数など、言語によっては難しい/不可能な仕様もありますが、いろいろ工夫して本物に近づくようにしてみてください。
1
2
3
4
5
6
7
#include <string.h>

// なにもフォーマットしてない
int mysprintf(char *str, const char *format, ... ){
    strcpy(str, format);
    return strlen(str);
}
正しい文(クイズ) (Nested Flatten)
「この文は0が□個,1が□個,...,9が□個あります」
が正しくなるように□を埋めてください.数値は10進数とします.
一般のn(<=16で可)進数でも解いてみてください.

たとえば2進数なら
「この文は0が11個,1が100個あります」
となります.
自然数の分割 (Nested Flatten)
自然数nとm(n>=m>0)が与えられたとき,nをm個の非負の整数の和で表すやり方を全て出力してください.
その際,和の組(x_1, ..., x_m)は大きい順に出力してください.
ここでm = 3の時の「(a, b, c)が(A, B, C)より大きい」とは
(a > A)
(a == A) かつ (b > B)
(a == A) かつ (b == B) かつ (c > C)
のいずれかが成り立つとき(つまりは辞書的順序)とします.

例:n = 5, m = 3が与えられたときは
5, 0, 0,
4, 1, 0,
4, 0, 1,
3, 2, 0,
3, 1, 1,
...
0, 1, 4,
0, 0, 5,
を出力する.
文字列の均等分割 (Nested Flatten)
一行の文字列を指定した数の行にできるだけ文字数が均等になるように分割してください.
ただし,除算や剰余算を使わないで書いてみてください.

sample = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく"

divid 4 sample =>
 "ゆめよりもはかなき世のなかを"
 "なげきわびつゝあかしくらすほ"
 "どに四月十よひにもなりぬれ"
 "ば木のしたくらがりもてゆく"

divid 5 sample => 
 "ゆめよりもはかなき世の"
 "なかをなげきわびつゝあ"
 "かしくらすほどに四月十"
 "よひにもなりぬれば木の"
 "したくらがりもてゆく"

divid 6 sample => 
 "ゆめよりもはかなき"
 "世のなかをなげきわ"
 "びつゝあかしくらす"
 "ほどに四月十よひに"
 "もなりぬれば木のし"
 "たくらがりもてゆく"
文字列リストをTRIE Optimizeされた正規表現に (Nested Flatten)

これは、実例を見た方が簡単だと思います。 CPANにRegexp::Assembleというモジュールがあるのですが、要はこれの簡易版を作って欲しいということです。私自身、同様のことを行うモジュールを過去にいくつか作っています(e.g Regexp::Optimizer)。

ここでは、文字列のリストを受け取って、それをTRIE化した正規表現に出来ればOKです。Regexp::AssembleやRegexp::Optimizerは正規表現を受け取ってそれをTrie化することも可能ですし、Perl 5.10では内部的にTrie Optimizationを行ったりするのですが、そこまでの機能は求めません。

なお、ここで言う「正規表現」は、必ずしもPerl互換のものである必要はありません。それがTrieになっていることをきちんと示せればOKです。

とはいうものの、Perl5互換になっていた方が、サポートしている環境が多くて有用性は高そうです。可能であればそうして下さい。

Dan the Regexp Assembler

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#!/usr/local/bin/perl
use strict;
use warnings;
use Regexp::Assemble;

my $ra = Regexp::Assemble->new;
while(<>){
    chomp;
    next unless $_;
    $ra->add($_);
}
print $ra->re, "\n"
__END__

% grep program /usr/share/dict/words 
program
programist
programistic
programma
programmar
programmatic
programmatically
programmatist
programmer

% grep program /usr/share/dict/words | perl sample.pl 
(?-xism:program(?:m(?:a(?:ti(?:c(?:ally)?|st)|r)?|er)|ist(?:ic)?)?)
BFコンパイラー (Nested Flatten)

「どう書く?」でまだ出ていないのが不思議なお題。それがBF処理系。 ここでは、BFで書かれたソースを、同じ言語に変換するコンパイラーを募集します。

私自身、すでにPerlとJavaScriptに関しては http://blog.livedoor.jp/dankogai/archives/50545151.html でやっているのですが、他の言語バージョンも是非見たいので。

Dan the Brainf.ucker

四字熟語パズルの作成 (Nested Flatten)

与えられた四字熟語のリストから下のように四角く配置することのできる熟語の組み合わせを探すプログラムを作成してください。

出力例:

無憂無風
礼  林
千  火
万水千山

知行合一
者  筆
不  勾
言語道断

四字熟語は左から右、上から下へ読むものとします。また右上隅の漢字と左下隅の漢字は異なるものでなければいけません。

四字熟語のデータは扱いやすい形(たとえばユニコード文字列のリスト)で与えられていると仮定して構いません。サンプルデータが必要であれば FOR Microsoft IME The四字熟語辞典(データ / 文書作成) にテキスト形式のデータが入っているのでそれを使えると思います。

問題の規模の参考までに、40行程度のPythonスクリプトでこのデータ(重複をのぞいて8312件)を処理してみたところ2.4GHzのCPUで13秒程度かかりました。結果は8133件出力されました。

水の移し替えパズル (Nested Flatten)

A, B, Cの容器があり,それぞれ水が4L, 2L, 10L入っている. ここで次の操作を繰り返す.

(*)「A, B, Cのどれか二つの容器から水を1Lずつくみ上げ,残りの容器に移す.」

たとえばA, Bから1Lずつくみ上げて移せばA=3L, B=1L, C=12Lとなる. くみ上げる前の容器には必ず水が入っているとする.

(*)を繰り返してどれか一つの容器にのみ水がはいっている状態にする最小手数を求めよ.

可能ならA=827392L,B=65536L,C=122880Lのときも求めよ.


このお題は光成さんの投稿を元に作成しました。ご協力ありがとうございます。

文字列の反転(括弧の対応を保存) (Nested Flatten)
与えられた文字列を前後反転する関数 reverseString2 を書いてください。
ただし、reverseString2 は単純に文字列を反転するのではなく、括弧の対応
を保存するようにしてください。

以前のお題で作成した単純に与えられた文字列を単純に前後反転したもの返す
reverseString では

  reverseString("文字列(もじれつ)の反転(はんてん)") 
    → ")んてんは(転反の)つれじも(列字文"

のように括弧の対応は保存されませんが、reverseString2 では

  reverseString2("文字列(もじれつ)の反転(はんてん)")
    → "(んてんは)転反の(つれじも)列字文"

のように括弧の対応が保存されます。
括弧文字は、'('と')'、'{'と'}'、'['と']'で、それぞれASCII文字と仮定し
てください。

  reverseString2("対応[の{とれている(さまざまな)括弧}の(例)]です。")
    → "。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対"

入力文字列では対応の取れている括弧の内側には対応の取れない括弧文字はな
いと解釈してください。たとえば、

  reverseString2("これ(は(対応のとれていない)括弧がある例です。")
    → "。すで例るあが弧括(いないてれとの応対)は(れこ"

次のような場合は対応のとれている括弧はないという解釈になります。

  reverseString2("これ(も{対応の)とれていない}括弧の例です")
    → "。すで例の弧括}いないてれと)の応対{も(れこ"

日本語対応にする場合の文字のエンコーディングは実装側で都合のよいように
仮定してください。日本語対応であることは望ましいですが、必須ではありま
せん。 

---
このお題はnobsunさんに投稿いただきました。ご協力ありがとうございます。
続・ファイル内の重複行削除 (Nested Flatten)

ファイル内の重複行削除(後優先) 」の続編です。

1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。

このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、 スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。

しかし、与えられたファイルが運悪く「一致する部分のないファイル」である可能性を考えてみましょう。たとえ1行ずつ読んで処理をしたとしても、「重複するかどうかの判定」のために前の行をまるごとメモリに取っておいたのでは、最終的にファイルを丸ごとメモリに乗せることになってしまいます。

こういうデータが入力されうる状況の場合にどう書くか、というお題です。前回のお題の条件3「ファイル全体を一度にメモリに読み込んで処理しないこと」を「たとえすべての行が異なるようなデータであっても、メモリの消費量をファイルサイズのおよそ10%程度に抑えること」と読み替えてください。

追記:「メモリの10倍」はさすがに条件として厳しすぎました。「ファイルのサイズは4ギガバイト未満であり、メモリの消費量をファイルサイズの半分以下に抑えること」と読み替えてください。半分以下に抑えられているのならば題意は満たすものとします。もちろん、頑張ってもっと少ないメモリで動くようにするのもアリです。

ファイル内の重複行削除(後優先) (Nested Flatten)
アレイのuniq」の応用編です。

入力されたテキストデータから重複する行をとりのぞいて、その結果を標準出力へ出力するプログラムを作成してください。

重複行の排除については、以下の仕様を満たしてください。

  1. 読み込み順序は変更しないこと
  2. 重複する行があった場合、以前のデータを削除すること (後に読み込んだ方が強い)
  3. ファイル全体を一度にメモリに読み込んで処理しないこと
  4. 比較は行全体で行うこと

#4.はおまけですがある/なしで作りが変わってくると思われるので追加しました。


この問題はraynstardさんにご投稿いただきました。ご協力ありがとうございます。 ところで、素朴な実装のしかたをするとメモリ容量の数倍のサイズのすべての行が異なっているファイルを読ませたときに大変なことが起こりそうな気がしますが、そういうシビアなお題設定ではないので素朴に解いてしまって構いません。シビアなのは続編にしたいと思います。
格子点の列挙 (Nested Flatten)
二次元平面上の格子点(X,Y座標がともに整数の点)を、原点から近い順に列挙してください。

同じ距離の点はどういう順番でも構いませんが、可能であればX軸に一番近い第一象限の点から原点を中心として反時計回りの順に列挙してください。 列挙の方法は、1行に一つの点の、X,Y座標を出力することとします。

サンプル出力

0, 0
1, 0
0, 1
-1, 0
0, -1
1, 1
-1, 1
1, -1
-1, -1
2, 0

最低でも1000件まで列挙できることを確認してください。 また「反時計回り」の条件も満たしている場合は、1000番目の頂点が何かも併せて答えてください。

このお題はかもさんの投稿を元にしています。ご協力ありがとうございました。

制限時間内のキー入力検査 (Nested Flatten)
ユーザーの入力を検査する関数 InputCheckerを作成して 3回連続実行してください。

関数 InputCheckerは、以下の仕様を満たしてください。

  1. 引数に 時間(秒) Nと文字列 Sを受け取ること。
  2. ユーザからの標準入力とあらかじめ指定された S を比較し、 一致すれば「OK」、一致しなければ「NG」を標準出力へ出力すること。
  3. ユーザーの入力がN秒以内に完了しなかった場合は、比較せず 「TIME OUT」を標準出力へ出力すること。
  4. 経過時間はユーザーが入力を開始した地点から計測すること。
  5. ENTER キーの入力によってユーザー入力が完了したと仮定すること。
  6. ユーザの入力が完了するまでは、完了を待ち続けること

たとえば、「InputCheker(5, "ABCDEF")」と指定した場合、 出力例はこんな感じです。

  1. input(ABCDEF) =>ABCDEF<ENTER>
    1. result => OK
    2. result => NG
    3. result => TIME OUT

1. input(ABCDEF) =>

と出力して入力待ちをし、ユーザーが「ABCDEF<ENTER>」を入力したとき、 入力開始から5秒以内ならば「OK」、5秒をこえていれば「TIME OUT」を出力します。 このとき、ユーザーがキーを押下しなければ1. を出力してから たとえ10秒たっていても「TIME OUT」にはならないので注意してください。 時間計測はあくまでユーザーが入力を開始してからです。


このお題はraynstardさんの投稿です。ご協力ありがとうございます。
ソートするコードの生成 (Nested Flatten)
Meta-Loopless Sortsの改題です.

n個の整数をソートするプログラムを生成するプログラム gensort を 書いて下さい.条件は以下のとおり

  1. 生成するプログラム,生成されたプログラムは同じ言語にして下さい.
  2. 生成したプログラムはファイルに書き込んでください.
  3. 生成されたプログラムでは最初に n 個の整数を読み込んで, n個の変数を初期化してください.「可能なら」変数名は,アルファベット 一文字で a,b,c ... の順で使ってください.n = 5 なら 変数は a, b, c, d, e です.
  4. 生成されたプログラムでは,if 文あるいは if 式で2つの変数を比較して いって,変数の順が確定したら,その順で変数の値を出力するようにして 下さい.
  5. 生成される側のプログラムでのアルゴリズムやデータ構造を工夫する問題では ありません :)

gensort 3 で生成した Pascal のプログラム例は以下のとおりです.

program sort(input,output);
var
a,b,c : integer;
begin
  readln(a,b,c);
  if a < b then
    if b < c then
      writeln(a,b,c)
    else if a < c then
      writeln(a,c,b)
    else
      writeln(c,a,b)
  else
    if a < c then
      writeln(b,a,c)
    else if b < c then
      writeln(b,c,a)
    else
      writeln(c,b,a)
end.

n の値を 2 〜 10 くらいまで変化させて以下の処理時間を測定してください.

1. gensort n の処理
2. 生成したプログラムの処理
   2-1. コンパイル言語の場合は,コンパイル時間と実行時間
   2-2. インタプリタ言語の場合,可能ならロード時間と実行時間を別測定,
        分解できないなら実行時間
ごさっしのとおり,出力されたプログラムは n の値で急激に大きくなります. n が大きいと gensort n で文法的に正しいプログラムは生成できてもコンパ イル や実行ができないということもありえると思います.処理系ごとの限界がわか ると面白いのではないかと思います.オリジナルの問題は Pascal のプログラム コードを生成するプログラムを書けという問題でしたが,生成する側とされる側 の言語を同じにするほうが面白いですよね.
この問題はnobsunさんからの投稿です。ご投稿ありがとうございました。助かります。
exp(pi * sqrt(n))が整数に近くなるnを探す (Nested Flatten)
1以上200未満の整数nのうち、 exp(pi * sqrt(n))がほとんど整数であるようなnを求めるコードを書いてください。 なお、expは底がeである指数関数 - Wikipedia、 piは円周率、sqrtは平方根です。また「ほとんど整数である」とは 整数からプラスマイナス0.0001の範囲にあることとします。

Pythonで34行のスクリプトを書いて得られた出力の例が下のようになります。

37 199148647.999978
58 24591257752.000000
67 147197952743.999999
163 262537412640768744.000000 
この問題は光成さんに教えて頂いた e^{π*sqrt{163}}≒26253741640768744 が元になっています。ご協力ありがとうございました。
音声合成でHello, world! (Nested Flatten)
与えられた文字列を音声合成して再生する関数を作ってください。

使用したライブラリはタグでつけてください。またOSに依存する場合もタグでつけてください。日本語文字列も発音できることが好ましいですが、必須ではありません。

以下はサンプルです。

>>> say("Hello, world!")
>>> say("con nitch were") # 「こんにちは」
>>> say("daw cat coo org, sole what program mar know tum yen know Colosseum death")
改行をBRタグに置き換える (Nested Flatten)
一部のHTMLタグを通すフィルタ どう書く?の続編です。 前回の条件を満たしつつ、入力中の改行を<br/>に置き換えてください。ただし、たとえば"<a\nhref=...>"といったようにタグの中に改行がある場合、単純に置換するわけには行かないことに注意してください。

また、ユーザの入力注の<br>は<br/>に変換してください。

このお題はperezvonさんの提案を元にした三部作の二問目です。ご協力ありがとうございました。

一部のHTMLタグを通すフィルタ (Nested Flatten)
ユーザが入力した文字列から、一部のタグだけを許可して他をエスケープするコードを書いてください。要件は次のようになります。
  • 通すタグはAとBRとSTRONGのみ。大文字小文字は区別しない。
  • それ以外のタグとして意味を持ちうる文字列は<を&lt;に変換することで無効化する(削除するのではない。>は変換してもしなくてもよい)
  • Aタグのhrefとname以外の属性は削除する。BRやSTRONGの属性はすべて削除する。

このお題はperezvonさんの提案を元にしています。ありがとうございました。 ただ、いきなりだと難しいかと思ったので、肝の部分以外を先に出題しました。このお題は続編で徐々に難しくなっていきます。

追記:属性に<や>が含まれてしまうケースに漏れのある解答が多いようなのでテストケースを追加します。
これは「この出力なら十分」という意味です。この出力の通りでなければいけないという意味ではありません。

<script foo="<script>alert('bar')</script>">alert('foo')</script>
&lt;script foo="&lt;script&gt;alert('bar')&lt;/script&gt;"&gt;alert('foo')&lt;/script&gt;


<script foo="<a href='link'>link</a>">alert('foo')</script>
&lt;script foo="&lt;a href='link'&gt;link&lt;/a&gt;"&gt;alert('foo')&lt;/script&gt;

<a href='www.g>oogle.com'>link</a>

<a href="./www.g%3Eoogle.com">link</a>
文字列からの情報抽出 (Nested Flatten)
与えられた文字列から特定の条件を満たす文字列を抽出するコードを書いてください。 状況としてはテキスト形式で渡された原稿の中から、画像のファイル名を抽出するようなものをイメージしてください。

サンプル入力

aaa abc-hidden.png>hoge-big.jpeg
---foo-hidden-small.gif|^_^a.bmp
--hiddena-hoge.png<=not hidden~~
--small.jpg<=not small(^_^)
normal-small-big.hoge

サンプル出力

name:'abc', ext:'png', size: normal hidden: True
name:'hoge', ext:'jpeg', size: big hidden: False
name:'foo', ext:'gif', size: small hidden: True
name:'a', ext:'bmp', size: normal hidden: False
name:'hoge', ext:'png', size: normal hidden: False
name:'small', ext:'jpg', size: normal hidden: False
name:'small', ext:'hoge', size: big hidden: False

探すべき文字列は下の条件を満たします

  • アルファベットと1個のピリオド、ハイフンで構成される
  • 前後にはアルファベットではない文字がある(abcd.jpgがaaaabcd.jpghogeなどと書かれていることはない)
  • ピリオドの後ろは拡張子で、アルファベットだけで構成されている
  • ピリオドの直前に-hidden, -small, -bigがある場合には特殊な意味がある。複数個ある場合(a-hidden-big.jpgなど)も同じ
  • ファイル名に-hiddenと-smallまたは-hiddenと-bigの両方が含まれる場合は-hiddenの方が先にある
  • 特殊な意味の-hidden, -small, -big以外でハイフンが使われることはない
  • 特殊な意味の-smallと-bigの両方が付くことはない

出力は以下の条件を満たす必要があります

  • ファイル名が出現した順に表示される
  • ファイル名に-hiddenが含まれるかどうかを真偽値で表示する
  • ファイル名に-smallまたは-bigが含まれる場合はsmallまたはbigと、含まれない場合はnormalと表示する
  • -hidden, -small, -bigを取り除いたファイル名部分と、拡張子を表示する

このお題は、正規表現のグループに名前をつけて連想配列として取得できるPythonからの挑戦状です。

PageRankの計算 (Nested Flatten)
ページランク - Wikipediaを求めるプログラムを作ってください。(PageRankはGoogleの商標です)

詳しい導出方法はGoogle の秘密 - PageRank 徹底解説の3章に載っていますが、 簡単に説明すると

  1. ページがn枚ある場合、n×nの2次元配列を用意する。
  2. ページiからページjにリンクがある場合、mat[j][i] = 1 / num_link[i]とする。ただしnum_link[i]はi番目のページから出ているリンクの総数。
  3. 行列計算ライブラリを使ってできあがった2次元配列の固有値、固有ベクトルを求める。
  4. 出力された固有ベクトルから合計が1になるようなPageRankを算出する

という流れになります。

Pythonで表現すると下のようになります。 ?????の部分は空行を入れて10行でしたので 何百行ものコードになってしまった場合は きっとお題の趣旨から外れていると思います。 このお題の趣旨は「行列計算ライブラリを使って」PageRankを計算することなので、 自力で固有値の計算を実装することは求められていません。

data = {
    1: [2, 3, 4, 5, 7],
    2: [1],
    3: [1, 2],
    4: [2, 3, 5],
    5: [1, 3, 4, 6],
    6: [1, 5],
    7: [5],
}

?????

print pagerank
# [0.303514376997, 0.166134185304, 0.140575079872,
#  0.105431309904, 0.178913738019, 0.0447284345048,
#  0.0607028753994]
このお題はところてんさんの「行列演算系のお題が欲しい」という要望を元に考えたものです。ありがとうございました。
全ての組み合わせ (Nested Flatten)
2個以上のリストlist1, list2, list3...が与えられたときに、 その複数個のリストの中の要素を一つずつとりだして組にする方法の全通りのリストを返すコードを書いてください。

Pythonで表現すると下のようになります。

>>> c = CrossProduct([1,2,3,4], "abc")
>>> list(c.all())
[[1, 'a'], [1, 'b'], [1, 'c'], [2, 'a'],
 [2, 'b'], [2, 'c'], [3, 'a'], [3, 'b'],
 [3, 'c'], [4, 'a'], [4, 'b'], [4, 'c']]

>>> c = CrossProduct([0, 1], "ab", ["Foo", "Bar"])
>>> list(c.all())
[[0, 'a', 'Foo'], [0, 'a', 'Bar'], [0, 'b', 'Foo'], [0, 'b', 'Bar']
 [1, 'a', 'Foo'], [1, 'a', 'Bar'], [1, 'b', 'Foo'], [1, 'b', 'Bar']]
順番はこの通りでなくても構いません。返すものはリストと書きましたが、 なんらかの「一度に全部をメモリ上に作成しないリスト状のモノ」がある言語ではそちらを使う方がおすすめです。 数値や文字列を一つのリストに混在させるのがやっかいな言語では整数のリストに限定しても構いません。

このお題はZIGOROuさんとのやりとりにヒントを得て作りました。 (しまった、先にブログで公開されてしまった→Yet Another Hackadelic - 直積の導出と考えうる全ての値を網羅したハッシュの生成)

追記:サンプル出力が間違っていたのでoceanさんの解答を使って出力し直しました。

与えた条件を満たす候補 (Nested Flatten)
['and', 'or', 'not', 'and']
のような入力が与えられた場合に、
式 x1 and x2 or not x3 and x4 の値が
Trueとなるような、x1~x4の組み合わせを全て
出力するプログラムを作成してください。
x1~x4には真と偽の2通りの値だけが入るものとします。

Pythonであれば上の入力に対し、
(True, True, True, True)
(True, True, False, True)
(True, False, False, True)
(False, True, False, True)
(False, False, False, True)
と出力します。

andとorの優先順位は同じで左結合性、
つまりa and b or c and dは
(((a and b) or c) and d)
という順番で評価されるものとします。

参考:
d.y.d.

キミならどう書く2.0の小町算問題と似てますが。
このお題はmorchinさんの投稿をもとに作成しました。 ご投稿ありがとうございました。
元ネタの 充足可能性問題 - Wikipedia は、 同じリテラル(x1とかnot x2とか)が複数回出てくることを想定しているので、 今回の問題のようにそれぞれ別の変数でだと乗法標準形 - Wikipediaにした場合に、答えが…と色々悩みどころでした。
JPEGをGETして色反転して保存 (Nested Flatten)
ネットからのデータ取得(これはすでにありましたが…)および画像データの取り扱いに関係したライブラリの理解をとう問題として次のようなものはいかがでしょう。 

『ネットで公開されている JPEG ファイルを取得し、色反転して保存するスクリプトを記述せよ。』 

もちろん例によって Squeak Smalltalk からの挑戦状でもあります。

このお題はsumimさんからの投稿です。ご投稿ありがとうございます。 画像の処理という切り口も面白いですね。

整数の漢数字表記 (Nested Flatten)
キーボードから正の整数を入力すると、それを漢数字で表示するプログラムを作ってください☆ 例えば「1732050807568877」なら「千七百三十二兆 五百八億 七百五十六万 八千八百七十七」といった感じです☆ 「一七三二兆 〇五〇八億 〇七五六万 八八七七」ではダメですよ^^;

このお題は匿名での投稿です。 与えられる整数の範囲は一京未満(10000000000000000未満)としたいと思います。 ご投稿ありがとうございます。

2年前のLL Day&Nightの「キミならどう書く」で、 これ専用のCPANモジュールが作られていたような記憶があるので 勝手にPerlからの挑戦状とみなしておきます(笑)

モノクロ画像の類似検索 (Nested Flatten)
1024 * 768のサイズのモノクロ二値画像が100枚あるとします。 その中の一枚を指定したときに、その画像以外で一番その画像に似ている画像を見つけるコードを書いてください。 なお、同じ位置のピクセルが同じ値であるほど「似ている」とします。

説明のために2*3のサイズで説明します。

画像1
■■■
■■■

画像2
□□□
□□□

画像3
■■■
□□□

指定された画像
■■■
■□□
この場合、画像1とは4つのピクセルが同じ値なので類似度は4、 画像2との類似度は2、画像3とは上半分の3つと下半分の白2つが一致するので類似度は5、よって一番類似しているのは画像3となります。

このお題の趣旨は検索処理の実行速度にあるので、 実行してみて実用的な速度で動くことを確認することを強く推奨します。 可能であればマシンのスペックと実行にかかった時間を書いてもらえると参考になっておもしろいと思います。

なおこのお題はC言語からスクリプト言語への挑戦状です。 スクリプト言語に有利な問題が多すぎるので、この手の問題も大募集します。

ローカル変数の一覧を取得 (Nested Flatten)
リフレクション系のお題の続編です。 ローカル変数の内容を取得して連想配列(ハッシュ、辞書など)に詰める コードを書いてください。

Pythonで表現すると、下のコードの???部分を埋めることになります。

>>> def foo():
	x = 1
	y = "hello"
	???
	return result

>>> foo()
{'y': 'hello', 'x': 1}
トランプの和と積のパズル (Nested Flatten)
ここにトランプが一組あります.
司会者がそこから二枚抜いて,その積をAさんに,その和をBさんに教えました.

#トランプにジョーカーはなく、1~13までの数字が書かれたカードであると考えて構いません.
#たとえば,二枚のトランプの数字が2と5なら,Aさんには10,Bさんには7を教えます.
#二つの数は同じかもしれません.

司会者がAさん,Bさんに二つの数字が分かるかと質問しました.
Aさん「(この情報だけでは)分かりません」
Bさん「私も分かりません.ただ,Aさんが『分かりません』というのは分かっていました」
それを聞いたAさん「それなら,分かりました」
それを聞いたBさん「それなら,私も分かりました」
元の二つの数はなんだったのでしょうか.
この「2つの数」を求めるプログラムを作ってください。解が複数個ある場合はすべて求めてください。 このお題は光成さんの投稿が元になっています。ご投稿ありがとうございます。
RFC 4180対応版 CSVレコードの分解 (Nested Flatten)
ある関数(splitCSV)に渡された文字列を配列に分解して列ごとに表示してください。
渡される文字列は、CSVデータの1レコードが設定されているとします。

使用するデータはK3形式が元になっている仕様で
エクセルが出力しているような形式です。

書式には次のような特徴があります。
1. 各レコードは「改行」によって区切られている。
2. 各列は「,」によって区切られている。
3. 列のデータは「"」によって囲んでも良い。
4. 列に「,」「改行」「"」いずれかを含む場合「"」で
   囲わなければならない。
5. 列データに「"」を含める場合「""」とする。

本来、改行コードはCRLFですが今回は特に指定しません。

次の入力があった場合
"aaa","b
bb","ccc",zzz,"y""Y""y",xxx

出力は
1 => aaa
2 => b
bb
3 => ccc
4 => zzz
5 => y"Y"y
6 => xxx

となります。
このお題はraynstardさんの投稿によるものです。ご投稿ありがとうございます。助かります。
Tiny MML (Nested Flatten)
文字列の入力をとり、音を鳴らすプログラムを作ってください。

入力はcがド、dがレ、eがミ、fがファ、gがソ、aがラ、bがシ、rが休符とします。この8文字以外の文字は入力に含まれていないと仮定して構いません。おのおのの音符・休符は八分音符・八分休符とします。

オクターブや音の長さの変更、同時発音などの機能は不要です。

サンプル入力(カエルの歌)

cdefedcrefgagfercrcrcrcrcdefedcr
マップの通り抜け (Nested Flatten)
ここにピリオド(.)とプラス(+)と改行で構成された入力ファイルがあります。

ピリオドは通れないマス、プラスは通れるマスを表現しています。 上から下へたどり着く道があるかどうかを判定するコードを書いてください。

通り抜けられる例

.+.....
.+.+++.
.+.+.+.
.+++.+.
.....+.
通り抜けられない例
..+...+
++.+++.
.+...++
++++.+.
.+..+.+
呼んだのは誰? (Nested Flatten)
自身を呼び出した関数(メソッド)の名前を返す関数(メソッド)を書いてください。

Ruby で表現すると、 以下のような「fooという関数を呼び出す関数」#bar、#bazがあるとき

def bar; foo end
def baz; foo end
このbar, bazの返り値が以下のようになるような関数fooを定義してください。
bar  #=> "bar"
baz  #=> "baz"

このお題は匿名の「Smalltalk からの挑戦状」を元に作成しました。 確かにこの手のリフレクションの機能が言語によってどう違うのかは興味深いところです。 リフレクションを使う問題をいくつか考えてみたいと思います。 ご投稿ありがとうございました。

日本語メールのエンコード (Nested Flatten)
UTF-8で書かれたテンプレートに,任意の文字列を差し込んだ文書を,ISO-2022-JPのテキストメール形式にエンコードしてください. Dateヘッダ,Message-IDヘッダなどはプログラム側で適切に追加するものとします.

----テンプレート----

From: [[from]]
To: [[to]]
Subject: [[name]]さんにメッセージが届いています

[[name]]さんに[[fromname]]さんからメッセージが届いています。
以下のURLからアクセスできます。
[[url]]
----テンプレート----

----差し込みデータ----

from => 'from@example.org',
to => 'to@example.org',
name => 'どう書く',
fromname => '管理者',
url => 'http://ja.doukaku.org/',
----差し込みデータ----

----出力----

From: from@example.org
To: to@example.org
Subject: =?ISO-2022-JP?B?GyRCJEkkJj1xJC8kNSRzJEslYSVDJTshPCU4JCxGTyQkJEYkJCReJDkbKEI=?=
Date: Fri, 13 Jul 2007 22:27:32 +0900
Message-ID: <0.1184333252.27836.123@example.org>
MIME-Version: 1.0
Content-Type: text/plain; charset="ISO-2022-JP"
Content-Transfer-Encoding: 7bit

どう書くさんに管理者さんからメッセージが届いています。
以下のURLからアクセスできます。
http://ja.doukaku.org/
----出力----

※実際の上記出力の日本語部分の文字コードはISO-2022-JPです.

差し込みタグの形式は[[名称]]でなくてもかまいません.

言語標準以外のライブラリを使った場合,それをタグに書いてください.

このお題は沢渡みかげさんの投稿を元にHTMLタグなどを付加したものです。 サンプル入出力までそろった投稿で非常に助かりました。ありがとうございます。

追記:補足があったのでこちらもご覧ください。 出題の意図(埋もれないように)

長方形の交差判定 (Nested Flatten)
ここに二つの長方形があります。左上隅のx座標、y座標、右下隅のx座標、y座標をそれぞれleft, top, right, bottomとします。また、おのおのの長方形についてleft < right, top < bottom が成り立つものとします。

この二つの長方形が重なっているかどうかを判定するコードを書いてください。なお辺で接する場合(例えば(0, 0, 100, 100)と(100, 0, 200, 100))は重なっていないものとします。

なお変数名に関して、例えば1番目の長方形の左上隅x座標がleft[0]なのかleft1なのか、それともrect1.leftなのかは自由に選んで構いません。

逆順になるあみだくじ (Nested Flatten)
nを2以上の整数とします。 上と下で順番が完全に逆転するような縦線がn本のあみだくじを書くプログラムを作ってください。

たとえばnが3の場合は下のように出力してください。

0 1 2
|_| |
| |_|
|_| |
| | |
2 1 0
nはプログラムを書き換えずに指定できるようにしてください。

このお題はoceanさんの投稿を元に作成しました。ご投稿ありがとうございます。

/*コメント*/を取り除く (Nested Flatten)
与えられた文字列から「/*」と「*/」で挟まれた部分を取り除くコードを書いてください。

なお、「/*」と入力末尾で挟まれた部分も取り除いてください。 つまり、入力が「AAA/*BBB」なら出力は「AAA」です。 また、コメントは入れ子になりません。入力が「AAA/*BBB/*CCC*/DDD*/EEE」のとき、ひとつめの「*/」でコメントが終わるので出力は「AAADDD*/EEE」になります。 「//」や「**」が混ざる場合の挙動は失敗しやすいので要注意です。

Pythonでの実行例は下のようになります:

>>> remove_comment('AAA')
'AAA'
>>> remove_comment('AAA/*BBB*/')
'AAA'
>>> remove_comment('AAA/*BBB')
'AAA'
>>> remove_comment('AAA/*BBB*/CCC')
'AAACCC'
>>> remove_comment('AAA/*BBB/*CCC*/DDD*/EEE')
'AAADDD*/EEE'
>>> remove_comment('AAA/a//*BB*B**/CCC')
'AAA/a/CCC'

このお題は匿名での投稿を参考にして作成しました。 ありがとうございます。

分数を小数に展開 (Nested Flatten)
整数a, bを受け取り,分数a/bを小数に展開した文字列を返す関数/メソッドを作成してください。結果が循環小数になる場合は,循環部を{}でくくってください。例:
a=3, b=8 → 0.375
a=3, b=14 → 0.2{142857}

与えられる整数a, bは次の条件を満たすものと仮定して構いません。 1 ≦ a < b ≦ 2147483647。なお2147483647は2^31-1です。

このお題はtnkさんの投稿を元に作成しました。ご投稿ありがとうございます。

コインを減らす払い方 (Nested Flatten)
いま、あなたの財布の中にはコインがたくさん入っています。これを少しでも減らしたいと思います。

支払うべき金額と持っているコインの種類と数を与えられたときに、どのコインを何枚出せばおつりを受け取った後のコインの数が最も少なくなるか返す関数を作ってください。おつりは最も枚数が少なくなる方法で渡されます。

例えば、1円玉2枚、10円玉4枚、100円玉3枚を持っていて、147円支払う場合、 1円玉2枚と100円玉2枚を渡して50円玉1枚と5円玉1枚を受け取るのが2枚減で最も枚数を減らせます。Pythonで表現するならば下のような挙動をする関数を作ってください。

>>> pay(147, {1: 2, 10: 4, 100: 3})
{1: 2, 100: 2}
2007-07-01追記:  minkeさんの指摘通り、「手元にある全てのコインを渡せば、結果としてもっとも枚数が少なくなる」 ので、「渡した硬貨がおつりで返ってくるような渡し方は禁止」と条件を追加します。

Index

Feed

Other

Link

Pathtraq

loading...