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

/home/cympfh/

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

はてなブログはクソなのでやめます.

なんでわざわざ、1企業がやってる1サービスのためだけに記法を覚えないといけないんだ… いろいろ苦痛なので乗り換えます.

hackmd.io

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

Advent of Code (Day l-7): Part 2

Thu Dec 24 19:26:29 JST 2015

Advent of Code (Day 1-7): Part 2

Day 1: Part 2

シミュレーション

c=1
gets.chars.each_with_index{|p,i|
  if p == '('
    c += 1
  else
    c -= 1
    if c == 0
      p (i+1)
      exit 0
    end
  end
}

Day 2: Part 2

算数

p open('./input').readlines.map{|line|
  x,y,z=line.chomp.split('x').map(&:to_i)
  (x+y+z-[x,y,z].max)*2+x*y*z
}.reduce :+

Day 3: Part 2

シミュレーション

require 'set'
visited = Set.new [[0,0]]

z = [[0, 0]]*2
dz = {'>' => [1,0], '<' => [-1,0], 'v' => [0,1], '^' => [0,-1]}

gets.chomp.chars.each_with_index{|c,i|
  x,y = z[i%2]
  dx,dy = dz[c]
  x += dx
  y += dy
  visited << [x, y]
  z[i%2] = [x, y]
}
p visited.size

Day 4: Part 2

全探索だとすると 16 ** 6 => 16777216 程度掛かるが果たして?

#!/bin/bash

TOKEN=yzbqklnj

for n in `seq $1 $2`; do
  FROM=$(( 10000 * $n ))
  TO=$(( 10000 * ( $n + 1 ) - 1 ))
  echo $FROM to $TO
  for i in `seq $FROM $TO`
  do
    MD5=$(echo $TOKEN$i | tr -d '\n' | md5sum)
    case $MD5 in
      000000* )
        echo HIT: $i $MD5
        exit 0
        ;;
    esac
  done
  sleep 0.1 # 念の為
done

結果 (とても時間がかかる):

   bash test.sh 60 3000
0 to 9999
10000 to 19999
  :
9900000 to 9909999
9910000 to 9919999
9920000 to 9929999
9930000 to 9939999
9940000 to 9949999
9950000 to 9959999
9960000 to 9969999
HIT: 9962624 0000004b347bf4b398b3f62ace7cd301 -

Day 5: Part 2

実装

p open('./input').readlines.select{|line|
  w = line.chomp
  n = w.size

  p = false
  for i in 0...n
    for j in (i+2)...n
      p = true if (w[i]==w[j] and w[i+1]==w[j+1])
    end
  end

  q = false
  for i in 0...(n-2)
    q = true if (w[i] == w[i+2])
  end

  p and q
}.length

Day 6: Part 2

N=1000
f = N.times.map{[0]*N}

readlines.each{|line|
  ts = line.split
  dl = 0
  if ts[0] == 'toggle'
    dl = 2
    a,b = line.split[1].split(',').map(&:to_i)
    c,d = line.split[3].split(',').map(&:to_i)
  else
    dl = 1
    dl = -1 if ts[1] == 'off'
    a,b = line.split[2].split(',').map(&:to_i)
    c,d = line.split[4].split(',').map(&:to_i)
  end

  for i in a..c
    for j in b..d
      f[i][j] += dl
      f[i][j] = 0 if f[i][j] < 0
    end
  end
}

p f.map{|v|v.reduce :+}.reduce :+
:!time ruby test.rb < input
15343601
ruby test.rb < input  2.95s user 0.00s system 99% cpu 2.953 total

Day 7: Part 2

96c95
<     b = 14146 :: Word16
---
>     b = 956 :: Word16

に書き換えてコンパイルし直すだけ.

Advent of Code (Day l-7): Part 2

Day 1: Part 2

シミュレーション

c=1
gets.chars.each_with_index{|p,i|
  if p == '('
    c += 1
  else
    c -= 1
    if c == 0
      p (i+1)
      exit 0
    end
  end
}

Day 2: Part 2

算数

p open('./input').readlines.map{|line|
  x,y,z=line.chomp.split('x').map(&:to_i)
  (x+y+z-[x,y,z].max)*2+x*y*z
}.reduce :+

