Writeups for Ghost in the Shellcode 2015
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以下でなくてはならないし、移動文字列は無限に繰り返される。
次のようなアルゴリズムを用いてこの問題に回答した。
- 一周期で移動する大きさsx, syを仮定した。
- n回以内で(sx, sy)に移動する方法をDFSで求めた。
- ただし、 障害物の判定では、(x + sx*k, y + sx * k) (k = 0, 1, 2, ...)を調べた。
- 移動方法がある場合、それが解、無い場合は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