CodeIQ：投影図から想像する立体

問題の概要

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

# 入力値をパースして数値の配列にする
def parseLine(line)
	ret = []
	line.scan(/\[(\d,\d,\d)\]/).each{|arr|
		ret << arr[0].split(",").map{|c| c.to_i}
	}
	return ret
end

# 上から見た入力値から最大の図形を返す
def getBaseShapeTop(shape, top)
	ret = [[[0,0,0],[0,0,0],[0,0,0]],[[0,0,0],[0,0,0],[0,0,0]],[[0,0,0],[0,0,0],[0,0,0]]]
	for h in 0...3
		for d in 0...3
			for w in 0...3
				ret[h][d][w] = shape[h][d][w] & top[d][w]
			end
		end
	end
	return ret
end

# 右から見た入力値から最大の図形を返す
def getBaseShapeRight(shape, top)
	ret = [[[0,0,0],[0,0,0],[0,0,0]],[[0,0,0],[0,0,0],[0,0,0]],[[0,0,0],[0,0,0],[0,0,0]],]
	for w in 0...3
		for h in 0...3
			ret[h][0][w] = shape[h][0][w] & top[h][2]
			ret[h][1][w] = shape[h][1][w] & top[h][1]
			ret[h][2][w] = shape[h][2][w] & top[h][0]
		end
	end
	return ret
end

# 前から見た入力値から最大の図形を返す
def getBaseShapeFront(shape, front)
	ret = [[[0,0,0],[0,0,0],[0,0,0]],[[0,0,0],[0,0,0],[0,0,0]],[[0,0,0],[0,0,0],[0,0,0]]]
	for h in 0...3
		for d in 0...3
			for w in 0...3
				ret[h][d][w] = shape[h][d][w] & front[h][w]
			end
		end
	end
	return ret
end

# 入力値から最大の図形を返す
def getBaseShape(top, right, front)
	shape = [[[1,1,1],[1,1,1],[1,1,1]],[[1,1,1],[1,1,1],[1,1,1]],[[1,1,1],[1,1,1],[1,1,1]]]
	shape = getBaseShapeTop(shape, top)
	shape = getBaseShapeRight(shape, right)
	shape = getBaseShapeFront(shape, front)
	return shape
end

# 図形から上から見た場合の投影図を返す
def bitProjectionTop(s)
	ret = 0
	ret |= (s | (s >> 9) | (s >> 18)) & 0b000000001
	ret |= (s | (s >> 9) | (s >> 18)) & 0b000000010
	ret |= (s | (s >> 9) | (s >> 18)) & 0b000000100
	ret |= (s | (s >> 9) | (s >> 18)) & 0b000001000
	ret |= (s | (s >> 9) | (s >> 18)) & 0b000010000
	ret |= (s | (s >> 9) | (s >> 18)) & 0b000100000
	ret |= (s | (s >> 9) | (s >> 18)) & 0b001000000
	ret |= (s | (s >> 9) | (s >> 18)) & 0b010000000
	ret |= (s | (s >> 9) | (s >> 18)) & 0b100000000
	return ret
end

# 図形から右から見た場合の投影図を返す
def bitProjectionRight(s)
	ret = 0
	ret |= ((s >> 6) | (s >> 7) | (s >> 8))      & 1
	ret |= ( ((s >> 3) | (s >> 4) | (s >> 5))    & 1 ) << 1
	ret |= ( (s | (s >> 1) | (s >> 2))           & 1 ) << 2
	ret |= ( ((s >> 15) | (s >> 16) | (s >> 17)) & 1 ) << 3
	ret |= ( ((s >> 12) | (s >> 13) | (s >> 14)) & 1 ) << 4
	ret |= ( ((s >> 9) | (s >> 10) | (s >> 11))  & 1 ) << 5
	ret |= ( ((s >> 24) | (s >> 25) | (s >> 26)) & 1 ) << 6
	ret |= ( ((s >> 21) | (s >> 22) | (s >> 23)) & 1 ) << 7
	ret |= ( ((s >> 18) | (s >> 19) | (s >> 20)) & 1 ) << 8
	return ret