Day 3: Part 2

シミュレーション

require 'set'
visited = Set.new [[0,0]]

z = [[0, 0]]*2
dz = {'>' => [1,0], '<' => [-1,0], 'v' => [0,1], '^' => [0,-1]}

gets.chomp.chars.each_with_index{|c,i|
  x,y = z[i%2]
  dx,dy = dz[c]
  x += dx
  y += dy
  visited << [x, y]
  z[i%2] = [x, y]
}
p visited.size

Day 4: Part 2

全探索だとすると 16 ** 6 => 16777216 程度掛かるが果たして?

Day 5: Part 2

実装

p open('./input').readlines.select{|line|
  w = line.chomp
  n = w.size

  p = false
  for i in 0...n
    for j in (i+2)...n
      p = true if (w[i]==w[j] and w[i+1]==w[j+1])
    end
  end

  q = false
  for i in 0...(n-2)
    q = true if (w[i] == w[i+2])
  end

  p and q
}.length

Day 6: Part 2

N=1000
f = N.times.map{[0]*N}

readlines.each{|line|
  ts = line.split
  dl = 0
  if ts[0] == 'toggle'
    dl = 2
    a,b = line.split[1].split(',').map(&:to_i)
    c,d = line.split[3].split(',').map(&:to_i)
  else
    dl = 1
    dl = -1 if ts[1] == 'off'
    a,b = line.split[2].split(',').map(&:to_i)
    c,d = line.split[4].split(',').map(&:to_i)
  end

  for i in a..c
    for j in b..d
      f[i][j] += dl
      f[i][j] = 0 if f[i][j] < 0
    end
  end
}

p f.map{|v|v.reduce :+}.reduce :+
:!time ruby test.rb < input
15343601
ruby test.rb < input  2.95s user 0.00s system 99% cpu 2.953 total

Day 7: Part 2

96c95
<     b = 14146 :: Word16
---
>     b = 956 :: Word16

に書き換えてコンパイルし直すだけ.

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
広告を非表示にする

Advent of Code (Day 1-7)

Tue Dec 15 19:04:11 JST 2015

Advent of Code (Day 1-7)

