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ランク A 相当)をGo「Template」で解いた【text/template】

Posted at

この記事は、「paiza×Qiita記事投稿キャンペーン」のキャンペーン対象問題の解説記事です。
通常の「paizaスキルチェック問題」の解答公開は禁止されています のでご注意ください。

Go Templateだけでスキルチェックを突破しようとする 実用性0の 記事2本目です。前回の記事はこちら。

解答

ソースコード（クリックで開く） 
package main

import (
	"bufio"
	"os"
	"text/template"
)

var tmplStr = `
{{- define "writeZero" -}}
	{{- if ge (len $) 1 -}}
		{{- $next := (slice $ 1) -}}
		{{- template "writeZero" $next -}}
		{{- print "0" -}}
		{{- template "writeOne" $next -}}
	{{- end -}}
{{- end -}}

{{- define "writeOne" -}}
	{{- if ge (len $) 1 -}}
		{{- $next := (slice $ 1) -}}
		{{- template "writeZero" $next -}}
		{{- print "1" -}}
		{{- template "writeOne" $next -}}
	{{- end -}}
{{- end -}}

{{- $line := $.In -}}
{{- /* 数字のパース */ -}}
{{- $nStr := "" -}}
{{- range $i, $_ := $.Looper -}}
	{{- /* 1文字読み込み整数に変換 */ -}}
	{{- if ge $i (len $line) -}}
		{{- break -}}
	{{- end -}}
	{{- $c := index $line $i -}}
	{{- /* 数字以外だったら読み込み終了 */ -}}
	{{- if or (gt $c '9') (lt $c '0') -}}
		{{- break -}}
	{{- end -}}
	{{- $digitCandidates := "0123456789" -}}
	{{- $digit := 0 -}}
	{{- range $i, $_ := $.Looper -}}
		{{- if eq $c (index $digitCandidates $i) -}}
			{{- $digit = $i -}}
			{{- break -}}
		{{- end -}}
	{{- end -}}

	{{- /* 現在の値を1桁増やして新しく読み込んだ桁を足す */ -}}
	{{- /* n = n * 10 + digit */ -}}

	{{- $digitStr := "" -}}
	{{- range $i, $_ := $.Looper -}}
		{{- if ge $i $digit -}}
			{{- break -}}
		{{- end -}}
		{{- $digitStr = print $digitStr " " -}}
	{{- end -}}

	{{- $prevNStr := $nStr -}}
	{{- range $i, $_ := $.Looper -}}
		{{- if ge $i 9 -}}
			{{- break -}}
		{{- end -}}
		{{- $nStr = print $nStr $prevNStr -}}
	{{- end -}}
	{{- $nStr = print $nStr $digitStr -}}
{{- end -}}

{{- template "writeZero" $nStr -}}
{{- print "\n" -}}
`

type Input struct {
	In string
	// HACK: ループの補助に使用
	Looper [20]struct{}
}

func readInput() Input {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()

	return Input{
		In:     sc.Text(),
		Looper: [20]struct{}{},
	}
}

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)
	}
}

解説

問題

紙に対して縦に二つ折りをn回繰り返すと折り目がどうなるのかを求める問題です。文章より公式ページの図を見るのが分かりやすいと思います。

解き方

Go Templateの解説に入る前に解法について軽く紹介します。（ご存じの方は次の章まで飛ばしてください）

1回折るごとに、折り目がどこに増えるのかに着目します。手元に紙を用意しながら読むとイメージが付きやすいと思います。

まずは1回目、真ん中が谷折りになります。

1回目.png

2回目は、折った状態で真ん中を谷折りにするため、開くと元々あった折り目の左側に谷折り、右側に山折りが追加されます。

2回目.png

3回目以降も、元々の折り目の左側に谷折り、右側に山折りが交互に追加されます。

3回目.png

新しく折り目を付ける瞬間その箇所の裏表に着目するとわかりやすいです。一番左の折り目から順に 表→裏→表→... となっているので、偶数番目の新しい折り目は開いたとき山折りになります。

出力形式では谷折りを 0、山折りを 1 と表すので、折った回数に応じて以下のような出力になるはずです。

想定出力（スペースは見やすさのために入れているので、実際には詰めて表示）
1:    1   
2:  0 1 1 
3: 0011011
...

実装

Go Templateプログラミングのテクニック

詳細については前回の記事をご覧ください。

前後の空白を無視

インデントを付けても結果に邪魔な空白が表示されないよう、 {{- -}} で前後の空白を除去します。

{{- if true -}}
    {{- println "got it!" -}}
{{- else -}}
    {{- println "no..." -}}
{{- end -}}
無駄なスペース、インデントが消える
got it!

加算、減算

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、文字列をループすることもできません、そのため、 looper というループ用配列をテンプレートの入力へ渡しています。

type Input struct {
	// HACK: ループの補助に使用
	Looper [20]struct{}
}

{{- /* Looperは配列なのでループに使用可能 */ -}}
{{- range $i, $_ := $.Looper -}}
    {{- /* この中で繰り返し処理（終わったらbreakで抜ける） */ -}}
{{- end -}}

標準入力を読み込む

まずは、標準入力を読み込み「折る回数 N」を取得します。

