この記事は、「paiza×Qiita記事投稿キャンペーン」の キャンペーン対象問題 の解説記事です。
通常の「paizaスキルチェック問題」の解答公開は禁止されています のでご注意ください。
TL; DR
{{- /* 座席の初期化 */ -}}
{{- $seats := "" -}}
{{- /* nSeats <= 100 なので、100回のループをnSeats回で打ち切れば 長さ nSeats の文字列が得られる */ -}}
{{- range $i, $_ := $.Looper -}}
{{- if ge $i $.NSeats -}}
{{- break -}}
{{- end -}}
{{- $seats = print $seats " " -}}
{{- end -}}
{{- /* グループを座席に座らせる */ -}}
{{- range $groupSeat := $.GroupSeats -}}
{{- /* 座席開始位置の取得(スライスは0-originなので1引いて調整) */ -}}
{{- $seatStartNumStr := "" -}}
{{- range $.Looper -}}
{{- if ge (len $seatStartNumStr) $groupSeat.SeatNum -}}
{{- break -}}
{{- end -}}
{{- $seatStartNumStr = print $seatStartNumStr " " -}}
{{- end -}}
{{- $seatStartNumStr = slice $seatStartNumStr 1 -}}
{{- $seatStartNum := len $seatStartNumStr -}}
{{- /* 席が空いているか確認 */ -}}
{{- $used := false -}}
{{- $seatNumStr := $seatStartNumStr -}}
{{- range $i, $_ := $.Looper -}}
{{- if ge $i $groupSeat.NMembers -}}
{{- break -}}
{{- end -}}
{{- $seatNum := len $seatNumStr -}}
{{- if ne (index $seats $seatNum) ' ' -}}
{{- $used = true -}}
{{- break -}}
{{- end -}}
{{- /* $seatNumStrのインクリメント(範囲を超えたら0番に戻る) */ -}}
{{- $seatNumStr = print $seatNumStr " " -}}
{{- if ge (len $seatNumStr) $.NSeats -}}
{{- $seatNumStr = slice $seatNumStr $.NSeats -}}
{{- end -}}
{{- end -}}
{{- /* 空いている場合座る */ -}}
{{- if $used -}}
{{- continue -}}
{{- end -}}
{{- $seatNumStr = $seatStartNumStr -}}
{{- range $i, $_ := $.Looper -}}
{{- if ge $i $groupSeat.NMembers -}}
{{- break -}}
{{- end -}}
{{- $seatNum := len $seatNumStr -}}
{{- $nextSeatNum := len (print $seatNumStr " ") -}}
{{- $seats = print (slice $seats 0 $seatNum) "x" (slice $seats $nextSeatNum) -}}
{{- /* $seatNumStrのインクリメント(範囲を超えたら0番に戻る) */ -}}
{{- $seatNumStr = print $seatNumStr " " -}}
{{- if ge (len $seatNumStr) $.NSeats -}}
{{- $seatNumStr = slice $seatNumStr $.NSeats -}}
{{- end -}}
{{- end -}}
{{- end -}}
{{- /* 座っている人数を数える */ -}}
{{- $customers := "" -}}
{{- range $i, $_ := $.Looper -}}
{{- if ge $i (len $seats) -}}
{{- break -}}
{{- end -}}
{{- $seat := index $seats $i -}}
{{- if ne $seat ' ' -}}
{{- $customers = print $customers "x" -}}
{{- end -}}
{{- end -}}
{{- $nCustomers := len $customers -}}
{{- println $nCustomers -}}
はじめに
Paizaスキルチェックでは、30種類以上の言語 が使用可能です。
しかし、皆さん、上記リストに直接は載っていないこの言語をお忘れではないでしょうか?
{{- $s := "world!" -}}
Hello, {{ $s }}
そうです、Goの text/template
です。
Go Template1はGo標準のDSL/テンプレートエンジンで、HugoやHelm等でも使用されています。
しかし、Go Templateは単なるテンプレートにとどまらず、その構文は Cコンパイラを実装できる ほど強力です。
というわけで、本記事ではPaizaの問題をGo Templateで解いてみたいと思います。
問題
挑戦するのはこちらの問題です。スキルチェックBランク相当の難易度です。
詳細についてはリンク先の図を見ていただくとして、簡単にまとめると
- 円卓2にお客さんをグループごとに案内する
- お客さんはグループ全員横並びでしか座れない
- 横並びで座れないならグループ全員帰る
- 最終的に座れたお客さんの人数を数える
という問題です。円卓であることがミソで、配列で計算する場合 seats[n-1]
と seats[0]
が隣どうしの扱いになります。
解答
ソースコード(クリックで開く)
package main
import (
"bufio"
"os"
"strconv"
"strings"
"text/template"
)
var tmplStr = `
{{- /* 座席の初期化 */ -}}
{{- $seats := "" -}}
{{- /* nSeats <= 100 なので、100回のループをnSeats回で打ち切れば 長さ nSeats の文字列が得られる */ -}}
{{- range $i, $_ := $.Looper -}}
{{- if ge $i $.NSeats -}}
{{- break -}}
{{- end -}}
{{- $seats = print $seats " " -}}
{{- end -}}
{{- /* グループを座席に座らせる */ -}}
{{- range $groupSeat := $.GroupSeats -}}
{{- /* 座席開始位置の取得(スライスは0-originなので1引いて調整) */ -}}
{{- $seatStartNumStr := "" -}}
{{- range $.Looper -}}
{{- if ge (len $seatStartNumStr) $groupSeat.SeatNum -}}
{{- break -}}
{{- end -}}
{{- $seatStartNumStr = print $seatStartNumStr " " -}}
{{- end -}}
{{- $seatStartNumStr = slice $seatStartNumStr 1 -}}
{{- $seatStartNum := len $seatStartNumStr -}}
{{- /* 席が空いているか確認 */ -}}
{{- $used := false -}}
{{- $seatNumStr := $seatStartNumStr -}}
{{- range $i, $_ := $.Looper -}}
{{- if ge $i $groupSeat.NMembers -}}
{{- break -}}
{{- end -}}
{{- $seatNum := len $seatNumStr -}}
{{- if ne (index $seats $seatNum) ' ' -}}
{{- $used = true -}}
{{- break -}}
{{- end -}}
{{- /* $seatNumStrのインクリメント(範囲を超えたら0番に戻る) */ -}}
{{- $seatNumStr = print $seatNumStr " " -}}
{{- if ge (len $seatNumStr) $.NSeats -}}
{{- $seatNumStr = slice $seatNumStr $.NSeats -}}
{{- end -}}
{{- end -}}
{{- /* 空いていない場合誰も座らない */ -}}
{{- if $used -}}
{{- continue -}}
{{- end -}}
{{- /* 空いている場合座る */ -}}
{{- $seatNumStr = $seatStartNumStr -}}
{{- range $i, $_ := $.Looper -}}
{{- if ge $i $groupSeat.NMembers -}}
{{- break -}}
{{- end -}}
{{- $seatNum := len $seatNumStr -}}
{{- $nextSeatNum := len (print $seatNumStr " ") -}}
{{- $seats = print (slice $seats 0 $seatNum) "x" (slice $seats $nextSeatNum) -}}
{{- /* $seatNumStrのインクリメント(範囲を超えたら0番に戻る) */ -}}
{{- $seatNumStr = print $seatNumStr " " -}}
{{- if ge (len $seatNumStr) $.NSeats -}}
{{- $seatNumStr = slice $seatNumStr $.NSeats -}}
{{- end -}}
{{- end -}}
{{- end -}}
{{- /* 座っている人数を数える */ -}}
{{- $customers := "" -}}
{{- range $i, $_ := $.Looper -}}
{{- if ge $i (len $seats) -}}
{{- break -}}
{{- end -}}
{{- $seat := index $seats $i -}}
{{- if ne $seat ' ' -}}
{{- $customers = print $customers "x" -}}
{{- end -}}
{{- end -}}
{{- $nCustomers := len $customers -}}
{{- println $nCustomers -}}
`
type Input struct {
NSeats int
GroupSeats []*GroupSeat
// HACK: ループの補助に使用
Looper [100]struct{}
}
type GroupSeat struct {
NMembers int
SeatNum int
}
func readInput() Input {
sc := bufio.NewScanner(os.Stdin)
sc.Scan()
elems := strings.Split(sc.Text(), " ")
nSeats, _ := strconv.Atoi(elems[0])
nGroup, _ := strconv.Atoi(elems[1])
groupSeats := make([]*GroupSeat, nGroup)
for i := 0; i < nGroup; i++ {
sc.Scan()
elems = strings.Split(sc.Text(), " ")
nMembers, _ := strconv.Atoi(elems[0])
seatNum, _ := strconv.Atoi(elems[1])
groupSeats[i] = &GroupSeat{
NMembers: nMembers,
SeatNum: seatNum,
}
}
return Input{
NSeats: nSeats,
GroupSeats: groupSeats,
}
}
func main() {
input := readInput()
tmpl, err := template.New("tmpl").Parse(tmplStr)
if err != nil {
panic(err)
}
err = tmpl.Execute(os.Stdout, input)
if err != nil {
panic(err)
}
}
標準入力のみGo側でパースして、テンプレートに渡しています3。
テンプレートを実行すると解答の出力文字列になります。
スキルチェックでは標準モジュールしか使えないため、Go Templateの便利関数ライブラリである sprig 4 に頼ることはできません。
整数の足し算もスライス生成もありません。
しかし、組み込み関数と仲良くなってこそのGo Template使い。以下、実装で使用したテクニックを解説します。
解説
Templateでのプログラミングの基本テクニック
まずは、プログラミング言語としてGo Templateを使用する場合の書き方について紹介します。
地の文 ({{ }}
で囲まれていない部分)には何も書かない
Go Templateでは、{{ }}
の外側に書いた文字は、そのまま表示されます。
Hello, {{ "world!" }}
Hello, world!
しかし、今回の問題では計算結果のみを表示したいため、 {{ }}
の外側には何も記載しないようにします。
前後の空白を除去
{{ }}
の両端に-
を付けると、かっこの外側の空白を詰めることが出来ます。これを使えば、{{}}
の外側でインデント、改行を入れてもすべて無視されます。
Go Templateプログラミングでは可読性のために必須です。付けないとワンライナー縛りが始まります。
- ハイフンなし
{{if true}}
{{println "got it!"}}
{{else}}
{{println "no..."}}
{{end}}
got it!
- ハイフンあり
{{- if true -}}
{{- println "got it!" -}}
{{- else -}}
{{- println "no..." -}}
{{- end -}}
got it!
変数
$hoge
で変数を宣言できます。また、 $
は特殊な変数で、テンプレート実行関数 tmpl.Execute
の第2引数からテンプレートへ渡した値が入っています。
構造体のフィールドについてはGo本家同様 $hoge.Fuga
の形式で参照可能です。
また、変数宣言を行っても文字は出力されないため、どこで使っても問題ありません。
{{- $s := "world!" -}}
Hello, {{ $s }}
Hello, world!
ループ
Go Template組み込み関数縛りで最も頭を悩ませる問題がループです。入力として スライス/配列かマップが与えられないとループできません。
理由:
- スライス、マップのリテラルが使えない(Template内で生成できない)
- 文字列はループできない
- 無限ループや
for i := 0; i < n; i++
形式のfor文が存在しない
今回は、入力の構造体に配列のフィールドを持たせることでループできるようにしました。
Go Templateプログラミングとしてグレーな気もするので別の解決策が欲しい...
type Input struct {
NSeats int
GroupSeats []*GroupSeat
// HACK: ループの補助に使用
Looper [100]struct{}
}
{{- /* Looperは配列なのでループに使用可能 */ -}}
{{- range $i, $_ := $.Looper -}}
{{- /* この中で繰り返し処理(終わったらbreakで抜ける) */ -}}
{{- end -}}
今回、問題文より座席数もグループ数も100以下であることが分かっているため、ループの回数を 100
にしています。
標準入力を受け取る
実際の処理を見ていきます。まずは標準入力から必要な情報を読み取ります。
残念ながらTemplate標準関数に Atoi
(文字列から整数への変換) が無い5ため、入力のパースまではGo本体側で行いました。
${座席数} ${グループ数}
${グループ1の先頭の座席番号} ${グループ1の人数}
${グループ2の先頭の座席番号} ${グループ2の人数}
...
type Input struct {
NSeats int
GroupSeats []*GroupSeat
// HACK: ループの補助に使用
Looper [100]struct{}
}
type GroupSeat struct {
NMembers int
SeatNum int
}
func readInput() Input {
sc := bufio.NewScanner(os.Stdin)
sc.Scan()
elems := strings.Split(sc.Text(), " ")
nSeats, _ := strconv.Atoi(elems[0])
nGroup, _ := strconv.Atoi(elems[1])
groupSeats := make([]*GroupSeat, nGroup)
for i := 0; i < nGroup; i++ {
sc.Scan()
elems = strings.Split(sc.Text(), " ")
nMembers, _ := strconv.Atoi(elems[0])
seatNum, _ := strconv.Atoi(elems[1])
groupSeats[i] = &GroupSeat{
NMembers: nMembers,
SeatNum: seatNum,
}
}
return Input{
NSeats: nSeats,
GroupSeats: groupSeats,
}
}
座席の初期化
いよいよTemplateに書かれた処理に入っていきます。はじめに座席の初期化です。
組み込み関数やリテラルではスライスを生成することができないため、代わりに文字列で以下のように表現します。
-
$seats
の長さは座席数 -
$seats
のi
文字目が- 空白: 座っていない
-
x
: 座っている
初期化時には、空文字を $.NSeats
回結合して誰も座っていない状態にします。
{{- $seats := "" -}}
{{- /* nSeats <= 100 なので、座席の初期化が途中で打ち切られることは無い */ -}}
{{- range $i, $_ := $.Looper -}}
{{- if ge $i $.NSeats -}}
{{- break -}}
{{- end -}}
{{- $seats = print $seats " " -}}
{{- end -}}
グループが座れるかどうかの確認
続いて、グループが座る予定の座席がすべて空いているかを確認します。
他の言語であれば、seats[seatStartNum]
から seats[seatStartNum+SeatNum-1]
の間に埋まっている座席が無いことを確認するだけです。
一方、Go Templateの組み込み関数では 加算、減算ができません 。seatStartNum+SeatNum
も seatStartNum+i
もそのままでは表現できません。
加算、減算の方法
Go Templateでは加算、減算ができないため、代わりに 文字列の長さ を使用します。
文字列は結合、スライシングにより長さを変えることができ、len
関数で長さを整数で取得できます。
- 加算
空文字を1文字結合することでインクリメントを代用できます。
{{- $numStr := " " -}}
{{- println (len $numStr) -}}
{{- $numStr = print $numStr " " -}}
{{- println (len $numStr) -}}
1
2
- 減算
slice
で先頭要素を省くことでデクリメントを代用できます。
{{- $numStr := " " -}}
{{- println (len $numStr) -}}
{{- $numStr = slice $numStr 1 -}}
{{- println (len $numStr) -}}
1
0
実装
最終的に以下のような実装になりました。ループ内で確認対象のインデックスを1つずつ増やせるよう、 $seatNumStr
の長さでインデックスを管理しています。インデックス取得直前に len
で整数に変換します。
また、円卓なので seats[nSeat-1]
と seats[0]
は隣接しており、 $seatNum
が 座席数以上になったら 0
へ戻るようにしています。
{{- /* グループを座席に座らせる */ -}}
{{- range $groupSeat := $.GroupSeats -}}
{{- /* 座席開始位置の取得(スライスは0-originなので1引いて調整) */ -}}
{{- $seatStartNumStr := "" -}}
{{- range $.Looper -}}
{{- if ge (len $seatStartNumStr) $groupSeat.SeatNum -}}
{{- break -}}
{{- end -}}
{{- $seatStartNumStr = print $seatStartNumStr " " -}}
{{- end -}}
{{- $seatStartNumStr = slice $seatStartNumStr 1 -}}
{{- $seatStartNum := len $seatStartNumStr -}}
{{- /* 席が空いているか確認 */ -}}
{{- $used := false -}}
{{- $seatNumStr := $seatStartNumStr -}}
{{- range $i, $_ := $.Looper -}}
{{- if ge $i $groupSeat.NMembers -}}
{{- break -}}
{{- end -}}
{{- $seatNum := len $seatNumStr -}}
{{- /* NOTE: $seats の要素はbyteになる(" " ではなく ' ')ことに注意! */ -}}
{{- if ne (index $seats $seatNum) ' ' -}}
{{- $used = true -}}
{{- break -}}
{{- end -}}
{{- /* $seatNumStrのインクリメント(ただし範囲を超えたら0番に戻る) */ -}}
{{- $seatNumStr = print $seatNumStr " " -}}
{{- if ge (len $seatNumStr) $.NSeats -}}
{{- $seatNumStr = slice $seatNumStr $.NSeats -}}
{{- end -}}
{{- end -}}
{{- /* ... */ -}}
{{- end -}}
グループを座席に座らせる
グループ全員が座れる場合、座席を座った後の状態に更新します。処理の流れは確認のときとほぼ同じです。
{{- /* グループを座席に座らせる */ -}}
{{- range $groupSeat := $.GroupSeats -}}
{{- /* 席が空いているか確認 */ -}}
{{- /* ... */ -}}
{{- /* 空いていない場合誰も座らない */ -}}
{{- if $used -}}
{{- continue -}}
{{- end -}}
{{- /* 空いている場合座る */ -}}
{{- $seatNumStr = $seatStartNumStr -}}
{{- range $i, $_ := $.Looper -}}
{{- if ge $i $groupSeat.NMembers -}}
{{- break -}}
{{- end -}}
{{- $seatNum := len $seatNumStr -}}
{{- $nextSeatNum := len (print $seatNumStr " ") -}}
{{- $seats = print (slice $seats 0 $seatNum) "x" (slice $seats $nextSeatNum) -}}
{{- /* $seatNumStrのインクリメント(範囲を超えたら0番に戻る) */ -}}
{{- $seatNumStr = print $seatNumStr " " -}}
{{- if ge (len $seatNumStr) $.NSeats -}}
{{- $seatNumStr = slice $seatNumStr $.NSeats -}}
{{- end -}}
{{- end -}}
{{- end -}}
座席更新では以下のように1文字だけ置換した新しい文字列を生成しています(文字列はimmutableなため)。
{{- /* seats[i] = 'x' とできないので、代わりに */ -}}
{{- /* seats = seats[0:i] + "x" + seats[i+1:] */ -}}
{{- $seats = print (slice $seats 0 $seatNum) "x" (slice $seats $nextSeatNum) -}}
座っている人数を数える
最後に座っている人数を数えて結果を表示します。$seats
に入っている空白以外の要素 (= 'x'
) の個数分 $customers
をインクリメントすることで、座っているお客さんの人数を数えます。
{{- /* 座っている人数を数える */ -}}
{{- $customers := "" -}}
{{- range $i, $_ := $.Looper -}}
{{- if ge $i (len $seats) -}}
{{- break -}}
{{- end -}}
{{- $seat := index $seats $i -}}
{{- if ne $seat ' ' -}}
{{- $customers = print $customers "x" -}}
{{- end -}}
{{- end -}}
{{- $nCustomers := len $customers -}}
最後の結果の表示では、これまでと異なり変数に代入していないことに注意してください。得られた文字列がレンダリングされ、結果として表示されます。
{{- /* 結果を表示 */ -}}
{{- println $nCustomers -}}
おわりに
以上、Go TemplateでPaiza Bランク相当の問題を解いてみた解説でした。Aランクには手が出せなかった...
なにより sprigに頼れないのが厳しかった 。sprig濫用で弛んでいた心に喝を入れ、標準機能本来の味を楽しむことができました。
みなさんも、Go Templateでスキルチェックしてみてはいかがでしょうか?
関連記事
Go Templateおもちゃシリーズ