増やす減らす二倍する

# 増やす減らす二倍する
# http://nabetani.sakura.ne.jp/hena/ord13updowndouble/
# http://qiita.com/Nabetani/items/89fb0e2e712d4b396535
#

PLUS = "+1"
MINUS = "-1"
DOUBLE = "x2"

def find_path(num)

	case num
	when 0
		return []
	when 1
		return [PLUS]
	when -> (n) { n.even? }
		return find_path(num / 2) + [DOUBLE]
	else
		plus_path = find_path(num - 1)  + [PLUS]
		minus_path = find_path(num + 1) + [MINUS]
		return plus_path.size > minus_path.size ? minus_path : plus_path
	end
	
end

def test(input, expected)
	path = find_path(input.to_i)
	result = path.size.to_s
	check = (result == expected) ? "OK" : "NG"
	puts "#{input} --> #{path.join(' ')} (#{result}) : #{check}"
end

test( "0", "0" )
test( "1", "1" )
test( "2", "2" )
test( "3", "3" )
test( "4", "3" )


test( "59", "9" )                       # 0
test( "10", "5" )                       # 1
test( "11", "6" )                       # 2
test( "12", "5" )                       # 3
test( "13", "6" )                       # 4
test( "14", "6" )                       # 5
test( "15", "6" )                       # 6
test( "16", "5" )                       # 7
test( "17", "6" )                       # 8
test( "18", "6" )                       # 9
test( "27", "8" )                       # 10
test( "28", "7" )                       # 11
test( "29", "8" )                       # 12
test( "30", "7" )                       # 13
test( "31", "7" )                       # 14
test( "32", "6" )                       # 15
test( "33", "7" )                       # 16
test( "34", "7" )                       # 17
test( "35", "8" )                       # 18
test( "41", "8" )                       # 19
test( "71", "9" )                       # 20
test( "1023", "12" )                    # 21
test( "1024", "11" )                    # 22
test( "1025", "12" )                    # 23
test( "1707", "17" )                    # 24
test( "683", "15" )                     # 25
test( "123", "10" )                     # 26
test( "187", "11" )                     # 27
test( "237", "12" )                     # 28
test( "5267", "18" )                    # 29
test( "6737", "18" )                    # 30
test( "14796", "20" )                   # 31
test( "18998", "20" )                   # 32
test( "23820", "20" )                   # 33
test( "30380", "21" )                   # 34
test( "31119", "21" )                   # 35
test( "33301", "20" )                   # 36
test( "33967", "21" )                   # 37
test( "35443", "22" )                   # 38
test( "35641", "22" )                   # 39
test( "43695", "23" )                   # 40
test( "44395", "23" )                   # 41
test( "44666", "22" )                   # 42
test( "987", "14" )                     # 43
test( "1021", "13" )                    # 44
test( "1019", "13" )                    # 45
test( "1015", "13" )                    # 46
test( "1007", "13" )                    # 47
test( "1011", "14" )                    # 48
test( "1003", "14" )                    # 49
test( "983", "14" )                     # 50
test( "999", "14" )                     # 51
test( "2731", "18" )                    # 52
test( "6827", "20" )                    # 53
test( "10923", "21" )                   # 54
test( "27307", "23" )                   # 55
test( "43691", "24" )                   # 56
test( "109227", "26" )                  # 57
test( "174763", "27" )                  # 58