paiza プログラミング

[Ruby]paiza クラス・構造体メニュー 出口のない迷路 (paizaランク B 相当)の解説

maze

こんにちは！じゃいごテックのあつしです。

今回はpaiza クラス・構造体メニュー からSTEP1: 出口のない迷路という問題を解説します。

この問題集はクラスの応用的な使い方に関する4個のSTEP問題(B~A級)とFINAL問題(A級)で構成されていて、STEP問題を解いて行けばFINAL問題も解けるはず！となっています。

STEP1: 出口のない迷路 (paizaランク B 相当)を解いてみる

※ paizaレベルアップ問題集 クラス・構造体メニューより

問題

洞窟を探検していたあなたは出口のない迷路に迷い込んでしまいました。
脱出するには、迷路の地点を与えられた指示通りに移動し、移動で訪れた（移動の開始・終了地点を含む）地点に置かれたアルファベットを
つなげた文字列を呪文として唱える必要があります。
各頂点からは、他の頂点に向かって一方通行の 2 つの道が伸びています。
各ポイントの情報と移動の指示が与えられるので、呪文となる文字列を出力してください。

入力される値

入力は以下のフォーマットで与えられます。

N K S
a_1 r1_1 r2_1
...
a_N r1_N r2_N
M_1
...
M_K

  • 1 行目では、地点の数 N と、移動の回数 K , 移動を開始する地点の番号 S が与えられます。
  • 続く N 行のうち i 行目(1 ≦ i ≦ N)では、番号 i 地点に置いてあるアルファベット a_i と 1 つめの道のつながっている地点の番号 r1_i , 2 つめの道のつながっている地点の番号 r2_i が与えられます。
  • 続く K 行のうち i 行目(1 ≦ i ≦ K)では、 i 回目の移動で選んだ道の番号 M_i が与えられます。

入力値最終行の末尾に改行が１つ入ります。

期待する出力

あなたが唱えるべき呪文となる文字列を 1 行で出力してください。
末尾には改行を出力してください。

条件

すべてのテストケースにおいて、以下の条件をみたします。

  • 与えられる値は全て整数
  • 1 ≦ N , K ≦ 10^5
  • 1 ≦ S ≦ N
  • a_i (1 ≦ i ≦ N) はアルファベット 1 文字
  • 1 ≦ r1_i , r2_i ≦ N (1 ≦ i ≦ N)
  • M_i (1 ≦ i ≦ K) は 1 または 2 である。
入力例1
4 4 1
p 2 4
a 3 1
i 4 2
z 1 2
1
1
1
2
出力例1
paiza
入力例2
5 10 5
o 5 4
f 1 5
b 1 2
k 1 5
k 2 4
1
2
1
2
2
2
2
2
1
1
出力例2
kfkfkkkkkfo
攻略ポイント

ポイント

  • 各地点の情報をクラスにまとめる
    • アルファベット1文字を持っている
    • 次のポイントに行く道を二つ持っている
  • プレイヤーの情報をクラスにまとめる
    • 移動で訪れた地点のアルファベットの情報を持っている
    • 現在位置の情報を持っている
    • 指定された道を進む

参考記事

クラス

メソッドの定義と呼び出し

標準入力・標準出力

問題を解く流れ

複雑そうな問題がでたら、入出力例を見ながら情報を整理してみましょう。
図にするとわかりやすいと思います。

入力例1

出口のない迷路_図1

0 1 2 3 4
現在位置（point） 1 2 3 4 2
進む道（direction） 1 1 1 2 -
文字(alphabet) p a i z a

入力例2

出口のない迷路_図2

0 1 2 3 4 5 6 7 8 9 10
現在位置（point） 5 2 5 2 5 4 5 4 5 2 1
進む道（direction） 1 2 1 2 2 2 2 2 1 1 -
文字(alphabet) k f k f k k k k k f o

地点と地点が一方通行の場所もありますね。
このように繋がりに方向があるグラフを有向グラフと言います。（方向が無いのは無向グラフ）

