CodeIQ:極めよプログラミング道!【実力判定:Bランク】

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「極めよプログラミング道!【実力判定:Bランク】」(CodeIQ)を参照してください。

問題の概要

問題を引用します。
【問題】
20桁の数字が提示されます。
一番左の桁を先頭として、右の桁へと順に見ていきます。
そして、隣り合った数が連続する数だった場合は、その双方を削除して先頭に戻ります。
最終的に、削除ができなくなった時点で数字を出力してください。


「95422357545868773174」→「95422357545868773174」→
「922357545868773174」→「922357545868773174」→
「9257545868773174」→「9257545868773174」→
「92575868773174」→「92575868773174」→
「925758673174」→「925758673174」→
「9257583174」(削除ができなくなったので、これが答え)

【入力】
標準入力から、複数行のデータが与えられます。1行のデータが、1つの20桁の数字になります。

【出力】
1行ずつ処理を行ない、その答えを1行ごと標準出力に出力します。

【入出力サンプル】
Input
95422357545868773174
24566191298259441958
34757881545564825469
86423251489513547814

Output
9257583174
26619259441958
75818269
8642511314

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def removeSeq(arr, i)
	if i >= arr.size-1 then return arr
	else
		if i < 0 then i = 0 end
		if (arr[i] == arr[i+1]-1) || (arr[i] == arr[i+1]+1) then
			arr[i] = nil
			arr[i+1] = nil
			arr.compact!
			i -= 1
		else
			i += 1
		end

		return removeSeq(arr,i)
	end
end

# main
while line = gets
	line.strip!
	if line.empty? then next end

	arr = line.split("").map{|a| a.to_i}
	puts removeSeq(arr, 0).join("")
end

解説

私がCodeIQの問題をやり始めてから2回目の実力判定問題です。
Bランクですがやはりそれほど難しくありません。

考え方

ある場所を見て次の値が±1だったらその2つの値を削除する。
削除した場合は位置を一つ戻す。削除しなかったら一つ進める。
という操作を数字列の最初から最後まで繰り返すだけです。

問題文では最初まで戻ることになっていますが、1つしか戻す必要はありません。

main

入力値を数値の配列に変換し、removeSeq()関数に渡した結果を印字します。

removeSeq(arr, i)

考え方に書いた通りの実装です。再帰で実装しています。
終了条件は最後の一つ手前までチェックすれば終わりです(一つ先までチェックするので)。
そうでなければ一つ先の値が±1だったらその2つの値を削除しますが、私は一旦nilにしたからcompact()で削除しています。1つずつ削除する場合は後ろの値から削除する必要があります。この場合は参照位置を一つ戻します。2つ以上前の数値列に連続する数は存在し得ないので最初まで戻す必要がありません。削除しなかったら参照位置を一つ進めます。そしてこの操作を行った数値列を再度removeSeq()に渡します。

雑感

最初ループでやろうとしましたが再帰にしました。最近の言語はC言語風のforループ
for(int i=0; i<Limit; i++){...}
が使えないものが多いですが、今回のようにインデックスを戻す必要があるような場合はwhileで書かなければならず、鬱陶しいので再帰にしました。
時々、インデックスカウンタを2以上とか条件によって異なる値で進めたり戻したりするとか、ブレーク条件をインデクスカウンタの値以外にしたい場合もあるのでC言語風のforループはあってほしいなぁと思います。