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

**デフォルトの名無しさん** · 2022/11/13(日) 19:00:36.84

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

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

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文
　　結果がある場合はそれも

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
https://runnable.com/
https://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

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

※前スレ
プログラミングのお題スレ Part20
https://mevius.5ch.net/test/read.cgi/tech/1624028577/

**デフォルトの名無しさん** · 2023/04/23(日) 16:27:41.83

テトリスで任意の模様を作成可能か

**デフォルトの名無しさん** · 2023/04/24(月) 12:22:06.49

**デフォルトの名無しさん** · 2023/04/25(火) 23:39:05.78

お題
上半分と下半分にそれぞれ文字列が書かれたカードがN枚ある。
カードiの上半分の文字列をx_i、下半分の文字列をy_iとする。
カードを何枚か選び横一列に並べ、上側と下側でそれぞれ文字列を結合する。
カードを上手く選ぶことで上側と下側の文字列を一致させることが可能か？
ただし、同じカードを2回以上使用しても良い。

**デフォルトの名無しさん** · 2023/04/25(火) 23:50:59.14

>>612
言ってる意味がよく分からない。そのカードは上下で分離できるものなのか？

**デフォルトの名無しさん** · 2023/04/26(水) 13:54:14.97

お題出すならまず自分で解答作ってそれに何個か入力してどんな出力になるのか例示しとくべき
そもそももちろん日本語で他人に伝わる仕様書書けないようでは話にならんのだけど

**デフォルトの名無しさん** · 2023/04/26(水) 22:38:58.02

問いは「可能か？」
答えは「可能(例:全て同一の文字列とする)」

以上

**デフォルトの名無しさん** · 2023/04/27(木) 14:44:36.68

自分でできてないなら出すな
以上

**デフォルトの名無しさん** · 2023/04/27(木) 23:16:52.66

ちょっと誰か >>612 を ChatGPT にコピペして入力してどう答えるか試してみ

**デフォルトの名無しさん** · 2023/04/27(木) 23:24:12.73

はい、上側と下側の文字列を一致させることが可能です。

以下の手順で可能です。

カードの上半分の文字列x_iをすべて結合すると文字列Xが得られます。
カードの下半分の文字列y_iをすべて結合すると文字列Yが得られます。
文字列Xと文字列Yを逆順に結合した文字列Z = X + Y'を考えます。ここでY'は文字列Yを逆順にしたものです。
Zの中央にあるカードを選びます。つまり、Zを左右に分割するときに真ん中にあるカードです。
このカードを選ぶことで、上側の文字列をカードの上半分の文字列に、下側の文字列をカードの下半分の文字列にすることができます。
残りのカードに対して、上側と下側で同じ文字列を選びます。このとき、カードを上下反転させたものを選ぶことで、
上側と下側で同じ文字列を選ぶことができます。
こうして選んだカードを横一列に並べることで、上側と下側の文字列を一致させることができます。

具体的には、以下の手順で解くことができます。

カードの上半分の文字列x_iをすべて結合すると文字列Xが得られます。
カードの下半分の文字列y_iをすべて結合すると文字列Yが得られます。
文字列Xと文字列YのLCSを求めます。LCSを求めるアルゴリズムには、動的計画法が使われます。
LCSを構成する文字列を上側と下側の文字列に選びます。このとき、同じ文字列を複数回選ぶことができるので、
LCSの中に同じ文字列が複数回現れる場合には、その文字列を選ぶことができます。
残りのカードに対して、上側と下側でLCSに現れない文字列を選びます。同じ文字列を複数回使用することができるので、
LCSに現れない文字列を上側と下側で同じように選ぶことができます。
こうして選んだカードを横一列に並べることで、上側と下側の文字列を一致させることができます。
このアルゴリズムの時間計算量は、文字列Xと文字列Yの長さの合計をNとした場合、O(N^2)です。
LCSを求める動的計画法の時間計算量はO(N^2)であり、残りの処理の時間計算量もO(N^2)です。したがって、全体としての時間計算量はO(N^2)となります。

**デフォルトの名無しさん** · 2023/04/27(木) 23:45:06.42

お題：立方体の頂点x,y,zを格納する配列がある。
ある面の頂点が4つ与えられるのでその頂点をコピーしてx軸上に少し移動させる。
与えられた頂点とコピーした頂点で、3点を結んで面を構築し立方体を表現する頂点のインデックスの配列を生成せよ。
(結果的に立方体の横に新しい立方体ができることがある)

頂点の配列は一次元の実数の配列でx,y,z,x,y,z,というふうに要素が並んでいる。
インデックスの配列も整数の一次元で3点をa,b,cとするとa,b,c,a,b,cというふうに並ぶ。
座標系は右手座標系とする。
頂点は左回りが表面とする。

**デフォルトの名無しさん** · 2023/04/28(金) 00:03:21.44

出題ミスりました
ごめんちゃい

**デフォルトの名無しさん** · 2023/04/28(金) 11:21:29.27

なんで自分で組んでみてから出題しないんだろう？

**デフォルトの名無しさん** · 2023/04/30(日) 20:51:55.51

お題
A、B、C、D、Eの5人が前を向いて横一列に座っている。以下は、異なる5人の発言である。

ア　メガネをかけている人は、私の左隣に座っている。
イ　私の右隣にはCが座っている。
ウ　私から右に3番目にはAが座っている。
エ　私の左隣にはB、Bから左に2番目にCが座っている。
オ　私の左隣にはDが座っている。

