ログイン
編集不可のページディスカッション情報添付ファイル
CTF/Writeup/Ghost in the Shellcode 2015/Edgy

MMA

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を別のものにして最チャレンジ

プログラムは次のようになった。

   1 #include <iostream>
   2 #include <cstring>
   3 #include <cstdlib>
   4 #include <vector>
   5 #include <set>
   6 #include <queue>
   7 #include <algorithm>
   8 using namespace std;
   9 int W,H,N;
  10 int px,py;
  11 vector<string> map;
  12 int used[1003][1003];
  13 int back[1003][1003];
  14 
  15 char DIRECTION[4] = {'W','S','A','D'};
  16 int dx[4] = {0,0,-1,1};
  17 int dy[4] = {-1,1,0,0};
  18 
  19 int size;
  20 int result[200];
  21 int dfs(int x, int y, int sx, int sy, int n, int maximum = 99999) {
  22   if(n == 0) memset(used, 0, sizeof(used));
  23   if(x == sx && y == sy) {
  24     for(int i = 0; i < n; i++) {
  25       cout << DIRECTION[result[i]];
  26     }
  27     cout << endl;
  28     exit(0);
  29     return true;
  30   }
  31   if(n >= N) return false;
  32   for(int d = 0; d < 4; d++) {
  33     int nx = x + dx[d], ny = y + dy[d];
  34     // check nx, ny
  35     int tx = nx, ty = ny;
  36     bool ok = true;
  37     int chk = 0;
  38     while(-size <= tx && tx <= size && -size <= ty && ty <= size && ok && chk < maximum) {
  39       if(map[ty + size][tx + size] == 'x') ok = false;
  40       tx += sx;
  41       ty += sy;
  42       chk++;
  43     }
  44     if(!ok)continue;
  45     if(!used[ny + size][nx + size]) {
  46       used[ny + size][nx + size] = true;
  47       result[n] = d;
  48       if(dfs(nx, ny, sx, sy, n + 1, chk)) return true;
  49       used[ny + size][nx + size] = false;
  50     }
  51   }
  52   return false;
  53 }
  54 int main() {
  55   cin >> W >> H;
  56   map = vector<string>(H);
  57   for(int y = 0; y < H; y++) {
  58     cin >> map[y];
  59     for(int x = 0; x < W; x++) {
  60       if(map[y][x] == '@') {
  61         px = x; py = y;
  62         map[y][x] = 'x';
  63       }
  64     }
  65   }
  66   size = W / 2;
  67   cin >> N;
  68   for(int sx = 0; sx <= N; sx++) {
  69     for(int sy = 0; sy <= N - sx; sy++) {
  70       if(sx + sy == 0) continue;
  71       dfs(0, 0, sx, sy, 0);
  72       if(sx != 0) dfs(0, 0, -sx, sy, 0);
  73       if(sy != 0) dfs(0, 0, sx, -sy, 0);
  74       if(sy != 0 && sx != 0) dfs(0, 0, -sx, -sy, 0);
  75     }
  76   }
  77   return 0;
  78 }

通信するプログラムを作成し、実行したらフラグを得ることが出来た。

   1 # coding:ASCII-8BIT
   2 require_relative 'ctf'
   3 require 'zlib'
   4 require 'digest/sha1'
   5 def parse_data(data)
   6   data = data.lines.map(&:chomp)
   7   w = data[0].size - 2
   8   h = data.size - 3
   9   map = Array.new(h){|i|data[i+1][1,w]}
  10   /(\d+) moves/ =~ data[-1]
  11   [w,h,map,$1.to_i]
  12 end
  13 
  14 def solve2(w, h, map, n)
  15   File.write('input', "#{w} #{w} #{map.map{|a|a.gsub(' ','.')}.join(" ")} #{n}")
  16   `./a.out < input`.strip
  17 end
  18 
  19 TCPSocket.open('localhost','44440') do |s|
  20   s.echo = false
  21   s.echo_color = false
  22   s.read_until(/Password/)
  23   s.print "EdgesAreFun\n"
  24   s.flush
  25   s.read_until(/\n\n/)
  26   caze = 0
  27   while(true)
  28     data = s.read_until(/moves/)
  29     STDERR.puts "Case: #{caze+=1}"
  30     unless data.lines[0].start_with?('--')
  31       STDERR.puts data.lines[0]
  32       data = data.lines[1..-1].join
  33     end
  34     w, h, map, n = parse_data(data)
  35     STDERR.puts "n=#{n}"
  36     s.print solve2(w, h, map, n) + "\n"
  37     s.flush
  38     s.gets
  39     if caze >= 112
  40       data = s.read_until(/text though\n/)
  41       /(\d+) bytes/ =~ data
  42       size = $1.to_i
  43       data = s.read(size)
  44       data = Zlib::Inflate.inflate(data)
  45       data += s.gets
  46       w, h, map, n = parse_data(data)
  47       s.print solve2(w, h, map, n) + "\n"
  48       s.flush
  49       while true
  50         print s.read(1)
  51         STDOUT.flush
  52       end
  53     end
  54   end
  55 end

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

CTF/Writeup/Ghost in the Shellcode 2015/Edgy (最終更新日時 2015-01-19 12:52:34 更新者 nomeaning)