情報の整理が出来たので、問題を解いていきます。

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。

INPUT1 = <<~"EOS"
  4 4 1
  p 2 4
  a 3 1
  i 4 2
  z 1 2
  1
  1
  1
  2
EOS
OUTPUT1 = <<~"EOS"
  paiza
EOS

INPUT2 = <<~"EOS"
  5 10 5
  o 5 4
  f 1 5
  b 1 2
  k 1 5
  k 2 4
  1
  2
  1
  2
  2
  2
  2
  2
  1
  1
EOS
OUTPUT2 = <<~"EOS"
  kfkfkkkkkfo
EOS

# 確認用コード
p INPUT1
# > "4 4 1\np 2 4\na 3 1\ni 4 2\nz 1 2\n1\n1\n1\n2\n"
p OUTPUT1
# > "paiza\n"
p INPUT2
# > "5 10 5\no 5 4\nf 1 5\nb 1 2\nk 1 5\nk 2 4\n1\n2\n1\n2\n2\n2\n2\n2\n1\n1\n"
p OUTPUT2
# > "kfkfkkkkkfo\n"

続いてPointクラス, Playerクラスと問題を解くsolveメソッドを変数の下に定義します。

まず、クラスを定義します。

Pointクラス

  • インスタンス変数
    • 地点が持つ文字 @alphabet : String（外部からの参照可）
    • 次の地点に行く道 @routes: Array（外部からの参照可）
  • initializeメソッド（引数: alphabet, routes）
    • @alphabet を alphabet で初期化する
    • @routes を routes で初期化する

Playerクラス

  • インスタンス変数
    • 現在位置 @current_point : Point
    • 呪文 @magic_spell : String
  • initializeメソッド（引数: start_point）
    • @current_point を start_point で初期化する
    • @magic_spell を start_point.alphabet で初期化する
  • インスタンスメソッド
    • next_idx（引数: direction）
      • @current_point.routes[direction] を返す
    • move（引数: next_point）
      • @current_point を next_point で更新する
      • @magic_spell の末尾に @current_point.alphabet を追加する
class Point
  attr_reader :alphabet, :routes

  def initialize(alphabet, routes)
    @alphabet = alphabet
    @routes = routes
  end
end

class Player
  attr_reader :magic_spell

  def initialize(start_point)
    @current_point = start_point
    @magic_spell = start_point.alphabet
  end

  # 次の point のインデックスを返す
  def next_idx(direction)
    @current_point.routes[direction - 1] - 1
  end

  # 移動した後の point を 現在地 @current_point にする
  # @current_point の alphabet を @magic_spell に追加する
  def move(next_point)
    @current_point = next_point
    @magic_spell += @current_point.alphabet
  end
end

# 確認用コード
points = []
points << Point.new("p", [2, 4])
points << Point.new("a", [3, 1])
points << Point.new("i", [4, 2])
points << Point.new("z", [1, 2])
points.each do |point|
  p point
end

player = Player.new(points[0])
[1, 1, 1, 2].each do |direction|
  next_idx = player.next_idx(direction)
  player.move(points[next_idx])
  pp player
end

# > #<Point:0x00007fffd6b12de8 @alphabet="p", @routes=[2, 4]>
# > #<Point:0x00007fffd6b12cd0 @alphabet="a", @routes=[3, 1]>
# > #<Point:0x00007fffd6b12c08 @alphabet="i", @routes=[4, 2]>
# > #<Point:0x00007fffd6b12b18 @alphabet="z", @routes=[1, 2]>
# > #<Player:0x00007fffd6b12168
# >  @current_point=#<Point:0x00007fffd6b12cd0 @alphabet="a", @routes=[3, 1]>,
# >  @magic_spell="pa">
# > #<Player:0x00007fffd6b12168
# >  @current_point=#<Point:0x00007fffd6b12c08 @alphabet="i", @routes=[4, 2]>,
# >  @magic_spell="pai">
# > #<Player:0x00007fffd6b12168
# >  @current_point=#<Point:0x00007fffd6b12b18 @alphabet="z", @routes=[1, 2]>,
# >  @magic_spell="paiz">
# > #<Player:0x00007fffd6b12168
# >  @current_point=#<Point:0x00007fffd6b12cd0 @alphabet="a", @routes=[3, 1]>,
# >  @magic_spell="paiza">

