Go to Qiita Advent Calendar 2024 Top
LoginSignup
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

paiza×Qiita記事投稿キャンペーン「プログラミング問題をやってみて書いたコードを投稿しよう！」
@Syuparn

【Paiza】長テーブルのうなぎ屋 (paizaランク B 相当)をGo「Template」で解いた【text/template】

Posted at

この記事は、「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おもちゃシリーズ

  1. Goのtext/templateの呼び方は何が公式なのかいまいち分かっていないのですが、簡便のため本記事では「Go Template」と記載します。 ↩

  2. 説明のためとはいえ、親父さん自慢の「長テーブル」、「円卓」って呼んじまってすまねえな。 ↩

  3. 失敗しないことが分かっているのでエラーが起きたらpanicしています。プロダクトコードではエラーハンドリングしようね ↩

  4. 例えばHelmではデフォルトでsprigの関数が使用可能です。 ↩

  5. 原理的には文字列を1バイトずつループし、ASCIIに応じて分岐することでパース可能です（が、力尽きてしまいました）。読者への宿題とします ↩

3
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?