読者です 読者をやめる 読者になる 読者になる

/home/cympfh/

はてなブログはクソなのでやめます => https://hackmd.io/s/SyQBwu6Kg#

Advent of Code (Day 8-14)

プロコン

Tue Dec 22 17:36:16 JST 2015

Advent of Code (Day 8-15)

Day 8

エスケープ文字を無難な一文字に置換して長さを足す. エスケープのためのエスケープに気をつける必要があってややこしい.

Ruby ならこんな感じ:

a=b=0
while s=gets
  s=s.chomp
  a+=s.length
  s=s[1...-1]
  s=s.gsub('\'', 'X')
  s=s.gsub('\\\\', 'X')
  s=s.gsub(/\\x../, 'X')
  b+=s.length
end
# p [a,b]
p a-b

なんで single quote なのに \\\\ なのか分からん.

Day 9

地点が $n$ あったら $n!$ 試す.

input ファイルを読み込んでる↓

require 'set'
nodes = Set.new []
m={}
`cat input`.chomp.split('\n').each {|line|
  s, _, t, _, d = line.split
  m[[s,t]] = d.to_i
  m[[t,s]] = d.to_i
  nodes << s
  nodes << t
}

nodes = nodes.to_a
nodes.permutation(nodes.length).each {|path|
  len = 0
  (path.length - 1).times {|i|
    len += m[[path[i], path[i+1]]]
  }
  p len
}

シェル (bash?) スクリプトをそのまま埋め込めるのすごい便利.

Day 10

def op(phrase)
  ret = ''
  last = phrase[0]
  cx = 0
  phrase.chars.each {|c|
    if last == c
      cx += 1
    else
      ret += cx.to_s + last
      cx = 1
      last = c
    end
  }
  ret + cx.to_s + last
end

phrase = '1321131112'
40.times {
  phrase = op(phrase)
}
p phrase.length

Day 11

問題がちょっと良く分からない

Day 12

require 'json'
data = JSON.parse `cat input.json`
def sum(obj)
  case
  when obj.is_a?(1.class)
    obj
  when obj.is_a?([].class)
    r=0
    for x in obj
      r += sum x
    end
    return r
  when obj.is_a?({}.class)
    r=0
    for _,v in obj
      r += sum v
    end
    return r
  else # string
    0
  end
end
p sum(data)

Day 13

$O(n!)$

require 'set'

persons = Set.new []

edges = {}

open('./input').readlines.each {|line|
  ts = line.chomp.split
  u = ts[0][0]
  v = ts[-1][0]
  x = ts[3].to_i
  x = -x if ts[2] == 'lose'
  persons << u
  persons << v

  if not edges[u]
    edges[u] = {}
  end
  edges[u][v] = x
}

ans = -1000000000

persons = persons.to_a
n = persons.size
(n-1).times.to_a.permutation(n-1).each {|v|
  assign = [persons[0]]
  for i in v
    assign << persons[i + 1]
  end

  total = 0
  for i in 0...n
    total += edges[assign[i]][assign[(i+1)%n]]
    total += edges[assign[i]][assign[(i-1+n)%n]]
  end

  ans = [ans, total].max
}

p ans

Day 14

p open('./input').readlines.map {|line|
  ts = line.chomp.split.map(&:to_i)
  v = ts[3]
  t1 = ts[6]
  t2 = ts[-2]
  2503/(t1+t2) * (v*t1) + [t1, 2503 % (t1+t2)].min * v
}.max