== Edgy (Programming 300) ==
接続すると次のようにメッセージとともに問題が与えられる。
{{{
Welcome to Edgy, please solve the following puzzle with the WASD keys
The pattern provided will be repeated until the edge of the map is reached
 Example: If WDD is sent then it will repeat WDDWDDWDD... until an edge is reached

---------
|xxxx x |
|x  x x |
| x     |
| x @ xx|
|       |
|  xx   |
|x x x  |
---------
You have a maximum of 3 moves
}}}

結局のところこの問題は、@にいるプレイヤーを正方形の辺まで移動させるのが目的である。ただし、移動文字列の長さは`n moevs`のn以下でなくてはならないし、移動文字列は無限に繰り返される。

次のようなアルゴリズムを用いてこの問題に回答した。
 1. 一周期で移動する大きさsx, syを仮定した。
 2. n回以内で(sx, sy)に移動する方法をDFSで求めた。
  * ただし、 障害物の判定では、(x + sx*k, y + sx * k) (k = 0, 1, 2, ...)を調べた。
 3. 移動方法がある場合、それが解、無い場合はsx, syを別のものにして最チャレンジ
プログラムは次のようになった。
{{{#!highlight c++
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
int W,H,N;
int px,py;
vector<string> map;
int used[1003][1003];
int back[1003][1003];

char DIRECTION[4] = {'W','S','A','D'};
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

int size;
int result[200];
int dfs(int x, int y, int sx, int sy, int n, int maximum = 99999) {
  if(n == 0) memset(used, 0, sizeof(used));
  if(x == sx && y == sy) {
    for(int i = 0; i < n; i++) {
      cout << DIRECTION[result[i]];
    }
    cout << endl;
    exit(0);
    return true;
  }
  if(n >= N) return false;
  for(int d = 0; d < 4; d++) {
    int nx = x + dx[d], ny = y + dy[d];
    // check nx, ny
    int tx = nx, ty = ny;
    bool ok = true;
    int chk = 0;
    while(-size <= tx && tx <= size && -size <= ty && ty <= size && ok && chk < maximum) {
      if(map[ty + size][tx + size] == 'x') ok = false;
      tx += sx;
      ty += sy;
      chk++;
    }
    if(!ok)continue;
    if(!used[ny + size][nx + size]) {
      used[ny + size][nx + size] = true;
      result[n] = d;
      if(dfs(nx, ny, sx, sy, n + 1, chk)) return true;
      used[ny + size][nx + size] = false;
    }
  }
  return false;
}
int main() {
  cin >> W >> H;
  map = vector<string>(H);
  for(int y = 0; y < H; y++) {
    cin >> map[y];
    for(int x = 0; x < W; x++) {
      if(map[y][x] == '@') {
        px = x; py = y;
        map[y][x] = 'x';
      }
    }
  }
  size = W / 2;
  cin >> N;
  for(int sx = 0; sx <= N; sx++) {
    for(int sy = 0; sy <= N - sx; sy++) {
      if(sx + sy == 0) continue;
      dfs(0, 0, sx, sy, 0);
      if(sx != 0) dfs(0, 0, -sx, sy, 0);
      if(sy != 0) dfs(0, 0, sx, -sy, 0);
      if(sy != 0 && sx != 0) dfs(0, 0, -sx, -sy, 0);
    }
  }
  return 0;
}
}}}

通信するプログラムを作成し、実行したらフラグを得ることが出来た。
{{{#!highlight ruby
# coding:ASCII-8BIT
require_relative 'ctf'
require 'zlib'
require 'digest/sha1'
def parse_data(data)
  data = data.lines.map(&:chomp)
  w = data[0].size - 2
  h = data.size - 3
  map = Array.new(h){|i|data[i+1][1,w]}
  /(\d+) moves/ =~ data[-1]
  [w,h,map,$1.to_i]
end

def solve2(w, h, map, n)
  File.write('input', "#{w} #{w} #{map.map{|a|a.gsub(' ','.')}.join(" ")} #{n}")
  `./a.out < input`.strip
end

TCPSocket.open('localhost','44440') do |s|
  s.echo = false
  s.echo_color = false
  s.read_until(/Password/)
  s.print "EdgesAreFun\n"
  s.flush
  s.read_until(/\n\n/)
  caze = 0
  while(true)
    data = s.read_until(/moves/)
    STDERR.puts "Case: #{caze+=1}"
    unless data.lines[0].start_with?('--')
      STDERR.puts data.lines[0]
      data = data.lines[1..-1].join
    end
    w, h, map, n = parse_data(data)
    STDERR.puts "n=#{n}"
    s.print solve2(w, h, map, n) + "\n"
    s.flush
    s.gets
    if caze >= 112
      data = s.read_until(/text though\n/)
      /(\d+) bytes/ =~ data
      size = $1.to_i
      data = s.read(size)
      data = Zlib::Inflate.inflate(data)
      data += s.gets
      w, h, map, n = parse_data(data)
      s.print solve2(w, h, map, n) + "\n"
      s.flush
      while true
        print s.read(1)
        STDOUT.flush
      end
    end
  end
end
}}}

{{{
$ ruby solve.rb
(中略)
Case: 112
n=27
I guess you've earned it, the key is:
EdsgerDijkstraWasOnTheRightPath
}}}