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

/home/cympfh/

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

Advent of Code (Day 15-21): Part 1,2

プロコン

Fri Jan 8 13:47:50 JST 2016

Advent of Code (Day 15-21): Part 1,2

問題

Day 15

配分の割合は最初の3つについては $1003$ 通りで残りの4つめは自然に決まる.

xs= `cat input | grep -o '[-0-9]*'`.split.map(&:to_i)
cs=[]
4.times {|i|
  cs[i]=[]
  5.times {|j|
    cs[i][j]=xs[i*5+j]
  }
}
ans= -1
for a in 0..100
  for b in 0..100
    for c in 0..100
      d = 100 - a - b - c
      if d >= 0
        ds = [a,b,c,d]
        # 頭の4つの成分の線形和の積
        prod = 4.times.map{|j| 4.times.map{|i| cs[i][j] * ds[i]}.reduce :+}.map{|x| x<0 ? 0 : x}.reduce :*
        if ans < prod
          ans=prod
        end
      end
    end
  end
end

p ans

Day 15: Part 2

xs= `cat input | grep -o '[-0-9]*'`.split.map(&:to_i)
cs=[]
4.times {|i|
  cs[i]=[]
  5.times {|j|
    cs[i][j]=xs[i*5+j]
  }
}
ans= -1
for a in 0..100
  for b in 0..100
    for c in 0..100
      d = 100 - a - b - c
      if d >= 0
        ds = [a,b,c,d]
        # 5つ全ての成分について線形和をとる
        es = 5.times.map{|j| 4.times.map{|i| cs[i][j] * ds[i]}.reduce :+}.map{|x| x<0 ? 0 : x}
        # 頭4つの積がスコア
        prod = es[0 ... -1].reduce :*
        # es[4]がカロリーの和になってる
        if es[4] == 500 and ans < prod
          ans=prod
        end
      end
    end
  end
end

p ans

Day 16

問題文意味不明

Day 16: Part 2

知らん

Day 17

容量 (liter) についての DP

N=1000
c = [1] + [0] * N # `c[i]` = the num of combination of `i` liter
open('./input').readlines.map(&:to_i).each{|x|
  (N-x-1).downto(0).each{|d| c[d+x] += c[d] }
}
p c[150]

Day 17: Part 2

容量 × 個数 についての DP

M=21
N=1000
c = [] # c[i][j] = the num of combination of `i` liter by `j` items
N.times{|i| c[i] = [0] * M }
c[0][0] = 1
open('./input').readlines.map(&:to_i).each{|x|
  (N-x-1).downto(0).each{|i|
    (M-2).downto(0).each{|j|
      c[i+x][j+1] += c[i][j]
    }
  }
}
# p c[150]
p c[150].select{|x|x>0}[0]

Day 18

真っ当なライフゲームの シミュレーション

f = open('./input').readlines.map{|line|
  line.chomp.chars.map{|c| c == '#'}
}
H = f.size
W = f[0].size

def around(f, i, j)
  v = 9.times.map {|k|
    i2 = i-1+k/3
    j2 = j-1+k%3
    k!=4 and i2>=0 and i2<H and j2>=0 and j2<W and f[i2][j2]
  }
  v.count(true)
end

def gen(f)
  g = H.times.map {|i| [false] * W}
  H.times {|i|
    W.times {|j|
      k = around(f, i, j)
      g[i][j] = (f[i][j] and k==2) || k==3
    }
  }
  g
end

100.times{|i| f = gen(f) }
p f.map{|line| line.count(true)}.reduce :+

演算子 ||or とは全く同じ意味のキーワードだと思ってたんだけど、 後者は優先度が最低らしく

irb(main):017:0> a = false or true
=> true
irb(main):018:0> a
=> false

となるのに気づかず、バグらせていた.

  • a=false or true(a=false) or (true) と解釈される
  • a=false || truea=(false||true) と解釈される

Day 18: Part 2

初期状態自体にと、次世代を作る最後に、四隅を turn on する.

f = open('./input').readlines.map{|line|
  line.chomp.chars.map{|c| c == '#'}
}
H = f.size
W = f[0].size
f[0][0] = f[0][W-1] = f[H-1][0] = f[H-1][W-1] = true

def around(f, i, j)
  v = 9.times.map {|k|
    i2 = i-1+k/3
    j2 = j-1+k%3
    k!=4 and i2>=0 and i2<H and j2>=0 and j2<W and f[i2][j2]
  }
  v.count(true)
end

