山手線を文字数で辿っていく

loop_detect.rb

require 'set'

Yamanote = %w[とうきょう ゆうらくちょう しんばし はままつちょう たまち しながわ おおさき ごたんだ めぐろ えびす しぶや はらじゅく よよぎ しんじゅく しんおおくぼ たかだのばば めじろ いけぶくろ おおつか すがも こまごめ たばた にしにっぽり にっぽり うぐいすだに うえの おかちまち あきはばら かんだ]

Station = Struct.new(:name, :val)

class Loop
	def initialize(array)
		@array = array.map do |a|
			if a.is_a? Station
				a
			else
				Station.new a.to_s, (a.is_a?(String) ? a.length : a)
			end
		end
	end

	def show_loop(cursor)
		array, loop_begin = detect_loop(cursor)
		puts "length: #{array.length}"
		a1 = array.slice(0, loop_begin)
		a2 = array.slice(loop_begin, array.length)
		puts "#{str a1} [#{str a2}]"
	end
	def show_loops
		loops = all_loops
		loops.each do |set|
			puts str(set)
		end
	end
	def show_longest
		show_loop longest_index
	end
	def show_magical
		magical.each do |loop|
			puts "#{loop.length}: #{str loop}"
		end
	end

	def magical
		loops = all_loops
		return false if loops.length != 1
		loop = loops.first
		return [loop] if loop.length == 1

		indexes = loop.map{|a| @array.index(a)}
		sub_indexes = ([email protected]).to_a - indexes
		subsets_of(sub_indexes) do |a|
			loop2 =(indexes + a).sort.map{|i| @array[i]}
			sub_magical = Loop.new(loop2).magical
			return [loop, *sub_magical] if sub_magical
		end
		raise 'magical detection failed'
	end

	private

	def str(array)
		array.map{|i| i.name}.join(',')
	end
	def start_from(cursor)
		loop do
			yield @array[cursor]
			cursor = (cursor + @array[cursor].val) % @array.length
		end
	end
	def detect_loop(cursor)
		stops = []
		loop_begin = nil
		start_from(cursor) do |a|
			return [stops, loop_begin] if loop_begin = stops.index(a)
			stops << a
		end
	end
	def detect_loops
		Enumerator.new do |y|
			@array.length.times do |i|
				y << detect_loop(i)
			end
		end
	end
	def all_loops
		detect_loops.map do |stops, loop_begin|
			stops.slice(loop_begin, stops.length).to_set
		end.to_set
	end
	def longest_index
		detect_loops.with_index.max_by{|a| a[0].length}[1]
	end
	def subsets_of(array)
		array.length.times do |n|
			array.combination(n).each{|sub| yield sub}
		end
	end
end

l = Loop.new(Yamanote.reverse)
l.show_longest
l.show_magical