5人のうち1人だけがメガネをかけているとしたら、それは誰か。

**デフォルトの名無しさん** · 2023/04/30(日) 21:48:41.86

お題……？

**デフォルトの名無しさん** · 2023/04/30(日) 21:57:15.12

このタイミングだと嫌儲からコピペだろうなあ

**デフォルトの名無しさん** · 2023/04/30(日) 22:27:50.40

ECDBA
イウアオエ

**デフォルトの名無しさん** · 2023/05/01(月) 12:33:57.06

>>622

haskell
https://ideone.com/fkv4nS

**デフォルトの名無しさん** · 2023/05/01(月) 12:39:19.81

証明支援言語ってこういう問題にも使えるのかな

**デフォルトの名無しさん** · 2023/05/01(月) 12:40:30.40

>>626
なんじゃこれすげえ

**デフォルトの名無しさん** · 2023/05/01(月) 16:21:07.51

Prologおじさんの大好物だろうけどさすがにもう絶滅したか

**デフォルトの名無しさん** · 2023/05/01(月) 23:58:39.74

よく見たら総当りしてるだけだった🥺

**デフォルトの名無しさん** · 2023/05/03(水) 19:34:29.78

お題

最長重複文字列を求めてください
入力: mississippi
出力: issi

**デフォルトの名無しさん** · 2023/05/03(水) 21:54:26.00

>>631
PowerShell

$s = "mississippi"
$n = $s.length - 1

$t = $u = ""
foreach ($i in 1..$n) {
　　$t += ((0..$n |% {("-", "#")[$s[$_] -ceq $s[$_ + $i]]}) -join "") + "`n"
　　$u += ($s[$i..$n + 0..($i - 1)] -join "") + "`n"
}

foreach ($i in $n..1) {
　　if (!($matches = [regex]::matches($t, "#" * $i)).count) {continue}
　　$matches |% {$u[$_.index..($_.index + $i - 1)] -join ""}
　　break
}

**デフォルトの名無しさん** · 2023/05/04(木) 13:03:48.76

>>631
C#
https://paiza.io/projects/xXnIlq3ZcXoPNRciPNj2tA

**デフォルトの名無しさん** · 2023/05/04(木) 15:56:11.94

お題
いろはに王国の国民はみな、氏・ミドルネーム・名を持つ

いろはに政府のマイナンバーシステムでは
氏・ミドルネーム・名
をそれぞれ別項目に保存するはずであったが
氏+ミドルネーム+名の処理が行われて一つの項目に保存されてしまっていた

政府とシステム開発会社のコミュニケーション不足が原因と思われる
再発防止をお願いした

さて、とある国民の名前が「いろはにほ」で保存されていた
この国民の名前を氏・ミドルネーム・名に分割するとき
考えられる分割の仕方をすべて列挙してください

例:
い・ろ・はにほ
い・ろは・にほ
い・ろはに・ほ
いろ・は・にほ
いろ・はに・ほ
いろは・に・ほ

**デフォルトの名無しさん** · 2023/05/04(木) 19:39:10.82

例をコピペ出力するだけでOKなのでそれより長いプログラムは冗長
むしろ出題からして最後の部分以外不要なのを踏まえてそこを楽しむべきかもしれない

**蟻人間** ◆T6xkBnTXz7B0 · 2023/05/04(木) 19:44:38.00

お題: 直方体の段ボール箱の幅・高さ・奥行きがcm単位で指定される。その段ボール箱の展開図をSVG形式で出力せよ。

**蟻人間** ◆T6xkBnTXz7B0 · 2023/05/04(木) 20:16:34.04

ヒント:
https://www.tohoho-web.com/ex/svg.html

**638** · 2023/05/05(金) 15:50:16.77

>>631 Perl5

$len = length ($s = 'mississippi');
for $a (0..$len-2) {
　for $l (1..$len-$a) {
　　$t = substr($s, $a, $l);
　　$b = index($s, $t, $a+1);
　　$h{length $t} = $t if 0 <= $b
　}
}
print $h{(sort keys %h)[-1]}, "\n";

注: インデントは全角スペースに置換してあります

実行結果
~ $ perl 21_631_mississippi.pl
issi

**デフォルトの名無しさん** · 2023/05/05(金) 20:55:42.28

>>631
haskell

https://ideone.com/KCTPkV

**デフォルトの名無しさん** · 2023/05/05(金) 22:37:41.22

>>634
Kotlin

なんというか、初心者向けお題？

https://paiza.io/projects/6IkrH8lybgONO3gGrwc-7Q

**デフォルトの名無しさん** · 2023/05/05(金) 23:20:24.37

>>638

重複を検出した文字の長さが二けた以上になる場合にも対応させるには

print $h{(sort keys %h)[-1]}, "\n";
↓
print $h{(sort{$a <=> $b} keys %h)[-1]}, "\n";

だな。

**634** · 2023/05/05(金) 23:33:20.01

>>640
そんなに簡単に解かれるとは思ってなかった
王国の話に引っ張られて解けない人いるかもと思ってた
3分割に限定したのが良くなかったかも

お題
文字列の分割パターンを全部列挙してください

入力: いろはにほ
出力:
い・ろ・は・に・ほ
い・ろ・は・にほ
い・ろ・はに・ほ
い・ろ・はにほ
い・ろは・に・ほ
い・ろは・にほ
い・ろはに・ほ
い・ろはにほ
いろ・は・に・ほ
いろ・は・にほ
いろ・はに・ほ
いろ・はにほ
いろは・に・ほ
いろは・にほ
いろはに・ほ
いろはにほ