クラスの動作が良さそうなら、確認用コードを削除してPlayerクラスの下にsolveメソッドを記述していきます。

まず、入力データを受け取る処理を書きます。

def solve(input_lines)
  # 入力データ受け取り
  input_lines = input_lines.split("\n")
  n, k, s = input_lines.shift.split.map(&:to_i)
  points = input_lines.shift(n).map do |point|
    alphabet, *routes = point.split
    routes.map!(&:to_i)
    [alphabet, routes]
  end
  directions = input_lines.shift(k).map(&:to_i)

  # 確認用コード
  [s, points, directions]
end

# 確認用コード
pp solve(INPUT1)
# > [1, [["p", [2, 4]], ["a", [3, 1]], ["i", [4, 2]], ["z", [1, 2]]], [1, 1, 1, 2]]
pp solve(INPUT2)
# > [5,
# >  [["o", [5, 4]], ["f", [1, 5]], ["b", [1, 2]], ["k", [1, 5]], ["k", [2, 4]]],
# >  [1, 2, 1, 2, 2, 2, 2, 2, 1, 1]]

データが正しく受け取れていれば、solve メソッドに処理を追加していきます。

  • 配列pointsの先頭から順にPointクラスでインスタンス化した配列で上書きします。
  • スタート地点を引数に与えてPlayerクラスをインスタンス化してplayerに格納します。
  • 配列directionsの値に従ってplayerを移動させます。
    • next_idxメソッドで次のpointのインデックスを調べる
    • moveメソッドで次の地点に移動
  • 移動終了時のplayer.magic_spellを返します。
def solve(input_lines)
  # 入力データ受け取り
  input_lines = input_lines.split("\n")
  n, k, s = input_lines.shift.split.map(&:to_i)
  points = input_lines.shift(n).map do |point|
    alphabet, *routes = point.split
    routes.map!(&:to_i)
    [alphabet, routes]
  end
  directions = input_lines.shift(k).map(&:to_i)

  # Pointクラスでインスタンス化して上書き
  points.map! { |alphabet, routes| Point.new(alphabet, routes) }

  # Playerクラスでインスタンス化
  player = Player.new(points[s - 1])

  # directions に従って player を移動させる
  directions.each do |direction|
    # 次の point のインデックスを調べる
    next_idx = player.next_idx(direction)
    # 次の point に移動する
    player.move(points[next_idx])
  end

  # player の magic_spell を返す
  player.magic_spell
end

# 確認用コード
p solve(INPUT1)
# > "paiza"
p solve(INPUT1) == OUTPUT1
# > false
p solve(INPUT2)
# > "kfkfkkkkkfo"
p solve(INPUT2) == OUTPUT2
# > false

このまま提出しても合格しますが、p solve(INPUT1) == OUTPUT1 -> true を確認するために、player.magic_spellの末尾に改行を加えます。

def solve(input_lines)
  # 入力データ受け取り
  input_lines = input_lines.split("\n")
  n, k, s = input_lines.shift.split.map(&:to_i)
  points = input_lines.shift(n).map do |point|
    alphabet, *routes = point.split
    routes.map!(&:to_i)
    [alphabet, routes]
  end
  directions = input_lines.shift(k).map(&:to_i)

  # Pointクラスでインスタンス化して上書き
  points.map! { |alphabet, routes| Point.new(alphabet, routes) }

  # Playerクラスでインスタンス化
  player = Player.new(points[s - 1])

  # directions に従って player を移動させる
  directions.each do |direction|
    # 次の point のインデックスを調べる
    next_idx = player.next_idx(direction)
    # 次の point に移動する
    player.move(points[next_idx])
  end

  # player の magic_spell 末尾に改行を追加して返す
  player.magic_spell << "\n"
