Language detail: dc - 's unsolved challenges
間違ってトピックにも同じものを投稿しました。投稿はこちらにお願いします。 住所のように任意の深さの階層性をなすキーとそれに対応したオブジェクトを ['東京都', '区部', '千代田区', object1] のように配列で表すとします。このような配列からなる配列 [['東京都', '区部', '千代田区', object1], ['東京都', '区部', '中央区', object2], ['東京都', '区部', '港区', object3], [東京都', '多摩地域', '支部', '昭島市', object4], ['東京都', '多摩地域', '支部', 'あきる野市', object5], ['東京都', '多摩地域', '西多摩郡', '奥多摩町', object6], ['東京都', '島嶼部', '大島支庁', '大島町', object7], ['東京都', '島嶼部', '三宅支庁', '三宅村', object8]] を階層的な連想配列に変換して下さい。可能なら、各連想配列をキーにしたがって並べてください。 もっとよいデータがあれば、それを使ってください。
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 | #!/usr/bin/ruby1.9.1 -Ku
class Array
def hashtree
sort_by {|a| a.first}
.each_with_object({}) do |a, h|
if a.length > 2
h[a.first] ||= []
h[a.first].push(a[1..-1])
else
h[a.first] = a[1]
end
end
.each_with_object({}) do |(k, v), h|
h[k] = v.instance_of?(Array)? v.hashtree : v
end
end
end
require 'pp'
pp [%w(東京都 区部 千代田区 object1),
%w(東京都 区部 中央区 object2),
%w(東京都 区部 港区 object3),
%w(東京都 多摩地域 支部 昭島市 object4),
%w(東京都 多摩地域 支部 あきる野市 object5),
%w(東京都 多摩地域 西多摩郡 奥多摩町 object6),
%w(東京都 島嶼部 大島支庁 大島町 object7),
%w(東京都 島嶼部 三宅支庁 三宅村 object8)].hashtree
# =>
{"東京都"=>
{"区部"=>{"中央区"=>"object2", "千代田区"=>"object1", "港区"=>"object3"},
"多摩地域"=>
{"支部"=>{"あきる野市"=>"object5", "昭島市"=>"object4"},
"西多摩郡"=>{"奥多摩町"=>"object6"}},
"島嶼部"=>{"三宅支庁"=>{"三宅村"=>"object8"}, "大島支庁"=>{"大島町"=>"object7"}}}}
|
以下の積み木のうち4つを、
重複を含めてランダムに選びます。
このとき、それらを4×4の箱に
詰められるかどうかを判定してください。
1.
■■■■
2.
■■
■■
3.
■■■
■
4.
■■■
■
5.
■■
■■
例えば、{ 1, 1, 1, 1 }, { 2, 2, 2, 2 } は箱につめることができますが、
{ 1, 2, 2, 3 } は箱につめることができません。
余力のある方は、以下の値を求めてみてください。
・箱につめることができる積み木の組み合わせの総数
・上記総数を、異なる詰め方の個数別にカウント
（箱の回転・裏返しで一致するものは同一視します）
イントロスペクションおよびメトリックスのお題です。
アジャイル界隈などでは、あまり長くだらだらと書いてはいけない…と言われている 関数 and/or メソッド ですが、ならば実際のところ、洗練された既存のライブラリにおいて、関数 and/or メソッド は平均すると何行くらいで記述されているのか…といった情報を具体的に把握しておきたいと思ったことはありませんか？
そこで、みなさんイチオシの言語それ自身で書かれているライブラリを、それなりの規模になるように集めてきて、1)集めたライブラリ群内に定義されている全 関数 and/or メソッド の合計数（母集団の確認のため）、と 2)関数 or メソッドのソースの平均の行数、を求めるコードと、その結果を示してください。
なお、関数 and/or メソッドに帰属するものであれば、コメント行やアノテーションのたぐいも行数のカウントに含めてください（コードが必要以上に複雑にならない範囲で結構です）。また、関数内関数定義やメソッド内クラス定義（ひいてはその中でのメソッド定義）といった入れ子になったコードの行数をどう解釈するかの判断はお任せします。関数とメソッドが共存する言語では両者を区別してカウントする必要はありません（しても構いません）。平均値を求めるコードを、対象言語で記述することが技術的に困難な場合は、UNIX的なツールを組み合わせたり、IDEなどが提供するメトリックス機能を活用して算出した結果を示すのでもよいと思います。
このお題は、平均行数が 8.4 行（Squeak Smalltalk の組み込みライブラリ＋αより、調査メソッド総数 4万）と、一般に簡潔さが美徳とされている Smalltalk からの挑戦(?)でもあります。
コレクションフレームワークに則ってコレクションクラスを実装して下さい．
具体的にどのようなコレクションを実装しても構いませんが，コレクションフレームワークで用意された基本的なメソッドは一通り呼べるようにして下さい． foreach系の構文があれば，それでも使えるとよいです．
例えば，Rubyであれば以下のようなコードで(mapを直接定義することなく)要素を列挙できる必要があるでしょう．
1 2 3 4 5 6 | p MyCollection.new.map {|i| i }
# for でも使える
for i in MyCollection.new
p i
end
|
並行処理のお題です。ある床屋の亭主は、客がいないときまって居眠りを始めます。床屋店内には三台の散髪兼順番待ち用の椅子があり、客は来店時に椅子に空きがあれば、いずれかに勝手に座って自分の番が来るのを待ち、散髪を終えてから店を出ます。空席が無ければそのまま何もせずに立ち去ります。居眠り中の亭主は、客の入店時に起こされると待ち客すべてをひとりずつ順に散髪しますが、誰もいなくなればまた居眠りを始めます。
この床屋店に16人の客が訪れた日のシミュレーションを行なうコードと、その結果（下に例として示したログ形式。「[スレッドのIDなど] イベント描写」の一覧と終了後の総括）を出力して示してください。なお、散髪には一人当たり100～400ミリ秒の時間（この範囲でランダムに変化）を要し、客は通常 0～200ミリ秒（同）の間隔で訪れます。ただし例外として9番目の客だけは前の客から1200ミリ秒程度の間隔（すなわち、最大三名の待ち客全員を散髪し終えるのに十分な時間）をあけて訪れるものとします。
実装に際し、実行時のデッドロックの回避はもちろんですが、そのほかにも、競合状態（席の空きを確認して座ろうとしたら、もう別の客が座っていた…というような事態）などの不整合も生じないよう配慮し、必要であればそのための対策を講じてください。たとえば来客の間隔が仮に０ミリ秒で固定の場合（つまり、客が一斉に来店した場合）でも、コードが正常に動作するかどうか試してみるのもよいかもしれません。
出力例：
[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人を散髪
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
正攻法からトリッキーな手段まで、いろいろお待ちしております。
see: 通信用語の基礎知識 UTF-8
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);
}
|
Twitter(http://twitter.com/)につぶやきを投稿してください。 APIに関しては http://watcher.moe-nifty.com/memo/2007/04/twitter_api.html に日本語訳があるようです。 「update」に投稿の仕様が説明されています。
一番長くしりとりを続けるためのプログラムを書いてください。
また、単語数に対して、計算量がどのように増えていくかも考えて下さい。
なお、単語リストの一例として
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/index-j.htmlで公開されている
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/fam55_40.txtがあります。
ただし、
・一度使った単語は使わないこと(リストに重複がある可能性は考えなくてよい)
・「ん」で終わる単語を使用するか、リスト内にしりとりを続けられる単語がなくなったときに、しりとりは終了する
・一番最初は、好きな単語から初めてもよい
・「一番長くしりとりを続ける」とは、しりとりが終了するまでに使用する単語数が最大になるよう、しりとりの単語を選ぶことをいう
see: 難聴者のための単語了解度試験用単語リスト
- 黒いマスにアリがいた場合、90°右に方向転換し、そのマスの色を反転させ、1マス前進する。
- 白いマスにアリがいた場合、90°左に方向転換し、そのマスの色を反転させ、1マス前進する。
詳しくはWikipedia等で調べるか、参考ページに拙作のデモがありますのでご覧下さい。
see: JavaScriptでラングトンの蟻
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 & refresh" onclick="location.reload();"></p>
<div id="canvas"></div>
|
20:18の場合，例えば以下の様な出力をするイメージです。
出力例:
■□■□□
□■□□■□
see: Binary Clock Widget
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
|
初期設定を読み書きするプログラムを書いてください。
保存先や形式は問いませんが，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();
}
}
}
|
リソースを使うときのパターンloanのサンプルを書いて下さい。 参考 Programming in Scala (P.170 , P.172)
- "255.255.255.0" から 24
- "255.255.255.128" から 25
- "255.255.255.255" から 32
などのようにネットマスクの数値への変換を作ってみてください。
出来れば逆変換も作ってみてください。
標準入力を読み込んで、行選択のUIをだし、選択されたものだけを標準出力にだしてください。 標準出力に出力するタイミングは選択終了をユーザーが報告したときです。(完了ボタンを想定してください)
UIライブラリは何をつかってもかまいません。 例えばncursesのようなコンソール上でのUIでもかまいませんし、GtkのようなGUIライブラリでもかまいません。
想定される使い方としては、以下のような感じです。
ps aux | handgrep | xargs kill -9
プロセスの一覧を表示、UI上で選択したものをkill
ストレンジアトラクタの描画をしてください。 ストレンジアトラクタの種類は問いません。 簡単に出力できる言語はその言語の出力機能を使ってもらってかまいません。 また、出力が難しい言語はgnuplotなどのグラフ出力ソフトを使って出力してください。 解答の際はどのタイプのストレンジアトラクタなのかを添えてください。
１６進数を１０進数に変換してください。
ただし、入出力は文字列とし、次の変換は最低必ずできなければいけないこととします。
- 0x12437308CCB6 →20080902065334
2.0x2C9C1227FC6520B →200904012311450123
あわせて、扱える最大の整数も明らかにしてください。
与えた文章の各単語の最初と最後の文字以外の文字を入れ替えた文章を出力する処理を実装して下さい。元の文章の与え方は特に問いません。
see: 確かに"読めてしまう"コピペ
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
|
1. 加算 ( 3 + i ) + ( 4 - i )
2. 減算 ( 5 - 9i ) - ( 2 + 6i )
3. 乗算 ( 5 + 3i ) * ( 5 + 8i )
4. 除算 ( 9 - 7i ) / ( 9 - 3i )
5. 絶対値 | 2 + 3i |
複素数計算を行う関数やクラスを定義して答えを求めること。
ライブラリがある場合はそれを利用してかまいません。
see: Wikipedia：複素数
（ナベアツ算を見てて思いつきました）
入出力の方法は標準入出力や引数・戻り値など、扱いやすい方法でかまいません。
文字単位でランダムに間違えても面白くないので、単語のリストから似た単語の候補を探すようにしてください。英単語でもＯＫです。単語のリストは参考ページからダウンロードしたものを加工して利用すると良いと思います。（４０００個あります）
結果がつまらなくても構いませんが、面白いボケをうむ工夫があると良いです。
※人が考えたボケは求めてませんよ！
入力の例として「どう書く？org」の前文をお借りしました。ご自分でヤホーで調べたりして手ごろな文章を見つけて下しあ。
see: 日本語単語リスト
1 2 3 4 5 6 7 8 9 10 11 12 13 | ＜入力例＞
ドウカク org ヘ ヨウコソ
コノ サイト ハ ダサレタ オダイ ヲ イカニ トクカ キソイアウ
プログラマ ノ タメノ コロシアム デス
トウコウ ヲ タメシテ ミタイ カタ ハ テスト
トリアエズ ナガメテ ミタイ カタ ハ ゲンゴ ノ イチラン ガ オススメ デス
＜出力例＞
ドウモク org ヘ ヨウコソ
コノ ザレゴト ハ ダサレタ オダイ ヲ イワハダ トシシタ キソイアウ
プログラマ ノ タチノミ コロシアム デス
トウコウ ヲ ハナシテ ミチノリ カタ ハ プリント
トリアエズ ナガメテ ミツリン カタ ハ ゲンゴ ノ キンラン ガ オススメ デス
|
手牌を表すのは、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 考えられる刻子のパターン:
刻子を手牌から抜く
手牌が順子の和となっていれば、和了形として抜ける
刻子を手牌へ戻す
対子を手牌へ戻す
ここに到達していれば、和了形ではない
|
与えられた文字列を指定されたバイト数以下に分割する関数
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")
|
「3の倍数と3がつく数字の時だけアホになる」コードを実装して下さい。
また、余裕のあるかたは更に、
「8の倍数のときに人探しをしてる感じに」「5の倍数のときにナルシストに」なるよう実装して下さい。
いわゆる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)
|
コピー元フォルダ、コピー先フォルダ、ファイル名(複数)を指定し、
コピー元フォルダ(配下含む)から、指定したファイル名のファイルを探し出し、
コピー先フォルダにツリーごとコピーする処理を実装して下さい。
[実装に際して]
・複数ファイル名を指定できればどのような形式でも構いません。
(例: コマンド引数, 外部ファイル)
・指定したファイル名が複数見つかった場合、すべてコピー対象として下さい。
・コピー先に既にファイルやフォルダが存在する場合、削除して下さい。
(コピー先が指定したファイルのみとなるようにする)
・コピー先フォルダが存在しない場合、新規作成して下さい。
[余裕のある方は]
・除外するファイル名、フォルダ名を指定できるようにして下さい。
・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
===============================
余裕があれば、土日祝日を休日として、終了日を後ろにずらした表示にすると良いですね。
開始日 日数
１．2009/1/10 21日間 (＃) ←わかり易いように記号を付けています
２．2009/1/15 6日間 (＠)
３．2009/1/10 8日間 (＊)
４．2009/1/16 1日間 (＝)
５．2009/1/16 3日間 (％)
６．2009/1/30 4日間 (＝)
結果例：
％
％
％
＝
＊
＊
＊
＊
＊
＊
＠
＠ ％
＠ ＠
＠ ＠
＃ ＃ ＝
＃ ＃ ＝
＃ ＃ ＃
＊ ＃ ＃ ＃
＊ ＃ ＃ ＃
＃ ＃ ＃ ＃
＃ ＃ ＃ ＃
1/1 1/5 1/12 1/19 1/26
ルール：
・下から上に向かって積み上げて下さい
・結果の表示は、記号でなくても、テキストでなくても構いませんが個々の予定が判別出来るようにして下さい
・表示範囲は１ヶ月(1/1～1/31)とします
表示範囲からはみ出した分は無視します
・１週間は月曜から日曜までとします
・予定は１日単位とします
このお題は、以前仕事で作った機能のほんの一部を抜き出して単純化してみました。
プロジェクト管理等でよくあるグラフですね。
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
この短縮を行う関数を作ってください。
余力のある方は逆変換（伸長）も考えてみてください。
この程度ならライブラリに備わってるかも？？
see: Wikipedia：IPv6
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
|
エレベータを制御して、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]
麻雀ゲームの部分的な作成がお題になります. 以下のメソッド/関数を組み込んで下さい.
- n人のプレーヤでゲームをする機能; n = 2--4.
- 牌をかき混ぜてから山を作成する機能.
- 手牌を理牌する機能.
- 山から牌を取る操作.
- 手配を切る操作 (ツモ切りで構いません).
- 河を保存する機能.
- 3--5を繰り返す機能.
ルールとしては,
- 配牌は親は14枚, 子は13枚.
- 親から順に手牌を切る.
- 自分の手番で始めにツモり, その後手牌を切る.
- 手牌の数は最大14枚.
- 山の牌が残り14枚になったら終了.
- 牌全体としては, (3人プレーヤでも) 日本で通常用いられている34種類136枚を使用.
と考えていただければ結構です.
鳴き, あがり, 自風, 場風などは考慮していただかなくて結構です.
改行文字を複数個含むテキストデータを格納する文字列を 最大長の行を除く各行末に指定したパディング文字を適切な数だけ追加して、 すべての行が最大長の行と同じ長さに揃う文字列に変換する 手続あるいは関数を書いてください。 元の文字列の最後は改行です。 行の長さはその行に含まれる（行末の改行を除く）文字の数です。 変換前の文字列例 "○○○○\n○○○○○○○\n\n○○○○○\n" 上の文字列例をパディング文字'☆'を指定して変換した文字列 "○○○○☆☆☆\n○○○○○○○\n☆☆☆☆☆☆☆\n○○○○○☆☆\n" 必須ではありませんが、 テキストデータをトラバースする回数を減らす工夫をすると面白いかもしれません。
(1) このときPからQまでいくのに何通りの経路があるか数えてください。ただし遠回りはせずかならずQに近づく方向に進む(右方向か下方向にだけ進む)とします。
(2) (1)と条件は同じで、図.2のように経路の一部がない(通れない)場合に、PからQまでいくのに何通りの経路があるか数えてください。
P-+-+-+ P-+-+-+
| | | | | | | |
+-+-+-+ +-+-+-+
| | | | | | |
+-+-+-+ +-+-+ +
| | | | | | | |
+-+-+-+ +-+ +-+
| | | | | | | |
+-+-+-Q +-+-+-Q
図.1 図.2
経路の表現の仕方、記憶の仕方は自由とします。上記のようなキャラクタでの表現でもよいですし、最初からプログラムで扱いやすいデータとして持っていてもOKです。入力も外部からの入力でもよいですし、プログラム中にコーディングされていてもOKです。
※問題は、野﨑昭弘「離散数学『数え上げ理論』」(講談社 ブルーバックス)「第3章 道順を数える」から拝借させて頂きました。
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
m×nの長方形のマス目のうちいくつかを黒く塗りつぶします。 このとき、白の島、黒の島がそれぞれいくつあるかをカウントしてください。 ただし、2つのマスは、同色マスの上下左右の移動で移れるとき、 同じ島にあると定義します。 例： □■■□ □□■□ □■□□ □■■□ 白の島は2つ 黒の島は2つ 例： □□□□ ■□■□ □■□□ □□□□ 白の島は1つ 黒の島は3つ
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
|
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
数値（たとえば1から10）と、アルファベット（たとえばAからJまで）を順に出力する別々のループ処理を並行に実行させ、共通の出力先に出力する極力シンプルなコードを書いてください。
念のため、実行後、出力先に数値とアルファベットが混ざって出力されている（たとえば、数値がすべて出力されてからアルファベットが続く…というふうになっていない）ことを確認してください。混ざってさえいれば、それぞれ１文字ずつ交互である必要はありませんし、もちろん交互でも構いません。
出力先や出力方法は自由です。標準出力、テキストファイル、コンテナオブジェクト（配列、リスト、コレクション）など使いやすいもので構いません。
例として Squeak Smalltalk でのコードと結果を示します。シンプルなコードなので Smalltalk に馴染みがない人も、おおよその内容は掴めると思います。
1 2 3 4 5 6 7 | | out |
out := OrderedCollection new.
[(1 to: 10) do: [:each | out add: each. Processor yield]] fork.
[($A to: $J) do: [:each | out add: each. Processor yield]] forkAndWait.
^out asArray "=> #(1 $A 2 $B 3 $C 4 $D 5 $E 6 $F 7 $G 8 $H 9 $I 10 $J) "
|
入力の'('と')'の対応をとってください。
ただし、コード中に'('と')'を含まないでください。
漢字の九九に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
|
タブ区切りのデータを読み込んで操作をし書き出す方法を教えてください。 読み込み・書き出しの方法は任意とします。
与えられるデータは:
- レコードの区切りは改行、カラムの区切りはタブです。
- 最初のレコードはヘッダで、カラムの名前が書いてあります。
- それ以降はデータで、第1,4カラムは整数値、第2,3カラムは文字列値です。
この入力データに対して以下の操作をしたものを書き出してください:
- 第1カラムの値でデータを昇順にソートする。
- 第2カラムと第3カラムをヘッダを含めて入れ替える。
- 第4カラムの値にそれぞれ1を加える。
入力の例:
ID Surname Forename Age 1 Sato Hanako 17 0 Suzuki Taro 18 ...
出力の例:
ID Forename Surname Age 0 Taro Suzuki 19 1 Hanako Sato 18 ...
LL Golf Hole 9のリリースをアナウンスしているエントリにトラックバックを打ってください(トラックバックURL)。マシンガンのようには打たないでください。ただし、このエントリにはスパムフィルタが搭載されているため、寄せることはできてもカップインできないかもしれません。その場合はtakano32が用意させていただきました打ちっ放し場にてガンガン試し打ちください(トラックバックURL)。
余力のあるものは感想を公式ブログの感想エントリにトラックバックくしてください。 余力がなくても感想をトラックバックしてくれるとスタッフがよろこびます。
see: トラックバック技術仕様書
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
|
2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 i, j, k は 0 以上の整数です。アルゴリズムのオーダーについても考えてみてください。
例えば最初の 10 個は次のようになります:
1 = 2^0 * 3^0 * 5^0 2 = 2^1 * 3^0 * 5^0 3 = 2^0 * 3^1 * 5^0 4 = 2^2 * 3^0 * 5^0 5 = 2^0 * 3^0 * 5^1 6 = 2^1 * 3^1 * 5^0 8 = 2^3 * 3^0 * 5^0 9 = 2^0 * 3^2 * 5^0 10 = 2^1 * 3^0 * 5^1 12 = 2^2 * 3^1 * 5^0
※解答では i, j, k の各値を示す必要はありません。
いわゆる、コマンドライン引数の取得(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秒となる日時を出力する関数 DateEx() を作成してください。
関数の仕様は次の通りです。
1. 入力となる日時の書式は任意である。
→ プログラムの都合に合わせてよい。
2. 入力となる時間(秒)は、負の値も許容すること。
また、負の値が指定された場合、指定の日時よりも前の日時を出力すること
3. 出力する日時は入力の日時と同じ書式をとる文字列であること
4. 出力する日時は正規化されていること
5. 出力先は標準出力、または、バッファのいずれでもよい。
たとえば、DateEx("20080827235925",40)ならば
出力は
「20080828000005」です。
余力があれば時間を省略可能とし、
省略された場合は「現在時刻」を利用するようにしてみてください。
与えられた自然数 n について、横向きで n 段のピラミッドを作ってください。 たとえば、 n に 4 が与えられた場合は以下のようなピラミッドを作ります。
4
*
**
***
****
***
**
*
与える自然数についてはリテラルで与える、標準入力で与える、引数で与えるなどは自由とします。
余力のあるものはこのプログラムを短くしてください。
※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、チケットは現在も発売中のほか、当日券もございます。よろしければ、メインイベントの方にもぜひご参加ください。
see: ピラミッドを作る どう書く？org
1 | n=gets.to_i*2;n.times{|i|puts"*"*(i<n/2 ?i:n-i)}
|
与えられたバイト数を読みやすくしてください。読みやすくとは、いわゆる human readable な表記とします（詳しくはサンプルのコードを参考にしてください）。
与えるバイト数についてはリテラルで与える、標準入力で与える、引数で与えるなどは自由とします。
余力のあるものはこのプログラムを短くしてください。
※ LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。
1 2 3 4 5 6 7 8 9 10 11 12 | b = gets.to_i
if b < 10**3
puts b
elsif b < 10**6
puts "%.1fk" % (b.to_f/10**3)
elsif b < 10**9
puts "%.1fM" % (b.to_f/10**6)
elsif b < 10**12
puts "%.1fG" % (b.to_f/10**9)
else
puts "%.1fT" % (b.to_f/10**12)
end
|
与えられた10進数の整数を2進数に変換してください。ただし、与えられる整数は0以上とします。
与える整数についてはリテラルで与える、標準入力で与える、引数で与えるなどは自由とします。
余力のあるものはこのプログラムを短くしてみたり、さまざまな基数への変換に対応させてみてください。
※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。
see: Integer - Rubyリファレンスマニュアル
1 2 | # 標準入力から整数を受け取る
ruby -e 'puts gets.to_i.to_s(2)'
|
与えられた自然数までの数え上げを行います。ただし、繰り上がりが起こったときは最上位の桁のみを数え上げます。また、与えられる自然数には0以外の桁が2回以上登場してはいけません。たとえば、300を入力として与えられた場合は以下のような出力となります。
0
1
2
3
4
5
6
7
8
9
10
20
30
40
50
60
70
80
90
100
200
300
与える自然数についてはリテラルで与える、標準入力で与える、引数で与えるなどは自由とします。
※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。
1 2 3 4 5 6 | #!/usr/bin/env ruby
def f(n, m = 0)
puts m
n == m ? return : f(n, m + 10 ** (m.to_s.size - 1) )
end
f(300)
|
TCPのechoクライアントを書いてください。
- サーバのホスト名ないしIPアドレス、およびポートはコマンドライン引数で指定します。
- 標準入力からユーザの入力を受け取り、echoサーバに送信します。
- echoサーバから受信したデータを標準出力に出力します。
Windowsなら、Simple TCP/IP Servicesを起動してやれば、ローカルの確認用echo サーバとして使えます。
my_program localhost 7 < input_file > result_file
のようにしてリダイレクトを行った場合にも、result_fileがinput_fileの内容と一致するようにしてみてください。
GNU GENERAL PUBLIC LICENSE Version 3に登場する単語について、単語が登場する行を示した索引を作成してください。
与えられる文章についてはリテラルで表記する、標準入力で与えられる、引数でファイル名が与えられるなどは自由とします。
余力のあるものはこのプログラムを短くしてみたり、短くしてみたり、短くしてください。
※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。
see: open-uri - Rubyリファレンスマニュアル
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
|
今日から2013年12月31日までの、13日の金曜日とその総数を表示してください。
余力のあるものはこのプログラムを短くしてみたり、短くしてみたり、短くしてください。
※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。
see: DateTime - Rubyリファレンスマニュアル
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #!/usr/bin/env ruby
require 'date'
from = DateTime.now
to = DateTime.parse("2013-12-31")
friday = (from..to).inject(0) do |friday, date|
if date.mday == 13 and date.wday == 5 then
puts date.strftime('%Y-%m-%d')
friday + 1
else
friday
end
end
puts friday
|
文字列に含まれる単語について、それぞれの単語の最初の文字を大文字にしてください。
たとえば、"LL future" と与えられたときは "LL Future" と出力する。"LL day and night" と与えられたときは "LL Day And Night" と出力する。
与えられる文字列はリテラルで表記する、標準入力で与えられる、引数で与えられるなどは自由とします。
余力のあるものはこのプログラムを短くしてみたり、短くしてみたり、短くしてください。
※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。
see: LL Golf
1 | ruby -e "p 'LL day and night'.scan(/(\w)(\w*)/).map{|a|a.shift.upcase + a.to_s}.join(' ')"
|
'tail'を実装してください。
巨大なファイルでも効率的に動作するようにしてください。
最低限必要な機能は、
- 行数指定
- 「-f」パラメータの対応
です。
２次元ランダムウォークをつくってみてください。
＊＊＊＊＊＊
元は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
分からないというヒトへの分かりにくいヒント：
今の位置から次の時間の位置が決まるのですが、決まりかたが、乱数で一歩後退するか一歩先にいくか?ということをやればよいです。
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のチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。
see: tinyurl.comでURLを短縮するRubyスクリプト
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
|
スペースやインデントなど、本来は必要なく開発効率を上げるために記述が許可されている項目について、 それらを可能な限り減らし、コードを短くするコード書いてください。 また、投稿時に対象とする言語と、実際の処理結果を記載できるとわかり易いかと思います。 以下詳細 ・全てを行う必要はありません、どこまで行うかは任意です。 ・ローカル宣言など、消しても動作に関係のない構文の削除や置き換えを行っても構いません。 ・必ず同じ入力に同じ結果が返るのであれば処理内容を変えることもかまいませんが、推奨・強制はしません。 ・コンパイラや実行環境に依存する圧縮は避けてください。
ソート対象のデータ同士で一切比較などを行わずにソートし、ソート結果を出力するプログラムを作成してください。条件は以下の通り。 ・最低値・最大値・個数・並び替え対象の4つを引数として受け取る ・最大値と最低値はあくまで取りうる可能性であり、実際に出現することを保障するものではない。 ・同値が複数出現することがある。 ・入出力方法及びフォーマットは自由、関数として実装し引数に渡す形でも良い。 ・小数点以下の数値が渡されることはないが、負の数は渡される可能性がある。 ・最大値や最低値を元に算出した数値との比較は使用しても問題ありません。 ・出来るだけ多様な条件のデータをソートできるアルゴリズムを使ってください(データが多少多いときや一定の並び順だとソート失敗するものはダメ) ・昇順降順はどちらでもかまいません 以下サンプル入出力 >>入力 -1 10 10 -1 9 4 8 9 6 3 9 5 2 >>出力 -1 2 3 4 5 6 8 9 9 9
設定ファイルのイメージも載せてください。
ここで設定ファイルとは、
・項目名と値のペアが書いてあるファイル
・フォーマットはその言語で扱いやすいものでよい
・コードと分離され、コードに影響を与えずに変更が可能
を条件とします。ファイルが難しければ同等のものでもかまいません（テーブル、環境変数など）。
例）
----
ファイル：ShowPrice.ini
ITEM_NAME=りんご
ITEM_COST=200
> showPrice()
「りんご」は210円（税込み）
----
ITEM_NAME=みかん
ITEM_COST=100
> showPrice()
「みかん」は105円（税込み）
YYYY年mm月dd日HH時MM分SS.xxx秒なら、「YYYYmmddHHMMSS.xxx」のようにミリ秒まで含んだ文字列を返すプログラムを書いてください。
プログラムコード中の文字の頻度は言語によって相当にばらつきがあると思います。ある言語はピリオドが頻出するとか、別の言語はカッコの頻出頻度が高い、とか。そこで、
- 文字の頻度解析をするプログラムを作成し、
- 適当なプログラムに対して実行し、結果を出力して、そのような頻度になっている理由を教えてください。
(その言語で書かれた「典型的な」プログラムコード、といえるようなものがあると良いのですが・・）
簡単すぎるという方は、複数文字にしてみたり単語の頻度にしてみてください。
参考；Wikipedia 頻度分析
http://ja.wikipedia.org/wiki/%E9%A0%BB%E5%BA%A6%E5%88%86%E6%9E%90
整数nを与えると 範囲lowからhigh内での位置を返すmodular関数を作ってください。
(
low <high かつ n=0のとき low を返す
n = 1 のとき low + 1 を返す。
n = high － lowのときhighを返す。
n = high － low + 1 のときlowを返す。
（循環 ： 例＊ を参考にしてください）
n = high － low + 2 のときlow+1を返す。
n = 整数 * （high － low） + 1 のときlowを返す。
n = 整数 * （high － low） のときhighを返す。
n = 整数 * （high － low） + 2 のときlow+1を返す。
....循環の繰り返し
)
例
modular(n,low,high) -> 出力
modular(0,100,200) -> 100
modular(50,100,200) -> 150
modular(100,100,200) -> 200
＊例
modular(101,100,200) -> 100
modular(-1,100,200) -> 200
modular(1,-5,200) -> -4
modular(-500,-5,-1) -> -5
ランダムな文字からMETHINKS IT IS A WEASELを作るプログラムを作れ。
簡単に流れを書いてみます。
１：ランダムな２０文字を持つ文字列をもった３００個作ります。
２：その文字列が"METHINKSITISAWEASEL"に近いものからソートします。
３：それぞれの文字列のなか1文字を別の文字に変化させたものを３つ用意します。
４：それを２：のソートをして上位３００個残す。（９００個あるうちで上位３００個残すということです。）
５：以後３：と４：を繰り返す。
ランダムな文字変化は大文字だけでいいです。簡単にするために空白文字を外してあります。
METHINKS IT IS WEASELができたら終了。３と4の間でソートしたもので一番上位のものを毎回表示させると変化が楽しめます。:-)
Rickard Dawkinsがブラインドウォッチメイカー(現題：盲目の時計職人）の３章で書いていた有名なものです。さらに一般化してもらってもいいです。
参考
標準入力から与えられたソースコードの変数名
を置換するプログラムを作ってください。
最近はリファクタリングツールなどの普及でこ
のような需要は少ないかと思われますが、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;
}
固定長のデータが記載されたファイルを読み込むプログラムを作成してください。読み込んだデータは、複数の値を格納できるデータ型に格納してください。
ファイルには、すべて ascii 文字で以下のデータが格納されています。デリミタはなく、固定長で格納されています。レコードとレコードのあいだも改行はありません。
- 姓 (12文字) 文字数が足りない場合は、後ろを空白で埋めてあります。
- 名 (12文字) 文字数が足りない場合は、後ろを空白で埋めてあります。
- 性別 (F,M,Uの3種類、1文字)
- 年齢 (3桁の数字、桁数が足りない場合は、ゼロで埋めず、頭を空白で埋めてあります。
- 年 2008 固定
- 月 03 固定
- さらに以下のデータが日付分くりかえされます。
- 日付 (01 〜 31) 2文字
- 朝食のメニュー (500文字)
- 昼食のメニュー (500文字)
- 夕食のメニュー (500文字)
以上の形式のデータ500人分を読みこんで、データを複数の値を格納できるデータ型に格納してください。データに大して何か処理を行う必要はなく、すぐに破棄してかまいません。
この問題は、このようなファイルをどのように扱うかを知りたくて作成しました。
WEB+DB 43のRecent Perl Worldを読んで知りました。 変数を初期化するに当たってPerlでは my $var ||= 'foo'; とかきます。この不備を補うためPerlの5.10には Defined-or演算子が実装されたそうです。 $zero //= 25; このような変数のデフォルト設定を行う方法を各種言語ではどうかくのでしょうか。
(x, y) の座標情報を以下の2種類の方法で整列する機能を実現してください。
- (x, y) の辞書順(まず x で昇順に整列して、x が同じデータに対して y で昇順に整列する)
- (0, 0) からの距離の昇順
データの表現方法はタプルなり構造体/オブジェクトなり各自で適当に選んで下さい。
予め言語内に用意されている場合は、(1)一般的な使用法と、(2)より進んだ使用方法を提示して下さい。
'ABCDEF'と'abcdef'等すべて対応する文字を書く必要があるものを、(1)基本版、'A-Z'と'a-z'のように"-"で範囲を指定できるものを(2)拡張版、2を更に発展させたものを(3)発展版とします。任意のものを選んで解答して下さい。
実行例. (与えられた文字列が、"typewriter"の場合)
tr 'qwertyuiop' 'QWERTYUIOP' "typewriter"
=> TYPEWRITER
1 2 3 4 5 6 7 8 | ;; 基本版/Arc
(def tr (orig subst str)
(tostring
(each c str
(pr (aif (pos c orig) (subst it) c)))))
(tr "qwertyuiop" "QWERTYUIOP" "typewriter")
;=>"TYPEWRITER"
|
セルオートマトンに関するお題です. 2次元タイプの'ライフゲーム'を実装して下さい. 初期値としては10行10列程度の格子上の平面に0.3程度の人口(?)密度を考え, 末端はループするようにして下さい. (例: 座標[-1, -1] = [10, 10]) それだけだと簡単すぎると思われる方は, 過密状態で間引きが発生するような機能を組み込んで下さい. 間引きは, 少なくともその後の1時間ステップにおける死亡率が, それをしなかった場合よりも小さくなれば結構です. (死亡率の最小化は複雑性が高すぎる感がありますし. ) サンプル: t = 0 [ ][*][ ][ ][ ][ ][*][*][*][ ] [ ][ ][ ][ ][*][ ][ ][*][*][ ] [ ][ ][ ][*][ ][ ][*][ ][*][ ] [*][ ][*][*][ ][ ][*][ ][ ][ ] [ ][*][ ][ ][ ][ ][ ][ ][*][ ] [*][ ][ ][ ][*][ ][*][*][ ][*] [ ][*][ ][ ][ ][ ][*][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][*] [*][ ][ ][ ][ ][ ][*][ ][ ][*] [ ][ ][ ][ ][*][*][ ][ ][*][ ] t = 1 [ ][ ][ ][ ][*][ ][ ][ ][ ][*] [ ][ ][ ][ ][ ][*][ ][ ][ ][*] [ ][ ][*][ ][*][*][*][ ][*][*] [ ][*][ ][*][ ][ ][ ][ ][ ][*] [ ][ ][*][*][ ][*][*][ ][*][ ] [ ][*][ ][ ][ ][*][*][ ][*][*] [ ][ ][ ][ ][ ][*][*][*][*][*] [ ][ ][ ][ ][ ][ ][ ][ ][ ][*] [*][ ][ ][ ][ ][*][ ][ ][*][ ] [*][ ][ ][ ][ ][ ][ ][ ][ ][ ]
see: Wikipedia:ライフゲーム
see: Wikipedia 閏年
以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。 1. 格子状の迷路であること。 2. 経路の幅は均等であること。 3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。 ループも認めません。 4. 出力の度にランダムな迷路であること。 ランダムシードが同じ時に同じ迷路になってしまうのはよいです。 たとえば、n=4, m=5の迷路の出力は以下のようになります。 ｜１｜２｜３｜４｜ ―■■■■■■■■■ １■ ■ ■ ―■■■ ■■■ ■ ２■ ■ ■ ―■ ■■■ ■ ■ ３■ ■ ■ ―■ ■■■ ■ ■ ４■ ■ ■ ■ ―■ ■ ■■■ ■ ５■ ■ ■ ■ ―■■■■■■■■■ こう言うのは、×の部分が3のルールに違反するのでダメです。 ｜１｜２｜３｜４｜ ―■■■■■■■■■ １■ ■×■ ■ ―■■■ ■■■ ■ ２■ ■ ■ ―■ ■■■ ■ ■ ３■ ■ ■ ―■ ■■■■■ ■ ４■ ■×××■ ■ ―■ ■×■■■ ■ ５■ ■×××■ ■ ―■■■■■■■■■ このようなループも2のルールに違反するのでダメです。 ｜１｜２｜３｜４｜ ―■■■■■■■■■ １■ ■ ■ ―■■■ ■ ■ ■ ２■ ■ ■ ―■ ■■■ ■ ■ ３■ ■ ■ ―■ ■■■ ■ ■ ４■ ■ ■ ■ ―■ ■ ■■■ ■ ５■ ■ ■ ―■■■■■■■■■ できたプログラムを使って n=1024, m=1024 の迷路を作るのにかかった時間を教えてください。 難易度高めです。限られたメモリを使って縦方向に無限に広い迷路を どうやって作るのかを考えると答えが見えてくると思います。 ソースコードはJavaで150行程度になりました。
引数に手札を与えると、ポーカーの役を表示するプログラムを作ってください。
条件：
- スートは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
see: ポーカー - Wikipedia
任意の数nを与えたときに ・nが偶数ならば2で割る (n=n/2) ・nが奇数ならば3倍して1を足す （n = 3*n+1) を繰り返すと、いづれは1になる。というものがあります。 数値計算の上ではかなりの数まで成り立つことが知られています。 （すべての数について成り立つかは不明） 参考リンク先参照 ある任意の数nがコラッツ・角谷の問題で1になるまでのステップ数をf(n)とします。 1～2^20までの数でf(n)を求めて、f(n)が最大になるときのnとf(n)を表示してください。 たとえばn=9だと次のような数列をたどって、19ステップで1になります。 9->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1 つまりf(9)=19です。 また、最大を求めた際の実行時間と環境を書いてください。
see: コラッツの問題の成り立つ範囲
nを入力としてn年の年間カレンダーを返すプログラムを作ってください
少なくとも日曜日と土曜日が判別出来るようにしてください
出力は標準出力でもファイルでも構いません
デザインは各自のお好みで
出力例1:
(y-calendar 2008)=>
#=Saturday, @=Sunday
2008/1 1 2 3 4 #5 @6 7 ...
2008/2 1 #2 @3 4 5 6 7 ...
...
2008/12 1 2 3 4 5 #6 @7 ...
出力例2:
(y-calendar 2008)=>
M T W T F S S M
2008/ 1 1 2 3 4 5 6 7 ...
2008/ 2 1 2 3 4 ...
...
2008/12 1 2 3 4 5 6 7 8 ...
出力例3:
(y-calendar 2008)は2008.htmlを出力する
2008.htmlの中身
----
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
"http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>2008 calendar</title>
<style type="text/css">
* {font-family: monospace;}
span {margin: 0px 3px;}
span.sunday {color:red;font-weight:bold;}
span.saturday {color:blue;font-weight:bold;}
dd ul li{display:inline;}
</style>
</head>
<body>
<h1>2008 calendar</h1>
<dl>
<dt>2008/1</dt>
<dd><ul>
<li><span class="weekday">1</span></li>
<li><span class="weekday">2</span></li>
<li><span class="weekday">3</span></li>
<li><span class="weekday">4</span></li>
<li><span class="saturday">5</span></li>
<li><span class="sunday">6</span></li>
...
</ul></dd>
...
</dl>
</body>
</html>
----
以下にけだし同感なので。
inferno :: どう書く？orgは多言語クックブックになれるか > 一般投稿が可になった時に、ちょっと感じてたんですがやっぱり最近ある傾向が顕著で。というのは数学パズル系とか、(数学的な、事務処理などではない)アルゴリズム勝負！なお題ばっかりなんですよね。
というわけで、たまには簡単でその場で答えが出て、なによりある言語使いにとって「外国語」ではこういうんだというのがわかる問題として考えてみました。
% program a b c d
で a, b, c, d を得るにはどうしたらよいかという、それこそネイティブには刺身タンポポより簡単だけど、「外国人」にはとっさに浮かばないという問題です。
Dan the Practical Programmer
スレッドプールに複数のワーカスレッドが待機しており、メインスレッドはいつでもワーカスレッドに仕事を渡せるような状態になっているとします。
さて、メインスレッドからスレッドプールにいくつか仕事を与え、メインスレッドは与えた仕事すべてが終了するまで待機し、次の処理に行ってはいけない、というようなコードを書いてください。 ＃現実に書く機会が多そうなコードですね…。
ここでの仕事の内容は、適当に5秒から15秒の間スレッドをスリープする、というもので結構です。 また、ワーカスレッドのスレッドプール自体の使用を終了するか、または残して再利用するかは問いません。できればコメントにスレッドプールを残したかどうかを書いてください。
ここでいう法演算とは，与えられた数(ここでは「法」と言います)で剰余をとりながら行う計算のことです．たとえば，法が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以下の範囲になるようにする，ということです
- 正規化をする際に，引き算を足し算へ変換する処理を一緒に行ってもかまいません．
- 計算過程で範囲外の数が現れたときには，正規化を行うことが望ましいですが，必ずしも行う必要はありません．(最終的な計算結果が正しければよしとします)
HTTPでGET その２ 前回のお題 http://ja.doukaku.org/18/ HTTPで指定されたURLをGETするコードを書いてください。 URLは「http://ja.doukaku.org/feeds/comments/」とします。 ただし ・Proxyサーバを経由してGETしてください。 ・タイムアウトを1秒に設定してください。 (デフォルトが1秒でも、1秒に変更してください) ・タイムアウトを十分に小さくした場合、GETが失敗することを確認してください。 もしOSに依存する場合はそのOS名のタグを、 依存しない場合は「OS非依存」というタグをつけてください。 わからなければつけなくても構いません。
see: HTTPでGET
お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．
このような数のことをMeertens数と言うそうです．
32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．
お題#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
一応、制約条件を示しておきます。
- あみだの横棒は縦棒をまたぐことはできません。常に隣接する縦棒同士の交換となります 。
- 同じ行に複数の横棒があっても良いですが、ひとつの縦棒の同じ点からふたつ横棒が出ることはありません。
一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。
たとえば、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 }は同じもの
とすることに注意してください。
古典的なパズルである小町算を解くプログラムを作成してください。
小町算とは：
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個の解答が得られました。
次のような書式で与えられた「あみだくじ」があります。 (あみだくじはコード中に埋め込んでも、標準入力や 外部ファイルから読み込んでも、書きやすい方法でかまいません) A B C D E | | |-| | |-| | |-| | |-| |-| |-| |-| | |-| | | | このあみだくじをたどって A B C D E | | |-| | |-| | |-| | |-| |-| |-| |-| | |-| | | | B D C A E のように結果を表示させるプログラムを作ってください。
与えられた矩形状の文字列中に存在する文字列"ウオリ"の位置を全て出力するプログラムを 書いてください。 文字列の検索方向は八方全てで、また連続している（左右や上下の境界をまたがない）ものを 対象とします。出力は起点"ウ"の座標と方向のリストにしてください。 サンプル入力： リオウウリウ ウオリウオリ オリリオリウ リリオオウオ サンプル出力： (2, 0), 左 (0, 1), 右 (0, 1), 下 (3, 1), 右 (4, 3), 左上 -- より一般には、任意の検索文字列への対応も考えてみてください。
そこで、ソース中に２進数を定数として書く方法、またはその代替手段を考えてください。
ある程度の評価基準を示します(できるところまでで構いません)。
・2進数の表示方法は0と1
・桁数は可変長
・コンパイル等の後に最適化等によって定数に変換されることが見込まれる
Cで関数として実装したものを示しておきます。
1 2 3 4 5 | int bin(int b1, int b2, int b3, int b4, int b5, int b6, int b7, int b8){
return b1<<7 | b2 <<6 | b3<<5 | b4<<4 | b5<<3 | b6<<2 | b7<<1 | b8;
}
int byte = bin(0, 1, 1, 0, 1, 0, 0, 1);
|
正整数の分割といったとき，同じ組み合わせのもの同じ分割とみなし，
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教えてください．
see: ヤング図形
スラッシュで区切られた文字列の配列(以下パスリスト)がある。 このパスリストにたいして擬似的なlsを行いたい。 lsはパスリストと表示対象ディレクトリのパスを入力する。 例としては以下のようになる。 pathList = ["aaa/bbb","aaa/ccc","aaa/ddd/eee","bbb/ddd/eee"] ls(pathList,"aaa/") >["bbb","ccc","ddd/"] ls(pathList,"aaa/ddd/") >["eee"] なおパスリストが大きくなったとき、速度がなるべく低下しないように実装するのが望ましい。 文字列は任意の文字コードであると仮定してかまわない。
- 標準でついているprintf系関数の使用禁止
- 標準でついているライブラリ以外の使用禁止
- 引数・返り値等の仕様はできるだけ似せればよい
1 2 3 4 5 6 7 | #include <string.h>
// なにもフォーマットしてない
int mysprintf(char *str, const char *format, ... ){
strcpy(str, format);
return strlen(str);
}
|
自然数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, を出力する．
一行の文字列を指定した数の行にできるだけ文字数が均等になるように分割してください． ただし，除算や剰余算を使わないで書いてみてください． sample = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく" divid 4 sample => "ゆめよりもはかなき世のなかを" "なげきわびつゝあかしくらすほ" "どに四月十よひにもなりぬれ" "ば木のしたくらがりもてゆく" divid 5 sample => "ゆめよりもはかなき世の" "なかをなげきわびつゝあ" "かしくらすほどに四月十" "よひにもなりぬれば木の" "したくらがりもてゆく" divid 6 sample => "ゆめよりもはかなき" "世のなかをなげきわ" "びつゝあかしくらす" "ほどに四月十よひに" "もなりぬれば木のし" "たくらがりもてゆく"
これは、実例を見た方が簡単だと思います。 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
see: Trie (en.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 | #!/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処理系。 ここでは、BFで書かれたソースを、同じ言語に変換するコンパイラーを募集します。
私自身、すでにPerlとJavaScriptに関しては http://blog.livedoor.jp/dankogai/archives/50545151.html でやっているのですが、他の言語バージョンも是非見たいので。
Dan the Brainf.ucker
どもraynstardです。 どちらにしようか迷いましたが発想の元ネタがUIさんの投稿からなので こちらに投稿してみます。 -------------- 以下の仕様を満たす文字列を 20行出力するプログラムを作成してください。 1. 1行の出力は「<行番号> '：' <メッセージ>」であること。 2. 行番号が 3の倍数であるとき、メッセージは「Fizz」であること 3. 行番号が 5の倍数であるとき、メッセージは「Buzz」であること 4. 行番号が 3の倍数かつ5の倍数であるとき、メッセージは「FizzBuzz」であること 5. 上記に記した条件以外のメッセージについては「hoge」であること 6. 条件分岐する場合、if文のみが使用でき、 かつ、論理式が成立した場合の処理のみが記述できます。 #アセンブリなどifがなければif以外でもかまわないです。(意味が同じならば) というわけでこの問題はFizz-Buzz問題をelseなしならどう書く？という問題です。 出力例： 1:hoge 2:hoge 3:Fizz 4:hoge 5:Buzz 6:Fizz 7:hoge 8:hoge 9:Fizz 10:Buzz 11:hoge 12:Fizz 13:hoge 14:hoge 15:FizzBuzz 16:hoge 17:hoge 18:Fizz 19:hoge 20:Buzz
与えられた四字熟語のリストから下のように四角く配置することのできる熟語の組み合わせを探すプログラムを作成してください。
出力例:
無憂無風 礼 林 千 火 万水千山 知行合一 者 筆 不 勾 言語道断
四字熟語は左から右、上から下へ読むものとします。また右上隅の漢字と左下隅の漢字は異なるものでなければいけません。
四字熟語のデータは扱いやすい形(たとえばユニコード文字列のリスト)で与えられていると仮定して構いません。サンプルデータが必要であれば FOR Microsoft IME The四字熟語辞典(データ / 文書作成) にテキスト形式のデータが入っているのでそれを使えると思います。
問題の規模の参考までに、40行程度のPythonスクリプトでこのデータ(重複をのぞいて8312件)を処理してみたところ2.4GHzのCPUで13秒程度かかりました。結果は8133件出力されました。
与えられた文字列を前後反転する関数 reverseString2 を書いてください。
ただし、reverseString2 は単純に文字列を反転するのではなく、括弧の対応
を保存するようにしてください。
以前のお題で作成した単純に与えられた文字列を単純に前後反転したもの返す
reverseString では
reverseString("文字列(もじれつ)の反転(はんてん)")
→ ")んてんは(転反の)つれじも(列字文"
のように括弧の対応は保存されませんが、reverseString2 では
reverseString2("文字列(もじれつ)の反転(はんてん)")
→ "(んてんは)転反の(つれじも)列字文"
のように括弧の対応が保存されます。
括弧文字は、'('と')'、'{'と'}'、'['と']'で、それぞれASCII文字と仮定し
てください。
reverseString2("対応[の{とれている(さまざまな)括弧}の(例)]です。")
→ "。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対"
入力文字列では対応の取れている括弧の内側には対応の取れない括弧文字はな
いと解釈してください。たとえば、
reverseString2("これ(は(対応のとれていない)括弧がある例です。")
→ "。すで例るあが弧括(いないてれとの応対)は(れこ"
次のような場合は対応のとれている括弧はないという解釈になります。
reverseString2("これ(も{対応の)とれていない}括弧の例です")
→ "。すで例の弧括}いないてれと)の応対{も(れこ"
日本語対応にする場合の文字のエンコーディングは実装側で都合のよいように
仮定してください。日本語対応であることは望ましいですが、必須ではありま
せん。
---
このお題はnobsunさんに投稿いただきました。ご協力ありがとうございます。
「 ファイル内の重複行削除(後優先) 」の続編です。
1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。
このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、 スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。
しかし、与えられたファイルが運悪く「一致する部分のないファイル」である可能性を考えてみましょう。たとえ1行ずつ読んで処理をしたとしても、「重複するかどうかの判定」のために前の行をまるごとメモリに取っておいたのでは、最終的にファイルを丸ごとメモリに乗せることになってしまいます。
こういうデータが入力されうる状況の場合にどう書くか、というお題です。前回のお題の条件3「ファイル全体を一度にメモリに読み込んで処理しないこと」を「たとえすべての行が異なるようなデータであっても、メモリの消費量をファイルサイズのおよそ10%程度に抑えること」と読み替えてください。
追記：「メモリの10倍」はさすがに条件として厳しすぎました。「ファイルのサイズは4ギガバイト未満であり、メモリの消費量をファイルサイズの半分以下に抑えること」と読み替えてください。半分以下に抑えられているのならば題意は満たすものとします。もちろん、頑張ってもっと少ないメモリで動くようにするのもアリです。
入力されたテキストデータから重複する行をとりのぞいて、その結果を標準出力へ出力するプログラムを作成してください。
重複行の排除については、以下の仕様を満たしてください。
- 読み込み順序は変更しないこと
- 重複する行があった場合、以前のデータを削除すること (後に読み込んだ方が強い)
- ファイル全体を一度にメモリに読み込んで処理しないこと
- 比較は行全体で行うこと
#4.はおまけですがある／なしで作りが変わってくると思われるので追加しました。
この問題はraynstardさんにご投稿いただきました。ご協力ありがとうございます。 ところで、素朴な実装のしかたをするとメモリ容量の数倍のサイズのすべての行が異なっているファイルを読ませたときに大変なことが起こりそうな気がしますが、そういうシビアなお題設定ではないので素朴に解いてしまって構いません。シビアなのは続編にしたいと思います。
同じ距離の点はどういう順番でも構いませんが、可能であれば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番目の頂点が何かも併せて答えてください。
このお題はかもさんの投稿を元にしています。ご協力ありがとうございました。
関数 InputCheckerは、以下の仕様を満たしてください。
- 引数に 時間(秒) Nと文字列 Sを受け取ること。
- ユーザからの標準入力とあらかじめ指定された S を比較し、 一致すれば「OK」、一致しなければ「NG」を標準出力へ出力すること。
- ユーザーの入力がN秒以内に完了しなかった場合は、比較せず 「TIME OUT」を標準出力へ出力すること。
- 経過時間はユーザーが入力を開始した地点から計測すること。
- ENTER キーの入力によってユーザー入力が完了したと仮定すること。
- ユーザの入力が完了するまでは、完了を待ち続けること
たとえば、「InputCheker(5, "ABCDEF")」と指定した場合、 出力例はこんな感じです。
- input(ABCDEF) =>ABCDEF<ENTER>
- result => OK
- result => NG
- result => TIME OUT
1. input(ABCDEF) =>
と出力して入力待ちをし、ユーザーが「ABCDEF<ENTER>」を入力したとき、 入力開始から5秒以内ならば「OK」、5秒をこえていれば「TIME OUT」を出力します。 このとき、ユーザーがキーを押下しなければ1. を出力してから たとえ10秒たっていても「TIME OUT」にはならないので注意してください。 時間計測はあくまでユーザーが入力を開始してからです。
このお題はraynstardさんの投稿です。ご協力ありがとうございます。
n個の整数をソートするプログラムを生成するプログラム gensort を 書いて下さい．条件は以下のとおり
- 生成するプログラム，生成されたプログラムは同じ言語にして下さい．
- 生成したプログラムはファイルに書き込んでください．
- 生成されたプログラムでは最初に n 個の整数を読み込んで， n個の変数を初期化してください．「可能なら」変数名は，アルファベット 一文字で a，b，c ... の順で使ってください．n = 5 なら 変数は a, b, c, d, e です．
- 生成されたプログラムでは，if 文あるいは if 式で2つの変数を比較して いって，変数の順が確定したら，その順で変数の値を出力するようにして 下さい．
- 生成される側のプログラムでのアルゴリズムやデータ構造を工夫する問題では ありません :)
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さんからの投稿です。ご投稿ありがとうございました。助かります。
n = 4の時には [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] が正解です。
問題の理解を促すために上のリストを2進数表記で表示してみます。
0000 0 1000 8 0100 4 1100 12 0010 2 1010 10 0110 6 1110 14 0001 1 1001 9 0101 5 1101 13 0011 3 1011 11 0111 7 1111 15n = 8などの場合のリストは音声のFFT演算でよく使わているそうです。 この問題は光成さんの投稿を元にしています。 ご協力ありがとうございました。
Pythonで34行のスクリプトを書いて得られた出力の例が下のようになります。
37 199148647.999978 58 24591257752.000000 67 147197952743.999999 163 262537412640768744.000000この問題は光成さんに教えて頂いた e^{π*sqrt{163}}≒26253741640768744 が元になっています。ご協力ありがとうございました。
また、ユーザの入力注の<br>は<br/>に変換してください。
このお題はperezvonさんの提案を元にした三部作の二問目です。ご協力ありがとうございました。
- 通すタグはAとBRとSTRONGのみ。大文字小文字は区別しない。
- それ以外のタグとして意味を持ちうる文字列は<を<に変換することで無効化する(削除するのではない。>は変換してもしなくてもよい)
- Aタグのhrefとname以外の属性は削除する。BRやSTRONGの属性はすべて削除する。
このお題はperezvonさんの提案を元にしています。ありがとうございました。 ただ、いきなりだと難しいかと思ったので、肝の部分以外を先に出題しました。このお題は続編で徐々に難しくなっていきます。
追記：属性に<や>が含まれてしまうケースに漏れのある解答が多いようなのでテストケースを追加します。
これは「この出力なら十分」という意味です。この出力の通りでなければいけないという意味ではありません。
<script foo="<script>alert('bar')</script>">alert('foo')</script>
<script foo="<script>alert('bar')</script>">alert('foo')</script>
<script foo="<a href='link'>link</a>">alert('foo')</script>
<script foo="<a href='link'>link</a>">alert('foo')</script>
<a href='www.g>oogle.com'>link</a>
<a href="./www.g%3Eoogle.com">link</a>
- 全部の要素が同じ値である(例：[1, 1, 1, 1])、
- 一つだけ仲間はずれがある(例：[1, 2, 1, 1, 1])、
- その他
型にうるさい言語のために：リストの中身は非負の整数だと仮定して負の値を未定義値代わりに使っても構いません。
追記：リストの長さは3以上であると仮定して構いません。(2個で異なる値の時にどちらが仲間はずれか決まらないので。) nobsunさん、noriさん、ご指摘ありがとうございます。
>>> pyramid("hoge")
e
g e
o g e
h o g e
>>> pyramid("abracadabra")
a
r a
b r a
a b r a
d a b r a
a d a b r a
c a d a b r a
a c a d a b r a
r a c a d a b r a
b r a c a d a b r a
a b r a c a d a b r a
サンプル入力
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からの挑戦状です。
詳しい導出方法はGoogle の秘密 - PageRank 徹底解説の3章に載っていますが、 簡単に説明すると
- ページがn枚ある場合、n×nの2次元配列を用意する。
- ページiからページjにリンクがある場合、mat[j][i] = 1 / num_link[i]とする。ただしnum_link[i]はi番目のページから出ているリンクの総数。
- 行列計算ライブラリを使ってできあがった2次元配列の固有値、固有ベクトルを求める。
- 出力された固有ベクトルから合計が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]
このお題はところてんさんの「行列演算系のお題が欲しい」という要望を元に考えたものです。ありがとうございました。
「重複無し乱数」で作ったbingo関数の結果を下のように「何番目の乱数か」とセットにして10個ずつ折り返して表示するコードを書いてください。
>>> bingo(30) 1 2 3 4 5 6 7 8 9 10 29 14 16 13 30 15 22 11 25 9 11 12 13 14 15 16 17 18 19 20 23 4 18 5 28 17 8 12 21 20 21 22 23 24 25 26 27 28 29 30 26 6 2 19 1 7 10 27 3 24 >>> bingo(35) 1 2 3 4 5 6 7 8 9 10 7 15 3 32 1 16 17 28 6 29 11 12 13 14 15 16 17 18 19 20 19 23 30 26 20 5 12 2 25 31 21 22 23 24 25 26 27 28 29 30 35 13 24 18 11 8 10 34 22 21 31 32 33 34 35 9 4 27 33 14
このお題はraynstardさんの投稿を元にしています。ご投稿ありがとうございました。 投稿の内容には表示のしかたも含まれていたのですが、 このお題では「重複しない1～nまでの乱数をどうやって作るか」という点に集中することにして、 結果の整形は続編としてこの後のお題で出すことにします。 サンプル入出力は下のようになります。
>>> bingo(10) [10, 7, 8, 4, 5, 2, 3, 1, 6, 9] >>> bingo(3) [2, 3, 1] >>> bingo(3) [2, 3, 1] >>> bingo(3) [3, 1, 2] >>> bingo(10) [7, 3, 8, 6, 4, 10, 9, 2, 1, 5]
分散関数呼び出しを実装してください． 呼び出される関数は，定価を整数で，割引率(%)を整数で受け取り， 文字列で「販売価格 ○円（定価○円から○%引き）」を返すものとします． また，数字は3桁のカンマ区切りにするものとします． たとえば，pricestring(2000, 20) なら "販売価格 1,600円 (定価2,000円から20%引き)" を返します． 関数の呼び出し元と，呼び出される側は，物理的に異なる サーバに配置できることを条件とします． 呼び出し方法は問いませんが，呼び出し方法に名前がある場合， それをタグに加えてください． （XML-RPC，SOAP，CORBA，RMI，など） また，作成した関数を直列に1万回呼び出して， 実行にかかった時間を測定してください． 測定時は別サーバでなくても構いません． （なるべく別サーバが望ましいです） 測定環境として， ・サーバとクライアントのCPU・メモリ ・同一サーバ内での実行か別サーバでの実行か ・別サーバの場合，通信経路．（100Mbps Ethernet等） ・言語のバージョン ・ミドルウェアを使用している場合，その名前とバージョン も併記してください． 1つの言語で複数の分散関数呼び出しの実装方法がある場合， 複数の回答を歓迎します． 出題の意図は，様々な分散呼び出し方法の実装例と， レスポンス速度の確認にあります．このお題は沢渡 みかげさんの投稿です。 まったく手を加えないでいい完成度の投稿で本当に助かります。 ありがとうございました。
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さんの解答を使って出力し直しました。
['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にした場合に、答えが…と色々悩みどころでした。
ソースコードの複数行にまたがる範囲を、範囲の前後に何かを書き足すだけで実行しないようにしてください。 「その範囲を削除する」などはダメです。 何重まで入れ子にできるか、どのような制限があるかを明記してください。 例えばJavaであれば/*～*/で複数行のコメントアウトができますが、入れ子/* /* */ */にできません。 Pythonであれば"""～"""で文字列化することでコメントアウトでき、'''～'''も使えるので2重まで入れ子にできます。
このお題は、無制限に入れ子にできるCommon Lispからの挑戦状です。 プログラミングシンポジウムで前田敦司先生の発表を聞いて思いつきました。
アクセスログの各行の先頭にIPアドレスがあります．そのIPアドレスを逆引き結果のFQDNで置き換えてください．
逆引きが出来なかった場合は，IPアドレスのまま残します． IPアドレス以外の部分は，そのまま加工せずに残してください．
----
例）192.168.7.1 が逆引きできない場合
210.166.209.71 - - [26/Jul/2007:22:32:47 +0900] "GET / HTTP/1.1" 403 283 "-" "Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.8.1.5) Gecko/20070713 Firefox/2.0.0.5"
192.168.7.1 - - [26/Jul/2007:22:32:48 +0900] "GET /favicon.ico HTTP/1.1" 404 290 "-" "Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.8.1.5) Gecko/20070713 Firefox/2.0.0.5"
↓
mikage.to - - [26/Jul/2007:22:32:47 +0900] "GET / HTTP/1.1" 403 283 "-" "Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.8.1.5) Gecko/20070713 Firefox/2.0.0.5"
192.168.7.1 - - [26/Jul/2007:22:32:48 +0900] "GET /favicon.ico HTTP/1.1" 404 290 "-" "Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.8.1.5) Gecko/20070713 Firefox/2.0.0.5"
----
アクセスログは膨大な量があるため，現実的な時間で処理できるよう，以下の条件をつけます．
・メモリに入りきらないような巨大なログも処理できるようにしてください．（ファイル全体をメモリに読み込むのはNG）
・十分な速度で処理できるよう，並列化する等の工夫をしてください．
・DNSサーバに大量のリクエストが行かないよう，結果をキャッシュしてDNSサーバへのアクセスを削減してください． なお，DNSのTTLは無視して結果をキャッシュしてかまいません． （ログの記録された時間の逆引きするタイミングがずれているため，正確な逆引きは元々無理なので）
名前解決はgethostbyaddrを利用しても良いですし，再帰的に名前解決が出来るDNSサーバと直接通信してもかまいません．
ログを順次読み取り処理する部分を，データを共有しつついかに並列化するか，という部分を問うのが目的です．
このお題は沢渡みかげさんの投稿です。ご投稿ありがとうございます。
このお題は匿名での投稿です。 与えられる整数の範囲は一京未満(10000000000000000未満)としたいと思います。 ご投稿ありがとうございます。
2年前のLL Day&Nightの「キミならどう書く」で、 これ専用のCPANモジュールが作られていたような記憶があるので 勝手にPerlからの挑戦状とみなしておきます(笑)
説明のために2*3のサイズで説明します。
画像1 ■■■ ■■■ 画像2 □□□ □□□ 画像3 ■■■ □□□ 指定された画像 ■■■ ■□□この場合、画像1とは4つのピクセルが同じ値なので類似度は4、 画像2との類似度は2、画像3とは上半分の3つと下半分の白2つが一致するので類似度は5、よって一番類似しているのは画像3となります。
このお題の趣旨は検索処理の実行速度にあるので、 実行してみて実用的な速度で動くことを確認することを強く推奨します。 可能であればマシンのスペックと実行にかかった時間を書いてもらえると参考になっておもしろいと思います。
なおこのお題はC言語からスクリプト言語への挑戦状です。 スクリプト言語に有利な問題が多すぎるので、この手の問題も大募集します。
「組み合わせ型の最小完全ハッシュ関数」とは 下のような「n個の値のうちm個が1で残りが0であるようなデータ」と整数とを対応づける関数です。下の例ではn=5でm=2になっています。 (「0以上n未満の整数から重複しないm個を選んだ組み合わせ」もデータとしては同じです)
>>> for xs in make_perm(5, 2): print xs, "=>", hash(xs, 5, 2) [1, 1, 0, 0, 0] => 9 [1, 0, 1, 0, 0] => 8 [1, 0, 0, 1, 0] => 7 [1, 0, 0, 0, 1] => 6 [0, 1, 1, 0, 0] => 5 [0, 1, 0, 1, 0] => 4 [0, 1, 0, 0, 1] => 3 [0, 0, 1, 1, 0] => 2 [0, 0, 1, 0, 1] => 1 [0, 0, 0, 1, 1] => 0
「ハッシュ関数」というとデータが文字列であるものを連想しやすいですが、 ここで扱う対象データは文字列ではありません。(ちなみに文字列のハッシュ関数は、異なる文字列が同じハッシュ値になることがあるので「完全」ではありません。)
さて、ここからが本題です。 組み合わせのデータを与えると整数を返すのがこのハッシュ関数でした。 この逆の関数、「整数xを与えると、hash(data) == xになるような組み合わせのデータdataを返す関数」を作ってください。
このお題はshuyoさんの提案を元に作成しました。ありがとうございました。
ここにトランプが一組あります． 司会者がそこから二枚抜いて，その積をAさんに，その和をBさんに教えました． #トランプにジョーカーはなく、1～13までの数字が書かれたカードであると考えて構いません． #たとえば，二枚のトランプの数字が2と5なら，Aさんには10，Bさんには7を教えます． #二つの数は同じかもしれません． 司会者がAさん，Bさんに二つの数字が分かるかと質問しました． Aさん「(この情報だけでは)分かりません」 Bさん「私も分かりません．ただ，Aさんが『分かりません』というのは分かっていました」 それを聞いたAさん「それなら，分かりました」 それを聞いたBさん「それなら，私も分かりました」 元の二つの数はなんだったのでしょうか．この「2つの数」を求めるプログラムを作ってください。解が複数個ある場合はすべて求めてください。 このお題は光成さんの投稿が元になっています。ご投稿ありがとうございます。
ある関数(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さんの投稿によるものです。ご投稿ありがとうございます。助かります。
Pythonの対話的インタプリタで表現すると下のようになります。
>>> def n_days_later(n):
?????
>>> five_days_later = n_days_later(5)
>>> datetime.datetime.now()
datetime.datetime(2007, 7, 20, 20, 11, 42, 78000)
>>> five_days_later(_)
datetime.datetime(2007, 7, 25, 20, 11, 42, 78000)
出題の意図としては「関数を返す関数」と「日時の差分の扱い方」を、それぞれ単体だと簡単すぎるので合わせ技にしてみた、というところです。
Ruby で表現すると、 以下のような「fooという関数を呼び出す関数」#bar、#bazがあるとき
def bar; foo end def baz; foo endこのbar, bazの返り値が以下のようになるような関数fooを定義してください。
bar #=> "bar" baz #=> "baz"
このお題は匿名の「Smalltalk からの挑戦状」を元に作成しました。 確かにこの手のリフレクションの機能が言語によってどう違うのかは興味深いところです。 リフレクションを使う問題をいくつか考えてみたいと思います。 ご投稿ありがとうございました。
例えば、定数が100で、4つの党の得票数がそれぞれ123, 4, 56, 78の場合、
int 定数 = 100;
int[] 得票数 = { 123, 4, 56, 78 };
配分すべき議席数は下のようになります。
48, 1, 21, 30このお題はcatsさんの投稿を元に作成しました。ご投稿ありがとうございます。
ここで「自分以外の約数の和が自分自身の2倍と等しいような整数」を「ダブル完全数」と呼ぶことにします。10000以下のダブル完全数をすべて求めるコードを書いてください。
----テンプレート----
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 どう書くさんに管理者さんからメッセージが届いています。 以下の
greentea #12222() Rating0/0=0.00
ファイル名の表示順序としてWindows Vista以降のExplorerや、KDEのDolphinでもいつの間にか、単純な辞書順ソートではなく数字混じりの文字列を数字順に並べるソートが採用されています。ここではそのソート方法を数字混じり文字列ソートと呼びます。
さて、数字混じり文字列ソートを実装してください。なお入力される文字はASCII文字を仮定して構いませんが、日本語の扱える文字コードにも対応していればより理想的です。
以下に、数字混じり文字列ソートでの挙動の例を示します。
例1:
辞書順ソート: 1.txt, 10.txt, 100.txt, 2.txt, 20.txt
数字混じり文字列ソート: 1.txt, 2.txt, 10.txt, 20.txt, 100.txt
例2:
辞書順ソート: x12, x13, x1A, x1B, xAB
数字混じり文字列ソート: x1A, x1B, x12, x13, xAB
例3:
辞書順ソート: A10B1, A10B10, A10B2, A1B1, A1B10, A1B2, A2B1, A2B10, A2B2
数字混じり文字列ソート: A1B1, A1B2, A1B10, A2B1, A2B2, A2B10, A10B1, A10B2, A10B10
[ reply ]