def gen(f)
  g = H.times.map {|i| [false] * W}
  H.times {|i|
    W.times {|j|
      k = around(f, i, j)
      g[i][j] = (f[i][j] and k==2) || k==3
    }
  }
  g[0][0] = g[0][W-1] = g[H-1][0] = g[H-1][W-1] = true
  g
end

100.times {f=gen(f)}
p f.map{|line| line.count(true)}.reduce :+

Day 19

lines = open('./input').readlines
rules = lines[0 ..-3].map {|line|
  line.chomp.split ' => '
}
base = lines[-1].chomp

rules.each {|rule|
  pos = 0
  while (idx = base.index(rule[0], pos)) != nil
    compose = base[0 ... idx] + rule[1] + base[idx + rule[0].size ... base.length]
    puts compose
    pos = idx + 1
  end
}
ruby main.rb | sort | uniq | wc -l

Day 19: Part 2

全探索しようとすると次数は最初のステップでは3で、最後では Part 1 の通りの次数程度になる. 一つのステップで文字列の長さは最大で8増えるけど、大抵の場合1とか2くらいしか増えない. ゴールの文字列の長さは488なので、最悪487程度のステップが必要かもしれない.

Day 20

house $i$ がもらえるプレゼントの数は $i$ の約数の和 $\times 10$.

INPUT=36000000

require 'prime'

def sum_of_division m
  div = Prime.prime_division m
  ret = 1
  for q,n in div
    ret *= (q**(n+1) - 1) / (q-1)
  end
  ret
end

m=INPUT/10
for i in 1..m
  if sum_of_division(i) >= m
    p i
    exit 0
  end # 831600
end

Day 20: Part 2

Part 1 のように綺麗にパッと求められそうに無いのでシミュレーションする. Elf 1 から $n$ までをシミュレートするとして $50n$ 時間. Part 1 の解が $8e5$ だから、$n \sim 8e5$ 程度であることを期待する.

INPUT=36000000
M=900000 # 8e5 程度

v = [0] * M
for i in 1..M
  for k in 1..50
    idx = i * k
    v[idx] += i * 11 if idx < M
  end
end

for i in 1...M
  if v[i] >= INPUT
    p i
    exit 0
  end
end
:!time ruby ./test.rb
884520
ruby ./test.rb  3.57s user 0.00s system 99% cpu 3.580 total

Day 21

実装&全探索

def test(player, boss)
  a = player[:damage] - boss[:armor]
  b = boss[:damage] - player[:armor]
  a = [a,1].max
  b = [b,1].max
  i = (boss[:hp].to_f / a).ceil
  j = (player[:hp].to_f / b).ceil
  i <= j
end

items = [[]]
readlines.each {|line|
  line = line.chomp
  if line == ""
    items << []
  else
    items[items.size - 1] << line.split(" ")[-3..-1].map(&:to_i)
  end
}

ans = 1e9 # take min cost

for i in 1 ...  items[0].size # one of weapons
  for j in 0 ... items[1].size # zero or one of armors
    rings = [0] + (0 ... items[2].size).to_a
    for ks in (rings.permutation(1).to_a + rings.permutation(2).to_a) # zero or one or two of rings
      cost   = items[0][i][0]
      damage = items[0][i][1]
      armor  = items[0][i][2]
      cost   += items[1][j][0]
      damage += items[1][j][1]
      armor  += items[1][j][2]
      for k in ks
        cost   += items[2][k][0]
        damage += items[2][k][1]
        armor  += items[2][k][2]
      end

      pl = {hp: 100, damage: damage, armor: armor}
      bs = {hp: 104, damage: 8, armor: 1}
      if test(pl, bs)
        ans = [ans, cost].min
      end
    end
  end
end

p ans
   cat input
Weapons:    Cost  Damage  Armor
Dagger        8     4       0
Shortsword   10     5       0
Warhammer    25     6       0
Longsword    40     7       0
Greataxe     74     8       0

Armor:      Cost  Damage  Armor
Leather      13     0       1
Chainmail    31     0       2
Splintmail   53     0       3
Bandedmail   75     0       4
Platemail   102     0       5

Rings:      Cost  Damage  Armor
Damage +1    25     1       0
Damage +2    50     2       0
Damage +3   100     3       0
Defense +1   20     0       1
Defense +2   40     0       2
Defense +3   80     0       3

   time ruby test.rb <input
78
ruby test.rb < input  0.03s user 0.00s system 98% cpu 0.032 total

Day 21: Part 2

21c21
< ans = 1e9 # take min cost
---
> ans = -1 # take max cost
41,42c41,42
<       if test(pl, bs)
<         ans = [ans, cost].min
---
>       if !test(pl, bs)
>         ans = [ans, cost].max