にゃみかんてっくろぐ

猫か百合を見守る壁になりたい

Linux コマンドの最長しりとりを求める

ネタ

「 Linux コマンドでしりとりをすると、最長でいくつ繋がるのか？」

この疑問を解消すべく、最長しりとりを求めるプログラムを実装しました。

結論

最長しりとり問題

論文「最長しりとり問題の解法」

全パターン網羅して最長を決める… といきたいところですが、単語数が増えてくると数時間掛けても解けません。

調べてみると、なんと論文になっています。整数計画問題として定式化した上で、分枝限定法により解を得るものです。さらには、既に実装済みのWebサービスやソースコードまであります。

しかし、 Crystal を触りたい、という別の目的から車輪の再発明をすることにしました。

Crystal 実装

ソースコード

論文を読み解きつつ再発明した実装は、 GitHub に公開しています（ソルバーに GLPK を使用しています）。やみくもに木で探索するものも入っています。

Crystal 言語

Crystal は、 Ruby に非常に似た文法を持つ、型推論の付いた静的型付け言語です。

private def self.find_closed_path(v : Char, x : Hash(String, Int32), k : Int32)
  edges = x.select { |k, v| v > 0 }.map { |e| e[0] }
  find_closed_path_recursively(v.to_s, edges, k)
end

型の指定方法、キャスト、プロパティの指定方法などは公式ドキュメントを参照しましたが、それ以外は Ruby のつもりで書けました。それくらい似ています。

ただし、 gem は使えません（ C バインディングは使えます）。「文法が似ている全く別の言語」であることを思い出させてくれます。

結果

各種 Docker イメージの PATH に含まれているコマンドを抽出し、最長しりとりを求めました（いずれも数秒程度で解き終わりました）。

Docker image:tag コマンド数 しりとり長 使用率
alpine:3.10.3 317 173 54.6%
amazonlinux:2.0.20191016.0 261 146 55.9%
centos:8 573 326 56.9%
debian:10.2 409 231 56.5%

なんと CentOS 8 では 300 以上のコマンドが繋がります。 Amazon Linux が Alpine Linux よりもコマンド数が少ないなど、しりとりとは無関係に興味深い点もあります。

以下に、しりとりの内容を記載します。 w または z で始まり、数字で終わっている点はどのディストリビューションも共通です。

Alpine Linux 3.10.3

Length: 173
Shiritori: whoami => ipcs => strings => setlogcons => setkeycodes => swapoff => fgrep => powertop => pmap => pgrep => pwd => depmod => dd => dc => crontab => brctl => lzma => add-shell => login => nologin => nsenter => rmdir => rm => microcom => md5sum => mkdir => reset => timeout => test => ttysize => ether-wake => env => volname => eject => touch => halt => tr => realpath => hdparm => modinfo => openvt => truncate => expr => raidautorun => nl => logger => rfkill => lzopcat => tunctl => lzcat => tail => ln => nmeter => remove-shell => lsusb => bc => chown => nproc => comm => mpstat => tac => crond => dnsdomainname => expand => dirname => ed => deluser => rmmod => date => echo => od => deallocvt => tar => readahead => dumpkmap => passwd => delgroup => ping => gzip => patch => hexdump => pkill => lzop => printenv => vconfig => gunzip => pwdx => xzcat => top => pscan => nc => cksum => mkpasswd => du => unlzma => arping => getopt => true => egrep => printf => fsync => cal => lsof => fdflush => hostid => diff => fbsplash => head => df => fstrim => mesg => getconf => fsck => killall => losetup => poweroff => flock => klogd => dmesg => grep => pidof => findfs => sysctl => ls => setserial => less => sum => mkmntdirs => sha512sum => mkdosfs => su => unix2dos => sync => clear => run-parts => slattach => hd => dumpleases => sendmail => ldconfig => groups => sha3sum => mktemp => ps => sha256sum => mkswap => pipe_progress => sha1sum => mknod => dos2unix => xargs => shuf => fuser => rev => vi => ifconfig => getent => tty => yes => scanelf => fatattr => readlink => kill => lspci => ipcalc => cryptpw => whois => swapon => nameif => factor => rdev => vlock => killall5

