プログラミングのお題スレ Part3

プログラミングのお題スレです。

前スレ
プログラミングのお題スレ
http://toro.2ch.net/test/read.cgi/tech/1357191974/
出されたお題をコーディングして罵られるスレ
http://toro.2ch.net/test/read.cgi/tech/1354393458/

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文

【ソースコードが長くなったら】
http://codepad.org/
http://ideone.com/

宿題は宿題スレがあるのでそちらへ。

あー、イク…ちんぽイク！
ﾆﾆЭ・:∴:・ﾟ・。。・:∴｡・ﾟ・・｡・。｡・ﾟ・'.

お題：aをもっとも近いbの倍数に丸める。ちょうど中間の場合は
0から遠ざかる方向へ丸める。bが実数の場合は誤差はやむを得ないものとする。
例
a=123,b=12 -> 120
a=126,b=12 -> 132
a=-123,b=12 -> -120
a=-126,b=12 -> -132
a=1.234,b=0.01 -> 1.23
a=1.235,b=0.01 -> 1.24

>>3
＞a=123,b=120 -> 120
＞a=126,b=120 -> 132
＞a=-123,b=120 -> -120
＞a=-126,b=120 -> -132
じゃないのか？仕様をちゃんと記述してみろよ、このスカポンタン

>>4
お前は馬鹿か?
bの倍数に丸めるのにbが120で解が132ってどんだけ間が抜けているんだ?

