Bash
ProjectEuler
数学

Project Euler Q42 【符号化三角数】

More than 1 year has passed since last update.

Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。

問題

三角数の$n$項は $t_n = \frac{1}{2}n(n+1)$で与えられる. 最初の$10$項は
$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...$

である.

単語中のアルファベットを数値に変換した後に和をとる. この和を「単語の値」と呼ぶことにする. 例えば $SKY$ は $19 + 11 + 25 = 55 = t_{10}$である. 単語の値が三角数であるとき, その単語を三角語と呼ぶ.

$16K$のテキストファイル words.txt 中に約$2000$語の英単語が記されている. 三角語はいくつあるか?

解答

cat words.txt |
tr -d '"' |
tr ',' '\n' |
sort |
nl |
awk '{for(i=1;i<=length($2);i++){print $1,substr($2,i,1)}}' |
sort -k2,2 |
join -j 2 - <(echo {A..Z} | tr ' ' '\n' | nl) |
sort -k2,2n |
awk '{a[$2]+=$3}END{for(i=1;i<=length(a);i++){print a[i]}}' |
awk '{print $1,sqrt(8*$1+1)}' |
fgrep -v '.' |
wc -l
162

「単語の値が三角数である」を整理すると、「$\sqrt(8*単語の値+1)$が整数である」ということが導ける。
※正確には整数であっても偶数の場合はNGだが、上記が偶数ということは$(8*単語の値+1)$が$4$の倍数ということである。これはありえない。

別解

cat words.txt |
tr -d '"' |
od -An -td1 |
tr -d '\n' |
sed 's/44/\n/g' |
awk '{for(i=1;i<=NF;i++){s[NR]+=$i};print s[NR]-64*NF}' |
awk '{print $1,sqrt(8*$1+1)}' |
fgrep -v '.' |
wc -l
162

odコマンドを使ってみた。普段は-tx1cで使うが、$10$進数が欲しかったので初めて-td1を使った。

答え合わせ

こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/042.html