**638** · 2023/05/06(土) 00:28:50.96

>>642　Perl5
use utf8;
binmode STDOUT => "utf8";
use feature qw{:5.16 signatures say};
say for sub($a, @b) {
　if (@b) {
　　my @s = __SUB__->(@b);
　　 (map{"$a・$_"} @s), (map{"$a$_"} @s);
　} else { $a }
}->(split'', 'いろはにほ');

※インデントは全角スペースに置換してあります。
　perl5の__SUB__は、5.16以降で使用可能な｢現在の関数(この場合無名関数)のリファレンス｣

実行結果
~ $ perl 21_642_いろはにほ.pl
い・ろ・は・に・ほ
い・ろ・は・にほ
い・ろ・はに・ほ
い・ろ・はにほ
い・ろは・に・ほ
い・ろは・にほ
い・ろはに・ほ
い・ろはにほ
いろ・は・に・ほ
いろ・は・にほ
いろ・はに・ほ
いろ・はにほ
いろは・に・ほ
いろは・にほ
いろはに・ほ
いろはにほ

**デフォルトの名無しさん** · 2023/05/06(土) 03:38:46.54

>>631
Kotlin

こんなんでいいのかな？

https://paiza.io/projects/jrSf8uCrlkADO_scotpuaA

**デフォルトの名無しさん** · 2023/05/06(土) 10:49:16.05

>>642
PowerShell 3以上 (文字列は32文字以下とする)

$s = "いろはにほ"
$n = $s.length - 1
foreach ($i in 0..((1 -shl $n) - 1)) {
　　(0..$n |% {$s[$_], "・"[!($i -band (1 -shl $_))]}) -join ""
}

[実行結果]

いろはにほ
い・ろはにほ
いろ・はにほ
い・ろ・はにほ
いろは・にほ
い・ろは・にほ
いろ・は・にほ
い・ろ・は・にほ
いろはに・ほ
い・ろはに・ほ
いろ・はに・ほ
い・ろ・はに・ほ
いろは・に・ほ
い・ろは・に・ほ
いろ・は・に・ほ
い・ろ・は・に・ほ

**デフォルトの名無しさん** · 2023/05/07(日) 06:28:33.03

>>642
Kotlin

このプログラムだと入力文字数の最大は31文字だと思う。

https://paiza.io/projects/z1nseigb4DZR3fJeizVYhA

**デフォルトの名無しさん** · 2023/05/07(日) 17:24:01.83

>>642
Kotlin完全に理解した
https://paiza.io/projects/Cp56cFkiivKE7ieuZw-ivg

**デフォルトの名無しさん** · 2023/05/12(金) 00:04:09.01

お題
次のように定義される関数f(x,y)を実装せよ。
x==0のとき：f(0,y):=y+1
y==0のとき：f(x,0):=f(x-1,1)
それ以外のとき：f(x,y):=f(x-1,f(x,y-1))

また以下の値を計算せよ。
f(1,1)
f(2,3)
f(3,4)
f(4,1)
f(4,2)

**デフォルトの名無しさん** · 2023/05/12(金) 00:10:00.43

罠かな

**デフォルトの名無しさん** · 2023/05/12(金) 17:49:03.47

アッカーマン関数？

**デフォルトの名無しさん** · 2023/05/12(金) 17:59:41.22

世の中にはもっとずっと急激に増加する関数があるんだよね
増加が速過ぎて、宇宙中のリソースを使ってもコンピューター言語では記述不可能

**デフォルトの名無しさん** · 2023/05/12(金) 18:17:41.52

>>648
メモ化してもf(4, 2)でスタックオーバーフローしたわ

**デフォルトの名無しさん** · 2023/05/12(金) 20:14:17.32

yはループでやれよ

**デフォルトの名無しさん** · 2023/05/12(金) 20:24:24.18

PowerShell 3以上 (x, yは0以上の整数とする)

function hyper($n, $a, $b)
{
　　if ($n -eq 0) {return $b + 1}
　　if ($n -eq 1) {return $a + $b}
　　if ($n -eq 2) {return $a * $b}
　　if ($n -eq 3) {return [BigInt]::pow($a, $b)}
　　$c = 1
　　1..[Int]$b |% {$c = hyper ($n - 1) $a $c}
　　$c
}

function f($x, $y)
{
　　(hyper $x 2 ($y + 3)) - 3
}

((1,1),(2,3),(3,4),(4,1),(4,2)) |% {"f($($_[0]), $($_[1])) = $(f $_[0] $_[1])"}

[実行結果]
f(1, 1) = 3
f(2, 3) = 9
f(3, 4) = 125
f(4, 1) = 65533
f(4, 2) = 2003529930…(19709桁省略)…5719156733

**デフォルトの名無しさん** · 2023/05/13(土) 14:43:52.11

計算できるのすご

**デフォルトの名無しさん** · 2023/05/13(土) 18:02:29.70

流石にネタでしょ

**蟻人間** ◆T6xkBnTXz7B0 · 2023/05/13(土) 19:33:04.83

お題: 地球によく似た星earth2では小さなインターネットmininetが整備されている。mininet上の端末はIPv2という2バイトのアドレスでアクセスできる。
IPv2の各バイトの範囲が最小値と最大値のペアとして与えられる。与えられた範囲内のIPv2に対して対応する2個の引数の関数fを呼び出すブルートフォースを順番に実行せよ(シングルスレッド)。関数fは実引数の内容を順番に表示するものとする。