>>3
; Common Lisp
(defun f3 (a b)
　(let* ((rem (rem a b))
　　　　 (i (- a rem)))
　　(if (< (abs rem) (/ b 2))
　　　　i
　　　　(funcall (if (plusp a) #'+ #'-) i b))))

>>3 Python
def f3(a,b):
　　x = a + b*(0.5+1e-10*(a*b)/abs(a*b))
　　return x - x%b

for a,b in [(123, 12), (126, 12), (-123, 12), (-126, 12), (1.234, 0.01), (1.235, 0.01)]:
　　if not isinstance(a+b, float):
　　　　print "a=%d, b=%d -> %d" % (a, b, f3(a,b))
　　else:
　　　　print "a=%f, b=%f -> %f" % (a, b, f3(a,b))

>>3 HSP
#module
#defcfunc f3 double a, double b, \
local abs_a, local abs_b, local is_minus, local c, local d, local r

abs_a=absf(a)
abs_b=absf(b)
if a*b<0.0 : is_minus=1
c=int(abs_a/abs_b)
d=abs_a-abs_b*c
if d*2>=abs_b : c++ : d-=abs_b

r=abs_a-d
if is_minus : r=-r
if double(int(b))=b : r=int(r)
return r
#global

mes f3(123, 12)
mes f3(126, 12)
mes f3(-123, 12)
mes f3(-126, 12)
mes f3(1.234, 0.01)
mes f3(1.235, 0.01)

>>3 Squeak Smalltalk
| a b |
a := 123. b := 12. a roundTo: b. "=> 120 "
a := 126. b := 12. a roundTo: b. "=> 132 "
a := -123. b := 12. a roundTo: b. "=> -120 "
a := -126. b := 12. a roundTo: b. "=> -132 "
a := 1.234. b := 0.01. a roundTo: b. "=> 1.23 "
a := 1.235. b := 0.01. a roundTo: b. "=> 1.24 "

>>3 Perl
use 5.016;
use warnings;
use bignum;

sub f { ($_[0] <=> 0) * (int((abs($_[0]) + abs($_[1] / 2)) / $_[1]) * $_[1]) }

say f(123, 12);
say f(126, 12);
say f(-123, 12);
say f(-126, 12);
say f(1.234, 0.01);
say f(1.235, 0.01);

>>3 Io
Number f := method(b, (self / b) round * b)

Io> 123 f(12)
==> 120
Io> 126 f(12)
==> 132
Io> -123 f(12)
==> -120
Io> -126 f(12)
==> -132
Io> 1.234 f(0.01)
==> 1.23
Io> 1.235 f(0.01)
==> 1.24

>>3 Haskell
roundToMultiple :: (Enum a, RealFrac a) => a -> a -> a
roundToMultiple _ 0 = 0
roundToMultiple a b0 = f $ map ((signum a *) . (b *)) [fromIntegral . floor $ a/b ..]
　　where
　　　b = abs b0
　　　f (x:y:ys)
　　　　　| abs (x-a) == b / 2 = y
　　　　　| abs (x-a) <　b / 2 = x
　　　　　| otherwise = f (y:ys)

main :: IO ()
main = print $ map (uncurry roundToMultiple)
　　　 [(123,12),(126,12),(-123,12),(-126,12),(1.234,0.01),(1.235,0.01)]
　　　 -- -> [120.0,132.0,-120.0,-132.0,1.23,1.24]

>>3 ruby 1.8.6
def f3(a, b)
(a / b.to_f).round * b
end
p [[123,12],[126,12],[-123,12],[-126,12],[1.234,0.01],[1.235,0.01]].map{|(a, b)| f3(a, b)}
↓
[120, 132, -120, -132, 1.23, 1.24]

>>3 ruby 2.1.0 p0
"a=123,b=12 -> 120
a=126,b=12 -> 132
a=-123,b=12 -> -120
a=-126,b=12 -> -132
a=1.234,b=0.01 -> 1.23
a=1.235,b=0.01 -> 1.24
"
.scan(/=([\d\-\.]+)/).flatten.each_slice(2) do | a , b |
  printf("[%s,%s]," % [a,b])
end

# => [123,12],[126,12],[-123,12],[-126,12],[1.234,0.01],[1.235,0.01],

お題：引数を表示して改行し、引数をそのまま返す関数。
例
p(p(p(1)+1)+1)
1
2
3

>>15 GNU Smalltalk
| p |
p := [:x | x printNl].
p value: (p value: (p value: 1) + 1) + 1

http://ideone.com/PKb532

--

Squeak Smalltalk
| p |
Transcript open.
p := [:x | Transcript showln: x. x].
p value: (p value: (p value: 1) + 1) + 1

>>15 ruby 1.8.6
def f15(x)
puts x;x
end
f15(f15(f15(1)+1)+1)

>>3
ttp://ideone.com/4h4Zue
C++標準でSign関数搭載してくれないかなぁ。イチイチ書くの面倒くさい。
Sign関数はNYSLでいいので。

>>15
関数パースしないといけないのかと思って一瞬ビビったのは内緒だ。

#include <iostream>

template<class T>
const T& p(const T& In){
std::cout << In << std::endl;
return In;
}

int main(){
p(p(p(1) + 1) + 1);

return 0;
}

>>15 Haskell
import Control.Applicative
import System.IO.Unsafe

p :: Show a => a -> a
p = unsafePerformIO . liftA2 (>>) print return

eval :: a -> IO ()
eval x = x `seq` return ()

main :: IO ()
main = eval $ p ( p ( p 1 + 1 ) + 1 )

>>15 HSP
#module
#defcfunc f15 int x
mes x
return x
#global

dummy=f15(f15(f15(1)+1)+1)

>>15 Perl
use 5.016;
use warnings;

sub p { sub{ $_[0] }->($_[0], say $_[0]) }

p(p(p(1) + 1) + 1);

お題：
リストを与え、ソートされていれば昇順(AS)か降順(DES)か全て同じ要素(EQ)かを出力する
ソートされていなければ先頭からソートされている個数を出力する
[6,6,3,2,6,4,7,4,7,4] => 4
[2,3,4,4,4,6,6,6,7,7] => AS
[7,7,6,6,6,4,4,4,3,2] => DES
[1,1,1,1,1,1,1,1,1,1] => EQ
[] => EQ
[1] => EQ

お題：
リストを与え、昇順でソートされている部分列のリスト出力する
[8,3,4,9,9,10,6,1,4,3] => [[8],[3,4,9,9,10],[6],[1,4],[3]]
[1,3,3,4,4,6,8,9,9,10] => [[1,3,3,4,4,6,8,9,9,10]]
[10,9,9,8,6,4,4,3,3,1] => [[10],[9,9],[8],[6],[4,4],[3,3],[1]]
[1,1,1,1,1,1,1,1,1,1] => [[1,1,1,1,1,1,1,1,1,1]]
[] => []
[1] => [[1]]

>>24
[3,4]も[3,4,9]だって部分文字列だろう。
適切な文言で表現をするべきだ。

>>23 Squeak Smalltalk
| sortOrder |
sortOrder := [:arr |
　 | signs |
　 arr size < 2 ifTrue: [#EQ] ifFalse: [
　 　 signs := (arr allButFirst - arr allButLast) sign.
　 　 true caseOf: {
　 　 　 [signs allSatisfy: #isZero] -> [#EQ].
　 　 　 [signs allSatisfy: #positive] -> [#AS].
　 　 　 [signs negated allSatisfy: #positive] -> [#DES]
　 　 } otherwise: [
　 　 　 | first |
　 　 　 first := signs detect: [:each | each ~= 0].
　 　 　 signs findFirst: [:sign | sign ~= 0 and: [sign ~= first]]
　 　 ]
　 ]
].

sortOrder value: #(6 6 3 2 6 4 7 4 7 4). "=> 4 "
sortOrder value: #(2 3 4 4 4 6 6 6 7 7). "=> #AS "
sortOrder value: #(7 7 6 6 6 4 4 4 3 2). "=> #DES "
sortOrder value: #(1 1 1 1 1 1 1 1 1 1). "=> #EQ "
sortOrder value: #(). "=> #EQ "
sortOrder value: #(1). "=> #EQ "

>>24 Squeak Smalltalk
| groupsOfSorted |
groupsOfSorted := nil.
groupsOfSorted := [:arr |
　 arr ifEmpty: [arr] ifNotEmpty: [
　 　 | limit rest |
　 　 limit := (1 to: arr size) findLast: [:m | (arr first: m) isSorted].
　 　 rest := arr allButFirst: limit.
　 　 {arr first: limit}, (groupsOfSorted value: rest)
　 ]
].

groupsOfSorted value: #(8 3 4 9 9 10 6 1 4 3). "=> #(#(8) #(3 4 9 9 10) #(6) #(1 4) #(3)) "
groupsOfSorted value: #(1 3 3 4 4 6 8 9 9 10). "=> #(#(1 3 3 4 4 6 8 9 9 10)). "
groupsOfSorted value: #(10 9 9 8 6 4 4 3 3 1). "=> #(#(10) #(9 9) #(8) #(6) #(4 4) #(3 3) #(1)). "
groupsOfSorted value: #(1 1 1 1 1 1 1 1 1 1). "=> #(#(1 1 1 1 1 1 1 1 1 1)). "
groupsOfSorted value: #(). "=> #(). "
groupsOfSorted value: #(1). "=> #(#(1)) "

>>23 HSP
#module
#const IS_ASCEND 1
#const IS_DESCEND 2
#const IS_EQUAL 4
#const MASK_ALL (IS_ASCEND|IS_DESCEND|IS_EQUAL)
#defcfunc f23 array arr, int arr_num, local mask
mask=MASK_ALL
repeat arr_num
if cnt=0 : continue
if arr(cnt)>arr(cnt-1) : mask &= IS_ASCEND
if arr(cnt)<arr(cnt-1) : mask &= IS_DESCEND
if mask=0 : r=cnt : break
loop
if mask & IS_EQUAL : return "EQ"
if mask & IS_ASCEND : return "AS"
if mask & IS_DESCEND : return "DES"
return str(r)
#global

arr=6,6,3,2,6,4,7,4,7,4
mes f23(arr, 10)
arr=2,3,4,4,4,6,6,6,7,7
mes f23(arr, 10)
arr=7,7,6,6,6,4,4,4,3,2
mes f23(arr, 10)
arr=1,1,1,1,1,1,1,1,1,1
mes f23(arr, 10)

mes f23(arr, 0)
arr=1
mes f23(arr, 1)

>>24 HSP
#module
#defcfunc f24 str s_, local s, local data_str, local data_num, local data, local ret
s=s_
if s="" : return "[]"

split s, ",", data_str
data_num=stat
repeat data_num
data(cnt)=int(data_str(cnt))
loop

ret=strf("[[%d", data(0))
repeat data_num-1, 1
if data(cnt)<data(cnt-1) {
ret+=strf("][%d", data(cnt))
} else {
ret+=strf(",%d", data(cnt))
}
loop
ret+="]]"
return ret
#global

mes f24("8,3,4,9,9,10,6,1,4,3")
mes f24("1,3,3,4,4,6,8,9,9,10")
mes f24("10,9,9,8,6,4,4,3,3,1")
mes f24("1,1,1,1,1,1,1,1,1,1")
mes f24("")
mes f24("1")

>>23 ruby 1.8.6
require 'enumerator'
def f23(a)
s = a.enum_cons(2).inject([]) {|cs, (x, y)|cs << (x == y ? '=' : x < y ? '<' : '>')}.to_s
pairs = [[/^[=]*$/, 'EQ'], [/^[<=]+$/, 'AS'], [/^[>=]+$/, 'DES'], [//, nil]]
pairs.find() {|(re, tag)| re =~ s}.last || 1 + [s.index('<'), s.index('>')].max
end
p f23([6,6,3,2,6,4,7,4,7,4])
p f23([2,3,4,4,4,6,6,6,7,7])
p f23([7,7,6,6,6,4,4,4,3,2])
p f23([1,1,1,1,1,1,1,1,1,1])
p f23([])
p f23([1])

>>24 ruby 1.8.6
def f24(a)
a.inject([[]]) {|xss, x|
!xss.last.last || xss.last.last <= x ? xss.last << x : xss << [x]
xss
}
end
p f24([8,3,4,9,9,10,6,1,4,3])
p f24([1,3,3,4,4,6,8,9,9,10])
p f24([10,9,9,8,6,4,4,3,3,1])
p f24([1,1,1,1,1,1,1,1,1,1])

>>25
リストを隣合う要素の左側が右側より大きい箇所を境目にグループ化したリストを出力する

>>25
勝手に文字列に変換してる奴がよく言うｗｗｗ

>>30 いちおう修正
def f24(a)
a.inject([]) {|xss, x|
xss.size < 1 || xss.last.last > x ? xss << [x] : xss.last << x
xss
}
end
p f24([])
p f24([1])
↓
[]
[[1]]

>>23
import Control.Monad

isSorted :: Ord a => [a] -> Either Int Ordering
isSorted [] = Right EQ
isSorted [_] = Right EQ
isSorted xs = foldM f EQ $ zip [1..] $ zipWith compare xs $ tail xs
　　where
　　　f EQ (_,x) = Right x
　　　f acc (_,EQ) = Right acc
　　　f acc (i,x)
　　　　　| acc == x = Right acc
　　　　　| otherwise = Left i

main :: IO ()
main = do
　　test [6,6,3,2,6,4,7,4,7,4] -- => 4
　　test [2,3,4,4,4,6,6,6,7,7] -- => AS
　　test [7,7,6,6,6,4,4,4,3,2] -- => DES
　　test [1,1,1,1,1,1,1,1,1,1] -- => EQ
　　test ([] :: [Int]) -- => EQ
　　test [1] -- => EQ

test :: (Ord a, Show a) => [a] -> IO ()
test xs = do
　　putStr $ show xs ++ " => "
　　putStrLn $ case isSorted xs of
　　　　Left i -> show i
　　　　Right EQ -> "EQ"
　　　　Right LT -> "AS"
　　　　Right GT -> "DES"

>>24
groupBySorted :: Ord a => [a] -> [[a]]
groupBySorted [] = []
groupBySorted (x0:xs0) = ls0 : groupBySorted rs0
　　where
　　　(ls0, rs0) = f x0 xs0
　　　f x [] = ([x], [])
　　　f x (y:ys)
　　　　　| x <= y = let (ls, rs) = f y ys in (x:ls, rs)
　　　　　| otherwise = ([x], y:ys)

main :: IO ()
main = do
　　test [8,3,4,9,9,10,6,1,4,3] -- => [[8],[3,4,9,9,10],[6],[1,4],[3]]
　　test [1,3,3,4,4,6,8,9,9,10] -- => [[1,3,3,4,4,6,8,9,9,10]]
　　test [10,9,9,8,6,4,4,3,3,1] -- => [[10],[9,9],[8],[6],[4,4],[3,3],[1]]
　　test [1,1,1,1,1,1,1,1,1,1]　-- => [[1,1,1,1,1,1,1,1,1,1]]
　　test ([] :: [Int])　　　　　-- => []
　　test [1]　　　　　　　　　　-- => [[1]]

test :: (Ord a, Show a) => [a] -> IO ()
test xs = putStrLn $ show xs ++ " => " ++ show (groupBySorted xs)

>>34 >>35 Haskell

>>23 Python
def f23(a):
　　sign = 0
　　for i in range(len(a)):
　　　　if i and a[i] != a[i-1]:
　　　　　　if sign and sign * (a[i] - a[i-1]) < 0: return i
　　　　　　sign = int((a[i] - a[i-1]) / abs(a[i] - a[i-1]))
　　return ["DES", "EQ", "AS"][sign+1]

q23 = [
　　[6,6,3,2,6,4,7,4,7,4],
　　[2,3,4,4,4,6,6,6,7,7],
　　[7,7,6,6,6,4,4,4,3,2],
　　[1,1,1,1,1,1,1,1,1,1],
　　[],
　　[1],
]
for x in q23:
　　print x, "=>", f23(x)

>>24 Python
def f24(a):
　　if len(a) == 0: return []
　　ans = []
　　i = 0
　　for j in range(len(a)):
　　　　if j and a[j] < a[j-1]:
　　　　　　ans.append(a[i:j])
　　　　　　i = j
　　return ans + [a[i:]]

q24 = [
　　[8,3,4,9,9,10,6,1,4,3],
　　[1,3,3,4,4,6,8,9,9,10],
　　[10,9,9,8,6,4,4,3,3,1],
　　[1,1,1,1,1,1,1,1,1,1],
　　[],
　　[1],
]
for x in q24:
　　print x, "=>", f24(x)

>>23
ttp://ideone.com/MB7PRq
バグいじくりまわしてたら正常動作するようになったぁゃしぃコード。まともなデバッグしてない。

>>24
ttp://ideone.com/okr2GQ
今回はボトムアップで作った。なんかコード短くなった気がする。

>>23 c
#include <stdio.h>
#define SIZE(a) (sizeof a / sizeof *a)
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int eq(int a, int b) {return a == b;}
int le(int a, int b) {return a <= b;}
int ge(int a, int b) {return a >= b;}
int count_true_pair_combo(int *is, int size, int (*f)(int, int)) {
int i;
for (i = 0; i < size - 1; i++) if (!f(is[i], is[i + 1])) break;
return i;
}
void f23(int *is, int size) {
int n_pairs = size - 1;
int n_eq = count_true_pair_combo(is, size, eq);
int n_le = count_true_pair_combo(is, size, le);
int n_ge = count_true_pair_combo(is, size, ge);
if (size < 2 || n_eq == n_pairs) puts("EQ");
else if (n_le == n_pairs) puts("AS");
else if (n_ge == n_pairs) puts("DES");
else printf("%d\n", 1 + MAX(n_le, n_ge));
}
int main() {
int a[] = {6,6,3,2,6,4,7,4,7,4}; f23(a, SIZE(a));
int b[] = {2,3,4,4,4,6,6,6,7,7}; f23(b, SIZE(b));
int c[] = {7,7,6,6,6,4,4,4,3,2}; f23(c, SIZE(c));
int d[] = {1,1,1,1,1,1,1,1,1,1}; f23(d, SIZE(d));
int e[] = {}; f23(e, SIZE(e));
int f[] = {1}; f23(f, SIZE(f));
return 0;
}

>>23-24 Perl
http://ideone.com/Q8Vxe7

お題 与えられた集合の要素を数珠順列に並べたもの全てを列挙せよ。

例
# {'a','b','c','d'} の数珠順列の全て
necklace=λ kfsAg:sum([[(kfsAg.sl[0],y)+x+(z,) for x in permutate(kfsAg-kfs([kfsAg.sl[0],y,z]))] for y,z in combinate(kfsAg.sl[1:],2)],[]); necklace(kfs("abcd"))
===============================
[('a', 'b', 'd', 'c'), ('a', 'b', 'c', 'd'), ('a', 'c', 'b', 'd')]


# [1, 2, 3, 4, 5] の数珠順列の全て
necklace=λ kfsAg:sum([[(kfsAg.sl[0],y)+x+(z,) for x in permutate(kfsAg-kfs([kfsAg.sl[0],y,z]))] for y,z in combinate(kfsAg.sl[1:],2)],[]); necklace(kfs([1,2,3,4,5]))
===============================
[(1, 2, 4, 5, 3), (1, 2, 5, 4, 3), (1, 2, 3, 5, 4), (1, 2, 5, 3, 4), (1, 2, 3, 4, 5), (1, 2, 4, 3, 5),
(1, 3, 2, 5, 4), (1, 3, 5, 2, 4), (1, 3, 2, 4, 5), (1, 3, 4, 2, 5), (1, 4, 2, 3, 5), (1, 4, 3, 2, 5)]

参考 URL;;http://www.geocities.jp/m_hiroi/light/pyalgo62.html

>>43
ttp://ideone.com/9drS0R
リンク先のベタ移植。値の加工はまた今度。たまたま時間なかった。
演算子がよくわからんかった。

>>43
ttp://ideone.com/cv8WVj
>>44の値を加工した。適当に加工したので使いにくいな。
実はC++には・・・順列が・・・。

ttp://ideone.com/CAHCou
C++。これライブラリ使って作ってみたけど、これ円順列の方かな？？？
そう言えば任意のオーダーで数珠順列作りたかったら、
まじめにけいさんして返ってきた(0,N]の配列を配列のインデックスにすれば良かったんだな。
考えが足りなかった。

>>43 Squeak Smalltalk 。例に書かれたコードを参考に。
| necklace |
necklace := [:arr |
　 arr size < 4 ifTrue: [arr] ifFalse: [
　 　 Array streamContents: [:ss |
　 　 　 arr allButFirst combinations: 2 atATimeDo: [:yz |
　 　 　 　 (arr copyWithoutAll: {arr first}, yz) permutationsDo: [:x |
　 　 　 　 　 ss nextPut: {arr first. yz first}, x, {yz second}]]]]].
necklace value: #(1 2 3 4 5)

=> #(
#(1 2 4 5 3)
#(1 2 5 4 3)
#(1 2 3 5 4)
#(1 2 5 3 4)
#(1 2 3 4 5)
#(1 2 4 3 5)
#(1 3 2 5 4)
#(1 3 5 2 4)
#(1 3 2 4 5)
#(1 3 4 2 5)
#(1 4 2 3 5)
#(1 4 3 2 5))

>>43
ttp://ideone.com/HoNicQ
ほぼC。たぶんこれで完成。
例文の関数言語は読めないので翻訳できない。Orz

>>43
AABCD
みたいに同一の要素が入ることは無いのかな？

>>46 ruby 1.8.6
def combination(a, k, is = [], acc = [])
if is.size == k
acc << is.map {|i| a[i]}
else
start = is.empty? ? 0 : is.last + 1
(start..a.size - 1).each {|i| combination(a, k, is + [i], acc) if i < a.size}
end
acc
end
def rotated_arrays(org, n_times, pos)
tmp = org.dup
(1..n_times).inject([]) {|ras, a| ras << (tmp << tmp.delete_at(pos)).dup}
end
def permutation(a, pos = 2, acc = [])
if a.size < 2
acc.concat a
elsif a.size == pos
acc.concat rotated_arrays(a, pos, -pos)
else
rotated_arrays(a, pos, -pos).each {|ra| permutation(ra, pos + 1, acc)}
end
acc
end

>>50 つづき。あ、>>50のリンク先はタイプミス。>>43が正解。
def f43(a)
a.size <= 3 ? a : combination(a[1, a.size - 1], 2).inject([]) {|acc, (y, z)|
permutation(a - [a[0], y, z]).inject(acc) {|acc, x|
acc << [a[0], y, x, z].flatten
}
}
end
p f43(('a'..'d').to_a)
p f43((1..5).to_a)
↓
[["a", "b", "d", "c"], ["a", "b", "c", "d"], ["a", "c", "b", "d"]]
[[1, 2, 5, 4, 3], [1, 2, 4, 5, 3], [1, 2, 5, 3, 4], [1, 2, 3, 5, 4], [1, 2, 4, 3
, 5], [1, 2, 3, 4, 5], [1, 3, 5, 2, 4], [1, 3, 2, 5, 4], [1, 3, 4, 2, 5], [1, 3,
2, 4, 5], [1, 4, 3, 2, 5], [1, 4, 2, 3, 5]]

combinationとpermutationの自作に正直ホネが折れた。
>>43が何を書いてるかサッパリ分からないがそこはフィーリングで。

お題：1から1001までしりとりで数え上げる。0は「ん」として
末尾が0の数字はスキップする。
例
1,11,12,2,21,13,...,1001

>>24 J
f=:3 :'if. y-:i.0 0 do. a: else.(1,0<(}:-}.)y)<;.1 y end.'
f 8 3 4 9 9 10 6 1 4 3
+-+----------+-+---+-+
|8|3 4 9 9 10|6|1 4|3|
+-+----------+-+---+-+
f 1 3 3 4 4 6 8 9 9 10
+--------------------+
|1 3 3 4 4 6 8 9 9 10|
+--------------------+
f 10 9 9 8 6 4 4 3 3 1
+--+---+-+-+---+---+-+
|10|9 9|8|6|4 4|3 3|1|
+--+---+-+-+---+---+-+
f i.0 0
++
||
++
f 1
+-+
|1|
+-+

>>52 Squeak Smalltalk
| shiritori |
shiritori := Generator on: [:g |
　 | keys |
　 keys := {'11'}, ((1 to: 9) gather: [:hd | (hd+1 to: 9) gather: [:tl |
　 　 {hd asString, tl},
　 　 (hd = 1 ifTrue: [{tl asString, tl}] ifFalse: [{}]),
　 　 {tl asString, (tl = 9 ifTrue: [hd = 8 ifTrue: [1] ifFalse: [hd+1]] ifFalse: [hd])}]]).

　 keys do: [:pair |
　 　 pair asSet size = 1 ifTrue: [g yield: pair first digitValue].
　 　 g yield: pair asNumber].

　 0 to: 9 do: [:m |
　 　 keys do: [:pair | g yield: (pair first asString, m, pair last) asNumber]].

　 g yield: 1001].

(shiritori next: 15) asArray. "=> #(1 11 12 2 22 21 13 3 33 31 14 4 44 41 15) "
shiritori contents last: 10. "=> #(896 699 997 798 897 799 998 899 991 1001) "

>>52
1~1001の中で末尾が0以外の数字は全部使うの？

自己解決.全部使えた

>>52 Haskell
http://ideone.com/MShWfd

>>52 ruby 1.8.6
伝家の宝刀「なぜか動いた」。脳みそ0mgでお送りします。
少なくとも1..101と1..1001のときなぜか答えを返すのを確認。
def f52(r)
trios = r.inject([]) {|trios, i|
cs = i.to_s.scan(/./)
l, r = cs.first.to_i, cs.last.to_i
r == 0 ? trios : trios << [l, i, r]
}
l, r = [trios.shift], [trios.pop]
while 0 < trios.size
trio = trios.shift
if l.last.last == trio.first
l.push trio
elsif trio.last == r.first.first
r.unshift trio
else
trios.push trio
trios.push l.pop if 1 < l.size
end
end
l.last.last == r.first.first ? (l + r).map {|trio| trio[1]} : nil
end
p f52(1..1001)

>>58 の出力。
[1, 155, 546, 697, 748, 81, 185, 596, 667, 768, 889, 91, 177, 798, 899, 991, 184
, 465, 566, 687, 788, 879, 981, 112, 2, 253, 364, 485, 576, 677, 778, 869, 971,
143, 394, 445, 526, 61, 175, 556, 647, 728, 859, 992, 233, 374, 475, 586, 657, 7
58, 849, 961, 197, 718, 839, 982, 283, 384, 425, 516, 637, 738, 829, 972, 213, 3
54, 495, 536, 627, 799, 962, 263, 344, 496, 617, 708, 819, 951, 193, 334, 455, 5
87, 789, 941, 165, 597, 779, 952, 203, 324, 486, 698, 809, 931, 164, 476, 607, 7
69, 942, 293, 314, 435, 567, 759, 932, 273, 304, 405, 577, 749, 921, 12, 294, 41
5, 557, 739, 922, 243, 395, 547, 729, 911, 122, 223, 385, 537, 719, 901, 183,
:
, 665, 564, 463, 362, 261, 116, 69, 958, 857, 756, 655, 554, 453, 352, 251, 128,
85, 59, 948, 847, 746, 645, 544, 443, 342, 241, 107, 74, 49, 938, 837, 736, 635
, 534, 433, 332, 231, 129, 96, 63, 39, 928, 827, 726, 625, 524, 423, 322, 221, 1
19, 97, 75, 53, 31, 19, 918, 817, 716, 615, 514, 413, 312, 211, 108, 86, 64, 42,
29, 9, 999, 989, 979, 969, 959, 949, 939, 929, 919, 909, 908, 898, 888, 878, 86
8, 858, 848, 838, 828, 818, 808, 807, 797, 787, 777, 767, 757, 747, 737, 727, 71
7, 707, 706, 696, 686, 676, 666, 656, 646, 636, 626, 616, 606, 605, 595, 585, 57
5, 565, 555, 545, 535, 525, 515, 505, 504, 494, 484, 474, 464, 454, 444, 434, 42
4, 414, 404, 403, 393, 383, 373, 363, 353, 343, 333, 323, 313, 303, 302, 292, 28
2, 272, 262, 252, 242, 232, 222, 212, 202, 201, 191, 181, 171, 161, 151, 141, 13
1, 121, 111, 109, 99, 98, 88, 87, 77, 76, 66, 65, 55, 54, 44, 43, 33, 32, 22, 21
, 1001]

>>52 Perl
http://ideone.com/W7AlWc

適当に昇順でサーチしてたら1001が余るなー。なぜだー。。。Orz

>>52
ttp://ideone.com/gY3R3j
ゴリ押しで問題といてみた。他の数字で動くときはほぼ偶然。
具体的には9から昇順サーチしてって、
1000個だとピッタリ循環するんだけど1001個だと1001番が余るので配列を結果見てから2個後ろにずらして、1001番を追加している。
非常にダーティなハックですなー。もっと綺麗に書きたい。
パズルとか思考のネストが深いと頭がオーバーヒートする。Orz

>>52 J
f=:3 :0
a=.~.;".&.>/:~":&.> ~./:~@(,|.&.":)&.>;/(#~0<10&|)>:i.1000
b=.(+/(1+i.9)="0 1[a)<;.1 a
c=.18}.;{.b
1,101,(;,(;/102+i.8),.(}.b),.(;/1+100*2+i.8)),c,1001
)

1 101 102 2 202 203 302 204 402 205 502 206 602 207 702 208 802 209 902 212
213 312 214 412 215 512 216 612 217 712 218 812 219 912 22 222 223 322 224 422
...
179 971 18 81 181 182 281 183 381 184 481 185 581 186 681 187 781 188 881 189
981 19 91 191 192 291 193 391 194 491 195 591 196 691 197 791 198 891 199 991
1001

自分で出題したのに知らないうちに難易度が上がってうまく解けないよ。
全部の数字を使い切らない解しか想定していませんでした。
みなさん、お題を育ててくれてありがとう。

>>63
> 全部の数字を使い切らない解しか想定していませんでした。

な、なんだって〜！ｗ
使い切らないで良いなら1,1001で終わるから違うんだろうなぁって判断した。

>>54の人がまじめに解いちゃったからね。いや、素晴らしいことだよ。ホント。

>>54 はすごいね、smalltalkはOO方面で伝説らしいし手をつけてみようか

>>52の問題って、アウトオブオーダー実行のチェイン見たくて不思議な魅力があって面白い。と、思う。
解も様々あるし。

>>66
>>54 は全部列挙できるルールを見つけたのでそれに基づいたジェネレーターを書き下ろしただけで
解いてはいません。ほめてもらってるのにすみません。でもSmalltalkに興味を持ってもらえるのは嬉しいです。

余計なことかもしれませんが、Smalltalkは処理系に違いで、あるいは同じ処理系でも
バージョンの違いですぐコードが動かなくなりますので、写経とかするときは注意してください。
古いバージョンでも大枠は学べるので、しょっぱな最新版をおっかけないほうがいいです。
一般に、何か教本を用いるときは、その教本が想定としている処理系（可能ならバージョンも）を
できるだけ一致させるのが吉です。あと、分からないことはプライドは捨ててどんどん訊いてください。
以下、比較的名前の知られた処理系のご紹介。

GNU Smalltalkは、紛らわしいことにSmalltalkとしてはかなり変わり種の処理系で、
ファンが作ったオレオレSmalltalk処理系ですが、通常のスクリプト言語に近い感じで使えるので
Smalltalkを素朴に言語処理系として学びたい人にはお勧めです。ideone.comでも使えます。

どうせなら（自分はともかく誰かが）仕事で使っているクオリティのきちんとした処理系で学びたい
ということでしたら、Cincom社のVisualWorksという処理系がお薦めです。非商用はフリーです。
http://smalltalk.cincom.jp/main/
http://smalltalk.cincom.jp/tutorials/index.ssp

Squeakは、処理系としてはめちゃくちゃですが、くだらない（というと語弊がありますが
「多岐のユースケースに沿った」というとちょっと恰好がつきますか…）クラスやAPIが充実しているので
こういうお題を解くときに痒いところに手が届くので個人的には気に入って使っています。
http://sourceforge.jp/projects/squeak-ja/
http://swikis.ddo.jp/squeak/13

PharoはSqueakのコアメンバーが、Squeakの冗長さにイヤ気して、よくある「整理したい」
「大胆にやりなおしたい」症候群でやっているプロジェクトで、Squeakより処理系としては
少しまともな半面、まだ発展途上なのが注意点です。
http://www.pharo-project.org/home
https://github.com/SquareBracketAssociates/PharoByExample-japanese
http://dotinstall.com/lessons/basic_smalltalk

お題：
n=1のとき
01
10

n=2のとき
0011
0011
1100
1100

n=3のとき
000111
000111
000111
111000
111000
111000

を表示する。

>>69 ruby 1.8.6
def f69(n)
puts ['0' * n + '1' * n] * n + ['1' * n + '0' * n] * n
end
(1..3).each {|n| f69(n)}

>>69 HSP
#module
#deffunc f69 int n
mes n_str(n_str("0", n)+n_str("1", n)+"\n", n)+n_str(n_str("1", n)+n_str("0", n)+"\n", n)
return

#defcfunc n_str str s, int n, local buf
sdim buf
repeat n : buf+=s : loop
return buf
#global

f69 1
f69 2
f69 3

>>69 Haskell
zeroOneMatrix :: Int -> String
zeroOneMatrix n = unlines . replicate n . (replicate n =<<) =<< ["01","10"]

main = putStr $ zeroOneMatrix 3

>>69 Squeak Smalltalk
| checker |
checker := [:n |
　 | zeros ones CRs |
　 zeros := Matrix new: n element: $0.
　 ones := Matrix new: n element: $1.
　 CRs := Matrix rows: n columns: 1 element: Character cr.
　 ((zeros, ones, CRs),, (ones, zeros, CRs)) asArray as: String].

checker value: 3.

000111
000111
000111
111000
111000
111000

>>69
http://ideone.com/6J77ik
ほぼC。いつもより多めに回っております。

>>69
http://codepad.org/Y0a4Rhvk

>>68
thx a lot! c++/java とは違う世界に期待して．
先日のお題で，√2 1000桁を追試しようと squeqk （だと思う）を早速いれたけれども，これってウィンドウシステム全体を入れたみたいな扱いなんですね．

>>75
トリ割れしたのにまだそれつかってんの？ｗ
それとも、それは勘違いでそのトリは新しいやつなの？

>>69 Io
f:=method(n,
a:="0"repeated(n)
b:="1"repeated(n)
(a .. b .. "\n")repeated(n)..(b .. a .."\n")repeated(n)
)

Io> f(2)println
0011
0011
1100
1100

>>69 C
void f(int n){
int x,y;
for(y=n*2;y--;){
for(x=n*2;x--;){
putchar(x/n^y/n|48);
}
puts("");
}
puts("");
}

int main(){
f(1);
f(2);
f(5);
return 0;
}

>>75
>これってウィンドウシステム全体を入れたみたいな扱いなんですね．

そうです。Smalltalk はアラン・ケイらが自身が構想した理想のパーソナルコンピューターである
「ダイナブック」http://swikis.ddo.jp/abee/74 の暫定OSとして独特な思想や世界観を背景
http://web.archive.org/web/20041016084842/marimpod.homeip.net/chomswiki/24 に作られたため
セルフホスティング（処理系・環境の大部分がSmalltalk自身で記述されている）の仮想OSのような構成で
独自のウインドウシステムも環境の中に備えています。余談ですが、このウインドウシステムを
スティーブ・ジョブズらが観てインスパイアされ（有り体に言えばパクって）LisaやMacを作ったり、
そのときは真似られなかったAPIを参考に、のちに改めてNeXTSTEP（今のOS X、iOSの前身）を
作ったのは比較的よく知られた話です。http://americanhistory.si.edu/comphist/sj1.html#soft

そんなわけで、もしSmalltalkを使うためだけに慣れたUNIX環境などから離れたくない、
ということでしたら、繰り返しになりますがGNU Smalltalkをお薦めします。
言語のみのSmalltalk、という本来のSmalltalkからすれば限定的な世界しか体験できませんが、
それでも組み込みライブラリひとつとってもSmalltalkはかなり盛りだくさんなので、
学ぶのに退屈することはないかと思います。

参考まで、件のコードをGNU Smalltalkでも動作するように書き換えてみました（ideone.com でも
時間切れにならないように 100桁で）。

| m x epsilon delta |
m := 100.
x := 1.
epsilon := 10 raisedTo: m negated.
[(delta := -2 * x * x + 1 * x / 2) abs > epsilon] whileTrue: [x := x + delta].
((x * 2) asScaledDecimal: m) printNl

http://ideone.com/MwgorF

>>79
>余談ですが、このウインドウシステムをスティーブ・ジョブズらが観て

いうまでもなく「このウインドウシステム」は、1979年当時の―です。念のため^^;
http://classes.soe.ucsc.edu/cmps112/Spring03/readings/st76figure3.gif

>>69 R
>>78の真似
f <- function(n){
a <- rep(0:1,c(n,n))
write(1-outer(a,a,"=="),"",n*2,sep="")
}

>>69 J
f =: '01'&([ {~ [: ~:/~ ] # [)

smoutput@(f"0) 1 2 3
01
10
0011
0011
1100
1100
000111
000111
000111
111000
111000
111000

お題：次の式をn=10について計算し、大きい順に式と値を表示する。
logは自然対数、sqrtは平方根、!は階乗、^は累乗とする。
2^n
2^log(n)
4^n
n
n^2
n!
n*log(n)
log(n!)
log(log(n))
sqrt(log(n))

>>83 ruby 1.8.6
def f83(n)
a = []
a << [2 ** n, '2^n']
a << [2 ** Math.log(n), '2^log(n)']
a << [4 ** n, '4^n']
a << [n, 'n']
a << [n ** 2, 'n^2']
a << [(1..n).inject(1){|r, i| r * i}, 'n!']
a << [n * Math.log(n), 'n*log(n)']
a << [Math.log((1..n).inject(1){|r, i| r * i}), 'log(n!)']
a << [Math.log(Math.log(n)), 'log(log(n))']
a << [Math.sqrt(Math.log(n)), 'sqrt(log(n))']
a.sort.reverse
end
puts f83(10).map {|a| a.join(' = ')}
↓
3628800 = n!
1048576 = 4^n
1024 = 2^n
100 = n^2
23.0258509299405 = n*log(n)
15.1044125730755 = log(n!)
10 = n
4.9334096679146 = 2^log(n)
1.51742712938515 = sqrt(log(n))
0.834032445247956 = log(log(n))

>>83 Squeak Smalltalk
| n exprs |
n := 10.
exprs := {
　 '2^n' -> [2 raisedTo: n].
　 '2^log(n)' -> [2 raisedTo: n ln].
　 '4^n' -> [4 raisedTo: n].
　 'n' -> [n].
　 'n^2' -> [n raisedTo: 2].
　 'n!' -> [n factorial].
　 'n*log(n)' -> [n * n ln].
　 'log(n!)' -> [n factorial ln].
　 'log(log(n))' -> [n ln ln].
　 'sqrt(log(n))' -> [n ln sqrt]}.
^(exprs collect: [:kv | kv value value -> kv key]) sort reversed

=> {3628800->'n!' .
1048576->'4^n' .
1024->'2^n' .
100->'n^2' .
23.02585092994046->'n*log(n)' .
15.10441257307552->'log(n!)' .
10->'n' .
4.9334096679146->'2^log(n)' .
1.517427129385147->'sqrt(log(n))' .
0.834032445247956->'log(log(n))'}

ttp://ideone.com/ixsTgz
あってるかな？数学はダメなんだよね。
階乗だけ手書きした。64ビット変数でも簡単にオーバーフローするので気をつけてね。

>>86　->　>>83
安価忘れてた。Orz

>>52 (>>55) Perl
http://ideone.com/faF5kM

出来てるはず……。

>>69 Perl
use 5.016;
use warnings;

sub f { map{ (join '', map{ $_ x $_[0] } @{$_}) x $_[0] } ([0, 1], [1, 0]) }

foreach(1 .. 3){
say join("\n", f($_));
}

>>83 Perl
http://ideone.com/GshPeG

>>83 Haskell
http://ideone.com/H9pU6e

>>69
　JavaScript
var NumberObj={};NumberObj.Number=0;
NumberObj.SetNumber=function (n){this.Number=n;}
NumberObj.Main=function (){
　var ReturnNumberString='';
　　for(l=0;l<this.Number;l++){
　　　for(n=0;n<this.Number;n++){var ReturnNumberString;ReturnNumberString+="0";}
　　　for(m=0;m<this.Number;m++){var ReturnNumberString;ReturnNumberString+="1";}
　　　ReturnNumberString+="\n" ;}
　　for(i=0;i<this.Number;i++){
　　　for(j=0;j<this.Number;j++){ReturnNumberString+="1";}
　　　for(k=0;k<this.Number;k++){var ReturnNumberString;ReturnNumberString+="0";}
　　ReturnNumberString+="\n";}
　window.alert(ReturnNumberString);
}
NumberObj.SetNumber(5);NumberObj.Main();
スマートではないですが勉強の一環として。改行多すぎといわれたため可読性低下。

>>69　JavaScript
var NumberObj={};
NumberObj.Number=0;
NumberObj.SetNumber=function (n){this.Number=n;}
NumberObj.Main=function (){
var ReturnNumberString='';
　　for(l=0;l<this.Number;l++){
　　　　for(n=0;n<this.Number;n++){ReturnNumberString+="0";}
　　　　for(m=0;m<this.Number;m++){ReturnNumberString+="1";}
　　　　ReturnNumberString+="\n" ;
　　}
　　for(i=0;i<this.Number;i++){
　　　　for(j=0;j<this.Number;j++){ReturnNumberString+="1";}
　　　　for(k=0;k<this.Number;k++){ReturnNumberString+="0";}
　　　　ReturnNumberString+="\n";
　　}window.alert(ReturnNumberString);
}
NumberObj.SetNumber(5);
NumberObj.Main();
NumberObj.SetNumber(5);NumberObj.Main();
スマートではないですが勉強の一環として。改行多すぎといわれたためインデント等省き可読性ゼロ。
スマートではないですが勉強の一環として。改行多すぎといわれたため可読性低下。

>>83 J
f=:3 :0
s=.'2^n';'2^log(n)';'4^n';'n';'n^2';'n!';'n*log(n)';'log(n!)';'log(log(n))';'sqrt(log(n))'
v=.((2&^);(2&^@^.);(4&^);(]);(^&2);(!);(*^.);(^.@!);(^.@^.);(%:@^.))y
;"1 |."1 ":&.> \:~ v ,. (<' = ') ,. s
)

f 10
n! = 3628800
4^n = 1048576
2^n = 1024
n^2 = 100
n*log(n) = 23.02585093
log(n!) = 15.10441257
n = 10
2^log(n) = 4.933409668
sqrt(log(n)) = 1.517427129
log(log(n)) = 0.8340324452

>>69 Maxima

f(n):=?format(?t,"~v@{~:*~v@{0~}~:*~v@{1~}~%~}~v@{~:*~v@{1~}~:*~v@{0~}~%~}",n,n,0);

>>69
>>93を元に、任意の文字を指定できるようにしてみた(Common Lisp)。
ideone.com/rzzYhs

ちなみにこっちは自分で一昨日書いたもの。
ideone.com/sEOxWw
"@" を使わず、"~:*" の使いどころもなってないので(formatの)引数がぐっちゃぐちゃ。

ボイヤー・ムーア法において，単語の検索が完了するまでの，

単語と英文の文字列比較の回数を数える
文字列比較の回数を画面表示する

ようなプログラムを作成しなさい。

　　 |=番兵|_
　　（　・ω・）　＜C/C++の宿題片付けます 166代目
　　○=｛=｝〇,
　 　|:::::::::＼, ', ´
､､､､し ､､､((（.＠）ttp://toro.2ch.net/test/read.cgi/tech/1381909900/

お題：ボイヤー・ムーア法で使う移動量の表をつくる。
文字と移動量の対応がわかれば表現は自由。

例　Jの場合
f=:3 :'|:~.y;"0((|.y) i. y){_1|.>:i.#y'
f'hello'
+-+-+-+-+
|h|e|l|o|
+-+-+-+-+
|4|3|1|5|
+-+-+-+-+
f'boyer-moore'
+--+-+-+--+-+-+-+
|b |o|y|e |r|-|m|
+--+-+-+--+-+-+-+
|10|2|8|11|1|5|4|
+--+-+-+--+-+-+-+

>>97 ruby 1.8.6
def bmmap(s)
cs = s.scan(/./)
(0...cs.size - 1).inject({}) {|m, i| m[cs[i]] = cs.size - 1 - i; m}.update({cs.last=>cs.size})
end
p bmmap('hello')
p bmmap('boyer-moore')
↓
{"l"=>1, "o"=>5, "e"=>3, "h"=>4}
{"m"=>4, "-"=>5, "b"=>10, "y"=>8, "o"=>2, "e"=>11, "r"=>1

>>97 Perl
use 5.016;
use warnings;

sub f {
sub {
+{ (map{ $_[$_] => $#_ - $_ } (0 .. $#_ - 1)), $_[-1] => 0+ @_ }
}->(split //, shift)
}

use Data::Dumper;
local $Data::Dumper::Terse = 1;
local $Data::Dumper::Indent = 0;
say Dumper(f("hello"));
say Dumper(f("boyer-moore"));

結果
{'l' => 1,'e' => 3,'h' => 4,'o' => 5}
{'-' => 5,'e' => 11,'y' => 8,'r' => 1,'b' => 10,'m' => 4,'o' => 2}

>>97
ttp://ideone.com/p3ohB2
ほぼC。これあってる？検索してでたページを勝手に解釈して作ったんだけど。
頭悪いからこういう理論系ってにがてー。Orz

>>97 Haskell
bmAlist :: Eq a => [a] -> [(a, Int)]
bmAlist [] = []
bmAlist xs = let (ln,(y,_):ys) = reverse `fmap` foldr f (0,[]) xs in (y,ln) : ys
　　where
　　　f x (i,ys) = maybe (i+1,(x,i):ys) (const (i+1,ys)) $ lookup x ys

main :: IO ()
main = mapM_ print $ map bmAlist ["hello","boyer-moore"]
-- [('o',5),('l',1),('e',3),('h',4)]
-- [('e',11),('r',1),('o',2),('m',4),('-',5),('y',8),('b',10)]

# ruby 2.1.0p0 (2013-12-25 revision 44422) [i386-mswin32_100]

# >>30 , >>33
def f24(a)
  a.inject([]){|xss, x| xss.empty? || xss.last.last > x ? xss << [x] : xss.last << x ; xss}
end
p f24([]) ; p f24([1])

# >>50 , >>51
p [1,2,3,4].combination(2).to_a
p [1,2,3,4].permutation(2).to_a

# >>84
n = 9
p [(1..n).inject(1,:*), 'n!']

# >>98
def bmmap(s)
  cs = s.split(//)
  cs.size.times.inject({}) {|m, i| m[cs[i]] = cs.size - 1 - i; m}.merge(cs.last=>cs.size)
end
p bmmap('hello') ; p bmmap('boyer-moore')

# => []
# => [[1]]
# => [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
# => [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]
# => [362880, "n!"]
# => {"h"=>4, "e"=>3, "l"=>1, "o"=>5}
# => {"b"=>10, "o"=>2, "y"=>8, "e"=>11, "r"=>1, "-"=>5, "m"=>4}

お題：与えられた年月のカレンダーを表示せよ。

回答例と出力例：
require 'date'
def weeks(year, mon)
first, last = Date.new(year, mon, 1), Date.new(year, mon, -1)
weeks = (first..last).inject([]) {|ws, d| d.day == 1 || d.wday == 0 ? ws << [d] : ws.last << d; ws}
weeks[0] = [nil] * (7 - weeks.first.size) + weeks.first
weeks[-1] = weeks.last + [nil] * (7 - weeks.last.size)
weeks
end
def calendar(year, mon)
weeks(year, mon).map {|days| days.map {|d| d ? "%2d" % d.day : ' '}.join(' ')}
end
def yearmon(date = Date.today)
[date.year, date.mon]
end
puts calendar(*yearmon)
↓
ttp://codepad.org/HvvYuSMi

>>103
#!/bin/sh -f
/bin/cal $2 $1

実際に何年も使っているコード

import calendar as cl; cl.prmonth(2014, 02, w=11, l=2)
February 2014
Monday Tuesday Wednesday Thursday Friday Saturday Sunday
1 2
3 4 5 6 7 8 9
・・
24 25 26 27 28

>>97 Squeak Smalltalk
| bmTable |
bmTable := [:str |
　 str asSet collect: [:chr | chr -> ((str size - (str lastIndexOf: chr)) - 1 \\ str size + 1)]
].
bmTable value: 'hello'. "=> a Set($o->5 $e->3 $h->4 $l->1) "
bmTable value: 'boyer-moore'. "=> a Set($y->8 $o->2 $-->5 $b->10 $r->1 $e->11 $m->4) "

>>103 Squeak Smalltalk
| ans month |
Transcript open.
ans := FillInTheBlank request: 'yyyy-mm' initialAnswer: (Date today yyyymmdd allButLast: 3).
month := (ans ifEmpty: [Date today] ifNotEmpty: [(ans, ' 1') asDate]) month.
month weeks do: [:week |
　 week dates do: [:date |
　 　 Transcript nextPutAll: (date month = month
　 　 　 ifFalse: ['__']
　 　 　 ifTrue: [date dayOfMonth printPaddedWith: $_ to: 2])
　 ] separatedBy: [Transcript space]
] separatedBy: [Transcript cr].
Transcript endEntry

'2014-02' =>
__ __ __ __ __ __ _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 __

>>103 Perl
https://ideone.com/i2tE8a

>>103 Common Lisp
ideone.com/sW9TkK

>>103 J
load 'dates'
f=:3 :0
({.6!:0'')f y
:
a=:>:i.(todayno x,(y+1),1)-todayno x,y,1
b=.'SMTWTFS'
(_7,\((weekday x,y,1)#0),a){'_123456789abcdefghijklmnopqrstuv'
)

2014 f 2
SMTWTFS
______1
2345678
9abcdef
ghijklm
nopqrs_

ttp://ideone.com/gZ6pim
ほぼC。まともに書いたの初めてかも。
色々検索してやっと書けた。
ライブラリなしでも書けるもんだな。

>>111　->　>>103
安価忘れた。コードあってるよね？

>>112
デバッグの楽しみを奪うのは気が退けるから自分で頑張ってテストしてくれ。
で、ぱっと見で気づいた点。
・trueと比較するな。
・全部大文字の変数名を作るな。
紛らわしい。

>>113
Defineは基本的には使わない主義なので全部大文字だと、困るかなぁ。
いい名前思い浮かばなかったのは確かだけど。まぁ、これは失態。
でも、trueと比較するのは個人的な流儀なのでこれは曲げれん。
葉末を叩くより、ロジックを洗って欲しかった。

>>114
そこはそれこそ、自分でやるべきことだがな＜ロジック

他に気づいた点。
・「与えられた」と言う仕様(お題)を満たしていない。
・主義なら止めないが、std::endlは'\n'とイコールではないぞ。
・定数にはconstをつけよう。特に、文字列。
・ついでに言えば、文字列配列はstaticにして無駄な代入は減らすべき。
・5とか6とかマジックナンバーうぜぇ。それこそ、const int Sunday = Saturday + 1;とかしたらいいのに。
・LastDayOfMonth()が折角異常時に負値を返しているのに呼び出し元がケアしてないのな。
・1900年から足すのは流石に地道過ぎる。例えば2000年辺りを基準に365*3+366で計算しちゃえば?
・つーか、元を糾せばtime.h使えば楽なのに。まぁ、そこを自力でやりたかったのか。

それにしても、trueと比較って意味がわからねぇ。
比較結果を返す関数の結果がtrueかどうか比較したくなるなら、なんで普通の比較はtrueと比較したくならないんだ?
ついでに言えば、折角コンパイラが勝手に最適化してくれる可能性を自ら潰しているぞ。

>113が教条主義なのは兎も角、全部大文字だと
書いた方は困らんだろうけど読む方は勘違いする罠。
それと、LastDayOfMonth()はテーブル使った方が見やすくないか?

>>103 Io
f := method(y,m,
d1 := Date clone setYear(y) setMonth(m) setDay(1)
d2 := Date clone setYear(y + (m / 12)floor) setMonth(m % 12 + 1) setDay(1)
a := (d2 - d1) days
w := d1 asString("%w") asNumber
writeln(" Su Mo Tu We Th Fr Sa")
for(i,1,w + a,
write(if(i <= w, "___", (i - w) asString(3,0).. if((i % 7) == 0, "\n","")))
)
writeln
)

Io> f(2014,2)
_Su_Mo_Tu_We_Th_Fr_Sa
____________________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

>>112
> コードあってるよね？

シラネｗ　ワカンネｗ

回答者ならではとか言語ならではの違いが見たいだけだから、
答えがあってるかどうかまでは見てないんす。すまんすｗ
あとはお題に対する解釈で、どこを押さえてくれて、
どこで遊んでくれるのかを見るのも、それも楽しみかなあ。
いいかげんで無責任な出題でホント申し訳ないｗ

>>115
おはよう。
お題をみたしてないってどういうこと？余計に表示してるってことなのか、それとも他に？
Endlineって\nじゃないの？
constはあんまり突ける癖ないな。コンパイル時定数はさすがにstatic constにするけど。
マジックナンバーは、最後の詰めが甘かったね。反省。ほぼ完成した後追加したから気が回らなかった。
関数書くときは異常系もちゃんと書いておくんだよ。あんまり使わないけど。自分の範囲内だから他人がいじるのは想定してない。
1900から足しているのは、仕様だ。まぁ、検索した時に出てきた資料に沿ったんだけどさ。あとはある程度ロールバックできるようにしたかった。
time.hって乱数以外で使ったこと無いのよね。自前で書けそうだったのと調べるの面倒だったので手書きした。
trueとの比較は、自分のコーディングスタイルなので効率とかそういう話じゃない。
とにかく、X==Yの形で書いてないと俺自身の字句解析がおかしくなるんだよ〜。かっこ厨だしな。
左から右に流れて読む癖があるからね。
とりあえず、要求満たしてないっていうのがどういうことなのか知りたい。

>>116
それについては俺も反省。
Define使わない主義だけど、やっぱ紛らわしいか。せめてスコープ内位は探して欲しいが。
テーブルの件は確かにそうだね〜。実質2時間程度で書いたので意識が散漫だった。
のと、グローバル変数はなるべく使わない主義なので、選択肢になかった。
でも、テーブルでも良かったかな。std::vectorがイニシャライザリスト使えることだし、そんなに悪い選択でもなかった。
あ、でもうるう年のとき面倒くさいな。難しい選択だ。

>>118
まぁ、そういうことなら一応安心。
蛇足も許してくれそうでよかった。

>>115
そだそだ、暇だったら参加してよ。
コールドリーディングもいい勉強になるからさ。

>>103 Haskell
http://codepad.org/NvNlmZ8f

>>121
コールドリーディングってなんぞ？コード・リーディングな。。。Orz
IMEのサジェストに頼ったのがいけなかったな。

>>121
いったい何を聞き出すんです？
まあSE的にはそれなりに役立ちそうな能力だが＞コールドリーディング

>>103 ruby 1.8.6
回答する人にとって余計な負担になると思って省いたが、
つけてる人の見るとやっぱそっちがカッコイイのでいちおうつけとく。

def calendar(year, mon)
lines = weeks(year, mon).map {|ds| ds.map {|d| d ? "%2d" % d.day : ' '}.join(' ')}
lines = [(0...7).map {|i| Date::DAYNAMES[i].gsub(/^(..).*/, '\1')}.join(' ')] + lines
lines = [(Date::MONTHNAMES[mon] + ' ' + year.to_s).center(lines.first.size)] + lines
end
↓
February 2014
Su Mo Tu We Th Fr Sa
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

>>109 Python
import calendar
calendar.setfirstweekday(calendar.SUNDAY)
calendar.prmonth(2014, 2)

>>119
「与えられた年、月のカレンダー」と言うお題に対して、2014年のカレンダーを出力しているってことでしょ。
ShowCalendar()がその意味ではお題に対する解ってことでいいんでない?

>>127
まぁ、そういうことなら安心だ。
何事かと思った。

お題：ワードサーチパズルのソルバーを書いてください。
問題の与え方は（ハードコードを含め）自由です。
結果は、先頭の文字の場所を示せればＯＫです。
余力があれば、一つの単語の解答が複数ある場合にも対応してください。

入力例：
WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH

WEEK
FIND
RANDOM
SLEUTH
BACKWARD
VERTICAL
DIAGONAL
WIKIPEDIA
HORIZONTAL
WORDSEARCH

出力例：
WEEK, なし; FIND, (2,5); RANDOM, (2,1); SLEUTH, (10,5);
BACKWARD, (2,10); VERTICAL, (1,2); DIAGONAL, (9,7);
WIKIPEDIA, (10,4); HORIZONTAL, (10,1); WORDSEARCH, (1,1)

>>129
もしかして、入力って2次元配列なの？

>>130
ワードサーチパズルは、たとえばこんなのです。
http://www.eigo21.com/03/srch/00.htm

>>129 Squeak Smalltalk
| str mat words dirs |
str := 'WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH'.

words := #('WEEK' 'FIND' 'RANDOM' 'SLEUTH' 'BACKWARD' 'VERTICAL'
'DIAGONAL' 'WIKIPEDIA' 'HORIZONTAL' 'WORDSEARCH').

mat := Matrix rows: str lines size columns: str lines first size contents: str lines concatenation.
dirs := {1@0. 1@1. 0@1. -1@1. -1@0. -1@ -1. 0@ -1. 1@ -1}.

^words collect: [:word |
　 | res pos |
　 mat replaceAll: word first with: $*.
　 res := 0@0.
　 [(pos := mat indexOf: $*) isZero] whileFalse: [
　 　 mat at: pos x at: pos y put: word first.
　 　 ((1 to: word size - 1) allSatisfy: [:m | m * dirs + pos anySatisfy: [:cur |
　 　 　 (mat at: cur x at: cur y ifInvalid: nil) = (word at: m + 1)]]) ifTrue: [res := pos]].
　 word -> (res isZero ifTrue: ['not found'] ifFalse: [res])]

=> {'WEEK'->'not found' . 'FIND'->2@5 . 'RANDOM'->2@1 . 'SLEUTH'->10@5 .
'BACKWARD'->2@10 . 'VERTICAL'->1@2 . 'DIAGONAL'->9@7 . 'WIKIPEDIA'->10@4 .
'HORIZONTAL'->10@1 . 'WORDSEARCH'->1@1}

>>129
出遅れたか……言語はC++
http://codepad.org/ER55e69s

なお、input.txｔと出力は次の通り(1行目は横サイズ・縦サイズ・単語数)
http://codepad.org/OruCO0Nq

>>131
うぇー、斜めあるんですか。。。
ちょっと大変だなー。

ttp://ideone.com/nBl1Uv
ほぼC。アーちきしょー。イッパイ殴られたわ。正直合ってるかどうかわからん。
汎用性は持たせたが、ほぼハードコーディングだし、処理速度遅め。
久しぶりにすごい勢いでコード書いたわ。あー疲れた。

最初もっと難しい問題かと思って何度か書きなおしちゃったよ。
6時間もかかるとか想定外だ。ほんっと疲れた。Orz

>>132の設計のほうがいいな〜。土台できてから書きえるのはリスキーだね。
自分の頭呪いたい。超絶呪いたい。俺に才能をクレ。

あーすまん。
グダグダ言ってしまったが、歯ごたえのあるイイ問題だった。
半分くらいは自分のせいだが、いやーすごかった。

>> 129 Python
def f129(table, words, SP = "*"):
　　result = dict((word, []) for word in words)
　　h, w = len(table), max(len(x) for x in table)
　　table = [x.ljust(w) for x in table]
　　def f129s(table, down=0, right=1):
　　　　if down:
　　　　　　if right < 0: table = [SP*i + table[i] + SP*(w-1-i) for i in range(w)]
　　　　　　elif right > 0: table = [SP*(w-1-i) + table[i] + SP*i for i in range(w)]
　　　　　　table = ["".join(table[i][j] for i in range(len(table))) for j in range(len(table[0]))]
　　　　for word in words:
　　　　　　rev_word = "".join(reversed(word))
　　　　　　for i in range(len(table)):
　　　　　　　　for (wd, inv, ofs) in [(word, 1, 0), (rev_word, -1, len(rev_word)-1)]:
　　　　　　　　　　if wd in table[i]:
　　　　　　　　　　　　row, col = i, table[i].find(wd) - inv*ofs
　　　　　　　　　　　　if down:
　　　　　　　　　　　　　　row += col*right
　　　　　　　　　　　　　　if right > 0: row -= w-1
　　　　　　　　　　　　　　row, col = col, row
　　　　　　　　　　　　result[word].append(((row+1, col+1), (row+inv*down*len(wd), col+inv*right*len(wd)),(inv*down, inv*right)))
　　for (down, right) in ((0,1), (1,0), (1,1), (1,-1)):
　　　　f129s(table, down, right)
　　for k in words:
　　　　print k, result[k]

table = ['WVERTICALL', 'ROOAFFLSAB', 'ACRILIATOA', 'NDODKONWDC', 'DRKESOODDK', 'OEEPZEGLIW', 'MSIIHOAERA', 'ALRKRRIRER', 'KODIDEDRCD', 'HELWSLEUTH']
words = ['WEEK', 'FIND', 'RANDOM', 'SLEUTH', 'BACKWARD', 'VERTICAL', 'DIAGONAL', 'WIKIPEDIA', 'HORIZONTAL', 'WORDSEARCH']
f129(table, words)

>>137 の出力(>>129 安価ミスったw)
WEEK []
FIND [((2, 5), (5, 8), (1, 1))]
RANDOM [((2, 1), (7, 0), (1, 0))]
SLEUTH [((10, 5), (9, 10), (0, 1))]
BACKWARD [((2, 10), (9, 9), (1, 0))]
VERTICAL [((1, 2), (0, 9), (0, 1))]
DIAGONAL [((9, 7), (0, 6), (-1, 0))]
WIKIPEDIA [((10, 4), (0, 3), (-1, 0))]
HORIZONTAL [((10, 1), (-1, 10), (-1, 1))]
WORDSEARCH [((1, 1), (10, 10), (1, 1))]

((開始位置), (終了位置), (探索方向)) のリストになってます

>>135
方向ごとに関数書くとかゴリ押しすぎるだろｗｗｗ

……ま、移動方向の差分が各方向に-1〜1で済むというアイデアは、
皆どこかで拾ったか昔思いついたんだろうね

>>137 ruby 1.8.6
def ddup(o)
Marshal.load(Marshal.dump(o))
end
def f129(table, words)
css = table.map {|s| s.scan(/./)}
trioss = (0...css.size).inject([]) {|trioss, i| trioss << (0...css[i].size).inject([]){|trios, j| trios << [i, j, css[i][j]]}}
naname = Array.new(trioss.size + trioss[0].size - 1) {|i| []}
tmp, a, b = trioss.dup, ddup(naname), ddup(naname)
while !tmp.empty?
trios = tmp.pop
i = trios.size - 1 - tmp.size
trios.each_index{|j| a[i + j] << trios[j]; b[i + j] << trios[trios.size - 1 - j]}
end
lines = trioss + trioss.transpose + a + b # 横、縦、斜め、逆斜め
lines = lines + lines.map {|trios| trios.reverse} # 逆方向
tails = words.inject({}) {|h, w| h[w] = w.scan(/./).size - 1; h}
lines.each {|trios|
s = trios.map{|trio| trio.last}.join
words.each{|w|
i = s.index(w)
puts w + ' ' + trios[i].inspect + '..' + trios[i + tails[w]].inspect if i
}
}
end
table = %w(WVERTICALL ROOAFFLSAB ACRILIATOA NDODKONWDC DRKESOODDK OEEPZEGLIW MSIIHOAERA ALRKRRIRER KODIDEDRCD HELWSLEUTH)
words = %w(WEEK FIND RANDOM SLEUTH BACKWARD VERTICAL DIAGONAL WIKIPEDIA HORIZONTAL WORDSEARCH)
f129(table, words)

>>140
↓
VERTICAL [0, 1, "V"]..[0, 8, "L"]
SLEUTH [9, 4, "S"]..[9, 9, "H"]
RANDOM [1, 0, "R"]..[6, 0, "M"]
BACKWARD [1, 9, "B"]..[8, 9, "D"]
HORIZONTAL [9, 0, "H"]..[0, 9, "L"]
WIKIPEDIA [9, 3, "W"]..[1, 3, "A"]
DIAGONAL [8, 6, "D"]..[1, 6, "L"]
WORDSEARCH [0, 0, "W"]..[9, 9, "H"]
FIND [1, 4, "F"]..[4, 7, "D"]

>>140のリンク先はタイプミス。>>129が正解。

>>139
勘違いして別の問題のコード書いてた設計そのまま使ったので結果的に損した感じ。
初見の選定眼って大事！Orz

>>129 HSP
#module
#defcfunc is_match array field, int x, int y, int c
if y<0 or y>=length(field) : return 0
if x<0 or x>=strlen(field.y) : return 0
return peek(field.y, x)=c
#deffunc f129 array field, var word, local found_count
vx= 1, 1, 0,-1,-1,-1, 0, 1
vy= 0,-1,-1,-1, 0, 1, 1, 1
for sy, 0, length(field)
for sx, 0, strlen(field.cnt)
for d, 0, 8
is_found=1
x=sx : y=sy
repeat strlen(word)
if is_match(field, x, y, peek(word, cnt))=0 : is_found=0 : break
x+=vx.d : y+=vy.d
loop
if is_found : mes strf("%s %d,%d", word, sx+1, sy+1) : found_count++
next
next
next
if found_count=0 : mes strf("%s not found.", word)
return
#global

field="WVERTICALL","ROOAFFLSAB","ACRILIATOA","NDODKONWDC","DRKESOODDK","OEEPZEGLIW","MSIIHOAERA","ALRKRRIRER","KODIDEDRCD","HELWSLEUTH"
words="WEEK","FIND","RANDOM","SLEUTH","BACKWARD","VERTICAL","DIAGONAL","WIKIPEDIA","HORIZONTAL","WORDSEARCH"

foreach words
f129 field, words.cnt
loop

>>144 訂正
for sx, 0, strlen(field.cnt)
↓
for sx, 0, strlen(field.sy)

>>129 Perl
https://ideone.com/BO0SSu

>>129
ttp://ideone.com/q1WcWA
ほぼC。>>132を勝手にいただいて書きなおした。
1/3になったんで>>135の時は相当おかしなこと考えてたんだな。
マダマダ修行が足りない。Orz

お題：
長方形状の盤面が与えられますので、その中に畳を敷いて下さい。
ただし、畳の縁が盤面を突っ切ってはいけません。

例：
5x6の場合、この盤面は矢印で示した2箇所がNG。
┌┬┬─┬┬┐
││├┬┤││
├┴┤│├┴┤
├┬┴┼┼─┤←
│├─┤├─┤
└┴─┴┴─┘
　　　　　　↑
一方、この盤面は突っ切りがないのでOK。
┌─┬┬─┬┐
├┬┤├─┤│
││├┴┬┼┤
├┼┴┬┤││
│├─┤├┴┤
└┴─┴┴─┘

入出力の形式：
自由です。標準入出力でもファイルでもソースに直書きでも構いません。

ヒント：
対称盤面を除かずにカウントした場合、条件に当てはまる盤面数は次の通り。
5x6→6個
5x8→108個
6x6→0個
6x7→124個

>>148
再帰関数で解こうと思ったがうまく敷き詰めるのもできないなー。
リファレンス求む。

>>149
リファレンス……模範解答ってことか？
参考になるかは分からんが、昔Cで書いたのがこんな感じ。
(stdin部分をコメントアウトしている)
http://codepad.org/csbtDZ5M

あ、ID出ないから分かりづらいけど>>150は私です

>>150-151
あら、ちゃんと出来てるなー。
俺は謎のバグが取れなくて泣いてるよ。なぜだーーー。
あと、どういうのが正常系の配列なのかの定義がよくわからん。

>>152
「突っ切る」イメージは>>148以上に説明しようがないのが辛いところです
（要するに、全ての縦/横の筋に対して、1枚でも畳が横切っていればOKということ）
どう実装するかは頭を捻ってもらうしか……

Ideonの調子が悪い。
正直、ギブアップなので、コード晒そうと思ったんだが。。。
これでは収まりが付かないので移植してみるか。
万が一うまく言ったらアップする。

>>152>>153
「盤の辺と同じ長さの直線が四辺以外に生じてはならない」とか、
「盤面を分断する直線はNG」とか、そういうことだと思う。

>>148の図を元にNGとされる直線を太線で示すとこうかな。
┌┬┬─┰┬┐
││├┬┨││
├┴┤│┠┴┤
┝┯┷┿╋━┥
│├─┤┠─┤
└┴─┴┸─┘

>>148 HSP
http://codepad.org/XjgdObG6

>>156
乙。HSPってこんなに重かったっけ……？
概説してくれると嬉しいかなって

>>157
HSP が遅いってのも少しはあるけど
アルゴリズムが悪いだけ

再帰呼び出しで畳をすべて敷き詰めてみてから
分断する線がないかどうかチェックしてる


縦方向に分断する線について考えるとき
横幅 ６ なら ５本 の可能性がある
畳を横向きに置いたとき
対応する縦線に対応するカウンタを増やす
最終的にカウンタが ０ の線があれば
分断されていると判断できる
横方向に分断する線についても同様に考える

カウンタを増やす理由は
１、０ だけでやると元に戻すときに変更前の値を保存しておかないといけないから
面倒くさいという理由

>>156 では畳に１〜 の番号を振って
カウンタも畳の番号と同じものを増減させてる

>>157
ttp://ideone.com/jZJoae
ベターCに移植してみた。設計いいから簡単だった。変換がちょっとややこしいけど。
移植してみた感想？うーん。わからん！利点は、グローバル変数が消えました。位・・・。Orz
チャック関数が何やってるのかサッパリわからん。

うーん。脱力。
ttp://ideone.com/IZDTEt
上のようなコードを移植前に書いていたがダサすぎる。
俺に才能をクレ。Orz

>>158
あー、私が書いたコードの場合はちゃんと枝刈りするから速いんでしょうね……
(明らかにこれは駄目だ、と判定されたら次の畳を置かない)
>>159
check関数では、「明らかに駄目」な盤面ならfalse(0)を返すようにしています
盤面データは、「0なら置かれていない、1以上(畳の番号)なら置かれている」として、
水平・垂直方向にそれぞれ走査してチェックしています。……まあ要するに、
「筋の両側のペアを見て、もし筋の両側が完全には埋まっていなかったり、
筋を跨ぐ方向に畳が存在した場合はチェックをパスする(駄目扱いしない)」
ってことなんですけどね

>> 148 Python
import itertools, copy
def f148(tate, yoko):
　　area = [[None for y in range(yoko)] for x in range(tate)]
　　result = dict()
　　def f148r(area, tate, yoko, n=0):
　　　　for x,y in itertools.product(range(yoko), range(tate)):
　　　　　　if not area[y][x]:
　　　　　　　　for (dx,dy) in [(1,0), (0,1)]:
　　　　　　　　　　if x+dx<yoko and y+dy<tate:
　　　　　　　　　　　　if not area[y+dy][x+dx]:
　　　　　　　　　　　　　　area_copy = copy.deepcopy(area)
　　　　　　　　　　　　　　area_copy[y][x], area_copy[y+dy][x+dx] = u"→↓"[dy], u"←↑"[dy]
　　　　　　　　　　　　　　f148r(area_copy, tate, yoko, n+1)
　　　　　　　　return
　　　　　　elif y != tate-1:
　　　　　　　　if x == yoko-1 and all(c in u"→←↑" for c in area[y]): return
　　　　　　else:
　　　　　　　　if x != yoko-1 and all(c in u"←↑↓" for c in [area[i][x] for i in range(len(area))]): return
　　　　else:
　　　　　　key = "".join("".join(line) for line in area)
　　　　　　if not result.has_key(key): result[key] = [1, area]
　　　　　　else: result[key][0] += 1
　　f148r(area, tate, yoko)
　　print "<result>", len(result.keys())
　　for key in sorted(result.keys(), lambda x,y: cmp(x[0],y[0]))[-3:]:
　　　　n,a = result[key]
　　　　print "(%d)" % (n)
　　　　for x in a: print "".join(x)
f148(6,7)

>>161 の出力(>>148また安価ミスったww)
<result> 124
(1)
↓↓→←↓→←
↑↑→←↑↓↓
↓→←→←↑↑
↑→←↓→←↓
→←↓↑→←↑
→←↑→←→←
(1)
↓→←→←→←
↑→←→←↓↓
→←→←↓↑↑
↓→←↓↑→←
↑→←↑→←↓
→←→←→←↑
(1)
↓→←→←→←
↑→←↓→←↓
→←↓↑→←↑
→←↑→←↓↓
↓↓→←↓↑↑
↑↑→←↑→←

>>160
解説ありがとう。参考にします。

>>156 を高速化
if x>=length(field) : x=0 : y++
↓
if x>=length(field) {
if y+1<length2(field) : if cnt_v(y)=0 : return
x=0
y++
}

>>114
＞trueと比較するのは個人的な流儀なのでこれは曲げれん。

記述性／可読性に関する個人的な見解に異論を挟むつもりはまったくないのだけれども、
こと、C/C++ に関しては true/false との比較では、単に可読性の問題ではすまないと考えているので、 >>113 が教条主義とはどうしても思えない。

歴史的事情なのかどうかは定かではないが、C/C++ では「true/false」は「非零／零」の対立に対応するので（isalpha() とかね）、
「== true」は、それをみただけで、「まずい」、と感じるセンスが必要なのかもしれないかと。

でも、最近、お題についていけないかわいそうな状態の私がこれ以上の意見を述べるのは、ここではちと身の程知らず
なにかお題を解いたら、これについてちょっと説明を考えてみますね、最近のお題は結構むずかしいなあ‥‥

で、クズが書いたプログラムは？

>>166
このスレでは　>>75 のみ

Qはもう棺桶に片足突っ込んでるな

system("ls -l ./prog");

お題：分母が自然数m以下の既約分数で0より大きく1より小さいものを小さい順にならべる。
m=3 -> 1/3,1/2,2/3
m=5 -> 1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5

>>166-167
もうクズ呼びでもいいやとでも思っているのだろうか……＞QZ

>>171
ム板のコテは自虐入ってるくせに非難されてもメゲないという地味にウザい性格の奴が多いようで

>>170
この問題いいの？
某所からのパクりじゃない？

>>170
ttp://ideone.com/0nAThz
保険にちょっと大げさに警告文書いておいた。訴訟もじさないなら流用してミソ。
>>173ソースプリーズ。
畳に比べたら簡単。ほぼC。

>>170 Common Lisp

(defun f (m)
(let ((rs (loop for n from 1 upto (1- m)
nconc (loop for d from 1 upto m for r = (/ n d) collect r))))
(sort (remove-duplicates (remove-if (complement (lambda (x) (< 0 x 1)))
rs))
#'<)))

(loop for m from 2 upto 10 do (format t "~D => ~S~%" m (f m)))

2 => (1/2)
3 => (1/3 1/2 2/3)
4 => (1/4 1/3 1/2 2/3 3/4)
5 => (1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5)
6 => (1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6)
7 => (1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7)

このスレは解答例無しでもOKになったの？

>>176
回答者の気まぐれによる。
あった方がいい。

無いほうがいい

一応出題者が一回解いてる前提で俺は回答している。

>>170 Haskell
import Data.List (nub, sort)
import Data.Ratio

f170 :: Integral a => a -> [Ratio a]
f170 m = sort . nub $ [a % b | b <- [2..m], a <- [1..b-1]]

main :: IO ()
main = flip mapM_ [3,5] $ print . f170
-- [1 % 3,1 % 2,2 % 3]
-- [1 % 5,1 % 4,1 % 3,2 % 5,1 % 2,3 % 5,2 % 3,3 % 4,4 % 5]

>>170 Squeak Smalltalk
| fractions |
fractions := [:m | ((2 to: m) gather: [:n | (1 to: n-1) / n]) asSet asSortedArray].
fractions value: 3. "=> {(1/3) . (1/2) . (2/3)} "
fractions value: 5. "=> {(1/5) . (1/4) . (1/3) . (2/5) . (1/2) . (3/5) . (2/3) . (3/4) . (4/5)} "

>>170 with PythonSf

m=3; ts(); sorted({`1r nmrtr/dnmntr for dnmntr in range(1,m+1) for nmrtr in range(1,dnmntr)})
===============================
[1/3, 1/2, 2/3]

m=5; ts(); sorted({`1r nmrtr/dnmntr for dnmntr in range(1,m+1) for nmrtr in range(1,dnmntr)})
===============================
[1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5]

>>170 Io
f:=method(m,g(0,1,1,1,m))
g:=method(a,b,c,d,n,
if(b+d<=n,
g(a,b,a+c,b+d,n)
write(a+c,"/",b+d," ")
g(a+c,b+d,c,d,n)
)
)

Io> f(3)
1/3 1/2 2/3 ==> false
Io> f(5)
1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 ==> false

俺がろくでもないこと書いたばかりに。うっ・・・うっ。っていうのは置いといて。
みんな、どうやって既約判定してるのか全然読めない俺の頭が恨めしい。
>>173が逃げたのでブラフは一応気にしなくていいよ。このスレ内ではね。

>>170 HSP
#module
#deffunc swap var a, var b, local c
c=a : a=b : b=c
return
#defcfunc gcd int a, int b
if b=0 : return a
return gcd(b, a\b)
#defcfunc f170 int n, local i, local j, local ans_double, local ans_frac, local ans_count, local ret
for i, 2, n+1
for j, 1, i
if gcd(j, i)=1 {
ans_double(ans_count)=double(j)/i
ans_frac(ans_count)=strf("%d/%d", j, i)
ans_count++
}
next
next
sdim ret
for i, 0, ans_count
for j, 0, ans_count-1-i
if ans_double(j)>ans_double(j+1) {
swap ans_double(j), ans_double(j+1)
swap ans_frac(j), ans_frac(j+1)
}
next
ret=strf("%s ", ans_frac(ans_count-1-i))+ret
next
return ret
#global
mes f170(3)
mes f170(5)

使ってくれてありがと。
いやー、ほんとユーグリッドの互除法無しでどうやって既約判定してるのか全然読めんわ。
なんか他アルゴリズムあるんだろうけど、俺にはわからないなー。Orz
ほんっと、数学ダメなんだよね。

>>170 J
f=:3 :'~./:~(#~1&>),%/~x:>:i.y'

f 3
1r3 1r2 2r3
f 5
1r5 1r4 1r3 2r5 1r2 3r5 2r3 3r4 4r5

>>170 HSP
#module
#deffunc ans_add double d, str f, array ans_double, array ans_frac, var ans_count, local i, local j
for i, 0, ans_count
if ans_double(i)=d : return
if ans_double.i>d : _break
next
for j, ans_count, i, -1
ans_double(j)=ans_double(j-1)
ans_frac(j)=ans_frac(j-1)
next
ans_double(i)=d
ans_frac(i)=f
ans_count++
return

#defcfunc f170 int n, local i, local j, local ans_double, local ans_frac, local ans_count
for i, 2, n+1
for j, 1, i
d=double(j)/i
f=strf("%d/%d", j, i)
ans_add d, f, ans_double, ans_frac, ans_count
next
next
sdim ret
repeat ans_count
ret+=ans_frac(cnt)+" "
loop
return ret
#global
mes f170(3)
mes f170(5)

うむ。ちと気持ち悪かったか。
ホント、何もしないって。

ごめん
何言ってるのか分からんかったが >>174 みてきたら分かったｗ

あー、そういうことなら良かった。杞憂でした。
たまたま被ったのか。そーりー。
これでしばらく黙ります。しーゆー。

最後に一言。
慣れないことはするもんじゃないね。トホホ・・・。Orz

>>184
>>175ですが、既約分数の判定は(陽には)していません。Common Lispでは除算
の結果が整数で表せない場合、分数が返されますが、それらは既に約分されて
います(他の分数を扱える言語やライブラリでもそうなんじゃないかな)。

(/ 2 4) ;=> 1/2
;; リテラルでも
2/4 ;=> 1/2

なので、分子(n)と分母(d)を列挙してそれらを除算(/ n d)した数のリストをま
ず作り、そこから重複要素を取除くことで目的の結果を得ています。

>>170の元ネタはこれかな。こっちは 0以上1以下 で、ソートは要件に入ってない。

結城浩の日記 - 2003年12月30日 (火) - 既約分数
http://www.hyuki.com/diary/dia0312.html#i30

Scheme:数遊び:既約分数
http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3A%E6%95%B0%E9%81%8A%E3%81%B3%3A%E6%97%A2%E7%B4%84%E5%88%86%E6%95%B0
上記問題に対するSchemeによる回答。
「Haskellによるエレガントな解法」へのリンクがあったらしいが404。一つだけInternet Archiveに残ってた。
http://web.archive.org/web/20060513102938/http://www.sampou.org/cgi-bin/cahier.cgi?Cahier%3a2004-01-02

黙るって言ったけど、返信する矛盾。
>>193
まず、反省なんだけど。
俺、既約って言うことについてWikipediaで読んだくらいの知識しか無いんだわ。
>>193読んでてそう言えば小学校で習ったかもと思い出した。俺、算数もできなくなってるよ。Orz
んで、やっぱり高級言語はそうでないとね。C系列はライブラリなさすぎなんだよなぁ。
解説ありがとう。色々納得いっていい勉強になりました。

アルゴリズムはこうか。
既約とは分数の約分がすでに終わっていることである。
分母分子の小さなものの答えが小さい方から貯めていって、
すでにあったらそれは分母分子が規約分数の倍数である。
なのでそれを取り除く。って感じか。

なるほど。前は違うこと考えて解いてたわ。（汗

>>170
ttp://ideone.com/g49nVI
コードは思うところがあって共変しようと思って>>188を参考に書いてみた。
これで循環。キモいな俺。

>>194
ソースありがとう。
なんかのコンテストじゃなくてよかったよ。

>>195
std::map 使えばいいのにｗ

>>196
あ、やっぱ言われた。
書き終わって、あーこれエラトステネスの篩と同じ系統だ。
と理解して納得したまでが今日のハイライト。

まぁ、暇なので書いてみるよ。

>>170,196
ttp://ideone.com/gP0wYa
書いたよ。アルゴリズムの理解が済んでると早いね。ただ合ってるかしらんけど。
ソートはMapが勝手にやってくれるので手でやる必要がない。
それくらいかな。

>>170 Perl
http://ideone.com/iozPxO

>>170 Lua >>198のやり方で
function f(m)
local r={}
for i=m,2,-1 do
for j=i-1,1,-1 do r[j/i]=j.."/"..i end
end
local d={}
for k,v in pairs(r) do table.insert(d,k) end
table.sort(d)
for i,v in pairs(d) do io.write(r[v].." ") end
print()
end

> f(3)
1/3 1/2 2/3
> f(5)
1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5

お題：乗算の筆算
入力：2つの正整数
出力：筆算の計算過程（例：http://codepad.org/lPPcBt2p）

>>201 HSP
#module
#defcfunc n_str str s, int n, local buf
sdim buf
repeat n
buf+=s
loop
return buf

#deffunc f171 int a, int b_, local result, local result_len, local b, local x
b=b_
result=a*b
result_len=strlen(str(result))
mes strf(strf(" %%%dd", result_len), a)
mes strf(strf("x%%%dd", result_len), b)
mes n_str("-", result_len+1)
repeat
if b=0 : break
x=a*(b\10)
if x : mes strf(strf(" %%%dd", result_len-cnt), x)
b=b/10
loop
mes n_str("-", result_len+1)
mes strf(strf(" %%%dd", result_len), result)
return
#global

f171 1234, 567
f171 1234, 1001

>>201 C++
#include <cstdio>
#include <cmath>
unsigned int GetUIntLen(unsigned int x) {
unsigned int len = 0;
do {len++, x /= 10;} while (x);
return len;
}
void OutputSpace(unsigned int len) {
for (unsigned int i = 0; i < len; i++) std::putchar(' ');
}
void OutputLine(unsigned int len) {
for (unsigned int i = 0; i < len; i++) std::putchar('-'); std::putchar('\n');
}
void func(unsigned int a, unsigned int b) {
unsigned int ans = a * b, a_len = GetUIntLen(a), b_len = GetUIntLen(b), ans_len = GetUIntLen(ans), DelSpace = 0, zero, output;
std::putchar(' '), OutputSpace(ans_len - a_len), std::printf("%u\n", a);
std::putchar('x'), OutputSpace(ans_len - b_len), std::printf("%u\n", b);
for (OutputLine(ans_len + 1), zero = 0; b; DelSpace += 1 + zero, zero = 0, b /= 10) {
while (b % 10 == 0) {zero++, b /= 10;}
output = a * (b % 10) * std::pow(10, zero);
if (GetUIntLen(output / std::pow(10, zero)) == a_len) std::putchar(' ');
OutputSpace(ans_len - a_len - DelSpace - zero), std::printf("%u\n", output);
}
OutputLine(ans_len + 1), std::printf(" %u\n", ans);
}
int main() {
func(1234u, 567u), func(1234u, 1001u), func(99u, 909090u);
return 0;
}

>>201
; Common Lisp
(defun f (n m)
(let* ((result (* n m))
(length (1+ (length (princ-to-string result))))
(kugiri (make-string length :initial-element #\-)))
(format t "~@?~%x~@?~%~a~%~@?~a~% ~d~%"
(format nil "~~~dd" length) n
(format nil "~~~dd" (1- length)) m
kugiri
(format nil "~~{~~~d@a~%~~}" length)
(loop for c across (nreverse (princ-to-string m))
for zero = 0 then (if (zerop i) (1+ zero) 0)
for space = 0 then (if (zerop i) space (1+ space))
for i = (* n (parse-integer (string c)))
unless (zerop i)
collect
(concatenate 'string
(princ-to-string i)
(make-string zero :initial-element #\0)
(make-string space :initial-element #\ )))
kugiri
result)))

ttp://ideone.com/ZhgnC7
ほぼC。速度で負けてしまったが、まぁいいんだ。
今回は表示系頑張ったよ。データが適当なので扱うの大変かも。
っていうか、コード片の流用禁止な。アルゴリズムは別にいいよ。
っていうかあってるか？

>>201 Perl
http://ideone.com/N9C270

>>201 Python
def f201(a, b):
　　mid = [(i, a*long(s)) for (i,s) in enumerate(reversed(str(b))) if s != "0"]
　　res = long(a)*long(b)
　　w = len(str(res)) + len("x")
　　aa = [str(a), str(b), "-"*w] + [str(x) + " "*i for (i,x) in mid] + ["-"*w, str(res), ""]
　　ss = ["".join(list(s)).rjust(w) for s in aa]
　　ss[1] = "x" + ss[1][1:]
　　for s in ss:
　　　　print s

f201(1234, 567)
f201(1234, 1001)
f201(12, 1999808070605040302010) #otsu

ごめん、ちょっと違ってたので修正。
http://ideone.com/ruEXDp

>>201 C
#include <stdio.h>
#define SPACE(n) (&"________________________________"[32-(n)]) /* ほんとは下線=SP */
#define BAR(n) (&"--------------------------------\n"[32-(n)])
static int len(unsigned long long x) {
　　int n; for (n = 0; n++, x /= 10, x;); return n;
}
static void f201(unsigned int a, unsigned int b) {
　　unsigned long long d, ans = (unsigned long long)a*b;
　　unsigned int i, n, w = len(ans);
　　printf(" %s%d\n", SPACE(w-len(a)), a);
　　printf("x%s%d\n", SPACE(w-len(b)), b);
　　printf(BAR(w+1));
　　for (i = 0, n = len(b); i < n; b /= 10, i++)
　　　　if (d = (b % 10))
　　　　　　printf(" %s%lld%s\n", SPACE(w-i-len(d*a)), d*a, SPACE(i));
　　printf(BAR(w+1));
　　printf(" %s%lld\n\n", SPACE(w-len(ans)), ans);
}
int main(void) {
　　f201(1234, 567);
　　f201(1234, 1001);
　　return 0;
}

>>208
筆算過程のヒネリ具合がなんか面白い。
C++にも多倍長演算入ってほしい。

>>201 Squeak Smalltalk
| hissan |
hissan := [:a :b |
　 | res bar |
　 a := a asString. b := b asString.
　 res := {a. b. a * b} asOrderedCollection.
　 res add: (bar := String new: (res last size max: res second size + 2) withAll: $-) before: res last.
　 res := res collect: [:each | each forceTo: bar size paddingStartWith: $_].
　 res second at: 1 put: $x.
　 (b asArray collectWithIndex: [:dig :idx | a * dig asString forceTo: bar size - b size + idx paddingStartWith: $_])
　 　 do: [:each | each asInteger isZero ifFalse: [res add: each after: bar]].
　 res add: bar before: res last; asStringWithCr].

hissan value: 1234 value: 567.

=>
__1234
x__567
------
__8638
_7404
6170
------
699678

お題：与えられた数列を以下のルールで縮小せよ
(a) 4つ以上連続した数を消す (複数ある場合は一番左を優先する)
(b) (a)を繰り返す
例：
-------
in : 11233344433331111143322211
out:
11233344433331111143322211
1123334441111143322211
11233344443322211
1123333322211
11222211
1111

-------
in : 1122224411112222
out:
1122224411112222
114411112222
11442222
1144
-------
in : 211222211333312
out:
211222211333312
21111333312
2333312
212

>>212
ttp://ideone.com/XqaHUW
ほぼC。今回は消去法で実装。あってるかな？
一ラインずつでももっと一気にガッツリ消したほうが早いと思う。

あ、そしたら答え変わっちゃうか・・・。Orz

>>212 Perl
use 5.016;
use warnings;

sub f {
my $d = $_[-1];
return ($d =~ s/(\d)\1{3,}// ? f(@_, $d) : @_);
}

say join("\n", f('11233344433331111143322211'));
say join("\n", f('1122224411112222'));
say join("\n", f('211222211333312'));

>>212 C++
#include <iostream>
#include <string>
#include <cstddef>
#define NUM 4
void func(std::string s) {
std::size_t p, i, n;
char c;
std::cout << s << '\n';
for (p = 0; p < s.size(); ) {
c = s[p];
for (i = p + 1, n = 1; c == s[i]; i++, n++);
if (n >= NUM) {
s.erase(p, n);
std::cout << s << '\n';
p = 0;
} else {
p++;
}
}
std::cout << "-------" << '\n';
}
int main() {
func("11233344433331111143322211");
func("1122224411112222");
func("211222211333312");
return 0;
}

>>212
途中解も出す必要があるのが面倒くさい……
C++で書こうかと思ったがだるいのでHSPに変更
http://codepad.org/u9j7BfcR

>>216
無駄な検索してた
p++;
↓
p += n;

>>212 Lua
f <- function(s)
local r = 1
while r == 1 do
print(s)
s,r = s:gsub("(.)%1%1%1","",1)
end
end

> f("211222211333312")
211222211333312
21111333312
2333312
212

>>212 Squeak Smalltalk
| dropQuad |
dropQuad := [:str |
　 | ra idx |
　 Transcript showln: str.
　 ra := str asString.
　 [(idx := (ra := ra as: RunArray) runs findFirst: [:len | len >= 4]) isZero] whileFalse: [
　 　 ra runs at: idx put: 0.
　 　 Transcript showln: (ra := ra as: String)
　 ]
].

Transcript open.
dropQuad value: 11233344433331111143322211.
dropQuad value: 1122224411112222.
dropQuad value: 211222211333312.

ideon重たいねぇ。ここ以外だとわんどぼっくすか。うーん。
VCと同等の環境ってなかなか置いてないね。
未満だとCodepad使えばいいんだけど。foreachとauto使えないのはやだなー。

>>219
間違えた。
f　<- は　f =　です。

>>212
Python 3
http://ideone.com/ZNq2Hz

お題：HRタグを使って楕円を描くHTMLコードを生成する。

ショートコーディング向きじゃない気がしますけどいかがでしょうか？

>>224
http://ideone.com/Ry0hWl
文句ばっか言ってるのもアレなんで、一応書いたよ。
最初に言っておくが美的センスは絶望的だ。
JSで書いたほうが効率的だな。書かないけど。
動作確認はIE11でやった。汚い縦伸びが見えた。
以上だ。

>>224
これってfizzbizzみたいに凝って書いたほうが評価高いの？

fizzbizzみたいなのって凝って書いたほうが評価高いの？

>>224 Io
f:=method(a,b,
for(y,-a,a,
writeln("<hr width=\"",(((1-y*y/(a*a))*b*b)sqrt*40)round,"\">")
)
)

>>228
あれはいかようにも書けるけど、設計を見る問題だと思ってるよ。
関数で書くより、オブジェクト思考で設計すると相当難易度上がる。
だから、熟練プログラマほど難しいんだってさ。

>>230の流れならば

お題：http://toro.2ch.net/test/read.cgi/tech/1364631733/12
Java: http://toro.2ch.net/test/read.cgi/tech/1313183984/190,191
C++: http://toro.2ch.net/test/read.cgi/tech/1313183984/730

>>224 Perl
use 5.016;
use warnings;

sub hr { qq{<hr style="padding: 0; margin: 0 auto; width: $_[0]">\n} }
sub _width { map{ int(sqrt((1 - ($_ / $_[1]) ** 2) * $_[0] ** 2)) } (0 .. $_[1] - 1) }
sub f { sub{ map{ hr($_ * 2) } (reverse(@_), @_[1 .. $#_]) }->(_width($_[0] / 2, $_[1] / 2 + 1)) }

say f(240, 80);

>>224 Python
import math
def f224(a, b, c=0.0):
　　""" 楕円を<hr>で表示するHTMLを出力
　　楕円 : (x/a)^2 + (y/b)^2 + 2*c*(x/a)*(y/b) = 1
　　ある y における x の座標: x = a*(c*y/b + sqrt((c*c-1)*y/b + 1))
　　y の範囲(最大値) : y = b/sqrt(1-c*c)
　　"""
　　a, b, c = [float(x) for x in (a, b, min(c,1.0))]
　　qq = []
　　max_y = b / math.sqrt(1-c*c)
　　for i in range(int(-max_y-0.5), int(max_y+0.5)+1):
　　　　Y = float(i) / b
　　　　D = max((c*c - 1.0)*Y*Y + 1.0, 0)
　　　　x1 = a*(-c*Y - math.sqrt(D))
　　　　x2 = a*(-c*Y + math.sqrt(D))
　　　　qq.append((x1, x2-x1))
　　
　　ofs = min(x1 for (x1,w) in qq)
　　qq = [(int(x1-ofs+0.5), int(w)) for (x1,w) in qq]
　　print "<html>\n<head>\n</head>\n<body>"
　　for (x,w) in qq:
　　　　print "<hr width=%d align=left style=\"margin-left:%dpx;\">" % (w, x)
　　print "</body>\n</html>"

f224(300,20,0.5)

>>233 修正
誤　a, b, c = [float(x) for x in (a, b, min(c,1.0))]
正　a, b, c = [float(x) for x in (a, b, min(max(c,-1.0),1.0))]

>>233
cが何を表しているのか解らなかったので実行してみた。
おお、傾きの度合いだったのか。

>>231 Squeak Smalltalk
| trait |
trait := Trait named: #FizzBuzz uses: #() category: 'FizzBuzz-Traits'.

trait compile: 'fizzBuzz: spec
　 | assoc |
　 (self isKindOf: Integer) ifTrue: [Processor activeProcess environmentAt: #fizzBuzz put: self->''''].
　 assoc := Processor activeProcess environmentAt: #fizzBuzz.
　 ^(assoc key isDivisibleBy: spec key)
　 　 ifTrue: [assoc value: assoc value, spec value; value]
　 　 ifFalse: [assoc value ifEmpty: [assoc key]]'.

trait compile: 'fizz ^self fizzBuzz: 3->''Fizz'''.
trait compile: 'buzz ^self fizzBuzz: 5->''Buzz'''.
trait compile: 'gizz ^self fizzBuzz: 7->''Gizz'''.

{Integer. String} do: [:class | class uses: trait].

1 fizz buzz. "=> 1 "
3 fizz buzz. "=> 'Fizz' "
5 fizz buzz. "=> 'Buzz' "
15 fizz buzz. "=> 'FizzBuzz' "
7 fizz buzz gizz. "=> 'Gizz' "
21 fizz buzz gizz. "=> 'FizzGizz' "
35 fizz buzz gizz. "=> 'BuzzGizz' "
105 fizz buzz gizz. "=> 'FizzBuzzGizz' "
105 fizz gizz buzz. "=> 'FizzGizzBuzz' "

>>231
999.fizz.buzz は "Fizz" の間違い？

>>237
失礼しました、ご指摘のとおり問題の間違いです。
3 でも 5 でも 7 でも割り切れなかったら、その数字をそのまま出力ください。

1
Fizz
Buzz
Gizz
FizzBuzz
FizzGizz
BuzzGizz
FizzBuzzGizz
997

>>231 Ruby >>236のパクリ
module FizzBuzz
def fizz_buzz(spec)
Thread.current[:fizzbuzz] = [self, ""] if kind_of?(Integer)
state = Thread.current[:fizzbuzz]
state[0] % spec[0] == 0 ?
state[1] += spec[1] :
(state[1].empty? ? state[0] : state[1])
end

def fizz; fizz_buzz([3, "Fizz"]) end
def buzz; fizz_buzz([5, "Buzz"]) end
def gizz; fizz_buzz([7, "Gizz"]) end
end

[Integer, String].each{ |klass| klass.include(FizzBuzz) }

1.fizz.buzz #=> 1
3.fizz.buzz #=> "Fizz"
5.fizz.buzz #=> "Buzz"
15.fizz.buzz #=> "FizzBuzz"
7.fizz.buzz.gizz #=> "Gizz"
21.fizz.buzz.gizz #=> "FizzGizz"
35.fizz.buzz.gizz #=> "BuzzGizz"
105.fizz.buzz.gizz #=> "FizzBuzzGizz"
105.fizz.gizz.buzz #=> "FizzGizzBuzz"
999.fizz.buzz #=> "Fizz"

>>231
そのJavaとかC++の解答例ってお題の要求仕様を無視してないか？
双方ともオープンクラスじゃないから、buzz(fizz(1)) で 1、
buzz(fizz(15)) で "FIzzBuzz" とかを返せるようにしないと。

>>231
ttp://ideone.com/qcjk9X
C++。自分が真面目に設計すると大体こんな感じになる。実装手抜きだけど。
一応簡単に拡張できるようにはなってるんだが、必要だっただろうか・・・。Orz

そう言えば、FizzBizzだと思ってたら、よく見るとFizzBuzzだった罰ゲーム。orz

今回真面目に作ったから、結構真面目に罵ってほしいなぁ。
そのほうが勉強になる。

>>243
>>240

>>231 Java >>240に従って>>239を参考に
http://ideone.com/Osyt5g

>>244
なるほど、これだったらクラスつかうんじゃなかったな。
>>245を参考にさせてもらう。

>>240
ま、評価結果自体を切り替えるのがホンモノですが、確かにその域までは無理でした‥‥

>>240,244-245
ttp://ideone.com/AZIcMU
ベターC。これであってると思う？保守性メチャクチャ悪いんだけど。
今回はちゃんとBuzzにしたよ！

クイズはいったんネタバレしちゃうとつまらないな…
逆に、スレッドローカル以外での実現方法はないものか。
換言すると、副作用を許さない関数型では絶対無理なんだろうか？

Q%Aサイトつくるかね？

>>231 Python
class FizzBuzzInt(int):
　　def __init__(self, number, tests={"fizz":3, "buzz":5, "gizz":7}):
　　　　self.number = number
　　　　self.tests = tests
　　　　self.strings = []
　　def test(self, name):
　　　　if (self.number % self.tests[name]) == 0:
　　　　　　self.strings.append(name.capitalize())
　　　　return self
　　def __getattr__(self, name):
　　　　if name not in self.tests.keys():
　　　　　　raise AttributeError
　　　　return self.test(name)
　　def __str__(self):
　　　　if self.strings:
　　　　　　return "".join(self.strings)
　　　　return int.__str__(self)

def fizz(x):
　　if not isinstance(x, FizzBuzzInt): x = FizzBuzzInt(x)
　　return x.test("fizz")
def buzz(x):
　　if not isinstance(x, FizzBuzzInt): x = FizzBuzzInt(x)
　　return x.test("buzz")
def gizz(x):
　　if not isinstance(x, FizzBuzzInt): x = FizzBuzzInt(x)
　　return x.test("gizz")

print gizz(buzz(fizz(15)))
print FizzBuzzInt(21).fizz.buzz.gizz
どっちの書き方でもできるようにしました。

>>239 fizz_buzz(spec)とかSmalltalkに引っ張られすぎてたので一部修正。
module FizzBuzz
def fizz_buzz(n, msg)
Thread.current[:fizzbuzz] = [self, ""] if kind_of?(Integer)
state = Thread.current[:fizzbuzz]
state[0] % n == 0 ? state[1] += msg : (state[1] == "" ? state[0] : state[1])
end

def fizz; fizz_buzz(3, "Fizz") end
def buzz; fizz_buzz(5, "Buzz") end
def gizz; fizz_buzz(7, "Gizz") end
end

[Integer, String].each{ |klass| klass.include(FizzBuzz) }

1.fizz.buzz #=> 1
3.fizz.buzz #=> "Fizz"
5.fizz.buzz #=> "Buzz"
15.fizz.buzz #=> "FizzBuzz"
7.fizz.buzz.gizz #=> "Gizz"
21.fizz.buzz.gizz #=> "FizzGizz"
35.fizz.buzz.gizz #=> "BuzzGizz"
105.fizz.buzz.gizz #=> "FizzBuzzGizz"
105.fizz.gizz.buzz #=> "FizzGizzBuzz"
999.fizz.buzz #=> "Fizz"

>>251
あー、これすげー。俺の実力では笑うしかない。
C++でやるときはどうすればいいかなー。
グローバル変数なしだとつらいなー。むー。

1.fizz.buzz + 2 #=> 3
15.fizz.buzz.gizz + "XXX" #=> "FizzBuzzXXX"

もしくは

buzz(fizz(1)) + 2 #=> 3
gizz(buzz(fizz(15))) + "XXX" #=> "FizzBuzzXXX"

となるかどうかで、要件を満たしているかが分かるからチェックしてみるといいと思うよ

>>254
>>236
1 fizz buzz + 2. "=> 3 "
(1 fizz buzz + 2 buzz) fizz. "=> 'Fizz' "
15 fizz buzz, 'XXX'. "=> 'FizzBuzzXXX' "

呼び出し方色々あって面白いね。C++はそう言うのないから。。。
intはプリミティブ型でいかなるプロパティとかメソッドとか持ってないんだよ。
そういうのは全部ライブラリ関数とかの仕事なんだ。
DにはUFCSっていうのが有るんだけどね。

あー、>>253のこれっていうのは、関数形式とクラス形式の両立。

俺　=>　>>253,256-257　ね。

>>230
FizzBuzzみたいな処理をオブジェクト思考で設計する同僚とか嫌すぎねぇ？
そういう書き方もできる頭を持った人間はそれはそれで有用だろうけど
必要もないのにそういう書き方する奴の書いたコードなんて触りたくない

>>259
そういうテストだからねぇ。

ちなみにそれを信じてとある会社の入社応募でサンプル提出したら落とされました。
C言語で原始的かつ素朴に書いたんだけど。
まぁ、あれ1個で審査しろって言ってもしょうがないけど。

>>260
FizzBuzzみたいな短いのは抜き打ちにその場でやらせるモノだろ。
まさか「あなたが書いたソースコードのサンプルを見せて下さい」
でFizzBuzz渡したのなら落とされて当然だけど、そんなことはない…よな？

>>261
それそれ。Orz
まぁ、今は無事ニートだ。祝ってくれ。LOL

>>231 Ruby 別解
http://ideone.com/4oU4k5

>>231 Perl

http://ideone.com/nj1VFQ

dualvarを使う
http://ideone.com/ITkg5t

>>262
よかった、捻ったFizzBuzz実装を求める会社は居なかったんだ・・・っ！
どんまい

>>231 Io
Fb := Object clone
Fb do(
n := nil
s := ""
f := method(x, a, b,
if(x type == "Number", n = x; s = "")
if(n % a == 0, s = s .. b, if(s == "", n, s))
)
)
fizz := method(Fb f(self, 3, "Fizz"))
buzz := method(Fb f(self, 5, "Buzz"))
gizz := method(Fb f(self, 7, "Gizz"))

>>266 　続き。実行結果。
Io> 1 fizz buzz
==> 1
Io> 3 fizz buzz
==> Fizz
Io> 5 fizz buzz
==> Buzz
Io> 15 fizz buzz
==> FizzBuzz
Io> 7 fizz buzz gizz
==> Gizz
Io> 21 fizz buzz gizz
==> FizzGizz
Io> 35 fizz buzz gizz
==> BuzzGizz
Io> 105 fizz buzz gizz
==> FizzBuzzGizz
Io> 105 fizz gizz buzz
==> FizzGizzBuzz

プログラミング雑談スレ♯+
http://toro.2ch.net/test/read.cgi/tech/1391921013/291

291 名前：デフォルトの名無しさん[sage] 投稿日：2014/02/23(日) 18:00:19.87
問題：
Windowsのエクスプローラでリネームすることな可能なファイル名をパラメータとして受け入れ、
それをファイル単位でechoした後に自身を同一のパラメータで再帰呼び出しするバッチファイルを作成せよ
エクスプローラ上でバッチファイルに対象ファイルをD&Dした際と同じルールでのクオートを想定すること
なお、cmd.exeの組み込みコマンド以外は使用を禁止する

実行例：
C:\>a.bat C:\^`!%&$()　001.txt "C:\^`!%&$() 002.txt"
C:\^`!%&$()　001.txt
"C:\^`!%&$() 002.txt"
C:\^`!%&$()　001.txt
"C:\^`!%&$() 002.txt"
(以下略)

でっていう。

% だの & だのをエスケープするのが面倒くさい
（つーか実行例の一行目の表記から期待する動作を引き出すのは無理かも）
ってことじゃないかね

2014年なんだからいい加減コマンドプロンプトじゃなくて
powershell使えよ

2014年なんだから Google chrome を使いましょう。

2014だからチン毛も逆立ついい女に出会えるぞ

>>264
dualvar を使ったシンプルな解法は Perl ならではですね。
Perl 嫌いだけどちょっと見直した。

お題：配列またはリストの複製をつくる。

>>275
% Prolog

リストの複製をつくる([],[]).
リストの複製をつくる([A|R1],[A|R2]) :- リストの複製を作る(R1,R2).

>>276
% Prolog

リストの複製をつくる(L1,L2) :- findall(A,member(A,L1),L2).

>>275
;;;Common Lisp
;;;リストの複製を作る

(defun Copy-list (lst)
(cond
((null lst) nil)
(t (cons (car lst)
(Copy-list (cdr lst))))))

>>275 Squeak Smalltalk には #copy #deepCopy #veryDeepCopy の三種類の複製メソッドがある。
| arr0 arr1 arr2 arr3 |
arr0 := #('a' 'b' 'c').
arr1 := arr0 copy. "配列のみ複製し、各要素は再利用（シャローコピー）"
arr2 := arr0 deepCopy. "各要素を単純に複製したものに置き換えた配列を作成"
arr3 := arr0 veryDeepCopy. "要素間の等価関係も維持しつつ配列を複製"
arr0 first at: 1 put: $X. "元配列の第1要素を破壊的に変更してみる"
{arr0. arr1. arr2. arr3}. "=> #(#('X' 'b' 'c') #('X' 'b' 'c') #('a' 'b' 'c') #('a' 'b' 'c')) "

arr0 := #('a' 'b' 'c' 'd').
arr0 first == arr0 fourth. "=> false "
arr0 at: 4 put: arr0 first. "第4要素を第1要素に置き換え"
arr0 first == arr0 fourth. "=> true "
arr1 := arr0 copy.
arr2 := arr0 deepCopy.
arr3 := arr0 veryDeepCopy.
arr0 first at: 1 put: $X.
arr2 first at: 1 put: $Y.
arr3 first at: 1 put: $Z.
{arr0. arr1. arr2. arr3}. "=> #(#('X' 'b' 'c' 'X') #('X' 'b' 'c' 'X') #('Y' 'b' 'c' 'a') #('Z' 'b' 'c' 'Z')) "

arr0 := #('a' 'b' 'c' 'd').
arr0 at: 4 put: arr0. "第4要素を自分自身に置き換え"
arr0 fourth == arr0. "=> true "
arr1 := arr0 copy.
"arr2 := arr0 deepCopy. => 無限ループ "
arr3 := arr0 veryDeepCopy.
{arr1 fourth == arr1. arr3 fourth == arr3}. "=> #(false true) "
{arr1 fourth == arr0. arr2 fourth == arr0}. "=> #(true false) "

>>275
ttp://ideone.com/MTSKdh
C++。配列の複製とstd::vectorの複製とvectorへ変換。
配列は扱いが面倒なので普段は使いません。STLを使いましょう。
境界線系のチェックもSTLなら簡単！

>>275 Perl
sub f { map{ (ref $_ eq 'ARRAY') ? [ f(@{$_}) ] : $_ } @_ }

お題：1からnのn個の連続した整数をシャッフルして適当に選んだ2個をとりのぞく。
のこりの数からとりのぞいた2個の数を求める。
例
3,1,2,6 -> 4,5

>>282
それ、入力があらかじめ与えられていないとインチキできませんかね……？
(まっとうに考えれば「シャッフル(O(N))してバケットソート(O(N)後、先頭から見ていって足りない2数を探す(O(N))」
　でいいが、「シャッフル(O(N))してから最後尾2つ以外を出力してから最後尾2つを出力する」という
　操作で「同じ表示」になる)

>>282
ソート禁止とは書いてないですね。
練習がてら書いてみるか。

ああ、もしソート禁止だとすると線形探索連打(O(N^2))しかないねこれ
ビットボードとかですらバケットソートに該当するし

ttp://ideone.com/HhGJ5s
C++。ピットボードで実装してみたんだが。遅かったか。
これより小さいコード書くのは結構大変だと思う。
std::vector<bool>の実装がタコだったりするので泣けるが。

>>282,285
ttp://ideone.com/7YIxZx
ほぼC。遅い方を実装してみた。
ついでにドロップ値を可変にしてみた。
メモリは確かに食わないがプロセッサ依存ですなー。

これアレだ。
今から数字いうから抜けてるやつを探してね。
って言って高速で数字言って混乱させるやつだ。

>>282 HSP
#module
#deffunc swap var a, var b, local c
c=a : a=b : b=c
return
#deffunc f282_ready array nums, int n, local work
repeat n
work(cnt)=cnt+1
swap work(cnt), work(rnd(cnt+1))
loop
dim nums, n-2
memcpy nums, work, 4*(n-2)
return
#defcfunc f282 array nums, local is_exist, local result, local result_num
dim is_exist, length(nums)+2+1
foreach nums
is_exist(nums(cnt))=1
loop
repeat length(nums)+2, 1
if is_exist(cnt)=0 {
result(result_num)=cnt
result_num++
}
loop
return arr2str(result)
#defcfunc arr2str array arr, local buf
sdim buf
foreach arr : buf+=strf("%d,", arr(cnt)) : loop
return buf
#global
f282_ready nums, 20
mes arr2str(nums) + " -> " + f282(nums)

>>282 Squeak Smalltalk
| n collection |
n := 6.
collection := (1 to: n) asOrderedCollection shuffled.
2 timesRepeat: [collection remove: collection atRandom].
^collection asArray -> ((1 to: n) difference: collection) "=> #(1 4 3 6)->#(2 5) "

>>282 Perl
use 5.016;
use warnings;
use List::Util qw(shuffle);

sub f {
my ($n) = @_;
my @list = (shuffle 1 .. $n)[ 2 .. $n - 1 ];

my @bin;
@bin[@list] = (1) x @list;

return [ @list ], [ grep{ !$bin[$_] } (1 .. $n) ];
}

say join ' -> ', map{ join ',', @{$_} } f(6);

>>282 R
f <- function(x){(1:(length(x)+2))[-x]}

> f(c(3,1,2,6))
[1] 4 5
> f(sample(1:1000000,1000000-2))
[1] 348288 977984

お題：長辺の長さがa、短辺の長さがbの長方形が納まる楕円の面積の最小値を求める。
例
a=31.0, b=2.0 -> 97.39
a=28.0, b=5.0 -> 219..91

>>292 訂正
> a=28.0, b=5.0 -> 219..91
a=28.0, b=5.0 -> 219.91

お題：第一引数を評価せず第二引数を返す関数やマクロを作る

>>292
数学的に解いた http://ideone.com/ZhzaJi
三分探索 http://ideone.com/Ph6MBb

>>294
ttp://ideone.com/m0kcsp
C++。こういうの必要なのってlisperあたりか？
>>292は俺には解けねぇOrz　>>295マジスゲー。

すまん、>>295がどういう計算したのか誰か教えてくれないか

>>297
まず一辺が１の正方形を囲む円の半径について考えると
半径 ｒ＝√２／２ → 面積Ｓ＝πｒ＾２＝ π／２

長辺方向にａ倍する
πａ／２

短辺方向にｂ倍する
πａｂ／２

完成！

その理屈(カバリエリの原理の応用)かｗ
三平方とかいろいろ考えてたはｗｗｗｗ

お題：次のような規則の配列でインデックス番号ｉの配列の値を求める。
・インデックス番号1の配列の値A(1)は1である。
・配列の値は昇順である。
・インデックス番号iの配列の値A(i)は配列内のiの個数である。
例
A(10) -> 5
A(100) -> 21
A(1000) -> 86

>>300
暗号すぎる。

あぁ、3番見落としてた

>>300
質問。一個の1000に一個の100は含まれているか？

グダグダ書いて悪いね。
多分、多倍長演算できないと無理なので、C++いつも書いてるが降りる。

やっぱりよくわからん。

>>300
ttp://ideone.com/FzkgAH
ほぼC。こういうことじゃないよね？

理解不能

出題者でてきてー。

>>300 こういうことでいいのかな
#include <iostream>
#include <vector>

using namespace std;

int A(unsigned int i)
{
vector<int> v(1, 1);
while (v.size() < i) {
v.insert(v.end(), v[v.back() - 1], v.back() + 1);
}
return v[i - 1];
}

int main()
{
cout << A(10) << endl;
cout << A(100) << endl;
cout << A(1000) << endl;
}

微妙にバグってたので修正
int A(unsigned int i)
{
vector<int> v(4);
v[0] = 0;
v[1] = 1;
v[2] = v[3] = 2;
while (v.size() <= i) {
v.insert(v.end(), v[v.back()], v.back() + 1);
}
return v[i];
}

>>309
その発想はなかった。なるほど。
そういう数列か。

>>310
解けなかった身であんまりチャチャ入れたくないんだが、
push_back使うとそういう最初にどれだけ確保したとか考えなくていいよ。

>>309-311
すまん、解説を頼む

えーっと、数字をインクリメントしてくカウンタを一つ用意する。
そのカウンタと同じ数だけ配列にそのカウンタの数を後ろに追加していく。
と、いう無限数列が有るわけだ。
その数列の10番目と100番目と1000番目を求めよという話だった。
条件としてA[1]が1である。ZEROの扱いが不定なのは出題者の不備だろう。

と、いうことだと思うんだが・・・。

って、俺が書いたらやばかったな。
>>309-310こそ勝者だ！

なんとなくわかったが、それを>>300から読み取るなんてエスパーや

Haskell http://ideone.com/E9K7EB
アルゴリズムあってるかわからん

>>317
f300 = [0,1,2,2] ++ f 3
こうしないと、でだしの数列がおかしい。

1オリジンのようだから、

A(10) -> 4
A(100) -> 14
A(1000) -> 45

が正しいのではないか。

A(1)->1
A(2)->2
A(3)->2
A(4)->3
A(5)->3
A(6)->4
A(7)->4
A(8)->4
A(9)->5
A(10)->5
A(11)->5
こうじゃない。

>>320
3が2つから始まるの？
122333444455555666666
こういう並びじゃないの？

>>321
「・インデックス番号iの配列の値A(i)は配列内のiの個数である。」から
A(3)->2 なので、数列に３は２つだけ

ttp://ideone.com/tSydPu
ほぼC。配列ですら無くてタダの関数だったのか？？
こういう感じかと思ったんだが、違うんだったら、>>314の数列は間違ってるな。
あるぅえー？謎は深まる。
なんかのローカルなセキュリティプロテクトか？これ。

>>322
理解した。>>314はミスリードしてるな。すまない。
すでに規定の配列を推測する問題だから、それでいいのか。
2の扱いに気づかなかったら解けないね。

ttp://ideone.com/VctS8c
ほぼC。モヤモヤしてたから自分流で書きなおした。
カッとなってやった今では反省している。
あーちくしょ。結構面白かったから自力で解きたかった。Orz

>>300 HSP
#module
#defcfunc f300 int i, local x
if length(s_ans)=1 : s_ans=0, 1, 2, 2
repeat
if length(s_ans)>i : break
x=s_ans(length(s_ans)-1)+1
repeat s_ans(x)
s_ans(length(s_ans))=x
loop
loop
return s_ans(i)
#global

mes f300(10)
mes f300(100)
mes f300(1000)

>>300 C
Wikipedia を見て

#include <stdio.h>
#include <math.h>
#define P (sqrt(5) / 2 + 0.5)

void f(int n) {
printf("%.f\n", pow(P, 2 - P) * pow(n, P - 1));
}

int main() {
f(10); // 5
f(100); // 21
f(1000); // 86
return 0;
}

>>327
申し訳ないがそのページ教えてください。

>>328
ここね
ttp://en.wikipedia.org/wiki/Golomb_sequence

※参考
http://pgf2.blogspot.jp/2011/08/blog-post.html

>>300 Squeak Smalltalk。Rubyでいうところの特異クラス（メソッド）的機構であるUniClassで。
| A |
A := OrderedCollection withAll: #(1 2 2).
A assureUniClass class compile: 'at: idx
　 [self size >= idx] whileFalse: [
　 　 | next |
　 　 next := self last + 1.
　 　 (self at: next) timesRepeat: [self add: next]].
　 ^super at: idx'.
#(10 100 1000 1000000) collect: [:idx | A at: idx] "=> #(5 21 86 6137) "

>>300 Perl
http://ideone.com/hmU8pn

>>329-330
アドレスありがとう。
なるほど。綺麗な数式があるのか。
しかし、微妙に出来損ないの数列に見えるな。
応用はまだ無いのかな。なんかに使えるかなぁ？？
最初見た時はセキュリティ暗号の一種に見えたんだよね。
こういう汚い規則性って直感的じゃないからね。ふむむ。

>>300
ttp://ideone.com/bB0qJR
ほぼC。
と、いうわけで、>>329に書いてあるColin Mallows式で。

>>300 Python
def f300(n):
　　A = [1]
　　while len(A) < n:
　　　　i = p = A[-1] + 1
　　　　if i <= len(A):
　　　　　　p = A[i-1]
　　　　A += [i] * p
　　return A[n-1]

print f300(10)
print f300(100)
print f300(1000)

>>300 C
#include <stdio.h>
int f300(int n) {
　　int len, val, p, s, a[1000]={1}; // 1*1 2*2 3*2 4*3 5*3 6*4 ...
　　for (len=1, val=1; len < n; len += (a[val-1]=p)) {
　　　　if (++val >= 1000) break;
　　　　p=2; if (len > 1) for (p=s=0; s < val; s+=a[p], p++);
　　}
　　return val;
}
int main(void) {
　　int i, TEST[] = {10,100,1000,};
　　for (i = 0; (size_t)i < sizeof(TEST)/sizeof(TEST[0]); i++)
　　　　printf("A(%d) = %d\n", TEST[i], f300(TEST[i]));
　　return 0;
}

お題
ウラムの螺旋を描くために、二次元整数格子上の点の数列を生成せよ。

数列例
[ 0., 0.] [ 1., 0.] [ 1., 1.] [ 0., 1.] [-1., 1.] [-1., 0.] [-1., -1.] [ 0., -1.] [ 1., -1.] [ 2., -1.] ...

この位置数列上の整数連番が素数のとき、その格子位置に印を描いていけばウラムの螺旋を描けます。

参考URL;;http://ja.wikipedia.org/wiki/ウラムの螺旋

>>337 の説明で、抜けが出た

この位置数列上の整数連番に対する印の付け方を isprime(n^2+n+1) など別のものに変
えてやれば、別の素数分布パターンを作れます。通常はランダム・パターンなるだけで
す。でも新しい素数分布パターンを見つけられたら、それを論文にできます。

>>338 の説明に追加
二次元ではなく、三次元整数格子上の位置数列を作れたら、別の素数パターンを見つけ
られるかもしれません。でも私の能力では、そのような位置数列を生成できませんでし
た。三次元整数格子上の位置数列を作れたら、是非とも教えてください。

>>337
前スレ>940の派生か?

>>340 前スレ>940の派生か?

前スレ>940 は知らんかった。

こっちの主題は素数分布のはなし。前スレでの格子点を覆う数列コードを持っているひ
とは、それで素数分布を表してくれ。それがウラムの螺旋と異なるパターンになるとき
は教えてくれ。

>>338 HSP
http://codepad.org/qEnUzuHN

描画系はシステムにグラフィックシステムがくんであると強いなぁ。
C++も簡易ウインドウライブラリ入りそうな気配は有るんだけどまだ何年も先の話だ。
非常にもどかしい。

ttp://ideone.com/wDU4Hj
ttp://eel.axfc.net/uploader/l/764163901231842/v/3189894.gif
ttp://www1.axfc.net/u/3189894.gif
ほぼC。グラフィックはほとんど扱わないから微妙にズレてるかも知れない。
こんな感じでいいのだろうか。Win32Apiは書きなおしてほしいなぁ。もーダサイ。
あと、axfcもあんまり扱わないので間違ってるかもしれない。

>>337 Perl
http://ideone.com/Mc2Q9F

現在プログラム板のID制導入の投票を実施中です
よろしくお願いします

プログラム板 強制ID制導入に関する投票スレ
http://kohada.2ch.net/test/read.cgi/vote/1394290844/

お題：引数を3個もつ関数をつくる。何をするかはおまかせします。

お洒落なお題だな

>>347
http://ideone.com/U4p3Nm
はいよ。C++。標準にはいってほしいと思ってる関数だ。ゲーム作るとき結構便利なのよ。
だいぶん前に考えたんだけど、どうにも広める手段がわからんのでここにさらしておく。

仕様は、Valueがいかなる値をとってもMin以上Max以下にはならないというもの。

>>349
お洒落な回答だね

わーい。褒められた〜。<3

>>349
template<typename T>const T& Limit(const T& lower, const T& upper, const T& value)
{
return std::min(std::max(value, std::min(lower, upper)), std::max(lower, upper));
}

>>352
ウマイことまとめたね。
俺が、引数の大小関係をうまく処理できないので3項演算子で処理してるわけなんだが。
おー、すばらしい。賞賛する。

パラメータがぴったり３つ必要な例を考えてみたけどいいのが中々思いつかない
２つならいくらでもあるし、３つ必要な場合は大抵４つ以上でも考えられるやつだ

>>347
3引数と言えばやっぱりたらい回し関数っしょ→
http://codepad.org/iowOAtSa

>>355
wikipedia 経由で‥‥http://d.hatena.ne.jp/aike/20111112

>>347 >>349 R
f <- function(a,b,c){median(c(a,b,c))}

あれ？IDつくようになったのね。

>>358
>>346

ふむ。そう言えば賛成書いておいたわ。

つきみとか言う変更人キャップが無理やり却下した挙句、
自演で議論誘導しようとして失敗して最後は辞任で逃走なんて騒ぎもあったがな
おそらく告知はやれ程度の話を議論でsageレス多ければ却下とかに拡大解釈したんだろうけど
Win32APIスレの無申告削除といい、この板に関わってるボランティアって一体どうなってんだ…

去年の名前変更事件を主だすね
おかげで高笑いさせていただいた

ヘタに権力を持つものではないってことかね。
日本人の性格を顧みて、陰湿な因子を持ったシステムはダメなんだろう。
明示的なことに弱いんだから明示的にするべき。実名は嫌だが。
それに適応できなければ先は暗いと思うし。まぁ、IDあれば当分は大丈夫だろう。

削除はせめてあぼーんにしてくれないとレスアンカーがめちゃくちゃになるよね

そだねー。雰囲気が悪くなるかもシレンけどね。
利便性との兼ね合いがちょっと難しい話だね。

お題：平面上の２つの点をゼロ個以上のひとつながりの連結された線分で結ぶ。
線分の連結部分は線分の端っこでなければならない。
線分の傾きは水平線の向きから30度刻みに制限される。
連結に使う線分の全体は点対称であり、中心点を中心に180回転すると一致する。
連結に使う線分は以上の条件を満たす最短距離でなければならない。
与えられた２つの点の座標値から連結に使う線分全部の座標値を求めよ。

線分は三本で充分

Cゲンガーの逆襲II！！
興味のあるベンチマークを作ってみよう。
なんでもいいです。コンピュータをイジメる欲望にしたがってベンチマークを作ってみましょう。
ベンチマークといったらタライ=竹内関数とかアッカーマン関数とかが有名ですが、
気が向いたら創作してみるのもいいじゃないですか。
貴方は何をつくりますか？
*見どころ。*
・速度向き極最適化後に重いほど良い。
・コーディングで手を抜いたら減点。
・なるべく読めるコードにしましょう。

発表時には、アルゴリズムについて一言ください。

*エラトステネスの篩ベンチ。*
5000個生成して更に最後に生成した数字から更に+50000プラスした数字の次の素数を求めた。
キャパシティは64bit整数です。それするとメモリもソレくらい必要になりますが。
追記型エラトステネスの篩を設計してみました。
作った後これクラス化できるナーと思ったけどヤってないです。
ttp://ideone.com/AtMDRS
ウチのPCでは15秒ほどかかります。

あー、同時にバグ情報なども募集中です。

>>368
「経過時間は777ミリ秒だ！」ってideoneさんが言ってたんだけど……

>>370
ソレはideonさんが良いPC使ってるからだよ。数字上げればもっと重くなるよ。
ゾロ目なのはたまたまでいい数字だと思うよ。
10000万個生成した後100000万まで生成してみたらIdeonさんがランタイムエラー吐いたので減らしたんだよ。
多分出力が多すぎたんだ。
で、どれくらい重いといいと思う？

>>368
274ミリ秒でした

っていうか>>370もナイスなベンチマークつくろう。（提案

>>372
なかなかいいPC使ってるね。俺も良いPCほしいよ。
これ、どっちかって言うと処理も食うけど単純にメモリもガッツリ食うんだよね。
規模を大きくするとボトルネックになるのはどっちかって言うとメモリ量。
ちなみに、大きな素数はお金になるよ。数学的知見がいるけど。

さて、測るのはイイ。秤をつくろう。

>>373
じゃあちょっとこのパズルのソルバ作ってくんない？
大きな盤面（ページ内の画像ぐらいの規模）になると急に回答時間が長くなるから困ってるんだ……
http://www4.ocn.ne.jp/~pachalle/paperchalleran126.html
http://www4.ocn.ne.jp/~pachalle/paperchalleran127.html

Haswell i5-4670K定格使用+DDR3-12800 16GB
i7にしようと思ったんだけどHTとL3キャッシュの事でベンチマーク厨じゃないから
これでいいやと妥協
その気になれば差し替えられるし

>>376
いや、俺はもうベンチ作ったから、あんた作ってよ。www
普通に重み付き経路問題で再帰処理をループに置き換えれば大きな迷路もイケルと思うよ。
ただ、普通の重みなし経路問題でも2000*2000位のやつをペインターアルゴリズムで解くと結構重いよ。
C#でランダム重みなし迷路作ってMSペイントに解かせた事あるんだよ。
普通にフリーズしたわ。

>>378
これただの経路問題じゃないんだわ……
「最短」じゃなくて「最高得点」を目指すから経路はかなり長くできるし、
交差点は二度通れるからクヌース先生のZDDすら使えないんだわ……

ベンチマークとしてはシミュレーションとかはどう？
二次元におけるラプラス方程式を陽的に解くやつを最近書いたから、
他人がどこまで書けるか興味ある。要するに連立方程式を解くだけなんだけどね

サンプル(windows.h使ってるからcodepadじゃ動かない)→http://codepad.org/wWHQDJXo

>>377
おぉいいね。最新構成じゃない。
俺もスカイレークが出たら変えようと思っている。
来年の話なのでまだ我慢！

>>379
設計の要点として、通ったところを壁にする。ッて言うことかな。
壁はビットで持っておくと1変数に4枚入るよ。
ちなみにこれ全通り試行しないと答えでないタイプじゃないの？

暇だから作ってみるか。期待すんなよ〜。
データ入力するのメンドクサ。

>>381
全通り出さないと駄目なタイプだからキツイでござる……
ビット操作も使ってるんだけど
と言うかいわゆる「計算量が爆発的に増大」するタイプだから小さい盤面でテストすることを推奨
>>382
確かにデータ構造を考えるのも入力するのも大変だった
自分の場合は入力データを↓のような感じにして、入力用コードを複雑にして対処している
----------
3 4
*3 +3
+5 -2 +1
*3 +1
-2 +5 +6
+7 +9
+7 +2 +7
-2 +6
----------

データ入力終わらん。何地獄だこれ。
うわわーん。

ttp://ideone.com/EEPhtH
データ入力して力尽きた。
これよく考えたら巡回セールスマン問題ライクなやつじゃねーか。
そりゃベンチになるけど、俺のターンは終わってるよ〜。

後は再帰的に解いてくだけなんだけど、再帰関数では足りないのでループで書かないとダメだな。
とにかく、データ入力は脳弱になるー。

この前の畳をヒントにすれば速度は出るかなーと思うけど、メモリが馬鹿にならん。
明日、覚えてたら続きやる。

>>368
これはエラトステネスの篩ではないよ

>>386
え？まじで？素数間違ってる？
エラトステネスの篩って、低い方の素数で整数を割ってくんだよね。
あれ？

>>383
ギブアップ。素直に、経路問題的手法で解こうと思ったんだが。
ttp://ideone.com/pVs5KO
エラトステネスの篩じゃないって言われて思考全部吹き飛んだ。www
エラトステネスの篩については、
完全なアルゴリズムだからここ数年考察していて最近納得行くコードがかけるようになったんだ。
それ否定されちゃったら結構大変だ。どこがバグってるか是非聞きたい。

>>371
あー、この発言バグってる・・・。
10000万じゃなくて、1万。100000万じゃなくて10万。
うほぉおおおお。ごめんなさい。

>>388
大昔に書いた最初のバージョン→http://codepad.org/Pky6fZZl
1、2ヶ月ほど掛けて高速化したバージョン→http://codepad.org/KUHgY3K3

実は、中学時代に当該画像
（http://www4.ocn.ne.jp/~pachalle/paperchalleran126.html）
を授業で解かされたことがあって、その時から最適解がどれだけか凄く
気になってたんだよね。最終的に下の経路が最適解（4091点）だと分かったんだけど、
http://i.imgur.com/mi86JzL.png
それが分かるまでにi7-4770K×100（学校のやつ）をマルチスレッドで動かして
5時間ほど掛かった……とんでもない難問だった……

エラトステネスの篩は後で書いてみます。

>>390
エラトステネスの篩は簡単だよ〜。
数字の半分までの素数を判別すればいいからマルチスレッド化も可能。同期機構いるけどね。
メモ化すればメモリ食うけど超高速になる。高強度暗号創造して君も大金持ちだ。

しかし、中学や高校からC言語できるとはいい環境ですなー。しかも機材が素晴らしい。
自分の時はBASICだったもん。しかもコンピュータクラブ入らないと扱えなかった。
C言語は専門行ってから覚えたし、ひたすら模写して覚えたもんだ。（遠い目
最初ポケコンでプログラム覚えたから、1ソース200行以上扱えないんだよね俺。
ローテクすぎる。

俺マルチスレッドプログラミングってできないんだよね。
C++標準化待ちしてる間にドンドン時代遅れになってくわ。
君、結構ハイスペックだな。

とりあえず>>386の召喚待ち。
結局、どういう意味だったのかわからなくて寝てないんだよ。
さすがにそろそろ辛くなってきた。むはぁ〜。

>>391
>ハイスペック
いやそれほどでも……私もコード書き始めたのは中学からHSPでですし

>>エラトステネスの篩
よし出来た。自環境(i5-3210M、64bitWin7、VS2013)では
MaxNumber=1000000にしても15.12秒（表示部分を抜いたら0.069秒)だった。
なお計測は「don - 簡易経過時間計測ユーティリティ」
(http://cetus.sakura.ne.jp/softlab/toolbox2/)を使用。
http://ideone.com/SwJLoq

>>393
おっさん流小言。。。
newするのやめよう。配列構造はvector、ツリー構造はset一族、list構造はlist一族をつかおう。これらはコンテナという。
<limits>のstd::numeric_limitsを使おう。C++標準定義の定数が得られる。
<cstdint>を使おうintはstd:::int32_t、unsigned intはstd::uint32_tを使おう。C/C++を使うからにはメモリのサイズも目を配ろう。
時間関係は<chrono>にお任せ。時計も取れます。
これらは標準なのでソース互換性が向上するよ。
C++は大きく行ってC++98、C++03、C++11、C++14、C++17。という規格があって大きな機能もそれに準じる。今はC++11が主流でC++14が準備中。未来では更に増えるだろう。

逆にSqrtMaxNumberはイイ最適化だね。ただ、!=だと切りの悪い数字で止まらなくなることがあるかも知れない。
大なり記号で制御したほうが安心。C++は生配列だとなかなかオーバーランで例外吐いて落ちるってことが無いからね。
コンテナだと違うんだけどね。

と、言うわけで今思いついた小言でした。

>>393
そだそだ。結構良いタイム出してるな。
俺もPC変えたい！Core2DuoE8500だよ。。。

*エラトステネスベンチ ver 0.3α*
ttp://ideone.com/0WsxkP
バージョンアーップ。

>>393の最適化をパクってみたら10倍位早くなった。吹いたわ。
ソレにともなって試験値を向上。
N200000まで生成後100000個追加で生成するように順番を入れ替えた。
これで改良まえと同じくらいの負荷になった。
あと、無意味にstd::map使ってたのをstd::setに差し替え。これは無知だった。
こういうことって有るんだねー。

これは「試し割り法」って言って、「エラトステネスの篩」とは別物。

ああ表示時間込みで15秒なのか
なら大差ないじゃん
計算時間だけならHaswellでも2倍ほどしか行かなかった

エラトステネスの篩か‥‥
なんだかんだいっていつも人気者だね

素数ってそんなに素敵なんだろうか？素数の勉強って数学のどの分野？

>>394
ん、newよりコンテナの方が速いですかね？
「!=」の部分は別にループの判定条件とは関係ありませんので問題ないかと。
<chrono>等は参考にさせてもらいます。
とりあえず書き直してみました。（注：MaxNumber=1000000だと0.005秒ほど）
http://ideone.com/VQVins
>>397
篩も2〜√nまで試したら終了だったと思うんだけど……
>>399
数論じゃね？
まあ今時は数論も「役立つ」分野だからな……

呼ばれた気がしたが
何言ってんだコイツって気分になった

おはよう。
>>397
何が違うのかワカラナイです。Orz
>>399
暗号とか知っとくとお金になるかもよ。RSAとかあのへん。
まぁ、完全なアルゴリズムだからね。簡単だし。
>>400
コンテナのほうが安全。
C言語系はバグでコンピュータをハード的にぶち壊せる言語なので一応気をつけるのだ。
まぁ、ハード的にぶち壊すのも結構大変だけどね。メモリ書き換えでOSの挙動変わることは結構あるよ。

>おはよう
ID:v5V8kLPfの生活リズムが、私気になります！
>何が違うのか
試し割り法→素数判定、もしくは素因数分解のために2〜√nまで順に割っていく手法
エラトステネスの篩→素因数の性質を利用した試し割り法のメモ化Ver、みたいなもの
前者は素因数分解法としても素数判定法としても素朴すぎてちょっとアレ
（大きな数相手だと性能が悪い≒遅い）
後者はメモリをビシバシ食うが素数一覧を出す用としてはかなり速い

>>403
ただの夜型人間だよ。昨日はたまたま昼も起きてたんだ。
うーん。わからん。Orz
ちとネット見てくる。

ウィキペディア見て分かった。
試し割り方は、素数を持つことが真で、
エラトステネスの篩は素数じゃない方を重視するのが真なんだな。
たぶん。
勘違いしてた。どっちもエラトステネスの篩の括りだとおもってたけど、名前ついてたとは。
エラトステネスのほうはまともなbitvectorあれば超高速だな。
追記型にするのはちと面倒だけども。
寝足りなくて頭回らん。。。Orz

わり算をしたらエラトステネスじゃなくてもう試し割りでしょう。
それゆえエラトステネスは高速になるわけです。
ただかわりにメモリを消費するので、それをどう節約するかが
工夫のしどころかと。
フラグにビットを使っても、ちょっと大きな素数を探すと
すぐメモリがあふれちゃいますし無駄が多いです。

>>400
＞まあ今時は数論も「役立つ」分野だからな……
考えてみれば、女王様も実は龍＋馬の無敵駒だったね

　　 |=番兵|_
　　（　・ω・）　＜ｽﾃﾝﾊﾞｰｲ
　　○=｛=｝〇,
　 　|:::::::::＼, ', ´
､､､､し ､､､((（.＠）

>>406
ビットに割り付ける数を小さい素数で篩っておけば多少は圧縮できるとかか
2の倍数を除外で作業用バイト数×16(8*2/1)とか
2と3の倍数を除外で作業用バイト数×24(8*2*3/2)とか
2と3と5の倍数を除外で作業用バイト数×30(8*2*3*5/8)とか
1GBも使えば30,000,000,000以下はカバーできる計算

ビットコイン採掘を高速にするソフト

>>409
2, 3, 5, 7 版がこちらに。
http://www.rsok.com/~jrm/printprimes.html

専門書ならなんでも目が回るような気がする‥‥ああ、困ったなあ

数学なんて、すうがくなんて・・・。うぅ。Orz

お題：以下の関数があるとしてf(x,y)の値からx,yを求める。
　　　　　x+y
f(x,y) = (�煤@n) + x　　　　(x≧0, y≧0)
　　　　　n=0
例
39 -> x=3, y=5
2014 -> x=61, y=1
246909876 -> x=12345, y=9876

>>414 C

#include <stdio.h>
#include <math.h>

void f(n){
int z = (sqrt(8 * n + 1) - 1) / 2;
int x = n - (z + 1) * z / 2;
printf("x=%d, y=%d\n", x, z - x);
}

int main(){
f(39);
f(2014);
f(246909876);
return 0;
}

す　う　が　く　な　ん　て　・　・　・　Orz
導関数とかマッタク理屈がわからん・・・。＼(^o^)／ｵﾜﾀ

>>368　いず　みー
ttp://ideone.com/stwHzp
ベンチマーク作ったよ。
これぞ究極の圧縮展開アルゴリズム！しかも可逆！！！ただし、o(N!)だ。
現在のC++では20バイト程度しか圧縮できない。
それでもかなりかかる。
軽いなーと思ったら、MakeData()の数字を上げてみましょう。
多倍長はいっても、何メガバイトまで圧縮できるのやら・・・。

＊順列圧縮＊
バイナリをとあるソート済みの配列の順列の途中経過であると仮定する。
ならば、バイナリを順列にかければ1週の間に最低一回はソート済みの数列になるのではないか。
という理論を思いつきまして、書いてみたんですよ。
採算分岐点は3kb程度、o(3000!)とかふざけてるが、それ以上になるとなんでも概ね3kb程度に収まる。
とにかく順列が馬鹿みたいに重いのでこれを高速化できればストレージ問題はほぼ解消する。
ランレングスこそ過去にして未来だったのだ。
と、いう感じです。

>>417
まさかお前……ブロックソートを知らないとでも言うのか……
まあアッチはO(n)かO(nloglogn)かO(nlogn)だけど。ベンチマークなら無駄に重くても別にいいのか

高速化する気全くないだろw

お題：>>417を高速化せよ

>>420
高速化も何も、思いっきりnext_permutation(STL)に依存しているじゃないですかー！

>>417
20文字越えると順列の序数がstd::uint64_tを超えるからこのコードでは死ぬんじゃないか？
>>418
変換後のデータ列に何番目の順列かって情報も含まれるからブロックソートとは違うな
あとブロックソートでは同じ文字が連続しやすいだけで連続すると確定してるわけじゃない
>>421
そこは脱STLするとかで。

>>422
まあブロックソートとは違うのは知ってる
それとブロックソートの方がずっと速いことも知ってる
……ああそうか、無駄に重いから高速化する実験にもってこいなのかｗ
ちょっと検討してみますね

>>422
yes!20バイトしか圧縮できないのはじぶんの手落ちでございます。
多倍長演算できないと自分には扱えない。
そして、O（N!）で死ぬ。

>>417になんで名前欄はいってるんだ。
間違ってないけど、入れる気はなかった。

>>418
名前は聞いたこと有るんだけど、理論がどういうものかはサッパリ。
数学なんてぇ〜。

>>425
要するに巡回シフトした文字列をソートすればええんやでー
http://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AD%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88
http://www.atmarkit.co.jp/ait/articles/0904/02/news113.html
http://www.geocities.jp/m_hiroi/light/pyalgo48.html
ガチな圧縮プログラムにも使われる優秀なアルゴリズムだったりする

>>426
なんとなく理解した。
配列を右か左に一回ずつシフトしていった履歴一列をXに展開するようにY方向へ並べていって、
まじめにソートされた列をX方向へY方向に観測しながら見つける。

これすごい発想だけど、メモリがN*N必要じゃん。
順列するより早いけど、ランレングスで1ブロックに1KBかかるな。
オンメモリの場合メモリ4Gで64kしか圧縮できなくないか？でも1/64なら相当か。
むむむ・・・・。

あぁ、頑張れば1/128いけるな。

>>427
消費メモリもケチろうと思えばずっとケチれる
本気でやりたければググって情報を集めることが肝心

>>426を参考に符号化はできた。
なんで完全にソートされネーんだーと悩んでたが、そういうものだったのね。
ランレングスは完全にソートされてないと効果薄いんだよな。

>>429
本業じゃないのでお遊びだけど、なかなか悩まされる。

>>427
既に実装されている≒特性を生かしつつ現実的なオーダまで計算量やメモリ量を削減する方法がある
逆変換の仕組みが面白いよねコレ
ttp://research.preferred.jp/2012/11/burrows-wheeler-transform-lf-mapping/
ウェブレット木と組み合わせた応用で全文検索にも使えるそうだ
で、生物学方面では次世代シーケンスデータ解析などのバイオインフォマティクス分野では普通に使われているらしい
ttp://d.hatena.ne.jp/biochem_fan/20140306/1394127619
>>430
同一単語・文章のN+1文字目を頭にした文字列は同じ位置に固まるから、N文字目は結構固まってるはずだよ
後ろ3文字がユニークな並びである10文字の単語が10回分あるなら、10文字ブロックが7回出現する計算になるはず
生データや簡単なフィルタ出力と比較したら桁違いに高性能だと思うけどなぁ…

ttp://ideone.com/Afo3na
バグってる。C++。
ベンチつくろうと思ってブロックソーティング実装してたんだが、ランダムデータ時にうまくいかねー。
とりあえずローテーションがうまくいってないのかよくわからん。
あー、もういいや。投げる。変換ばっか考えてたら頭死んだ。

>>431
そういう応用考えられるってすごいね。
ただ、メモリを削減するのに毎回苦心するのはやだなー。
マトリクス使わない実装が待たれるところだな。

　　 |=番兵|_
　　（　・ω・）　＜ｽﾃﾝﾊﾞｰｲ
　　○=｛=｝〇,
　 　|:::::::::＼, ', ´
､､､､し ､､､((（.＠）3% 5% 8%

お題：10進数を2進数にしてビットごどに反転したものを10進数に戻す。
例
1 -> 0
12345 -> 4038
256 -> 255

>>435
ttp://ideone.com/bIngPd
ほぼC。Xorはよくわからん。

>>435 HSP
#module
#defcfunc f435 int x, local y
y=x
y|=y>>1
y|=y>>2
y|=y>>4
y|=y>>8
y|=y>>16
return y-x
#global

mes f435(1)
mes f435(12345)
mes f435(256)

ttp://ideone.com/3J3ZjQ
ついでなんで、ブロックソーティングベンチのバグ取れた？？版を
合ってるかしらんけど復号のバグがとれたっぽい。
でも、なんかウマイことランレングスに適した形になったとは言いがたいな。
ハフマンはよくわからんし、とりあえず終了。

>>436
MakeBitOnArray()の引き数はその前段からintで充分じゃないかと。
ついでに言えば、return (std::uint64_t(1) << N) - 1; でいいべさ。

>>439
引数とかは趣味です。
まぁ確かにIntでもいいんですけど、マイナスとっちゃうと大変だなーとunsigned型にしたはずです。
後段は確かにそうかも。20分で書いたからスピード勝負であんまり設計に時間かけなかったんだよね。
とにかく、ご指摘ありがとう。参考にします。

>>438
乱数列は元々どんな圧縮アルゴリズムとも相性悪い。

ブロックソートは例えば「abcdef」って単語が100回出る文章を変換すると、
「bcdef【中略】a」が100行並んで結果「a」が100文字並び、
「cdef【中略】ab」が100行並んで結果「b」が100文字並び…て理屈でランレングスなどで圧縮しやすくなる。
乱数列では同じ文字の後に同じ並びがほぼ来ないから意味が無い。

ランレングスやスライド辞書は同じパターンの繰り返しを特定の記号で表すだけ。
乱数列では同じパターンがほぼ出て来ないから意味が無い。

ハフマン等の符号化は原文のビット列A(単語A)を出力ではビット列A’(略語A’)に置換するってだけ。
よく出現する原文のビット列(単語)に短い略語を当てたら出力も短くなるみたいな理屈。
注：原文のビット列(単語)は、通常原文を8ビット単位で区切って得られる256種の単語とかそういうノリなんで一般的な単語とは関係ない
乱数列では出現頻度が偏らないから短い略語を割り当てるべき入力語が無くてほぼ意味が無い。

>>435 Perl
use 5.016;
use warnings;

sub f { oct '0b' . join '', map{ $_ ^ 1 } split //, sprintf('%b', shift) }

say f(1);
say f(12345);
say f(256);

>>441
解説ありがとう。できればコードが間違ってるかどうかも検証していただけると非常に自信につながる。嫌なら嫌と。
で、そういえば、一様乱数だから偏り無いのか。圧縮の原理をすっかり失念していた。順列圧縮こそ至高と言いたいところだな。
関係ないけど、符号化時のメモリ量をN*2にする方法は思いついたんだけど、実装面倒でヤってない。
方法はネットにある方法とほぼ同じだと思いついてから気づいた。
でも、自己流だと、一個メモリ扱うクラス書かないといけないので面倒なんだ。Orz
まぁ、これで何かしようっていうアイディアもないのだけど、趣向としては面白かった。

>>443
＞符号化時のメモリ量をN*2にする方法
興味深い‥‥

>>444
いや簡単だよ。
ネットに書かれている通り、データの後ろに同じものをプッシュバックしてそれを長さNを仮想的に扱えるポインタコンテナ書くだけ。
あとはどうやってソートに耐えるデータ構造にするか。ということを考える。
というわけで、ポインタコンテナを自作しないといけないわけなのだ。俺流だとね・・・。

>>444
ttp://ideone.com/i7CpyV
と、言うわけで書いては見たもののGCCでは動かない。C++モドキ。
VCならそこはかとなく動いてる気がする。すげー自信ない。
普段から演算子オーバーロードやらないからサッパリわからん。
コンテナのソートがこんなに大変だったなんて・・・。Orz
ちなみに今回書いたコンテナのことを俺はゴーストメモリと呼んでます。
メモリそのものの所有権を主張しないので時たま便利ですね。

GCCのエラーはいみわからなさすぎる。慣れてないのもあるけど。

>>446
constメンバ関数にすればエラー消えたよ
constと非constの比較ってエラーに出てる

それとC++はメンバの並び順に初期化するけど、初期化リストがその順に
書いてないと警告を出すんでそれも直しといた
そんだけ

http://ideone.com/SfhtgY

ttp://ideone.com/49Ziod
>>447
ご指摘ありがとう。GCCは不慣れなので脳みそ停止してた。
こっちでも直してみたら治ったので今後の参考にします。
ありがとう。勉強になったよ。
ついでなんで直してくれたそのコードを貴方にライセンス致します。
対価はもうもらったんでもういらねーです。
内容は自己責任でお願いします。と、いうことで有効範囲は規定しません。
まぁ、こんな簡単にバグ潰せるんだったら自作簡単だと思うけどね。
で、なんかすごい圧縮ライブラリ作ってくださいよ。
それか、応用で自然言語解析とかで実績出してくれてもいいよ。
全部受け売りだけど。Orz

まぁ、俺は優しい人は好きなんだ。へへ。

しかし、省メモリにしたら自然と高速化されたなぁ。ベンチにするときゃどれくらい盛ればいいんだろう。
32BITで4Gアロケートできるときに大体2G程度のデータを処理できるくらいのものになった気がする。
元が64kbだったのに比べたら大分良くなったなぁ。
これ以上は自分のキャパシティ超えるので無理だなぁ。

まぁ、今日は満足したのでそろそろ寝るか。

Linuxではstd::random_deviceはちゃんと動くけど、MinGWでは-mtune=core-avx-i
オプションを付けないとRDRAND命令を使ってくれなくて、

http://www.cplusplus.com/reference/random/random_device/entropy/

これが0を返しちゃうな
Ivy-Bridge以降で正しく動くぜ

と思ったけど駄目だったorz
自分でRDRANDアセンブリルーチンをくっつけて呼び出すしかないや

+1612 (gcc4.8.1)
double
py() const noexcept
{ return 0.0; }

これじゃアカンな
gccの作者にアセンブリルーチン作って送りつけてやっか

>>450
ロートルVCユーザには関係ないはず。汗
パッチ書けるんだったら書いたほうがベターだねぇ。
俺にはちと無縁な話。

関係ないけど、>>448はGhostMemory自体は16バイトほどクラスストレージを食うのでもしかしたら、
16*Nバイト食うの計算にはいってないかも。結構バカにできんなー。

>>435 Io
Number f:=method((-self-1)&(2**(self log2 floor)-1))

Io> 1 f
==> 0
Io> 12345 f
==> 4038
Io> 256 f
==> 255

お題：http://toro.2ch.net/test/read.cgi/tech/1392388003/283
C: http://toro.2ch.net/test/read.cgi/tech/1392388003/284

つっこみその一：http://toro.2ch.net/test/read.cgi/tech/1392388003/286

>>453
ttp://ideone.com/Ir8Wdl
C言語。書いたは書いたんだが、VCとGCCで挙動が違う・・・。
更に小数点以下の挙動の制御ってあんまりヤったこと無いから誤差がボロボロ出てる。
この辺よくわからない・・・。Orz

お題：二次元配列を各行、各列ともに昇順になるように並べ替える。
例
1 5 3 4
0 4 1 0
7 2 3 1
　↓
0 0 1 4
1 2 3 5
1 3 4 7

>>455
その例じゃよく分からん……
レファレンスは無いの？

>>455 HSP
#module
#deffunc f455 array data, local w, local h, local work, local i, local j, local t
w=length(data)
h=length2(data)
dim work, w*h
for i, 0, h
memcpy work(w*i), data(0, i), 4*w
next
for i, 0, w*h
for j, 0, w*h-1-i
if work(j)>work(j+1) : t=work(j) : work(j)=work(j+1) : work(j+1)=t
next
next
for i, 0, h
memcpy data(0, i), work(w*i), 4*w
next
return
#global

dim data, 4, 3
data(0, 0)=1,5,3,4
data(0, 1)=0,4,1,0
data(0, 2)=7,2,3,1
f455 data
for y, 0, length2(data)
buf=""
for x, 0, length(data)
buf+=strf("%d ", data(x, y))
next
mes buf
next

縦ソート、横ソートと２回ソートやればできそうだが
もっと簡単な方法あるのかね

1 5 3 4
0 4 1 0
7 2 3 1
を
1 5 3 4 0 4 1 0 7 2 3 1
と１列にしてソートして
0 0 1 1 1 2 3 3 4 4 5 7
３列に分割する
0 0 1 1
1 2 3 3
4 4 5 7

>>458-459
x行y列の行列の場合、
縦横ソート→O(x log x) + O(y log y)
一列ソート→O((x + y) log (x + y))
となる。オーダは実質同じなので係数の問題？

x*log(x)+y*log(y) = log(x^x)+log(y^y)
(x+y)*log(x+y) = x*log(x+y)+y*log(x+y) = log((x+y)^x)+log((x+y)^y)

>>461
オーダーを単純に足し引きするのって意味あるんですかね……

まあ後者の方が遅くなる気はするが

よく分からないんだが(x+y)ってどっから出てきたんだ
一列にするならx*yじゃないの

>>463
そうだった……となると一列ソートはO(xy log xy)か
雑把にはn log nとn^2 log nだから明らかに後者の方が遅いね

縦横ソートも縦のソートは列の数だけ、横のソートは行の数だけやるんじゃないの

>>465
それもそうか。俺アホスｗｗｗｗ

>>459
これだと結果違わない？

>>455の示した答えと違うから間違いだね

答えはいくつもあります。
各行、各列が昇順であればokです。

>>469
じゃ、とりま縦ソート横ソートすれば大丈夫か
計算量(修正)はO(x*log(y)+y*log(x))かな
これ何か現実に活用できる問題だったりするの？

どっからその式が出てくるんだ

>>471
じゃ、O(x*y*log(y)+x*y*log(x))に修正

>>469の条件でよいなら>>459のやりかた(ソート1回)で十分でしょ

>>455 C++
>>458 のやり方で。
>>459 をやりたかったがわからなかった。

http://ideone.com/f5ahdZ

昇順になってなかったあばば

愚直なやり方

http://ideone.com/FrdgBI

>>455 C++
>>459 の方法で
http://ideone.com/cF31w0

>>455
ttp://ideone.com/slaSyu
ほぼC。>>458メソッドで書いてみた。できてる気がする。
見よ、渾身のバブルソートを！！
ちぐはぐな長さのジャグ配列食わせると落ちるので気をつけて。

>>455 Octave
列ごとにソートして行ごとにソートする
function z = f(x)
z = sort(sort(x), 2);
endfunction

一次元配列に直してソートしてから二次元配列に戻す
function z =　g(x)
a = size(x);
z = reshape(sort(x(:)), a(1), a(2));
endfunction

>>478
>ちぐはぐな長さのジャグ配列
そもそも元データは行列なんですがそれは

>>480
あー、オリジナルのデータ食わせるときね。

お題：二種類の文字からなる長さが奇数の文字列があるとき多数派の文字を求める。
例
aabaabbab -> a

>>482
どう書いてもO(n)は免れないのでなるべく単純に……
http://codepad.org/l5urRBhK

>>482 HSP
#module
#defcfunc f482 str s_, local s, local count, local c, local max_index, local is_valid
s=s_
dim count, 256
repeat strlen(s)
c=peek(s, cnt)
count(c)++
if max_index!c {
if count(max_index)=count(c) : is_valid=0
if count(max_index)<count(c) : max_index=c : is_valid=1
}
loop
return strf("%c", max_index*is_valid)
#global

mes f482("aabaabbab")

>>484
HSPなら、(長い文字列の場合)ループ回すよりそのまま置換した方が速くね？

;準備
StringBuffer = "aabaabbab"
sdim Char, 1, 2
dim Count, 2
;1種類目の文字を抽出
Char(0) = strmid(StringBuffer, 0, 1)
;strrep+strlenで各個数を数える
StringBuffer_ = StringBuffer
strrep StringBuffer_, Char(0), ""
Count(1) = strlen(StringBuffer_)
Count(0) = strlen(StringBuffer) - Count(1)
;2種類目の文字を検出して表示
Char(1) = strmid(StringBuffer_, 0, 1)
if(Count(0) > Count(1)){
　　mes StringBuffer + "->" + Char(0)
}else{
　　mes StringBuffer + "->" + Char(1)
}
stop

軽くベンチした結果、10000000バイトの文字列相手で、
>>484が6.634秒に対し>>485が0.391秒となった。
基本的にHSPは遅いので、命令を上手く使う方向で書いた方が速いです。

こういうこと？
#module
#defcfunc f482 str s_, local s, local char1, local char2
s=s_
char1=strmid(s, 0, 1)
strrep s, char1, ""
count1=stat
char2=strmid(s, 0, 1)
count2=strlen(s)
if count1>count2 : return char1
if count1<count2 : return char2
return ""
#global

mes f482("aabaabbab")

>>483
文字列の長さが事前に分かってるなら片方が過半数に達した時点で終われるんじゃないの？

>>483
なんで二重ループにするのはなぜなんだぜ
// C
#include <stdio.h>

#define ___ /*empty*/

char majorChar(const char* p) {
___ if (*p) {
___ ___ char cx = *p; // 先頭の文字は「一方の文字」で確定
___ ___ char cy = '\0'; // もう一方の文字（未定）
___ ___ int nx = 1;
___ ___ int ny = 0;
___ ___
___ ___ while (*++p) {
___ ___ ___ if (*p == cx) {
___ ___ ___ ___ ++nx;
___ ___ ___ }else{ ___ // 三種類以上は無いって信じてるぜ...
___ ___ ___ ___ if (!cy) cy = *p; // 毎回上書きのほうが効率いいかな??
___ ___ ___ ___ ++ny;
___ ___ ___ }
___ ___ }
___ ___ return (nx >= ny) ? cx : cy; // 偶数文字で同じ数だったら先頭の文字を返すぜ
___ }else{
___ ___ return '\0';
___ }
}
void main(void) {
___ char* given = "aabaabbab";
___ printf("%s -> %c\n", given, majorChar(given));
}

>>482
python3
http://codepad.org/fGHhbu15

>>490
賢いですね

>>484 バグってた
if count(max_index)=count(c) : is_valid=0
↓
if count(max_index)=count(c) : max_index=c : is_valid=0

>>482
ttp://ideone.com/2lFAWc
C++。先客がいたのでちょっとひねってみた。
O(2N)位？？オーダー計算はよくわからん。
毎度おなじみランダムデータ搭載。おまけです。
と、思ったら2種類限定だった・・・。Orz

>>488
その発想はあったわ……修正っと
http://codepad.org/oZiVUUFQ
>>489
よく見るんだぜ、内側ループはちゃんと終了後に抜けるからO(n)なんだぜ
俺だって2種類だと信じての実装なんだぜ
>>491
どこがだ、ソートはO(n log n)だろと

>>490
これはGJ。

>>491,495
>>488がヒントくれたから、思いついた

>>494
まぁ、コードをイッパイ書いてオーダー下げるのも手だが、
スマートなアルゴリズムで記述量を下げるのも高速化の手法では有る。
書いたら書いただけ処理量取られるからね。

>>482 Python
def f482(s):
　　return sorted(set(s), key=lambda x:s.count(x))[-1]
s = "aabaabbab"
print "%s -> %s" % (s, f482(s))

>>497
ま、記述量削った方が楽でいいわな……
スクリプト言語なんて特に、記述時間＋実行時間の
合計を短縮する方向性で作られているものだし

楽かと言われたらそうでもないよ。
2行を1行にするときの苦しみはソレはソレは楽しい瞬間だ。
まぁ、記述量減らすのはハッカーの本分でもあるので一度トライしてみるのがオススメ。

>>482 Haskell
import Data.Function (on)
import Data.List (sortBy)
import Data.Map (empty, toList, insertWith)

f :: String -> Char
f = fst . head . reverse . sortBy (on compare snd) . toList . foldl (flip $ flip (insertWith (+)) 1) empty

main :: IO ()
main = print $ f "aabaabbab"

>>501
head . reverse . sortBy (on compare snd) === maximumBy (on compare snd)

>>482 Perl
http://ideone.com/6he8zG

>>488
過半数に達したかどうか分かるのは最低でも全体の半分は検査が終わってる時点（aしか出現してないなど)
過半数判定そのものが１ループのコストより遥かに小さいものでないと速くならないが
実際は過半数判定がそれなりにコストのかかるものなので、過半数判定が無いものより高コストになるだけ

文字列検査の１ループは ループ処理のコスト[A]　＋　１文字判定・カウントのコスト[B]　＋　カウントが過半数に達したかの判定のコスト[C]

過半数判定なしは n×([A]+[B]) (文字列の最後まで検査)
過半数判定ありは m×([A]+[B]+[C]) (n/2 < m <= n)

過半数判定は前半部n/2では必要ないからループを前半部と後半部の２回に分けて
過半数判定ありは (n/2)×([A]+[B]) + m'×([A]+[B]+[C]) (0< m' < n/2)
とも出来るけど

m'×([A]+[B]+[C]) < (n/2)×([A]+[B]) になる確率はそんなに高くなさそうな気がするが

[A]はコスト 3 くらいか、[B]もコスト 3 くらい、[C]はコスト 2　くらいだとしたら
m'×8 < (n/2)×6 となるから m' < (3/4)×(n/2) ・・・ これは何なのか自分でも分からなくなった

>>482 Io
f:=method(s,
a := s at(0)
b := 0
c := 0
s foreach(v, c = c + if(a == v, 1, b = v; -1))
if(c > 0, a, b) asCharacter
)

Io> f("aabaabbab")
==> a

>>504
だったらベンチすればええやん……
まあ今回は処理が軽すぎてHSP(>>486)ですら役不足だが

サンプル数を100万位にふやしてみては？

立っているビットの数を数える

int count32bit(unsigned v) {
unsigned count = (v & 0x55555555) + ((v >> 1) & 0x55555555);
count = (count & 0x33333333) + ((count >> 2) & 0x33333333);
count = (count & 0x0f0f0f0f) + ((count >> 4) & 0x0f0f0f0f);
count = (count & 0x00ff00ff) + ((count >> 8) & 0x00ff00ff);
return (count & 0x0000ffff) + ((count >> 16) & 0x0000ffff);
}

int count64bit(unsigned __int64 v) {
unsigned __int64 count = (v & 0x5555555555555555) + ((v >> 1) & 0x5555555555555555);
count = (count & 0x3333333333333333) + ((count >> 2) & 0x3333333333333333);
count = (count & 0x0f0f0f0f0f0f0f0f) + ((count >> 4) & 0x0f0f0f0f0f0f0f0f);
count = (count & 0x00ff00ff00ff00ff) + ((count >> 8) & 0x00ff00ff00ff00ff);
count = (count & 0x0000ffff0000ffff) + ((count >> 16) & 0x0000ffff0000ffff);
return (int)((count & 0x00000000ffffffff) + ((count >> 32) & 0x00000000ffffffff));
}

http://marupeke296.com/TIPS_No17_Bit.html

>>504
過半数判定はCPUの中で完結するので「主処理で使わないCPUリソース内で処理できるなら」演算時間は増加しない。
入力がキャッシュに乗り切らない場合の主処理はメモリ速度が上限だから、CPUリソースが余る環境も普通にあるんじゃね？

>>482 Maxima
f(s):= (
a: sremove(charat(s, 1), s),
charat(if slength(s) / 2 < slength(a) then a else s, 1)
);

(%i20) f("aabaabbab");
(%o20) a

Cゲンガーの逆襲３。
トランプのカードを自分の手でシャッフルする様子をエミュレーションしてみましょう。
今回はヒンズーシャッフルを書いてみました。
http://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB_(%E3%82%AB%E3%83%BC%E3%83%89)

＊リファレンス＊
ttp://ideone.com/2abVbM
いい感じに偏った混ざり方してると思います。
ドヤァ！！

>>511 J
f=:3 :0
a=.(}.~?@#)@({.~>:@?@#)y
a,y-.a
)

f^:(10) i.52
23 25 26 27 28 41 42 43 44 45 46 47 48 49 50 51 13 29 30 31 32 33 34 35 36 37 38 10 11 12 14 15 16 17 18 40 39 5 6 7 8 9 19 20 21 22 24 0 1 2 3 4

発表するときはアルゴリズムについて一言お願いします。
と、かくの忘れました。Orz

>>512
ヒンズーシャッフルかな？相変わらずJはすさまじい言語だな。
読めないけど、この短さは素晴らしい。

>>511
せめて、「サラサラサラ」くらいの記述が欲しい。

>>435
今更ながら
言語はC
ideone.com/6CKmuQ

>>435
今更ながら
Schemeで
リスプ系初心者なのでよく言語をしらないので効率悪いだろうけど

ttp://ideone.com/imtVu8

お題
https://paiza.jp/poh/paizen

>>517
適当に書いてもテストケース3までは通ったけど……
それ以降になるともう一捻り要るか
(そもそもウィジェットに求めるサイズ大きくね？)

BM法を使ってテストケース4まで到達。もっと上に行けそうな予感……

メモ化して1.19秒までこぎつけた……が、駄目ッ……！
https://paiza.jp/poh/paizen/result/91838352dea16a5f25ac65adeb683218

僕はテストケース５までしか通らないわ
むずかしい

ふと閃いた方法を試したらテストケース5まで無事到達
http://paiza.jp/poh/paizen/result/5c37290eba362a5a8e6034a67424b689
しかし6は難しいなぁ……

前回は簡単だったが今回の問題は面倒そうだな

恐怖の畳問題じゃないか。
この前解けなかったんだよなぁ・・・。

>>522やったついでに、暇つぶしにpaizaに登録して
「コーディングスキルチェック」なるものを解いてるんだが、
あっという間にAランクまで解けたんだけど……
これ数冊アルゴリズム本読んでたらS余裕じゃね？

……あ。
> ただし面接時には書いたコードが求人企業側に提出されますので、
> コードの書き方、 コメントの入れ方、オブジェクト指向で書かれているかなど
> 各社の視点での評価がされるため、その点を意識してコードを書いてください。
いっけね、ICPC用に組んでたテンプレコードを弄って投稿したから結構テキトーだったｗ
どうでもいい機能インクルードしてるしコメント端折りまくりｗｗｗサーセンｗｗｗｗ

>コードの書き方、 コメントの入れ方、オブジェクト指向で書かれているか

こんなの気にしてあのを時間内に問題解けって無理だろｗ

>>527
競技プログラミングとは真逆の発想だよねｗ
いや別に難易度はそれほど高くないから
入れようと思ったら入れられないこともないけどｗｗｗ

あの問題サイズでオブジェクト指向とか何考えているんだよ(真顔)

クロッシング問題とは？


この問題では最初に1 ~ nまでの数字が小さい順位並んでいます。これを列１とします。

次にその数字の並びを適当に入れ替えます。これを列２とします。

列１を上に並べ、列２下に並べます。

そして同じ数字同士を線で結ぶと交差点がいくつかできると思います。この交差点の数を正確に速く数える問題です。

実際にチャレンジするのは『1 ~ 314159』の数字の交差点を数える必要があるのでもうやってられなーい状態なのです。

http://www.geocities.jp/xhkhc873/image/crossing/crossing.png
http://www.geocities.jp/xhkhc873/codeIQ/crossing.html

>>529
結城さんの問題でそういうのあったと思うので解いて発表しても大丈夫なのか！！？

>>529
それ多分１５パズルの成否を問う判定問題の拡張だろ？
よく知らないが楽勝なんじゃねーの？

その問題、ちょっと考えてみたんだが
１　２　３
＼｜／
　 ＊
／｜＼
３　２　１

のような並びの場合、交点が1箇所で重なると思うのだけど
これも交点3つって数えていいのかね？
それならさほど難しくなかったけど、多重交点をカウントする処理は骨が折れる

配置依存はなしにしないと答えが変わるのでは?
最大交点は2つで。こうすると3重はない。

1　2　3
3　2　　　　1

プログラムのお題だから、てっきり答えが並べ替えによって変化してもＯＫかと思ったぞい

>>534
正しい

>>533
それだと3点で交差しないかい？
俺、何か勘違いしてるかも。

並べ替えで答えが変わるのはいい。
並べ替えなしの配置だけで答えが変わるのは良くない。

ひゃっほーー７まで通った
個数さえカウントすれば良かったのか

直線の方程式解くとバブルソートと同じオーダーのような気がする。
なんか軽量化できないかなー。

元の位置とズレてる数だけ交点が発生するとかじゃないの？

ttp://ideone.com/cqKPGU
ほぼC。とりあえず書いてみた。3秒以内で30万件とか無理。
っていうかあってるのかどうかもわからん。
真面目に連立方程式といてみたんだけど数学苦手なんだよな。
ちなみにY軸が正規化された範囲で交差すること！っていう制約無いよね？？

たとえば列２で 11 という数字が列１での位置(11番目)より後方(例えば20番目)にある場合
1〜10の数で列２で19番目以下にあるものは 11 とは交差しない
　　言い換えると 1〜10の数で21番目以降にあるものは 11 と交差する
　　　　言い換えると 1〜10の数で19番目までに現れなかったものは 11 と交差する
12〜20の数で列２で21番目以降にあるものは 11 と交差しない
　　言い換えると12〜20の数で19番目以下にあるものは 11 と交差する
　　　　言い換えると 12〜20の数で19番目までに現れなかったものは 11 と交差しない
21以上の数で19番目以下にあるものは 11 と交差する
　　言い換えると19番目までに21以上の数が現れれば 11　と交差する

これをなんとかアルゴリズム化して1〜nまでの順繰りで交差数をカウントしていければいいんじゃないの？

>>529 Python, O(n^2)っぽい

import time, random, bisect, array
def f529(q):
　　count = 0
　　x = array.array('i') # 列2 <= 列1 の数字 (／)
　　y = array.array('i') # 列2 > 列1 の数字 (＼)
　　for i, a in enumerate(q):
　　　　j = bisect.bisect(x, a)
　　　　count += len(x) - j
　　　　if i+1 <= a:
　　　　　　x.insert(j, a)
　　　　else:
　　　　　　k = bisect.bisect(y, a)
　　　　　　count += len(y) - k
　　　　　　y.insert(k, a)
　　return count

q = array.array('i', range(1, 1+314159))
random.shuffle(q)
t0 = time.clock()
count = f529(q)
t1 = time.clock()
print "cross points of 1~%d = %d (%f second)" % (len(q), count, t1-t0)

http://gyazo.com/88c216f64dbaebe801e4f519c0d2dcc2
これわからんちん

>>544
マルチはどうなるかわかってるよなぁ・・・。

ttp://gigazine.net/news/20140425-ultima-richard-garriott-first-rpg/
暇人向け。移植してみましょう。
RNDは(0,1)を返すみたい。

>>546
めっちゃBASICなのに草生えるｗ
https://d2sx9mrt4zumaq.cloudfront.net/wp-content/uploads/2014/04/DND1_Complete.pdf

>>547
関数の概念はまだ見えるけどラベルすら無いとか泣けるわ。
マジで意味のわからんGotoが大量にある。

>>548
しかし中身はD＆D……数日後には他言語で書きなおされた奴がうｐされるんじゃね(適当)

この程度ならベーマガに投稿されたプログラム読むのと大差なくね

チャレンジ問題：N88-BASICソースをCソースに変換するプログラム

インデントなし、GOTOの嵐、IFにELSEもなしかよ

きっとラインエディタとかいう超高機能なエディタを使ってた時代だろう

お題：0の0乗は数学の分野によって不定だったり、1だったり0だったりするようですが
あなたの使っているプログラミング言語ではどうなりますか？

お題？
ただの質問？

>>552-553
Racet NECDOS を使えばキレイに展開してくれる...

1であるほうがしっくりくる

100^0 = 1
1^0 = 1
0.01^0 = 1
0.0000001^0 = 1
0.0000000000000000000001^0 = 1

うん、そーだねー(棒)

　0^2=0
　0^1=0
　0^0=1

>>554
冪乗をサポートしない言語も結構あるけど・・・？

0^2 = 1*0*0 = 0
0^1 = 1*0　 = 0
0^0 = 1　　 = 1

;;;べき乗が実装されてない場合
;;;掛け算と引き算で作ると
;;;その場合、0^0 → 1 が自然だな

(define **
(lambda (a b)
(cond
((zero? b) 1)
(else
(* a (** a (- b 1)))))))

>>560
乗法の単位元たる1の意味がもろ出る再帰定義だな

>>554
数学的に考えると0の0乗は「定義されない」が正解(極限をとっても定まらないから)
で、数式処理ソフトではMathematicaは「Indeterminate」、Maximaは「undefined」と定める
(しかしなぜかMapleでは1として扱う)

でもクヌース先生的には「(実用的な意味で)1と定義するのが妥当」だそうな
それだからか知らんが、0の0乗は色々な言語で「1」として扱われる
(WikipediaによるとJava・Python・Ruby・Perl・Haskell・Common Lisp・ML・Scheme・
R・MATLAB・APL・J・Windowsの電卓・Googleの電卓機能など)

>>562
むちゃくちゃや

"0^0-0/0"さん元気かな―

>>520
C++で全て0.01で通ってる人が居るんだがどうやってるんだろう
規模ごとに処理を分けてるのかな

x^xのグラフから分かる。

>>566
別に0^0が「x^xでx→0」とは限らないじゃん？
「0^xでx→0」とか「x^0でx→0」とかもありうるわけで、
数学的にはそれらが全て同じ値にならないと「極限が存在している」とは言えない

数学で 0.1 の 0.1乗 がどうなるのか

x^xを微分なりなんなりすればいいんじゃね

x^xのグラフ


http://www.rupan.net/uploader/download/1398513458.png

x^xのグラフは、1/eで極小で、約0.6922らしい。

>>554 Rebol
>> power 0 0
== 0.0
>> power 2 0
== 1.0

お題：自然数nが与えられたとき、n桁の自然数で各桁の数のn乗の和が元の数と等しくなるもの(たとえばn=3のとき 370 = 3^3 + 7^3 + 0^3 = 27 + 343 + 0)をすべて求める。
例
n=4 -> 1634 8208 9474
n=5 -> 54748 92727 93084
n=8 -> 24678050 24678051 88593477

>>573
C言語系だと簡単にオーバーフローしそうな・・・。

シンソフィア開発ソフト「がんばる私の家計ダイアリー」の電卓機能におけるバグを再現する
http://www.nintendo.co.jp/ds/a2yj/inf.html
再現するのは「多桁×多桁の掛け算(110.6×19など)」だけでかまわない
入出力仕様:
110.6*18=1990.8
110.6*19=1101.4(!)
110.6*20=2212
1106*19=11014(!)
110.5*19=2099.5

余裕があれば「割られる数が9桁の割り算」も再現する
不具合が出る入力は不明なので各自推理する
入出力仕様:
214358881/11=19487171
965782365/19=50830650.7(切り捨て)

>>575
10進化浮動小数点型が流行るまでお茶を濁せ！

>>573
ttp://ideone.com/XUbsST
一応、書いてみた。ほぼC。今回は桁切るのにベクター使ってみた。
いつも使ってるのは処理食うのでメモリにキックしてみた。
8桁はIdeonさんでも時間的に無理だったので値を低くしてある。

はやい‥‥
自由バイト長多桁演算libを「考えていた」ところだったんだが‥‥
宿題スレからの分岐時点から居るが、このスレは恐ろしいね

>>575
ttp://ideone.com/uN4hUf
これであってる？
浮動小数点型の問題は扱いが難しいので面倒くさいんだよな。
俺も完全には扱えてないし銀行なんかはデシマルつかうよ？
業務アプリにFloatつかうなんてもってのほかだと思うんだが、ドウだろう。
これ、報酬つくのかねー。笑

>>578
もっと褒めてー。笑
そのライブラリのパーツのクイズといてるだけなので、設計なんてほとんど適当だし適時直しておいて。

9つある出力結果のうち仕様通りのものは正しい答えの3つしかないじゃん

>>581
割り算は精度系のバグで、掛け算は表示系のバグじゃね？向こうの。
定数で10^Nとかなんか引き算してるようにしか見えないんだけど。

NDSの開発用SDKの仕様なんかよく知らんが、要するにfloat使ってたせいなの？
中の石(ARM946E-S)の仕様を見る限りでは32ビットARMアーキテクチャで、
IEEE 754に完全対応(倍精度もOK)らしいんだけど……
http://www.arm.com/ja/products/processors/classic/arm9/arm946.php

>>583
パンピーがそんなこと知るわけねーだろ。浮動小数点型の仕様は情報の基礎だぞ。
誤差なんか簡単に出るし古代人は整数でエミュレーションしてました。

「110.6*19=1101.4」になるバグを再現してほしかったし

IEEE754 32bit-floatなら8桁のときも不具合がおきると思ったので
単純な精度問題だとは考えていなかった
割り算の出力形式はよくある電卓同様で
・むやみに小数点以下の0を付けない
・9桁(小数点含まず)を超えた場合は10桁目を切り捨てる
を守ってほしい

だから>>579では駄目だね

>>585
ふむ、じゃ俺の手番は終わりだ。俺にはわからん。
他の人任せた。

>>585
コード書けるのなら自分で試行錯誤してみてはどうか？
>>582のようにfloatに起因する以外の原因だってありえるんだし

女子大生のタイル詰めるやつは全クリの最高ランク行った?
やってみようかと。
大小の包含関係で並べ替えて、小さい順に探索して、結果をキッシュして再利用すればいいんだよな?

あの女の子イラストを全バージョンみたいだけなんだ‥‥

POH!のはヒキ板のプログラミング雑談で色々アイデア出し合ってたみたいね

>>589
とりあえず自分の結果(ちなみにCとAのみ)とTwitter漁っただけ。誰かBとDのURL教えてくれ……
(注：Eは全問失敗、Cは3番めまで、Aは5番めまで(？)、S以降は全問正解な模様)

E　http://paiza.jp/poh2/images/poh2_majide.jpg
C http://paiza.jp/poh2/images/poh2_yareyare.jpg
A http://paiza.jp/poh2/images/poh2_mumu.jpg
S http://paiza.jp/poh2/images/poh2_otto.jpg
SS http://paiza.jp/poh2/images/poh2_sugoine.jpg
SSS http://paiza.jp/poh2/images/poh2_kirakira.jpg

まあ一発書きでSSS取る変態もTwitterを見る限りいるようだがｗ

SSS通るコード書けるなら終了時間を微調整してやれば揃えられるんじゃね
ちなみにSランクは俺が見た限り2パターンあるよ

>>592
え、マジ？
もう一方のURL教えてくれ

>>593
http://nozomi.2ch.net/test/read.cgi/prog/1389862103/298

>>594
thx
……何すれば画像が違ってくるのそれｗ
Sその2 http://paiza.jp/poh2/images/poh2_awawa.jpg

>>590
見てきた。……シンプルなコードで全ケース通過とかヤバすぎｗｗｗ
(いやメモ化自体は俺も思いついて実装していたが、それをもっと推し進められるとは……
ちょっと実装してS取ってくる)

初で女子大生の問やってみるけど、
たとえば1を調べるのに、2-4が置ける場所を事前に調べてあったら、
ビット演算などで置ける可能性の場所を絞り込んだらいいと思うが。


1
■■■■■
■■■■■
■■■■■
■■■■■

2
■■
■■
■■
■■

3
■■■■
■■■■

4
■■■
■■■
■■■

0.66秒いけたんだけどそれ以上はムリポ
ウィジェットごとに検索してたら５以降通らないね
予めすべてのサイズの個数だけカウントしとけば良い

ヒキどもは時間がたっぷりあるからな

>>595だけど、参考にして書いたらケース7まで通ったぜええええええええ！！！！
http://paiza.jp/poh/paizen/result/96a040a413a4dfd7736578e387dae2fb

……後は最適化に全力を尽くしてみる所存
ちなみにケース3はウィジェットサイズ＞盤面サイズなのが混じってる問題だから気をつけろよ！

スクリプト系言語だと普通にサイズオーバーなウィジェット出題される条件になってるがな

>>600
まあそうだけどね……
C++で書いてたから最初気付かなくてさ
思い込みで書くとエライ目に遭う典型といえる

>>599
おめ！これは別のＳパターンか

プログラミングというよりパズル問題やってる気分だ

>>573 Python
import time, itertools
def f573(n):
　　t = time.clock()
　　ans = []
　　q = [i**n for i in range(10)]
　　cwr = itertools.combinations_with_replacement
　　for p in cwr(range(10), n):
　　　　s = sum(q[d] for d in p)
　　　　if len(str(s)) == n and s == sum(q[int(c)] for c in str(s)):
　　　　　　ans.append(s)
　　ans.sort()
　　print "n=%d -> %s %f" % (n, str(ans), time.clock() - t)

for n in [3,4,5,6,7,8]:
　　f573(n)

n=3 -> [153, 370, 371, 407] 0.000000
n=4 -> [1634, 8208, 9474] 0.000000
n=5 -> [54748, 92727, 93084] 0.016000
n=6 -> [548834] 0.031000
n=7 -> [1741725, 4210818, 9800817, 9926315] 0.078000
n=8 -> [24678050, 24678051, 88593477] 0.172000

お題：
与えられたa,b,c,d,eに対して
{ax + by ≦ 0
{cx + dy ≧ 0
{y ≦ e
がなす面積を求めるプログラム。

abcdeは正負０にもなりうるの？

>>604
なんでこんな速いの？

定義域は実数全体。Maximaを使ってもよい。

仕事で非線形連立式の面積やら体積やらを求める問題が出てくるんで、Maximaで計算する方法を教えてくれ。

>>607
ループ回数を調べてみた
n=3 : 220
n=4 : 715
n=5 : 2002
n=6 : 5005
n=7 : 11440
n=8 : 24310

リファレンスによると、繰り返しを許した組合せ
# combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
で組み合わせの数の計算式は (10+n-1)! / n! / (10-1)!

>>605
俺にはわからんけど、仕事投げるんじゃネーですよ。

>>605
よく分からんが、つまり三角形の面積を出したいのか？
三直線の交点を出して、後はベクトル使えば一瞬で面積が出る
(不等号によって「解なし」があり得る場合は別途外積で判別する)
http://www004.upp.so-net.ne.jp/s_honma/heron/heron.htm
http://marupeke296.com/COL_Basic_No1_InnerAndOuterProduct.html

交点つっても2直線は原点を通ってるし
片方はy固定だからy=eが交点だし

底辺かける高さわる2だろ

それは体積求めるやつやろ

底面かける高さわる3だっけ？

それはピラミッドパワーを作るやつだろ

ヒランヤの謎

知らんや

ここの連中ってCodeIQとかのアルゴリズム系問題を解いてたりするん？

高速回転三所責めのアルゴなら考えてる

怖いから解いてない。

お題：1のビットが3個ある二進表記文字列が与えられたとき、次に大きい
1のビットが3個ある二進表記文字列を求める。
例
111 -> 1011
1110 -> 10011
101100 -> 110001

>>623
http://codepad.org/WvYMXjft

>>623
http://ideone.com/cx6aI3

>>623 HSP
#module
#defcfunc n_str str s, int n, local ret
sdim ret
repeat n : ret+=s : loop
return ret

#defcfunc f623 str s_, local s, local l, local c, local count
s=s_
l=strlen(s)
dim count, 2
for i, l-1, 0-1, -1
c=peek(s, i)
if c!'0' and c!'1' : return "ERROR"
if count(1) : if c='0' : _break
count(c-'0')++
next
if count(1)=0 : return "ERROR"
return strmid(s, 0, i)+"1"+n_str("0", count(0)+1)+n_str("1", count(1)-1)
#global

mes f623("111")
mes f623("1110")
mes f623("101100")

>>623 C
#include <stdio.h>
#include <string.h>
void f623(char *dst, const char *src) {
　　int k;
　　char *p, *base, *q;
　　sprintf(dst, "000" "%s", src);
　　for (p = dst; *p; p++)
　　　　*p = (*p < '1') ? '0' : '1';
　　(base = strrchr(dst, '1')) || (base = dst);
　　for (k = 0, p = dst; p <= base; k += (*p++ >= '1'));
　　while (k >= 3)
　　　　for (k++; (*base += 1) >= '2'; k--, *base-- = '0');
　　for (; *(base+1); base++);
　　while (k < 3)
　　　　for (p = base, k++; (*p += 1) >= '2'; k--, *p-- = '0');
　　if (dst[0] != '1')
　　　　for (p = dst, q = strchr(dst, '1'); *p++ = *q++;);
　　printf("%s -> %s\n", src, dst);
}
int main(void) {
　　char buf[64+sizeof("000")];
　　f623(buf, "111");
　　f623(buf, "1110");
　　f623(buf, "101100");
　　return 0;
}

>>623 Haskell
http://codepad.org/BPAfTRSX

あ、"00"のパターンは書かなくても良かったか

>>623
ttp://ideone.com/CNUaCe
ほぼC。バグっている。ウオーニング等は出てない。VCでもGCCでも同じ挙動。
64bitで書くとなんか謎の挙動しててバグが取れなかった。
らしい動きはしてるんだが、これなんだろう・・・。Orz

これって、コンパイラが64ビット対応ビットシフトAsm吐いてないってこと？？
よくわからねー。

>>623
http://ideone.com/zKFNBg

ttp://ideone.com/vKkIVH
ほぼC。バグ取れた。リテラルの問題だった。
リテラルはあんまり使わないのですっかり失念していた。
俺が間違っていた・・・。Orz

>>623 Io
f := method(s,
n := s fromBase(2)
a := n ^ (n & (n - 1))
b := a + n
(b | ((b ^ n) / a) / 4) asBinary
)
Io> f("111")
==> 1101

>>634
実行結果が間違っていました。訂正と他の例を追加します。
Io> f("111")
==> 1011
Io> f("1110")
==> 10011
Io> f("101100")
==> 110001

>>623 clojure

(defn f [s]  (->> (Integer/parseInt s 2)
       inc
       (iterate inc)
       (map #(Integer/toBinaryString %))
       (drop-while #(not= ((frequencies %) \1) 3))
       first))

(println (f "101100")) ;; 110001

>>517
模範解答とかいうのが各言語１〜３番まで出てて３番のがテストケース７まで通るコードだね

>>637
模範を見ずに自力で7まで突破してから見たけど、あの#defineだらけのコードなんじゃこれ……

お題：辺の長さがa,b,cの鋭角三角形がある(a >= b >= c)。
この三角形の内部に点をとり、その点から各頂点までの距離の和の最小値を求める。
例
20,18,10 -> 26.89
1,1,1 -> 1.73
7,6,5 -> 10.29

>>639 HSP
#module
#defcfunc heron double a, double b, double c, local s
s=(a+b+c)/2
return sqrt(s*(s-a)*(s-b)*(s-c))

#defcfunc len double x, double y
return sqrt(x*x+y*y)

#defcfunc sum3 double x, double y, double a, double b, double c
return len(x, y)+len(x-a, y)+len(x-b, y-c)

#defcfunc f639 double a, double b, double c, local ax, local ay, local x, local y, local d, local dx, local dy
ay=heron(a, b, c)*2/a
ax=sqrt(b*b-ay*ay)
dx=1.0 : dy=1.0
x=0.0 : y=0.0
repeat 1000
d=sum3(x+dx, y, a, ax, ay)-sum3(x, y, a, ax, ay)
if d>0 : dx*=-0.4 : else : x+=dx : dx*=1.5
d=sum3(x, y+dy, a, ax, ay)-sum3(x, y, a, ax, ay)
if d>0 : dy*=-0.4 : else : y+=dy : dy*=1.5
loop
return sum3(x, y, a, ax, ay)
#global

mes f639(20, 18, 10)
mes f639(1, 1, 1)
mes f639(7, 6, 5)

>>623
Scheme
http://codepad.org/8js70IEm

>>623
elispかcommon lisp

(defun next-bigger (bin)
(let ((fst (car bin))
(last1 (car (last bin)))
(mid (cdr (butlast bin))))
(append '(1)
(next-bigger2 mid)
'(1))))

(defun next-bigger2 (bin)
(if (eq 1 (car bin))
(append (cdr bin) '(0 1))
(append (cdr bin) '(0))))

すげー間違ってる恥ずかしい

>>623
@Mathematica

nextThreeOne[d_]:=Module[{countOne,addN},

　　countOne[dx_]:=IntegerDigits[dx]//
　　　　Count[#,1]&;

　　addN[dx_,nx_]:=dx//
　　　　IntegerDigits[#,10]&//
　　　　FromDigits[#,2]&//
　　　　#+nx&//
　　　　IntegerDigits[#,2]&//
　　　　FromDigits[#,10]&;

　　NestWhile[addN[#,1]&, addN[d,1], countOne[#]!=3&]
];

In := {111, 1110, 10110}//Map[nextThreeOne, #] &
Out = {1011,10011,11001}

>>623
ttp://ideone.com/QfNisQ

>>645
一番最後、間違ってないかい？

>>639 十進BASIC
FUNCTION f(a,b,c)
LET d=(a+b+c)/2
LET s=SQR(d*(d-a)*(d-b)*(d-c))
LET f=SQR(a*a+c*c-2*a*c*COS(ASIN(2*s/a/c)+PI/3))
END FUNCTION

PRINT USING "f(20,18,10) = ######.##": f(20,18,10)
PRINT USING "f(1,1,1) = ######.##": f(1,1,1)
PRINT USING "f(7,6,5) = ######.##": f(7,6,5)
END

実行結果
f(20,18,10) = 26.89
f(1,1,1) = 1.73
f(7,6,5) = 10.29