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

**デフォルトの名無しさん** · 2023/08/03(木) 13:52:13.20

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

【出題と回答例】
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/

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

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

**デフォルトの名無しさん** · 2023/08/03(木) 14:04:23.10

>>1
O2

**デフォルトの名無しさん** · 2023/08/06(日) 12:21:14.08

お題
1行につき一つの文章が入力されます
アルファベット26文字がすべて含まれている文章をフィルタリングしてください
大文字小文字は区別しません
そのうちもっとも短い文章を出力してください

入力
The quick brown fox jumps over a lazy dog.
The jay, pig, fox, zebra and my wolves quack!
Pack my box with seven dozen liquor jugs.
The horse, pig, fox, zebra and my wolves quack!
Jackdaws love my small sphinx of quartz.
Jackdaws love my big sphinx of quartz.
The quick brown fox jumps over a lazy cat.
Pack my box with five dozen liquor jugs.

出力
Jackdaws love my big sphinx of quartz.

**デフォルトの名無しさん** · 2023/08/06(日) 17:47:37.64

>>3
Kotlin
https://paiza.io/projects/cmJpXwaAhFH6jYozb0bb2g

**デフォルトの名無しさん** · 2023/08/06(日) 18:08:09.04

>>3
C
https://paiza.io/projects/McLPuKlM4c-1C9EgarDGjw

**デフォルトの名無しさん** · 2023/08/06(日) 19:07:03.27

use std::io::{self, BufRead, BufReader};
const FULL_BITS: u32 = (1 << 26) - 1;
fn main() {
　let mut shortest: Option<String> = None;
　for line in BufReader::new(io::stdin()).lines() {
　　let line = line.unwrap();
　　let mut bits = 0;
　　for b in line.as_bytes() {
　　　let index = match b {
　　　　b'A'..=b'Z' => b - b'A',
　　　　b'a'..=b'z' => b - b'a',
　　　　_ => continue,
　　　};
　　　bits |= 1 << index;
　　}
　　if bits != FULL_BITS {
　　　continue;
　　}
　　if let Some(ref shortest) = shortest {
　　　if shortest.len() < line.len() {
　　　　continue;
　　　}
　　}
　　shortest = Some(line);
　}
　if let Some(shortest) = shortest {
　　println!("{shortest}");
　} else {
　　eprintln!("ERROR: no matched lines");
　}
}

**デフォルトの名無しさん** · 2023/08/06(日) 20:04:54.35

>>3
R
https://ideone.com/ZdKsPa

**デフォルトの名無しさん** · 2023/08/07(月) 01:25:47.55

>>6
それなんて言語？

9 · 2023/08/07(月) 01:46:18.23

>>3 Perl5

for (<DATA>) {
　my %h = map{$_ => 1} grep{/[a-z]/i} split '';
　push @a, $_ if 26 == keys %h;
}
@s = sort{length($a) <=> length($b)} @a;
print $s[0];
__DATA__
The quick brown fox jumps over a lazy dog.
The jay, pig, fox, zebra and my wolves quack!
Pack my box with seven dozen liquor jugs.
The horse, pig, fox, zebra and my wolves quack!
Jackdaws love my small sphinx of quartz.
Jackdaws love my big sphinx of quartz.
The quick brown fox jumps over a lazy cat.
Pack my box with five dozen liquor jugs.

※ 見易くするためインデントを全角スペースに置換してあります。

実行結果：

$ perl 22_3_az26.pl
Jackdaws love my big sphinx of quartz.

**デフォルトの名無しさん** · 2023/08/07(月) 01:57:03.56

>>9 ｺﾞﾒﾝ、2行目に間違いあり…orz

　my %h = map{$_ => 1} grep{/[a-z]/i} split '';
　↓正しくは
　my %h = map{$_ => 1} map{lc} grep{/[a-z]/i} split '';

実行結果は今回のテストデータだとたまたま同じ結果になる。

**デフォルトの名無しさん** · 2023/08/07(月) 09:39:33.60

>>8
Rustでは？

**デフォルトの名無しさん** · 2023/08/07(月) 19:28:19.42

>>11
言われてみればRustに見えるな。
Rustは趣味で学習始めたばかりでよく分からなかった。

**デフォルトの名無しさん** · 2023/08/07(月) 20:51:54.50

>>3
Haskell
https://ideone.com/ACKqL8

**デフォルトの名無しさん** · 2023/08/08(火) 16:30:48.37

>>10 2行目はもっと簡潔に書ける

