Code Jam 2009, Round 1C 문제 풀이 ruby, python

알고리즘은 금방 생각할 수 있었다.

같은 진법에서 102345... 같은 숫자가 가장 작다.

가장 적은 수 진법일 때 가장 작다.

처음에는 ruby input, output 처리에 시간이 걸렸다.

특별한 case 처리를 잘 못해서 small input에서 답을 틀렸다.

111 일 때, 2진법 숫자인데, 1진법 숫자라고 계산해 버렸다.

어떤 case에서 왜 틀렸는지 찾는 것에 1시간 걸렸다 T_T

역시, 처음, 끝 값 등에 대한 처리는 다시 한 번 확인해보고, unit test를 하는 게 좋겠다.

총 2시간 쯤 걸렸던 것 같다.

# https://code.google.com/codejam/contest/189252/dashboard

SAMPLE = 'sample.in'
SMALL = 'A-small-practice.in'
LARGE = 'A-large-practice.in'

input = File.open(LARGE)
output = File.open('./out.txt', 'w')
$log = File.open('./log.txt', 'w')

class AliensMinDday

  def initialize(numberText)
    @numberHash = Hash.new
    @numberText = numberText.gsub("\n", '')

    order = 0
    @numberText.split("").each do |c|
      if @numberHash[c] == nil then
        @numberHash[c] = order
        order += 1
      end
    end
  end

  def solve()

    base = @numberHash.count()
    if base == 1 then
      base = 2
    end
    result = 0

    index = @numberText.length - 1

    $log.write "\n"
    $log.write @numberText
    $log.write "\n"

    @numberText.split("").each do |c|
      number = @numberHash[c]
      if number == 0 then
        number = 1
      elsif number == 1 then
        number = 0
      end

      result += number * (base ** index)

      $log.write "#{number}"

      index -= 1

    end
    $log.write " #{base}\n"

    result

  end

end


count = input.readline()
iCase = 0
input.read.each_line do |line|
  iCase += 1
  answer = AliensMinDday.new(String.try_convert(line)).solve()
  output.write "Case ##{iCase}: #{answer}\n"
  $stdout.write "\n#{line} Case ##{iCase}: #{answer}\n"
end

vector 연산으로 center of mass, average velocity를 쉽게 구할 수 있었다.

ruby에서 vector 기능을 찾는 것에 한참의 시간을 소비했다. 30분 이상?

나중에 알고 보니, python 상위권 입상자들은 vector 연산을 손으로 구현했더라 -0-

막상 center of mass까지는 쉽게 구했는데, 최단 거리일 때의 시간을 구하는 것은 잠깐 막막했다.

시작할 땐, 막연하게 될 것 같았는데, code로 만들으려니까 될지 말지도 의심이 되더라.

종이에 vector 수식을 세우고서 쉽게 된다는 것을 알았다. 역시, 종이에 써가면서 풀어야 하겠다.

이것도 한 번에 small input을 통과하지 못 했다.

특별한 case를 생각하지 못했다.

print해 놓은 log를 보니, 틀린 부분을 찾을 수 있었다. 시간이 음수인 상황이 있었다.

center of mass가 원점으로부터 멀어지는 경우. 이 경우에는 t = 0

또 1시간 헤맸다..

총 3시간 쯤 걸렸으려나.

# https://code.google.com/codejam/contest/189252/dashboard#s=p1

require "matrix"

$log = File.open('log.txt', 'w')

class CenterOfMass

  def initialize
    @rows = Array.new
  end
  def append(data)
    vector = Vector.elements(data.split(' ').map { |e| e.to_f })
    #puts vector
    @rows.push vector
  end

  def solve
    #puts @rows
    sum = Vector[0, 0, 0, 0, 0, 0]
    @rows.each {
      |row|
      #puts row, sum
      sum = sum + row
    }
    averageRow = sum / @rows.count
    # puts @rows
    # puts sum

    # puts averageRow
    center = Vector.elements(averageRow[0..2])
    velocity = Vector.elements(averageRow[3..5])

    if velocity.r > 0.00000001 then
      minTime = - velocity.inner_product(center) / velocity.inner_product(velocity)
    else
      minTime = 0
    end

    if minTime < 0 then
      minTime = 0
    end

    distance = center + velocity * minTime
    puts minTime, center, velocity, distance

    return distance.magnitude, minTime

  end
end

sample = 'sample.in'
small = 'B-small-practice.in'
large = 'B-large-practice.in'
out = 'out.txt'
input = File.open(large)
output = File.open(out, 'w')


count = input.readline()
iCase = 0
while true
  iCase += 1

  nFlies = input.readline()
  break if input.eof?



  nFlies = nFlies.to_i
  mass = CenterOfMass.new
  nFlies.times {
    data = input.readline()
    mass.append(data)
  }

  # if iCase > 11 && iCase < 16 then
    solution = mass.solve
    # puts solution[0], solution[1]
    output.write "Case ##{iCase}: #{solution[0]} #{solution[1]}\n"
  # end
end

2가지 알고리즘을 생각했다.

첫 번째 알고리즘으로, 매번 가운데에서 가까운 prisoner를 석방해가면서 문제를 쪼개가면 풀 수 있다고 생각했다.