例)
data = {{1, 3}, {3, 4}}
→ f(1, 3), f(1, 4), f(2, 3), f(2, 4), f(3, 3), f(3, 4).

※フィクションです。

**デフォルトの名無しさん** · 2023/05/14(日) 01:48:51.69

お題：割り算を逆数の掛け算で近似する
単に逆数を掛けるだけだと簡単過ぎるので、例えば、
x/60 = x*(1/64 + (1/60 - 1/64)) = x*(1/64 + 1/960) = x*(1/64) + x*(1/960)
の様に、
a)2の整数べき乗と、
b)残り(除数の逆数-a)
に分割する事を考える(∵2の整数べき乗との乗算は誤差が発生しない)。

ゼロより大きい除数が与えられた時、これをa, bに分割せよ。
分割は、除算の計算精度が最も高いものにすること。

**デフォルトの名無しさん** · 2023/05/14(日) 03:59:03.17

>>657
Kotlin

入力は面倒なのでスペース区切りで数字4つにした。

https://paiza.io/projects/p_KTsUi1uFk-5hyv5_7EBw

**デフォルトの名無しさん** · 2023/05/14(日) 10:23:02.41

要するに2進展開の小数部の最初のゼロでない桁決定するの？

**デフォルトの名無しさん** · 2023/05/14(日) 10:41:00.83

>>658

haskell
https://ideone.com/619HA0

**蟻人間** ◆T6xkBnTXz7B0 · 2023/05/14(日) 13:13:59.00

お題: 縦3マス、横3マスの○×ゲーム(まるばつげーむ)について、ゲームが完了したときの盤面のパターンを重複なく出力し、何通りのパターンがあるかを計算せよ。

**デフォルトの名無しさん** · 2023/05/14(日) 14:04:22.95

対称性は無視？

**蟻人間** ◆T6xkBnTXz7B0 · 2023/05/14(日) 14:43:17.58

>>663
無視です。

**デフォルトの名無しさん** · 2023/05/14(日) 14:44:40.86

>>658
PowerShell 3以上

function bceil([UInt]$n)
{
　　if (!$n) {return 0}
　　$m, $n = [UInt]1, ($n - 1)
　　while ($n) {$m, $n = ($m -shl 1), ($n -shr 1)}
　　$m
}

function GCD([UInt]$a, [UInt]$b)
{
　　while ($b) {$a, $b = $b, ($a % $b)}
　　$a
}

2..20 + 40, 60 |% {
　　if (($a = bceil $_) -eq $_) {return "x/$_ = x*(1/$a)"}
　　$d= GCD $a $_
　　$b, $c = (($a - $_) / $d), ($a / $d * $_)
　　"x/$_ = x*(1/$a) + x*($b/$c)"
}

**デフォルトの名無しさん** · 2023/05/14(日) 14:44:57.54

[実行結果]
x/2 = x*(1/2)
x/3 = x*(1/4) + x*(1/12)
x/4 = x*(1/4)
x/5 = x*(1/8) + x*(3/40)
x/6 = x*(1/8) + x*(1/24)
x/7 = x*(1/8) + x*(1/56)
x/8 = x*(1/8)
x/9 = x*(1/16) + x*(7/144)
x/10 = x*(1/16) + x*(3/80)
x/11 = x*(1/16) + x*(5/176)
x/12 = x*(1/16) + x*(1/48)
x/13 = x*(1/16) + x*(3/208)
x/14 = x*(1/16) + x*(1/112)
x/15 = x*(1/16) + x*(1/240)
x/16 = x*(1/16)
x/17 = x*(1/32) + x*(15/544)
x/18 = x*(1/32) + x*(7/288)
x/19 = x*(1/32) + x*(13/608)
x/20 = x*(1/32) + x*(3/160)
x/40 = x*(1/64) + x*(3/320)
x/60 = x*(1/64) + x*(1/960)

**デフォルトの名無しさん** · 2023/05/15(月) 20:46:01.76

>>662
R
ideone.com/W0gYyh

合っているか分からないが、対称な盤面を除去すればWikipedia英語版に載っている
138通りに一致するから、合っていそう。

**デフォルトの名無しさん** · 2023/05/15(月) 20:54:26.02

>>662

(3^9)/4
= 4920.75

じゃね？

**デフォルトの名無しさん** · 2023/05/15(月) 21:03:02.31

>>668

(((3^9)-3)/4)+3
= 4923.

だったか

**デフォルトの名無しさん** · 2023/05/15(月) 21:10:44.54

>>667の情報を見て思ったが、日本では先攻が〇、英語版では先攻が×。
その時点でパターンが変わる。

**658** · 2023/05/15(月) 22:33:44.26

>>660
除数が2の整べき乗よりちょっと大きい場合は、引き算にした方が精度が出たりします。
tps://sagecell.sagemath.org/?z=eJx9j8FqwkAQQO-B_MOClyyahlmN8eLHSGlQ6DZL2A9wEw-KJ-uhlF7FioUIvbT0YD9mCMlnOIlGb8LusPN23uxsGEeSSSVHeswmUkWxpqxDO7QtqR5U_PQ4BDFgLUYR0zWmKabz4vuY_23RfJa7eZG9oXnHZGlbeggemQ4EvBI8CDB5vePZloonL9rRVTmaNZosn27QfJX_KzSzYrcsFwc6UGe4tO4K3g6fo5F2wK-B3-vx5jWq6Yo2XRAkRzTj9Ll7cepcBIKUmwN9FzyCttVixcdvfjiW-03-k2GSNP-jta1nvY4MHUbB1dzT_ApFBcUZngDsTonA&lang=python&interacts=eJyLjgUAARUAuQ==