Amazon Linux 2.0.20191016.0

Length: 146
Shiritori: zic => curl => ln => nohup => pwd => dd => db_load => diff => fg => gpg => gpg-error => rmdir => rpm => md5sum => mkdir => rpmkeys => sotruss => stat => tzselect => tsort => tset => trust => tput => timeout => test => tabs => split => tty => yes => signver => reset => tr => rpmdb => bg => gsettings => sum => makedb => bashbug => groups => stdbuf => false => ex => xmlcatalog => glib-compile-schemas => sprof => factor => rview => whoami => iconvconfig => getpcaps => shuf => fold => df => find => db_printlog => gdbm_load => dir => read => db_tuner => realpath => hostid => db_recover => rm => mknod => db_stat => truncate => expand => db_checkpoint => touch => head => dircolors => sha512sum => mkfifo => oldfind => db_hotbackup => pldd => db_dump => paste => egrep => printf => fgrep => pinentry-curses => ssltap => pr => rvi => infotocap => printenv => vi => infocmp => pinky => yum => mktemp => ptx => xargs => sleep => python => nice => expr => runcon => numfmt => true => echo => od => du => users => sha384sum => mv => vdir => rpcgen => nl => ls => sha256sum => modutil => lua => applygnupgdefaults => setcap => pk12util => ldconfig => getopts => sdiff => fmt => tail => luac => chown => nproc => cp => pydoc => cut => tic => chkconfig => gdbus => sync => crlutil => localedef => fc => cmp => p11-kit => tac => cmsutil => logname => env => view => wc => certutil => ldd => diff3

CentOS 8

Length: 326
Shiritori: zic => cracklib-unpacker => runuser => rtpr => rmdir => rmmod => dmfilemapd => depmod => dd => dbus-send => db_load => dnf => fg => gpg => groupdel => loginctl => localectl => lastb => busctl => logname => egrep => pmap => pgrep => ps => systemd-tmpfiles => systemd-sysusers => systemd-cgls => strings => ss => sotruss => systemd-delta => as => sum => md5sum => mksquashfs => sha512sum => mkfs.cramfs => sha384sum => mkfs => systemd-run => nologin => newusers => su => users => systemd-machine-id-setup => prlimit => tzselect => tsort => trust => timeout => test => telinit => taskset => tracepath => hash => halt => top => pinky => yum => mktemp => pwunconv => vi => ipcs => swapon => nohup => pwconv => vipw => w => wipefs => sulogin => newuidmap => pwscore => elfedit => type => eject => truncate => echo => objcopy => ypdomainname => evmctl => lesspipe.sh => hostnamectl => login => nl => losetup => pkill => lsns => systemctl => lslogins => sysctl => lslocks => swaplabel => ls => skill => less => setfacl => lnstat => timedatectl => last => tail => ldattach => hostname => ethtool => ldconfig => gpgparsemail => lastlog => gsettings => sg => groups => systemd-hwdb => bg => gapplication => namei => ifcfg => groupmems => systemd-cgtop => pkg-config => glib-compile-schemas => strip => ping => getpcaps => setpriv => vmcore-dmesg => getfacl => lsmem => makedb => bashbug => getopts => systemd-path => hexdump => pwdx => xmlcatalog => gprof => fips-finish-install => localedef => fips-mode-setup => printf => fgrep => poweroff => fsck.cramfs => swapoff => findfs => stdbuf => fstrim => mesg => gpgconf => fsck.minix => xzless => sprof => fold => df => find => dbus-test-tool => lsmod => dwp => pwd => dmsetup => pldd => dracut => tload => dmesg => genl => lsinitrd => db_printlog => gdbmtool => ldd => dbus-uuidgen => nisdomainname => expand => dbus-run-session => nm => mknod => dirmngr-client => touch => hostid => db_hotbackup => pkgconf => fsck => kmod => du => update-crypto-policies => sha256sum => mkinitrd => db_dump => pidof => flock => kill => ld.gold => dhclient-script => tty => yes => sha224sum => mkdumprd => dhclient => true => ex => x86_64-redhat-linux-gnu-pkg-config => gdbus => sha1sum => modinfo => od => dirmngr => read => dir => routef => fix-info-dir => resolvconf => factor => runlevel => logger => rpm => mkhomedir_helper => rm => mkdir => runcon => nsenter => rpmdb => blkid => dbus-monitor => ranlib => blkdiscard => db_tuner => realpath => head => db_recover => rtmon => nice => expr => rview => watchgnupg => gtar => rpmkeys => sleep => pwhistory_helper => routel => ld.bfd => delpart => tr => rfkill => ld => dbus-update-activation-environment => tar => raw => whoami => iconvconfig => gpg-error => rdma => applygnupgdefaults => shutdown => newgrp => printenv => vigr => readelf => fdisk => kernel-install => ln => newgidmap => pivot_root => tee => env => vdir => rdisc => coreutils => sync => command => dbus-daemon => nproc => chpasswd => dmstats => sha512hmac => chmod => dircolors => sha384hmac => chgpasswd => dbus-cleanup-sockets => sha256hmac => cd => db_stat => tipc => chkconfig => getconf => fc => capsh => hwclock => kexec => comm => mountpoint => tac => colrm => mkfs.minix => xzdec => cracklib-packer => rvi => ipcalc => chcpu => update-alternatives => sha224hmac => cksum => mv => view => wc => cp => pr => resolvectl => lsipc => chgrp => ptx => xargs => sha1hmac => chmem => mkswap => partx => xz => zless => shuf => faillock => kdumpctl => lscpu => unxz => znew => whereis => setterm => mkfifo => objdump => p11-kit => tracepath6