small input에서 틀리고서.. 2번째 알고리즘으로 다시 풀었다.

문제를 subproblem으로 쪼개면서 풀되, dynamic programming으로 시간을 절약하기.

dynamic programming을 하지 않고, 모든 case에 대해 다 쪼갠다면, small input은 풀 수 있겠다.

dynamic programming으로도 large input까지 풀 수 있다는 확신은 없이 시작했다. 첫 알고리즘이 틀리는 case를 찾으려고, 비교용으로 구현한 셈.

두 결과를 비교해 보고, 결과가 틀린 부분에서 debugging을 했다.

dynamic programming이 더 optimal한 결과를 냈다.

첫 번째 알고리즘은 그제서야 파기 T_T

이 경우에 dynamic programming을 효율적으로 쓰려면,

1 5 [3, 4] case와 2 6 [4, 5] 가 같은 case라고 인식하도록 하는 게 좋겠다.

2 6 [3, 4] 도 같은 case라고 인식하게 만들면 좋겠지만, 여기까지는 못했다.

횡으로 translation을 하되, parameter로 넘길 때는 알아보기 쉽도록 원본 input scale을 썼다.

recursive function에서 결과로 어떤 과정이었는지 debugging용 string도 return하게 만들고, 실행 시점에는 ""로 대체했다.

large input을 실행시켰더니, 컴퓨터가 먹통이 된다 -_-

python ide로 canopy는 안되겠다. windows도 쓸 만한 os는 아닌 것 같다.

처음에는 메모리를 쓰더라도 계산을 빨리 하려고, dynamic programming table을 global로 1개를 썼다.

ide를 jetbrains pycharms로 바꾸고,

print문을 없애고, table을 매 case 생성하는 것으로 바꿨더니, large input에서 case 별 1초 정도 걸리는 것 같다.

총 5시간 가까이 걸렸으려나 T_T

import sys
import os

sample = "sample"
small = "C-small-practice"
large = "C-large-practice"
current = large

fin = open(current + ".in", "r")
fout = open(current + ".out", 'w')
f1out = open(current + "1.out", 'w')
f2out = open(current + "2.out", 'w')

#sys.stdout = open(os.devnull, 'w')

T = int(fin.readline())

def bribe(rs, s, e):
    if not rs:
        return 0
    if s >= e:
        return 0
    center = (s + e) / 2.0
    closest = e + 2
    for i in rs:
        if abs(center - i) < abs(center - closest):
            closest = i
    
    left = [a for a in rs if a < closest]
    right = [a for a in rs if a > closest]
    print s, e, closest, e - s, left, right
    return (e - s) + bribe(left, s, closest - 1) + bribe(right, closest + 1, e)
    
solutions = {}
def dynamic_bribe(rs, s, e, space):
    if not rs:
        return "", 0
    if s >= e:
        return '', 0
    
    s0 = 1
    e0 = e - s + 1
    rs0 = [a - s + 1 for a in rs]
    
    key = str(e0) + ':' + (',').join(str(a) for a in rs0)
    keystr = str(s) + '~' + str(e) + ':' + (',').join(str(a) for a in rs)
    solution = solutions.get(key)
    if solution:
        #print space, s, e, rs, solution, "key:" + key
        #return '\n' + space + '<' + keystr + '_' + str(solution) + '>\n', solution
        return '', solution
    else:
        candidate = sys.maxint
        way = ""
        for r in rs:
            left = [a for a in rs if a < r]
            right = [a for a in rs if a > r]
            left_way, lc = dynamic_bribe(left, s, r-1, space + '   ')
            right_way, rc = dynamic_bribe(right, r+1, e, space + '   ')
            cc = (e - s) + lc + rc
            if cc < candidate:
                candidate = cc
                way = '\n' + space + '<' + keystr + '_' + str(cc) + ',' + left_way + ',' + right_way + '>\n'
        solution = candidate
        solutions[key] = solution
        #print space, s, e, rs, solution
        #return way, solution
        return '', solution
        
#print dynamic_bribe([3], 1, 8, '')

def solve(P, Q, rs):
    a = bribe(rs, 1, P)
    #print ''
    
    #if a != b:
    #    print "DIFFERENT", a, b, a > b
    
    return a
    
def dynamic_solve(P, Q, rs):
    way, b = dynamic_bribe(rs, 1, P, '')
    print way
    return b
    
cases = [15]

for i in range(T):
    #if i > 3:
    #    break
    solutions = {}
    P, Q = map(int, fin.readline().split())
    rsline = fin.readline()
    rs = map(int, rsline.split())
    
    #if i in cases:
    if True:
        print P, Q, rs
        #answer = solve(P, Q, rs)
        #line = "Case #%d: %s" % (i+1, str(answer))
        #print line + '; ' + rsline + '\n'
        #f1out.write(line + '\n')
        
        answer2 = dynamic_solve(P, Q, rs)
        line2 = "Case #%d: %s" % (i+1, str(answer2))
        print line2 + '; ' + rsline + '\n'
        fout.write(line2 + '\n')
    
fin.close()
fout.close()
f1out.close()
f2out.close()

#sys.stdout = sys.__stdout__