**658** · 2023/05/15(月) 22:37:15.73

すぐ消えるかも知れない方のリンク(中身は同じ)
tps://sagecell.sagemath.org/?q=tkqhls

**658** · 2023/05/16(火) 04:50:29.58

補足：>>671の「引き算」は、>>658での「b)残り(除数の逆数-a)」を負数にする事に
相当します。

**デフォルトの名無しさん** · 2023/05/16(火) 09:51:49.00

>>673
こんな結果が出ましたが、この検証の仕方は合っていますか？
shortlink
https://sagecell.sagemath.org/?q=lftfab
permalink
https://sagecell.sagemath.org/?z=eJyFUs1OwkAQvpPwDg1c2AA2u_3BC89iiJFIYqUh-wBuMQTFixpjjCYcIIBiwHiRGMSHGQu9-QrOtlvUJmLSTme_mW929_tabdQdzXGdCt_Xao5bb3BcFfCtplOOu-U29nbLlG1rWQ0jNC-h2YRme_W88F8HIIbBqL2aXIO4Aa-TTrmN2iHPZf7tzJB0Kp3iZarjPjlaInK8TkvgXWzgxvO5bAdxCWLiH_VBjIP3cxDHq1EnOJligpOpGm0wkq8e1Cs8R60QsEyTxLthj8HyWEAQOSw-jk2KihOuWYkh5ZtD7SLVEUSK8YOimi2b5KPUNCxGkjTLxqqsSAGy2up25k8XwUPff5mA58Ua4TMI77q-slHQMBQ50TlZg0yCLAFSCdIYXHviVHb3a4d7kaRl20yIHO88VLq2W8urJ4zBsIemRCda3j36b1gdx76cfcxOMYLogegiC0Tnc979w8Sx3-2AJ4LFHDwcMlz274LRXP4J3DZ3aDnUUVfCl4jC2W881DnKN9iCPONvXuRQtAg92mSSElVOlLrKb0JveUhVSloh76VK9HcpA-IeRAvVypAv4NdijA==&lang=python&interacts=eJyLjgUAARUAuQ==

**デフォルトの名無しさん** · 2023/05/16(火) 09:59:14.32

元のお題に「分ける」とあるのてマイナスなしなんじゃないの？

**デフォルトの名無しさん** · 2023/05/16(火) 15:16:43.16

回分かどうか判定するプログラムを書きなさい。回分とは逆から読んでも同じ文である。
例　step on no pets
使用言語　C

**デフォルトの名無しさん** · 2023/05/16(火) 18:13:35.98

回文ね

**デフォルトの名無しさん** · 2023/05/16(火) 18:38:20.59

>>676 補足
入力した文が回分かどうか判定するプログラムを書きなさい。

**デフォルトの名無しさん** · 2023/05/16(火) 20:23:20.23

>>676,678
これ後から絵文字やらクラスタやらどんどん補足していくパターン

**デフォルトの名無しさん** · 2023/05/17(水) 02:03:28.90

>>678
これなんの補足をしたつもりだったんだ…？

**デフォルトの名無しさん** · 2023/05/17(水) 10:28:21.37

>>676

Haskell

isPalindrome x = x == ( reverse x )

main = do
print $ isPalindrome "step on no pets"

**667** · 2023/05/17(水) 23:14:17.75

>>662
最終盤面が何通りか理論的に求めてみた。○を先手とし、最終盤面での○と×の個数をそれぞれa, bとすると、(a, b) = (3, 2), (3, 3), (4, 3), (4, 4), (5, 4) の5種類に場合分けされる。

(1) (a, b) = (3, 2) のとき
・○は縦・横・斜めの8本のどれかに並べて置くので8通り
・×は残り6マスのどれかに置くので ₆C₂ = 15通り
・以上より、盤面数は 8 × 15 = 120通り

(2) (a, b) = (3, 3) のとき
・○は縦・横・斜めの8本のどれかに並べて置くので8通り
・×は残り6マスのどれかに置くので ₆C₃ = 20通りだが、○が縦/横に並ぶ場合は、×が縦/横の残り2本のどちらかに並ぶ2通りを除外する
・以上より、盤面数は 8 × 20 － 6 × 2 = 148通り

(3) (a, b) = (4, 3) のとき
・○は3個を縦・横・斜めの8本のどれかに並べ、1個を残り6マスのどれかに置くので、8 × 6 = 48通り
・×は残り5マスのどれかに置くので ₅C₃ = 10通りだが、○が縦/横に並ぶ場合は、×が縦/横の残り1本に並ぶ1通りを除外する
・以上より、盤面数は 48 × 10 － 6 × 6 × 1 = 444通り

(4) (a, b) = (4, 4) のとき
・×は3個を縦・横・斜めの8本のどれかに並べ、1個を残り6マスのどれかに置くので、8 × 6 = 48通り
・○は残り5マスのどれかに置くので ₅C₄ = 5通りだが、○が縦/横に並ぶ場合は、×3個が縦/横の残り1本に並び1個が残り2マスのどちらかに並ぶ2通りを除外する
・以上より、盤面数は 48 × 5 － 6 × 6 × 2 = 168通り