end

# 図形から前から見た場合の投影図を返す
def bitProjectionFront(s)
	ret = 0
	ret |= (s | (s >> 3) | (s >> 6)) & 0b000000001
	ret |= (s | (s >> 3) | (s >> 6)) & 0b000000010
	ret |= (s | (s >> 3) | (s >> 6)) & 0b000000100
	ret |= ((s >> 6) | (s >> 9) | (s >> 12)) & 0b000001000
	ret |= ((s >> 6) | (s >> 9) | (s >> 12)) & 0b000010000
	ret |= ((s >> 6) | (s >> 9) | (s >> 12)) & 0b000100000
	ret |= ((s >> 12) | (s >> 15) | (s >> 18)) & 0b001000000
	ret |= ((s >> 12) | (s >> 15) | (s >> 18)) & 0b010000000
	ret |= ((s >> 12) | (s >> 15) | (s >> 18)) & 0b100000000
	return ret
end

# h,d,wのブロックを削除した投影図を返す。
# ブロックを取れない（ブロックがない、上にブロックがある）場合はnilを返す
# 3方向の入力値が一致しない場合もnilを返す
# 3方向の投影図が一致する場合はその図形を返す
# @param shape 図形のビット表現
# @param h,d,w 削除位置
# @param pj 入力された投影図のビット表現
def getNext(shape, h, d, w, pj)
	i = 9*h+3*d+w
	if (shape >> i) & 1 == 0 then return nil end
	if (i >= 9) && ((shape >> (i-9)) & 1 == 1) then return nil end

	mask = 0b111111111111111111111111111 ^ (1 << i)
	nxt = shape & mask

	if checkProjection(nxt, pj) then return nxt
	else return nil
	end
end

# 投影図が入力値と同じかをチェックする
def checkProjection(shape, pj)
	# 投影図が同じかチェック
	pt = bitProjectionTop(shape)
	if pt != pj[0] then return false end

	pr = bitProjectionRight(shape)
	if pr != pj[1] then return false end

	pf = bitProjectionFront(shape)
	if pf != pj[2] then return false end

	return true
end

def toBit(arr)
	ret = 0
	arr.each_with_index{|v, i|
		ret |= (v<<i)
	}
	return ret
end

def shapeToBit(shape)
	return toBit(shape.flatten)
end

def projectionToBit(proj)
	return toBit(proj.flatten)
end

# 問題を解く
def solve(input)
	projection = [projectionToBit(input[0]), projectionToBit(input[1]), projectionToBit(input[2])]
	shape = getBaseShape(input[0], input[1], input[2])
	b = shapeToBit(shape)

	if checkProjection(b, projection) == false then return 0 end

	queue = [b]
	results = {b=>true}

	while !queue.empty?
		s = queue.shift

		for h in 0...3
			for d in 0...3
				for w in 0...3
					nxt = getNext(s, h, d, w, projection)
					if nxt == nil then
						next
					else
						if results[nxt] == nil
							queue << nxt
							results[nxt] = true
						end
					end
				end
			end
		end
	end

	return results.size
end

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

	input << parseLine(line)
end

p solve(input)

解説

★★★の問題で相応に難しいです。この問題の難しさは3次元のデータの取り扱いによるプログラミング自体の難しさと計算量の2点があります。ただ、数学的な能力をそれほど要求されるわけではないので頑張ればできる問題と思います。

[
    [[1,0,0],[0,0,0],[0,0,0]],
    [[1,1,0],[1,1,0],[0,0,0]],
    [[1,1,1],[1,1,1],[1,0,1]]
]

[
    [[1,0,0],[0,0,0],[0,0,0]],
    [[1,1,0],[1,1,0],[0,0,0]],
    [[1,1,1],[1,1,1],[1,0,1]]
]

雑感

結構しんどい問題でした。図形の問題も2次元ならそれほどでもありませんが、3次元になると数倍難しくなります。
ちなみに、私は問題の通り右方向から扱いましたが、右方向の値は反転して左方向から扱う様にした方がコードが単純になったと思います（左上奥が最初で右下手前が最後に統一できるので）。