　my %h = map{$_ => 1} map{lc} grep{/[a-z]/i} split '';
　↓
　my %h = map{lc $_ => 1} /([A-Za-z])/g;

結局、これでよい筈

for (<DATA>) {
　my %h = map{lc $_ => 1} /([A-Za-z])/g;
　push @a, $_ if 26 == keys %h;
}
@s = sort{length $a <=> length $b} @a;
print $s[0];
__DATA__
… (ry

**デフォルトの名無しさん** · 2023/08/08(火) 19:36:27.56

>>3
Rust

use std::collections::HashSet;
use std::io::{self, BufRead, BufReader};

fn main() {
　match BufReader::new(io::stdin())
　　.lines()
　　.map(Result::unwrap)
　　.filter(|line| {
　　　line.bytes()
　　　　.filter(|b| matches!(b, b'A'..=b'Z'| b'a'..=b'z'))
　　　　.collect::<HashSet<_>>()
　　　　.len()
　　　　.eq(&26)
　　})
　　.min_by_key(String::len)
　{
　　Some(shortest) => println!("{shortest}"),
　　None => eprintln!("ERROR: no matched lines"),
　}
}

**デフォルトの名無しさん** · 2023/08/09(水) 12:27:32.68

無駄に比較回数が増えるsortを使っている>>13と>>14は不正解
単純にminが正解

**デフォルトの名無しさん** · 2023/08/10(木) 13:37:16.01

>>3
Perl
https://paiza.io/projects/05DzwASHT6-4bVjpenNDBQ

**蟻人間** ◆T6xkBnTXz7B0 · 2023/08/10(木) 19:00:30.10

お題: ちょっとした画像処理。

赤い丸がいくつか描画された不透明な画像ファイル「input.png」を読み込んで、赤い丸を緑の丸に描き変えたものを画像ファイル「output.png」に保存するプログラム。

ここに「赤い」とは、HSV色空間において、色相が0度～60度か300度～360度の範囲にあり、彩度が30%以上で、明度が50%以上の色であると定義する。
「丸」とは、円形度が0.7～1.3の範囲の単一色の図形であると定義する。
「緑」とはRGBで#008000の色であると定義する。

**デフォルトの名無しさん** · 2023/08/10(木) 19:03:42.87

絶対自分でやる気ないお題出すな

**デフォルトの名無しさん** · 2023/08/10(木) 19:07:41.57

>>6
>>15
同じ言語とは思えないほど違うな

**デフォルトの名無しさん** · 2023/08/10(木) 21:44:28.63

>>16
このスレで正解とか不正解とか言ってる時点で不正解

**デフォルトの名無しさん** · 2023/08/11(金) 00:03:07.62

>>16
head , sort で無駄ソートは起こらない
minimumByと最大2倍程度の差しか発生しない

https://hackage.haskell.org/package/base-4.18.0.0/docs/src/Data.OldList.html#sort

**デフォルトの名無しさん** · 2023/08/11(金) 00:37:49.70

今回のようなsortを一切必要としない問題で何度もsortを用いるプログラマーは劣等生

**デフォルトの名無しさん** · 2023/08/11(金) 00:43:13.53

>>23
Haskellのhead . sortはソートしないってのに
sortって書いてあるからソートすると思ってるんやろ？

**デフォルトの名無しさん** · 2023/08/11(金) 01:09:02.59

sortを使うことを問題にしているのであって
sortしていないなら問題ないだろう
個別の話などしていない

そこまで言うならとHaskellのプログラム
>>13を見にいってみたが
入力文字列を各文字でソートして重複を取り除いてabcdefghijklmnopqrstuvwxyzと比較しているのか

hasAllAlph = ( == [ 'a' .. 'z' ] ) . tail . nub . sort . map toLowOrSp . ( ' ' : )

9 · 2023/08/11(金) 02:38:50.64

ｽﾚが伸びているので何かと思えば、ｵﾚほか一部の回答者がsortを使ったのが
そんなに気に入らなかったか、気に障ったか、
ざまぁみろｗとしか言いようがないが

後出しでｹﾁつけてるのは出題者じゃないようだが
そしたらsortも、そしてminもあえて使わないバージョン、
書き方はいろいろあると思うけど：

>>3 Perl5
use List::Util 'first';
for (<DATA>) {
　my %h = map{lc $_ => 1} /([A-Za-z])/g;
　$a[length $_] = $_ if 26 == keys %h;
}
print first{defined} @a;
__DATA__
The quick brown fox jumps over a lazy dog.
The jay, pig, fox, zebra and my wolves quack!
Pack my box with seven dozen liquor jugs.
The horse, pig, fox, zebra and my wolves quack!
Jackdaws love my small sphinx of quartz.
Jackdaws love my big sphinx of quartz.
The quick brown fox jumps over a lazy cat.
Pack my box with five dozen liquor jugs.

実行結果
~ $ perl 22_3_az26_a.pl
Jackdaws love my big sphinx of quartz.

**デフォルトの名無しさん** · 2023/08/11(金) 02:52:08.14

そう、haskellの評価戦略はcall by need (の一種) で必要に応じて展開される、head . sort では「sortした後の最初の項」を求めているのでそれを出すための必要最小限の事しかしない

件のData.Listにおけるsortでは
①与えられた列を1回目のバスで広義単調増大列いくつかに分割する、コストはO(n)
②できた列を２つずつマージして広義単調増大列の個数を半分にする、全部やればコストはO(n)
③②を列の数が1になるまで繰り返す、コストはO(log(n))
で全部の処理を要求してもO(nlog(n))でいわゆるクイックソートと同じコスト
しかしheadがこのsortの処理を呼ぶ時にはmergeする2列の中の最小値だけ残されてあとは捨てられる、なので最初の①の結果が最悪のケース、長さ1の列がn個できた場合でもmerge処理は最大n-1回だけ行われて終了する、すなわち事実上minimumと一緒
じゃあminimumBy ( on length )でいいじゃんという話なのだけど「遅延評価を利用すればほとんどコストレスでminimumByと同様の事ができる」というのがHaskellの面白いところ
なのでそっちを採用
これは遅延評価の文化に慣れてないと中々わからない

**デフォルトの名無しさん** · 2023/08/11(金) 07:58:17.97

>>25
そちらのsortはO(nlog(n))なのでダメですね

9 · 2023/08/11(金) 08:37:47.88

O(nlog(n))がダメかどうかは、データの規模および実行時間による

**デフォルトの名無しさん** · 2023/08/11(金) 09:12:59.75

あかん、通じてないね
時間の無駄やった

**デフォルトの名無しさん** · 2023/08/11(金) 09:22:47.99

Perlな人の短く書ければよいだけで計算量とか知らないだろうから仕方ないと思うよ
しかしHaskellな人がsortを何箇所も使っているのは驚いた
head . sort以外のsortはあかんね

**デフォルトの名無しさん** · 2023/08/11(金) 09:27:54.00

お前ら賢いんだから自分も疑え

**デフォルトの名無しさん** · 2023/08/11(金) 14:03:26.02

doubt

17 · 2023/08/11(金) 16:34:17.24

俺は Perl で書いたやつも sort 使わず >>4,5 と同じやり方にした。
一番短い文を最後に出すだけで良いなら sort やる必要ないよね。
何らかの制約があってそうしなければ出来ないとか、使っても思い切り最適化されて最終的に同じ動きになるというなら使うかも知れないが。

**デフォルトの名無しさん** · 2023/08/11(金) 17:25:08.27

遅延評価は馴染みない人にはわからんからしょうがない

**デフォルトの名無しさん** · 2023/08/11(金) 17:41:01.68

Haskell版で問題にされてるのは
遅延評価でO(n)となるhead $ sort部分ではなく
O(nlog(n))のsortが別途あること

**デフォルトの名無しさん** · 2023/08/11(金) 22:35:55.39

>>35
遅延評価は色んな言語にあるよ
その対象や動作は各言語や各機能によって様々で
PromiseやFutureのような非同期に遅延評価されるものもあるけど
今回のお題だとC#のLINQメソッドチェーンによる遅延評価やRubyのlazy指定などが有効だね
>>15のRustのイテレータメソッドチェーンも遅延評価されるから何万行の入力が来てもメモリを消費せずに済むね

**デフォルトの名無しさん** · 2023/08/14(月) 19:55:41.01

マサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲ
マサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲ
マサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲ
マサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲ

ヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマ
ヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマ
ヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマ
ヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマ

マサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲ
マサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲ
マサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲ
マサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲマサナヲ

ヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマ
ヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマ
ヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマ
ヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマヲナサマ

**デフォルトの名無しさん** · 2023/08/14(月) 20:16:21.84

>>38
Java

public class Main {
　public static void main(String[] args) {
　　System.out.println(
　　　　"マサナヲ".repeat(8).concat("\n").repeat(4).concat("\n")
　　　　　　.concat("ヲナサマ".repeat(8).concat("\n").repeat(4).concat("\n"))
　　　　　　.repeat(2));
　}
}

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

このサイトより
http://agora.ex.nii.ac.jp/digital-typhoon/
2023/8/1/0/0 から 2023/8/16/23/0 まで
表示日時を変更しながら1時間毎の静止気象衛星画像（地球）を収集し
(衛星画像は可視光 2048x2048 程度 512x512 等も可起動オプションで指定出来るとボーナス特典)
gif animation または png animation ファイルに変換せよ

例
8/14/0/0 http://agora.ex.nii.ac.jp/digital-typhoon/globe/color/2023/512x512/HMW923081315.globe.1.jpg
8/15/0/0 http://agora.ex.nii.ac.jp/digital-typhoon/globe/color/2023/512x512/HMW923081415.globe.1.jpg
8/15/15/0 http://agora.ex.nii.ac.jp/digital-typhoon/globe/color/2023/512x512/HMW923081505.globe.1.jpg

**デフォルトの名無しさん** · 2023/08/15(火) 23:36:55.46

蟻人間がコテハン外したのかな

**デフォルトの名無しさん** · 2023/08/16(水) 10:34:21.25

可視光より赤外線の方が雲はきれいだけど
可視光は影が毎日くるくる回るからこっちはこっちで面白いね

9 · 2023/08/16(水) 13:32:44.58

>>40 bash、curl および GraphicsMagick の convert コマンドを使用。動作確認したOSはUbuntu 20.04LTS。数百枚のjpegからgifへのconvertには多少時間がかかります。
オプション -h または --highres を指定すると 2048x2048、オプション無しあるいは -l または --lowreso を指定すると 512x512、なおボーナスはスイス銀行の秘密口座に。
※見易くするためインデントは全角スペースに置換してあります。8月16日23時まで取得するようにしているがまだ無い将来の画像は含まない。

res='512x512' # default
OPT=`getopt -o hl -l highreso,lowreso -- "$@"`
eval set -- "$OPT"
while true; do
　case "$1" in
　　-h | --highreso)
　　　res='2048x2048'
　　　shift ;;
　　-l | --lowreso)
　　　res='512x512'
　　　shift ;;
　　--)
　　　shift
　　　break ;;
　esac
done
dir=$(mktemp -d TmpDir.XXXXXX)
for d in $(seq -w 01 16); do
　for h in $(seq -w 0 23); do
　　dh="$d$h"
　　file="HMW92308${dh}.globe.1.jpg"
　　url="http://agora.ex.nii.ac.jp/digital-typhoon/globe/color/2023/${res}/${file}"
　　echo $url; curl -f -s -R -o "$dir/$file" $url
　done
done
#set -x
time convert $(ls $dir/*.jpg) TyphoonAime${res}.gif
ls -o TyphoonAime${res}.gif

9 · 2023/08/16(水) 13:42:58.39

>>43 ｔｙpo orz
-h または --highres
↓
-h または --highreso

9 · 2023/08/16(水) 19:12:35.95

>>43 これだと、scriptを実行するたびに全てのjpegファイルをtemporaryディレクトリにdownloadするためサーバの負荷の面で行儀がよくないので、
　ディレクリは TyphoonJpegDir512x512 または TyphoonJpegDir2048x2048 で固定とし、未取得のjpegがあればdownloadするように直すわ。

res='512x512' # default
OPT=`getopt -o hl -l highreso,lowreso -- "$@"`
eval set -- "$OPT"
while true; do
　case "$1" in
　　-h | --highreso)
　　　res='2048x2048'
　　　shift ;;
　　-l | --lowreso)
　　　res='512x512'
　　　shift ;;
　　--)
　　　shift
　　　break ;;
　esac
done
dir=./TyphoonJpegDir${res}
for d in $(seq -w 01 16); do
　for h in $(seq -w 0 23); do
　　file="HMW92308${d}${h}.globe.1.jpg"
　　url="http://agora.ex.nii.ac.jp/digital-typhoon/globe/color/2023/${res}/${file}"
　　[ -f $dir/$file ] || { echo $url; curl -f -s -R -o "$dir/$file" $url; }
　done
done
#set -x
time convert $(ls $dir/*.jpg) TyphoonAime${res}.gif
ls -o TyphoonAime${res}.gif

※見やすくするためインデントは全角スペースに置換してあります。