(5) (a, b) = (5, 4) のとき
・×は9マスのどれかに置くので ₉C₄ = 126通りだが、3個を縦・横・斜めの8本のどれかに並べ1個を残り6マスのどれかに置く 8 × 6 = 48通りを除外する
・○は残り5マスに置くので1通り
・以上より、盤面数は (126 － 48) × 1 = 78通り

**667** · 2023/05/17(水) 23:14:48.75

(1)～(5)を合計すれば、盤面数は 120 + 148 + 444 + 168 + 78 = 958通り

よって>>667のプログラムでの計算値が正しいことが検証された。>>667のプログラムの行列Sを調べると、(1)～(5)の各場合の盤面数も上記の値と一致した。上のように場合分けして盤面を組み立てていく手順をプログラムで記述するのは複雑で面倒なので、>>667のようにゲームを実際に行ってみるプログラムの方が簡潔に書けて良い。

**デフォルトの名無しさん** · 2023/05/18(木) 14:03:59.67

>> 676 の回答例を載せときます
#include <stdio.h>
#include <string.h>
void kaibun_judge(char *str);
int main(void)
{
char ss[80];

printf("文字列を入力してください ");
gets(ss);
kaibun_judge(ss);

}
void kaibun_judge(char *str)
{
char *p, *q, dmy[strlen(str)];
p = str;
q = dmy;

for (int i = strlen(str)-1;i >= 0;i--) {
dmy[i] = *p++;
}
if (strcmp(str, dmy) == 0) printf("回文です\n");
else printf("回分ではありません\n");

}

**667** · 2023/05/18(木) 21:14:06.06

>>682の(4)の訂正
(誤)○が縦/横に並ぶ場合は、×3個が
(正)×が縦/横に並ぶ場合は、○3個が

**デフォルトの名無しさん** · 2023/05/20(土) 00:00:46.48

>>684
よくあるバグ入でかつ分かりやすい速度向上の余地を持つ良い例だ

**デフォルトの名無しさん** · 2023/05/20(土) 05:48:17.89

>>684
そのプログラムは char 一つで1文字を表す文字コード以外ではまともに動かない。
80文字以上の入力でバッファーオーバーランする。
dmy[] 配列の最後の次のメモリに \0 以外のゴミが入っていたら strcmp() が想定した通りに動かない。

**デフォルトの名無しさん** · 2023/05/20(土) 05:50:36.82

C使い慣れてないなら他の文字列が楽々使えてメモリ管理についてほとんど考えなくても良い言語使って作った方が良いのではないか？

**デフォルトの名無しさん** · 2023/05/20(土) 06:06:53.76

>>662
Kotlin

馬鹿正直に○×と交互に打ちながら途中で縦横斜め何れかで3つ揃ったらそこで終了という感じで全パターンやらせたら
255168 パターンになったのだが、これで合っているのか謎だ。対象になるパターンを抜くとすると4で割って 63792 になる。
それと出力が多すぎて恐らくどのサイトでも実行されると結果がまともに出ない。
paiza.io にソース置いておくが実行するとパターン 1651 の途中で Timeout して中途半端に終わっている。

https://paiza.io/projects/2eV3pNvLM7kdKO0gYfHc-w

**デフォルトの名無しさん** · 2023/05/20(土) 06:14:37.20

よく見たら >>676 は使用言語がCだけになってたんだな。
じゃあC使うのは仕方がないが、Cだと色々と気を付けなければならないことが多いので要注意だ。

**デフォルトの名無しさん** · 2023/05/20(土) 17:36:52.34

>>676
C

Locale 考慮して wchar_t 使って書いた。日本語読ませても処理できる。
但しやってることは文字列の順序入れ替えて比較しているだけなので>>684と考え方は同じ。
(書きながら一々メモリ確保して逆順に並べなくても出来ると気付いたがそれは後で公開する)。
入力元が Unicode になっていた場合は濁点半濁点の合成文字みたいなのもあって MacOS でやった時とその他 OS で違ってしまうかも知れないが、その辺は考慮されていない。

https://paiza.io/projects/YXLsX3FqAsVF6DVDxye7bA

**デフォルトの名無しさん** · 2023/05/20(土) 17:50:35.91

>>676
C

>>691の改良版。リバースした文字列をわざわざ作らず半分を前後から比較するだけ。

https://paiza.io/projects/VPN0R2nAEGYugRnNLiVBfQ

**692** · 2023/05/20(土) 18:08:07.96

>>692は改行のみが入力された時の反応がおかしかたのでちょっとだけこっそり修正した。
同様に>>691もおかしかったがそっちは面倒なので放置。

**デフォルトの名無しさん** · 2023/05/21(日) 09:10:07.45

>>684 gets()のかわりにfgets()を使うと改行を含んでしまうので\0で埋めてやらないといけない。

**デフォルトの名無しさん** · 2023/05/21(日) 11:15:13.97

文字列がらみはもはやライブラリ使わないと無理やろ
ユニコードのコーディングルールはもう複雑すぎて素人が自作で作ってもまずうまくいかない
この手のルールは数学的にこうなってるはずだ、こうなってないとおかしいとかいうロジックが何一つ通用しない、単なる取り決めるなのでただひたすら覚えるしかないけど、もはや色んな言語全部取り込むために魑魅魍魎の世界

**デフォルトの名無しさん** · 2023/05/22(月) 00:54:31.79

