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

/home/cympfh/

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

Advent of Code (Day 8-14): Part 2

Fri Dec 25 19:52:16 JST 2015

Advent of Code (Day 8-14): Part 2

問題: http://adventofcode.com/

Day 8: Part 2

d=0
while s=gets
  # s=s.chomp # 差が欲しいだけなので不要
  d+=2+s.count('"')+s.count('\\')
end
p d

Day 9: Part 2

Part 1 を max から min にするだけ. Part 1 を書いた時から多少はRubyコードが洗練されたと思う. ruby っぽく (Lispっぽく?) 書けた.

require 'set'
nodes = Set.new []
m={}
open('./input').readlines.each{|line|
  ts = line.split
  s = ts[0]
  t = ts[2]
  x = ts[4].to_i
  m[s] = {} if m[s] == nil
  m[t] = {} if m[t] == nil
  m[s][t] = m[t][s] = x
  nodes << s
  nodes << t
}
nodes = nodes.to_a
p nodes.permutation(nodes.length).map{|path|
  (path.length - 1).times.map{|i| m[path[i]][path[i+1]] }.reduce :+
}.min

Day 10: Part 2

数値がちょうど異なる境目から左と右とで別々に処理して後で連接しても正しい解が得られるので、 分割統治が使えることが分かる. そのままだと分割統治しても計算量は下がらないけど、 一片の長さ4程度になったら素朴に解くことにすると、 直接解こうとする入力は $104$ 通りしかないので、メモ化が使える.

Part 1 の 40回程度だと、これでも数秒で解けるんだけど、 Part 2 では 50回で、もっと高速化が必要.

# memized naiive
$memo = {}
def f(cs)
  if $memo[cs] != nil
    return $memo[cs]
  end

  last = cs[0]
  cx = 0;
  d = ""
  cs.each {|c|
    if last == c
      cx += 1
    else
      d += cx.to_s + last
      last = c
      cx = 1
    end
  }
  d += cx.to_s + last
  ret = d.chars
  $memo[cs] = ret
  ret
end

# divide and conquer
def solve(cs)
  # p "solve of #{cs.length}"
  if cs.length <= 4
    f(cs)
  else
    for d in 0 ... cs.length/2
      for sgn in [-1, 1]
        i = cs.length/2 + sgn * d
        if cs[i-1] != cs[i]
          rs1 = solve cs[0...i]
          rs2 = solve cs[i...cs.length]
          return rs1 + rs2
        end
      end
    end
    return f(cs)
  end
end

cs="1321131112".chars
50.times {|i|
  cs = solve cs
  puts "len(f^#{i+1}(cs)) = #{cs.length}"
}
p cs.size

Day 11: Part 2

知らん

Day 12: Part 2

require 'json'
obj = JSON.parse `cat input`

def sum(o)
  if o.class == Array
    o.map{|q| sum(q)}.reduce :+
  elsif o.class == Fixnum
    o
  elsif o.class == Hash
    r = 0
    for _,v in o
      return 0 if v == 'red'
      r += sum(v)
    end
    r
  else
    0
  end
end

p sum(obj)

Day 13: Part 2

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
}

persons = persons.to_a

edges["Me"] = {}
for u in persons
  edges[u]["Me"] = 0
  edges["Me"][u] = 0
end

persons << "Me"

ans = -1000000000

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: Part 2

秒毎にシミュレーションすることにする

deers = open('./input').readlines.map {|line|
  ts = line.chomp.split
  v = ts[3].to_i
  t1 = ts[6].to_i
  t2 = ts[-2].to_i
  {:name => ts[0], :v => v, :t1 => t1, :t2 => t2, :x => 0, :score => 0 }
}
T=2503
for t in 0...T do
  mx = -1
  deers.each{ |d|
    if t % (d[:t1] + d[:t2]) < d[:t1]
      d[:x] += d[:v]
    end
    mx = [mx, d[:x]].max
  }
  deers.each{ |d|
    d[:score] += 1 if d[:x] == mx
  }
end
# deers.each{|d|p d}
p deers.map{|d| d[:score]}.max