Namaran

Code daily. Without assist.

2026-10-17

tower.rs

fn tower(xs: &[u32]) -> u32 {
}

列 xs が [x1, x2, …, xn] のとき、x1^(x2^(…^xn)) を返す tower を書いてください。ここでの ^ は Rust の演算子ではなく累乗の記号で、数学で 2^3^2 を 2^(3^2) と読むのと同じく、右から順に計算します。このように累乗を重ねた式を、累乗の塔(power tower)といいます。要素が1つならその値を、空の列には 1 を返します。結果が u32 に収まる入力だけを考えます。

入力例 1

tower(&[2, 2, 3])

出力例 1

256

入力例 2

tower(&[3, 2])

出力例 2

9

入力例 3

tower(&[])

出力例 3

1
Reference
fn tower(xs: &[u32]) -> u32 {
    xs.iter().rev().fold(1, |acc, &x| x.pow(acc))
}

右から計算するので、列を後ろから畳み込みます。rev() で後ろの要素から取り出し、fold の累積値 acc にはそこまでに計算した右側の指数を持たせて、x.pow(acc) で1段ずつ積み上げます。[2, 2, 3] なら、acc は 1 から始まって、3、8、256 と進みます。

初期値の 1 は空の列の答えで、要素が1つのときも x.pow(1) が x になるので、場合分けは要りません。rev() を忘れると、先頭の要素がいちばん上の指数に回り、[2, 2, 3] は 3^(2^2) の 81 になります。(2^2)^3 のように左から計算すると、今度は 64 です。

掲載したのは参考実装で、唯一の正解ではありません。xs.iter().rfold(1, |acc, &x| x.pow(acc)) も後ろから畳み込みます。スライスパターンで [x, rest @ ..] に分け、x.pow(tower(rest)) を返す再帰で書いても、右から計算する形がそのまま式に出ます。