>>676
U+10000以上の文字、異体字セレクタ、結合文字に対応したプログラムはPowerShellでは
簡単に書ける。ただし、IDS（漢字構成記述文字列）には対応していない。
tps://tio.run/##XZJPS8MwGMbv/RQxVGjRFnvxMPA4hjdhw8sYoxvZVumS2WQqzoKtf5kHD8KGG4i3zcNQbx7ULxM63E3wA8ykm1sxl6bv8@T3Pm/TBjlEHq0h151OK01cZg7BgDLPQweaSnWlpQCxVAa2AITxPp9xScl2nWNbes0s8xxc3cYVUkilMojl0BFLu6iOMEvjZh15NiOeRIGTVdCKQWoRrAmkP0crvqL8a21tJpobe8TBQKV5wzJNQ6Wmi3CV1QrxOeIhu1wDwg6ECTYQo0BgMBEk1IDrAE5GPR4Mv9qvP4/nAQ9ueNj7fnr74MFg9pCFhToUbqiDWeMN07Ti1PGbXBrUxp2X6P1Wl2Rt3B3Eez2vFgsLUzyjUwHailoUqNlEIr8PkEvRX8HalKXFIRhdnI07V9GoG113U0KCS2lyepmUGEzkifoPQhPD8OCZByEP2zz45EGfh3cyYkK@lzEpMMpoXzCWcefX6svPqe5kd8XvIC4iZ5dcNJ3@Ag

これはOutputの下の方に表示されているようにLinuxでの実行結果だが、Windowsと同様に
動作しOSに依存しない。CではOSに依存しないで書くのは難しそう。

(旧式)はUTF-16のワードを逆順に並べただけなので、U+10000以上のU+29E3D、異体字
セレクタ使用のU+82B1 U+E0101、結合文字のU+304B U+309Aが含まれる2番目の例では
正しく判定できていないが、(新式)はできている。異体字は対応しているフォント（例えば
Windowsの標準フォントでは游ゴシック）でないと正しく表示されない。

**デフォルトの名無しさん** · 2023/05/22(月) 17:00:26.90

>>696 ワイド文字対応だけでもすごいのにそこまでやるとは

**デフォルトの名無しさん** · 2023/05/23(火) 00:39:57.91

>>696をIDS（漢字構成記述文字列）対応にした。ビャンビャン麵のビャンという漢字の
IDSを正しく表示できるのは、源ノ等幅、源ノ明朝、源ノゴシックのバージョン1.xxxと
Visual Studio Code, Edgeなどの組み合わせに限られる。正しく表示されるとこうなる。
://i.imgur.com/TEDafUA.png
バージョン2.xxxxではビャンという漢字に単独のコードU+30EDEが割り当てられたので、
IDSでは表示できなくなった。

function strrev($s)
{
　　$m = 2, 2, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2
　　$p = $q = ""
　　$n = 0
　　[Globalization.StringInfo]::GetTextElementEnumerator($s) |% {
　　　　if (0x2FF0..0x2FFB -contains $_[0]) {
　　　　　　if (!$n) {$n = 1}
　　　　　　$n += $m[$_[0] - 0x2FF0]
　　　　}
　　　　$p += $_
　　　　if (!$n -or !--$n) {$p, $q = "", ($p + $q)}
　　}
　　$p + $q
}

foreach ($s in "⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心麵で麵⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心", "⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心麵で麺⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心") {
　　$t = strrev $s
　　"元文字列: $s"
　　"逆文字列: $t"
　　("回文ではありません。", "回文です。")[$s -ceq $t]
　　""
}

**デフォルトの名無しさん** · 2023/05/23(火) 00:40:48.32

[実行結果]
元文字列: ⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心麵で麵⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心
逆文字列: ⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心麵で麵⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心
回文です。

元文字列: ⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心麵で麺⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心
逆文字列: ⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心麺で麵⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心
回文ではありません。

**デフォルトの名無しさん** · 2023/05/23(火) 06:35:45.73

文字列はカオスだわ
https://jp.emeditor.com/forums/topic/mac%E3%81%A7%E5%85%A5%E5%8A%9B%E3%81%95%E3%82%8C%E3%81%9F%E3%83%8F%E3%83%B3%E3%82%B0%E3%83%AB%E6%96%87%E5%AD%97%E3%81%AE%E8%A1%A8%E7%A4%BA%E3%81%AB%E5%AF%BE%E5%BF%9C%E3%81%97%E3%81%A6%E6%AC%B2/

>>698
これは対応が難しい？

https://tio.run/##pVPBattAEL3rKzZCBZtYwnYhB0MvhST0VkjoxZigmHWsIq8UadOGpgbLcpzWJZik0NAE7B4KTgihLbnkUvdb3EWl6cWGfoA7u4ol1fTWZdGO5r15M5od2dZz7LhVbJrTaWWHlKlhEeRSx8HPUoqblvYkBEuh6AGSZWEXV01rUzeNFzrnamvUMcjWI1KxSoXCKqbreJcum7iGCV0mOzXs6NRyuBR6eQ/tCSFlAy2CZP1OWqpL0lzqfDJ3DULyGb7vi53/5w65NpffjotVCNjZ/69bKPBlVFAqu5tfWclqmjgfIrVsEaobxIUPK2ZL6QR7FrGgEHCLYnL1v1DwLULJtaKIRSoKxUsRKabDx3HqhjSnjFTLQQuqGuawM7MGZFCKh8BrOhSpz3rEfbzr823PLSX6rj61DIIUt6jmNE1VXM3EZItWS@K6LAfr5SokcBGQZBtTF4EMsUAJ25Bavr06Zd75z86X3x9aHvPesObp5OLmK/MG4cEdEXoObB7E/NfM70RP7hoPW@NhbzzcnzM4NukPjib97rfvjcNJ/@giNgeROTjmJicH3Y/M7zL/mjU/M/8SjVrHo3Zv1L78ddOIbASIwK@BCxFy8jbF8N4NKDQm8svBvv/j3UFwdRK8OikAIsfQbaOdhGgMpeTgrAcYdIR5n5jXZM0O84bMO2PNt6LgGH4vp4vQarWMt0EjHg6YcrgN5fHaE/iJ4R7X9U0TT6d/AA