12月はこういう、advent calendar とかいうイベントが各方面であるらしい. 薄々は知ってる. その分野の記事を毎日誰かが担当して書くらしい. Advent of Code は、プロコンの問題を毎日一題ずつ出題される (他にも; http://www.adventar.org/calendars/912).

まだ Day 7 までしか解いてないからかもしれないけど易しい部類のものばかりが並ぶ. 問題と大きい入力が与えられるので、手元で実行して出力結果を送信する系.

以下、私の解法

Day 1

順序を気にせず開き括弧と閉じ括弧を数えるだけ

cat input | grep -o '(' | wc -l
cat input | grep -o ')' | wc -l
# 引き算!

Day 2

算数

Day 3

シミュレーション

Day 4

md5sum コマンドを使って全探索. 時間は掛かった. 雑に言えば、$165$ 個に 1個は、目的のものが得られるはず.

Day 5

example まで含めて英文を気をつけて読めばOK.

Day 6

シミュレーション. 時間はかかるけど入力は300程度しかない.

Day 7

真面目にシミュレーションすることをせず、 ソースコードに変換して、コンパイラに投げることにした. 変数の依存関係が怪しいので、 自由な順序で宣言しても上手いことしてくれるHaskellにした. (a までに) ループはどうせ無いだろうと踏んだ. あったら困ったけど無かった.

# コードのヘッダ
cat << EOM > test.hs
import Data.Word
import Data.Bits
main :: IO ()
main = print a
  where
EOM

# 入力をHaskell語に変換
sed '
s/AND/.\&./g
s/OR/.|./g
s/NOT/complement/g
s/LSHIFT/`shiftL`/g
s/RSHIFT/`shiftR`/g
s/^\(.*\) -> \(.*\)$/    \2 = \1 :: Word16/g'
input >> test.hs

# 処理系に丸投げ
runghc test.hs

変数名に do if などのキーワードがあったので、手作業で doo iff みたいに変換する手間があった.

Word という型が、符号なし整数らしい. 学んだ. Haskellのビット演算は、演算子が気持ち悪い. ライブラリ実装な時点であれだ.

広告を非表示にする

CODERUNNER 2015 本戦

Sun Dec 13 14:46:11 JST 2015

CODERUNNER 2015 本戦

(一瞬だけ) (スコアの上昇速度で) 輝けた

  • 問題長いので、全部読むのは諦めた
  • 部分だけを使って極めれば勝てるだろうという楽観
  • 結果的に、外注を引き受けることをしなかった
    • 完全に敗因これ

解法

APIを使う練習のつもりで、次のプログラムをひとまず書いて動かそうとする

  1. 国から受注
  2. 社員を割り当てる
    • その仕事種類についての速度でソートして上から2人だけ取る

ちょっとルールを理解してきれてなかった.

  1. 期間内に仕事をこなせるぎりぎりの人間を割り当てるように変更
    • 実際にPOSTを投げる箇所のコードを、「2人だけ取る」のままで90分ほど過ごし、最下位争いをしていた.
  2. ギリギリOKな人間を割り当てたはずなのに、何故かエラー (この人間だと納期に間に合わない) が帰ってきた
    • 仕事を実際よりも2倍あるものと見なして、人間を割り当てることにした
    • エラーが帰ってきたら外注に出すように処理 (例外処理)
    • 割り当てる人間が6人以上必要なとき、そんなに人間を使うのが勿体無いので、外注にする
    • その他、割り当てに失敗するときにも外注

getinfo

その時点での、自分の情報を得るAPI. これは、別のプログラムとして、1.1秒ごとに取得させて利用した.

TOKEN=9F7RPQP86817D3PJMIAQES8L0XLN6FZ9
while :; do
  curl -s http://game.coderunner.jp/getinfoJson?token=$TOKEN > tmp.json
  mv tmp.json info.json
  date;
  sleep 1.1
done

わざわざ書くほどのものでもないけど. 最後の1時間くらい、このAPIが頻繁に (1/10の確率) 死ぬようになった. そうすると古い情報で社員を割り当てるので、しょっちゅう、「その社員は既に働いています」エラーが出た.

  timeout 1 curl -s http://game.coderunner.jp/getinfoJson?token=$TOKEN > tmp.json &&
    mv tmp.json info.json

に変更した. timeout コマンド便利. curlタイムアウトのオプションとかいちいち覚えてられないです.

知見

  1. 自分たちで仕事が出来るならそれが一番良い
  2. 外注に出す行為はリスク
  3. 国から仕事を受けるのは運ゲー
  4. 外注から仕事を取るのが賢い

プログラム

最終的なプログラムはこれ.

fs = require 'fs'
{execSync} = require 'child_process'
info = require './info.json'

exec = (com) ->
  execSync(com).toString()

TOKEN = '9F7RPQP86817D3PJMIAQES8L0XLN6FZ9'

int = (x) -> x | 0

# [仕事のID] [納期までの残り時間(秒, 小数点以下切り捨て)] [仕事量] [仕事の種類] [報酬] [賠償]
[tid, time, w, k, reward, risk] =
  exec("curl -s http://game.coderunner.jp/taketask?token=#{TOKEN}").split(' ').map(int)
console.warn "受注: #{[tid, time,w,k,reward,risk]}"
fs.appendFileSync 'log', [tid, time,w,k,reward,risk]
fs.appendFileSync 'log', '\n'

## 外注
#
outsource = ->
  cost = reward * 0.7
  cost = cost | 0
  console.warn "* 外注: cost = #{cost}"
  exec "curl -s 'http://game.coderunner.jp/outsource?task=#{tid}&orderReward=#{cost}&token=#{TOKEN}'"

## 内
#
inner = ->
  workers = []
  info.workers.forEach (w, i) ->
    return if w.time > 0
    workers.push { id: w.id, speed: w.speed[k] }
  workers.sort (a,b) -> b.speed - a.speed

  qs = []
  sum = 0
  ok = false

  for i in [0 ... workers.length]
    qs.push workers[i].id
    sum += workers[i].speed
    if sum * time > (w*1.2)
      ok = true
      break

  if qs.length > 8
    ok = false

  console.warn "* 割り当て: #{qs} (#{sum})"
  if ok
    res =
      exec "curl -s 'http://game.coderunner.jp/assign?token=#{TOKEN}&task=#{tid}&worker=#{qs.join(',')}'"
    console.warn res
    if res.indexOf('Error:') is 0
      do outsource
  else
    console.warn '* 割り当て無理'
    do outsource

do inner

延べて2時間程度はプログラムを書き続けてたのに、結果的に書いたのはこれだけと思うと、しょぼい. 他の人のはどんなだろう.

実況

2015/12/12 2:30 PM - 5:30 PM

(長い負スコアから偶然脱却したときのコメント)

(うん、だってバグってるからね)

(割り当てに失敗した仕事を放置してたので一気に賠償してた)

(外注に出す、外注を受ける、って言ってくれればいいのに)

(自分の点数の折れ線グラフ smooth bezier)

(プログラム変更してるはずなのにprinfデバッグもできないぞ、おかしいなあ、と思ったら違うファイル触ってた、みたいなタイプのバグです)

(まともにスコアを稼ぎはじめたので、様子見のために、自分と一位と割と上位の人のスコアを比較し始める. 実はコレと同じグラフを描いてくれるためのツールが用意されてたらしい)

(他の何よりも使うAPIなんですよ、これ)

(じわりじわりと、親に顔向け出来る順位に来たので安心してトイレに立つ頻度が増える)

(もうこれ以上プログラムを変更する気はない、という意思表明です)

(バグが取れてからは、メインのプログラムに一切変更せずにここまで来たので浮かれた)

(最後の30分、外注天国になっていたらしく、外注から美味しい仕事を引き受けるほうが点数が稼げたようです)

(最終スコア)

(最終スコア)

広告を非表示にする

SECCON 2015 - Web 100

SECCON 2015 - Web 100

URL http://entryform.pwn.seccon.jp/register.cgi だけが渡される. メールと名前だけの入力欄があるフォーム. http://entryform.pwn.seccon.jp/ にアクセスすると、 /SECRETS register.cgi_bak の存在が確認できて、 特に register.cgi_bak では register.cgiソースコードらしきものがテキストとして読める.

中を見ると Perl で、 大事そうなとこだけ引用すると、

if($q->param("mail") ne '' && $q->param("name") ne '') {
  open(SH, "|/usr/sbin/sendmail -bm '".$q->param("mail")."'");
  print SH "From: keigo.yamazaki\@seccon.jp\nTo: ".$q->param("mail")."\nSubject: from SECCON Entry Form\n\nWe received your entry.\n";
  close(SH);

Perl 知らないけどたぶん、 "/usr/sbin/sendmail -bm '".$q->param("mail")."'" という文字列を bash に投げるのだと思われる. というわけで、mail に ' ; echo Hi ; ' みたいな文字列を渡すことで OSコマンドインジェクションができる.

あと、

  open(LOG, ">>log"); ### <-- FLAG HERE ###
  flock(LOG, 2);

とあるので、作業ディレクトリ直下の log というファイルを覗いてみれば良いらしい.

肝心の sendmail が正しく動いてなかったり、 ファイルを新しく作ることが許可されてなかったりするので、 直接ファイルの中身を我々に見る手立てが無い. というわけでブラインドする.

tailed さんが自動化スクリプトを書いてくれたのでそれを使った. 賢いことに、 n文字目が何であるか? の命題 (真なら即座に結果が返って来て、さもなくば sleep 10 する) と、その逆の命題を同時に投げ、 先に返って来た命題が正しいと判定することでさっさとできる.

base64 に変換してからその判定に掛けるように変更して、ls の結果がわかるようになる

chars.each {|c|
  check("test $(ls -a . | base64 -w0 | cut -b #{i}) = #{c}")
}

で、 SECRETS/backdoor123.php なるファイルの存在を確認した. ブラウザでこれにアクセスして、エスパーして cat ../log したらできた (直接さっきのスクリプトで cat してもよかったのでは).

広告を非表示にする