おそらく、「そんなのscanして終わりだろ」と思われるかと思いますが、整数 N を得るまでには以下の行程が必要です。整数の足し算ができない（素の）Go Templateに split atoi trim などという文明の利器はありません。

  • 一行読み込み（ここはGo本体で実行）
  • 末尾の改行を取り除く or 無視
  • 整数に変換
    • 1バイトずつ読み込み、読み込んだ文字から整数値を計算

さらに、Go Templateは整数の加減乗除ができないため、整数の代わりに 「長さがその整数となる文字列」を生成して計算を行う必要があります。

1バイトずつ読み込み

まずは、入力行を1バイトずつ調べます。前述の通り文字列を1バイトずつループすることはできないので、Looper を使ってループ変数のインデックスのバイトを読み込んでいます。
末尾に改行が付いているため、数値でない ((c > '9') || (c < '0')) 場合は読み込みを打ち切っています。

{{- $line := $.In -}}
{{- $nStr := "" -}}
{{- range $i, $_ := $.Looper -}}
	{{- /* 1文字読み込み整数に変換 */ -}}
	{{- if ge $i (len $line) -}}
		{{- break -}}
	{{- end -}}
	{{- $c := index $line $i -}}
	{{- /* 数字以外だったら読み込み終了 */ -}}
	{{- if or (gt $c '9') (lt $c '0') -}}
		{{- break -}}
	{{- end -}}
	{{- /* ... */ -}}
{{- end -}}

入力バイトを整数に変換

続いて、入力バイトを1桁の整数に変換します。文字列 "0123456789" の何番目の要素に一致するかを判定することで整数を得ます。2。

{{- range $i, $_ := $.Looper -}}
	{{- /* ... */ -}}

	{{- $digitCandidates := "0123456789" -}}
	{{- $digit := 0 -}}
	{{- range $i, $_ := $.Looper -}}
		{{- if eq $c (index $digitCandidates $i) -}}
			{{- $digit = $i -}}
			{{- break -}}
		{{- end -}}
	{{- end -}}

	{{- /* ... */ -}}
{{- end -}}

Nを更新

最後に、得られた一の位の値をもとに N を更新します。式で書くと N = N * 10 + digit ですが、掛け算は存在しないので N に自身を9回足すことで10倍しています。

{{- range $i, $_ := $.Looper -}}
	{{- /* ... */ -}}

	{{- /* 計算のため、一の位の値の整数と同じ長さの文字列を生成 */ -}}
	{{- $digitStr := "" -}}
	{{- range $i, $_ := $.Looper -}}
		{{- if ge $i $digit -}}
			{{- break -}}
		{{- end -}}
		{{- $digitStr = print $digitStr " " -}}
	{{- end -}}

	{{- /* 現在の値を1桁増やして新しく読み込んだ一の位の値を足す */ -}}
	{{- /* n = n * 10 + digit */ -}}

	{{- /* $nStrを10倍 */ -}}
	{{- $prevNStr := $nStr -}}
	{{- range $i, $_ := $.Looper -}}
		{{- if ge $i 9 -}}
			{{- break -}}
		{{- end -}}
		{{- $nStr = print $nStr $prevNStr -}}
	{{- end -}}

	{{- $nStr = print $nStr $digitStr -}}
{{- end -}}

折り目を計算

続いて、折り目を計算する処理です。

再帰を用いて、折り目の前後に 0 と 1 を追加します。

   1   
 0 1 1 
0011011
...

Go Templateの再帰には define と template を利用します。ややこしいですが、define はテンプレート内に子テンプレートを作成する機能です。template で作成した子テンプレートを呼び出せます。他の言語でいう関数に近い使い方ができます3。

そこで、

  • 0 を表示するテンプレート
  • 1 を表示するテンプレート

を作り、表示の前後で再帰的にテンプレートを呼び出すことで折り目を生成します。

{{- define "writeZero" -}}
	{{- /* 引数は残りの折る回数。0の場合は何もしない */ -}}
	{{- if ge (len $) 1 -}}
		{{- /* 残りの折る回数を1引いておく */ -}}
		{{- $next := (slice $ 1) -}}
		{{- /* 前に付ける0の折り目（この折り目の前後にも折り目がつくため再帰呼び出し） */ -}}
		{{- template "writeZero" $next -}}
		{{- /* 本体の0の折り目 */ -}}
		{{- print "0" -}}
		{{- /* 後に付ける1の折り目 */ -}}
		{{- template "writeOne" $next -}}
	{{- end -}}
{{- end -}}

{{- define "writeOne" -}}
	{{- if ge (len $) 1 -}}
		{{- $next := (slice $ 1) -}}
		{{- template "writeZero" $next -}}
		{{- print "1" -}}
		{{- template "writeOne" $next -}}
	{{- end -}}
{{- end -}}

後は入力された折る回数を引数に指定して呼び出します。末尾の改行も忘れずに。

{{- template "writeZero" $nStr -}}
{{- print "\n" -}}

おわりに

以上、Go Templateでスキルチェック問題を解いてみた解説でした。みなさんもGo Templateプログラミングの腕試しをしてみてはいかがでしょうか？

関連記事

Go Templateおもちゃシリーズ

  1. Sprig等の外部ライブラリを使えば可能ですが、Paizaスキルチェックでは標準モジュールしかimportできないため使用できません。 ↩

  2. byteは整数として扱えるため '0' を引くことでも得られますが、減算ができない都合上文字列長による計算が必要になり余計に計算コストが増えてしまいます。 ↩

  3. ただし、値を返すことはできません。 ↩

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?