**デフォルトの名無しさん** · 2023/05/23(火) 21:04:58.28

>>700
こっちのPowerShellでやれば全部OK
https://github.com/PowerShell/PowerShell
Name Value
---- -----
PSVersion 7.3.4
PSEdition Core

.NET 7凄すぎ

**デフォルトの名無しさん** · 2023/05/27(土) 01:36:20.91

お題：現在の日時の文字列が与えられるのでその文字列の先頭から秒数分を切り出して出力せよ

**デフォルトの名無しさん** · 2023/05/27(土) 02:11:47.73

>>702
それって秒の部分だけが残れば良いってこと? たとえば 2023/05/27 02:03:45 なら最後の 45 だけになれば良いの?
もしそうなら sed 使ってこうすればできるな。

sed 's/^.*://'

YYYY/MM/DD hh:mm:ss 形式ではなく秒が最後に出て来ない形式だったとしても最後のコロンの直後の数字が秒で、
その秒の数字文字列の後に数字でない文字が必ず来るのだとすれば (例えば Sat May 27 02:05:47 JST 2023 の
ような形式だとすれば)こうすれば良い。

sed 's/^.*://;s/[^0-9].*$//'

**デフォルトの名無しさん** · 2023/05/27(土) 02:42:42.27

サンプルケース書いてくれ

**デフォルトの名無しさん** · 2023/05/28(日) 09:45:16.03

お題　ナイトツアー

5×5の狭いチェスボードのどこかにナイトのコマを置きそこからナイトの可能な動きでコマを動かします
ただし同じマスは2回通れません
このとき全マス25マスを全て通る手順の数を数え上げて下さい
しかし実際全部数えるのは流石に無駄なので対称性を利用して
♯{A1→B3}×8
+ ♯{A3→B5}×8 + ♯{A3→C4}×8
+ ♯{B2→C4}×8
+ ♯{C3→D5}×8
はよいとします

例
♯{A1→B3} = 152

--ナイトの動き--
桂馬の動きと同じ、水平方向の移動量+垂直方向の移動量 = 3となる移動(もちろん盤の中)

**デフォルトの名無しさん** · 2023/05/28(日) 11:22:07.87

>>705

訂正
> --ナイトの動き--
水平方向の移動量+垂直方向の移動量 = 3となる移動で水平、垂直な移動はなし(もちろん盤の中)

**デフォルトの名無しさん** · 2023/05/28(日) 23:12:57.01

>>705
対称性を考慮するのは面倒なので全部数え上げる。Rで書いたら5秒以内に到底終わらなかったので、
ideone.com/y5Dwy7
C++に移植した。盤面表示はideoneでは途中で切れてしまうので非表示にした（関数moveの
コメント部分をコメントでなくせば表示される）。
ideone.com/6Muw9F

対称性を考慮すれば、手順数は1728 / 8 = 216通りになる。

**蟻人間** ◆T6xkBnTXz7B0 · 2023/05/29(月) 01:40:51.78

お題: 水の流れる複数のタンクにおいて水の流れをシミュレーションしたいので、以下に定義する入力文字列でタンクと
水の流れなどを記述する。入力文字列は次のような形式の行の並びとする。

「(タンクの名前), (タンクの底面積[m^2]), (タンクの底からの排水口までの高さ[m]), (次のタンクの名前)」

各行は各タンクの情報とその次のタンクを表す。入力文字列の最初の行は最初に水が入るタンクに対応する。最初のタンクには外部から水が0.5[m^3/min]の速度で入る。タンクの形状は円錐か四角錐とし、底面は平面状とする。
各タンクには排水口が付いているかも知れない。排水口があるのならそれはタンクの底より高く、タンクの側面に付いている。
排水口は次のタンクにつながっている。次のタンクはその前のタンクより低い位置にある。各タンクにおいて排水口に水が届いていないときは水は排水されない。
タンクとタンクの間の長さと水の落差にかかる時間は無視して構わない。次のタンクがN/Aならそのタンクに排水口と排水先はない。

シミュレーション開始後、1分ごとに各タンクに何[m^3]の水が入っているかを出力せよ。タンクCが満タンなら終了せよ。

(入力)
A, 3, 0.5, B
B, 2, 0.7, C
C, 1, 0.4, N/A

**デフォルトの名無しさん** · 2023/05/29(月) 01:46:57.43

>>705
Kotlin

馬鹿正直に再帰で全パターンやっているだけ。
途中経過は出力しない。既に置かれたマスは1bitで記録されるようにして 5 * 5 = 25 bit で Int (32bit) に収まるのでそれを利用している。
恐らく Boolean の配列を使って書くとそこまで最適化されなさそうなのでこうした。

https://paiza.io/projects/O4Ejxs76h64GSeXYCVs2mg

結果は同じ 1728 になったので多分これで合っていると思う。