Debian 10.2

Length: 231
Shiritori: znew => wc => ctrlaltdel => ldconfig => groupmod => dd => diff => fgrep => paste => e2image => expr => runuser => rmt-tar => rmdir => rm => md5sum => mkfs.cramfs => ss => swapon => nologin => newusers => switch_root => tzselect => tsort => tset => tput => timeout => test => taskset => tarcat => tune2fs => stat => tabs => su => users => split => tty => yes => sum => mkfs.bfs => sha512sum => mkfs => sha384sum => mke2fs => sha256sum => md5sum.textutils => sha224sum => mkhomedir_helper => runcon => nsenter => rtstat => tr => run-parts => sha1sum => mkdir => resize2fs => sort => tar => rtcwake => e4crypt => truncate => expiry => ypdomainname => e2mmpstatus => script => true => env => vigr => renice => egrep => pr => rgrep => pager => rtmon => nohup => ptx => xargs => sulogin => newgrp => printf => factor => routef => fsck.cramfs => swapoff => findfs => stdbuf => fold => df => find => dash => hostid => delgroup => pwd => dumpe2fs => shred => dircolors => setsid => debugfs => sed => du => usermod => dpkg-deb => b2sum => mknod => debconf => fstrim => mklost+found => dpkg-trigger => readprofile => expand => dpkg-maintscript-helper => realpath => head => debconf-set-selections => sleep => policy-rc.d => debconf-apt-progress => setcap => pldd => dir => rbash => hostname => echo => od => dpkg => groupadd => dmesg => getconf => filefrag => gzip => ping => groups => shadowconfig => groupmems => sg => getpcaps => savelog => getopt => tzconfig => gpasswd => debconf-copydb => bashbug => getent => toe => e4defrag => gunzip => pidof => faillog => groupdel => lastlog => genl => login => nl => losetup => perl => lsattr => routel => logger => rename.ul => lsns => swaplabel => lscpu => userdel => ldd => deluser => remove-shell => localedef => fmt => tail => ln => namei => installkernel => lslogins => shuf => findmnt => tempfile => e2label => lslocks => setterm => mesg => grep => passwd => deb-systemd-helper => rdma => add-shell => lsipc => chown => nproc => comm => mountpoint => tipc => cksum => mount => tic => choom => mktemp => prlimit => tc => chmem => mkswap => pivot_root => tac => cppw => wdctl => lsmem => mv => vipw => wipefs => sync => chcpu => useradd => debconf-show => wall => ls => sdiff => fdformat => tee => e2freefrag => getcap => pwunconv => vdir => raw => whoami => install => lastb => badblocks => start-stop-daemon => numfmt => touch => hwclock => killall5

ふたたび結論