end

# 確認用コード
p solve(INPUT1)
# > "paiza\n"
p solve(INPUT1) == OUTPUT1
# > true
p solve(INPUT2)
# > "kfkfkkkkkfo\n"
p solve(INPUT2) == OUTPUT2
# > true

入出力例での動作確認が出来ましたので、標準入力からのデータ受け取りに変更して、手動で動作確認をしたら提出します。
複数行のデータ受け取りなので STDIN.read を使います。（入力終了は Ctrl+D 又は Ctrl+Z)

解答コード
class Point
  attr_reader :alphabet, :routes

  def initialize(alphabet, routes)
    @alphabet = alphabet
    @routes = routes
  end
end

class Player
  attr_reader :magic_spell

  def initialize(start_point)
    @current_point = start_point
    @magic_spell = start_point.alphabet
  end

  # 次の point のインデックスを返す
  def next_idx(direction)
    @current_point.routes[direction - 1] - 1
  end

  # 移動した後の point を 現在地 @current_point にする
  # @current_point の alphabet を @magic_spell に追加する
  def move(next_point)
    @current_point = next_point
    @magic_spell += @current_point.alphabet
  end
end

def solve(input_lines)
  # 入力データ受け取り
  input_lines = input_lines.split("\n")
  n, k, s = input_lines.shift.split.map(&:to_i)
  points = input_lines.shift(n).map do |point|
    alphabet, *routes = point.split
    routes.map!(&:to_i)
    [alphabet, routes]
  end
  directions = input_lines.shift(k).map(&:to_i)

  # Pointクラスでインスタンス化して上書き
  points.map! { |alphabet, routes| Point.new(alphabet, routes) }

  # Playerクラスでインスタンス化
  player = Player.new(points[s - 1])

  # directions に従って player を移動させる
  directions.each do |direction|
    # 次の point のインデックスを調べる
    next_idx = player.next_idx(direction)
    # 次の point に移動する
    player.move(points[next_idx])
  end

  # player の magic_spell 末尾に改行を追加して返す
  player.magic_spell << "\n"
end

puts solve(STDIN.read)

今回のまとめ

STEP1は有向グラフを扱ったので少し情報が複雑でしたが、今まで挑戦した問題の復習的な内容でした。

A級からはグラフを使った問題が沢山出てきますので少しづつ慣れていきましょう！


【PR】アルゴリズム学習でお世話になった本


アルゴリズム関連の技術書は大抵C/C++で書かれていますが、ある程度プログラムが出来れば、処理の流れは理解することが出来ます。





通称: 螺旋本。C++で解説されています。AOJ(Aizu Online Judge)を運営している会津大学の渡辺准教授が書いた本です。データ構造や計算量の内容から丁寧に書いてありますのでアルゴリズム学習の最初の参考書としてオススメです。


プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 [ 渡部有隆 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング




通称: 蟻本。C++で解説されています。競技プログラミング中級者の定番書と言われていて、競技プログラミングで利用できる色々なアルゴリズムを学ぶことが出来ます。かなり高度な内容も含まれているので1冊分を完全に理解するのにはかなりの時間がかかりそうですが、手元に置いて何度も読み返しています。


プログラミングコンテストチャレンジブック第2版 問題解決のアルゴリズム活用力とコーディングテクニッ [ 秋葉拓哉 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング




通称: チーター本。C#, C++, JAVAでTopcoderの問題を解説しています。初心者～中級者向けに書かれているので解説が非常に丁寧です。


最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド【電子書籍】[ 高橋 直大 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング




Python3でアルゴリズムを解説している本です。講義スタイルの本で、図やフローチャートを使ってアルゴリズムとデータ構造についてしっかりと説明されています。代わりにコードは少なめです。Pythonコードが読めなくても十分理解できると思います。


Pythonで体験してわかるアルゴリズムとデータ構造 [ 西澤 弘毅 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング

-paiza, プログラミング
-, ,

© 2024 じゃいごテック