Code War 2017 - Online Round Write-ups - Part 2

code-war-banner

phần 1, chúng tôi đã gửi đến các bạn hướng dẫn cho một số bài trong phần Code Puzzles của vòng loại Code War 2017 bao gồm:

  • Welcome to Code War 2017
  • Point Of View
  • Messed Up Poem
  • 2D is Hard
  • Let Take A Break
  • Coding Is Art
  • His Best Friend
  • Wall Of Text
  • 8 is 8 but 8 is not 8
  • KubEye Challenge

Và bài viết này sẽ gồm những chia sẻ về phần write-ups cho các bài còn lại, bao gồm :

  • Shall We Play A Game
  • CodeWar.js
  • Tricky-Ricky Reading
  • Dev's Madness
  • Trust Me
  • Old Riddle

Hãy để lại những comments chia sẻ với chúng tôi suy nghĩ, cảm tưởng của các bạn về những bài thi lần này, hay chia sẻ những cách giải mà bạn cho là hay, và ưng ý hơn so với của ban tổ chức nhé 😄

Shall We Play A Game (250 point)

Trước tiên, hãy search Google và bạn sẽ tìm thấy mô tả game bull and cow trên wiki https://en.wikipedia.org/wiki/Bulls_and_Cows Nội dung là người chơi đoán số cho đến khi đoán trúng. Số này không có chữ số nào bị lặp. Số chữ bull là số chữ số xuất hiện trong kết quả và đúng vị trí. Số chữ cow là số chữ số xuất hiện trong kết quả nhưng không đúng vị trí. Viết 1 chương trình đơn giản dùng TCP socket để nhận và gửi gói tin, lần lượt đưa ra các dự đoán. Ta có dùng 1 chiến thuật rất đơn giản. Ban đầu khởi tạo mảng chứa tất cả các số có thể. Tại mỗi lượt chọn random trong mảng đó, nhận kết quả số lượng bull, cow trả về từ server và filter lại mảng để thu hẹp phạm vi đoán. Do server giới hạn số lượng lần đoán và chiến thuật của mình là chọn random nên nhiều lúc sẽ không thể tìm ra được kết quả. Tuy nhiên, với một chút may mắn, thử chạy đi chạy lại chương trình vài lượt thì cũng sẽ có thể nhận được flag. Dưới đây là đoạn code để giải bài puzzle, được viết bằng ngôn ngữ ruby. Các bạn có thể cải thiện thuật toán để việc dự đoán hiệu quả hơn.

require 'socket'

arr = {}
(4..6).each do |dg|
    valid_set = []
    (10**(dg-1)..10**dg-1).each do |i|
      digits = i.to_s.split("")  
      valid_set.push i if digits.length == digits.uniq.length  
    end
    arr[dg] = valid_set
end  

def cmp d1, d2
    d1 = d1.to_s.split("")
    d2 = d2.to_s.split("")
    return [-1, -1] if d1.length != d2.length
    b = 0
    c = 0
    d1.each_with_index do |ch, i|
        if d2.index(ch)
            if ch == d2[i]
                b += 1
            else
                c += 1
            end
        end
    end
    return [b, c]
end 

puts arr[4].length

count = 0
status = 0
s = TCPSocket.new 'bullandcow-challenge.framgia.vn', 2015

value_set = []
while true
  line = s.recv(2014)
  puts "[#{line}]"
  if (d = line.match(/(\d)-digit/)) && (!line.match(/bull|cow|nothing/))
    if (status == 0)
      d = d[1].to_i if d
      value_set = arr[d]
      status = 1
      guess = value_set.sample if value_set
      puts "#{guess}"
      s.puts "#{guess}" 
    end
  elsif line.match(/bull|cow|nothing/)
    if line.match(/nothing/)
        b = 0
        c = 0
    else
      b = line.split(/\s/).count("bull")
      c = line.split(/\s/).count("cow")
    end
    puts "bull=#{b} cow=#{c}"
    value_set = value_set.select{|x| cmp(guess, x) == [b, c]} if guess
    guess = value_set.sample if value_set
    puts "#{guess}"
    s.puts "#{guess}" 

  elsif line.match(/another/)
    status = 0  
  else
    count += 1
    break if count >= 30
  end
end

s.close   

Flag: CodeWar{you_hit_it_bingo_bingo}

CodeWar.js (70 point)

Sometimes, JS doesn't mean JS at all. WTF ? But it a hint

Bạn dễ dàng nhận ra đây không phải là file js mà chỉ là một cái ảnh png. Đổi từ js sang png bạn sẽ có một cái ảnh bình thường xem được. Tại sao một bức ảnh lại được đặt phần mở rộng là js, hơn nữa ảnh này có khác ít nhiều với ảnh gốc (nếu không muốn nói là khác hẳn), phải chăng đây là steganography, chúng ta có thể dùng javascript để tìm kiếm thứ gì ẩn sau bức ảnh đó. Hãy làm một phép Google đơn giản nhé http://bfy.tw/BLVX 😄

Bạn tìm thấy ngay thư viện https://github.com/petereigenschink/steganography.js/ đúng không? Hãy dùng thư viện này với bức ảnh trên ta có một mã base64, decode nó chúng ta sẽ có được flag.

Flag: CodeWar{peter-eigenschink}

Tricky-Ricky Reading (200 point)

4 LNF OXOX1BX1 64C6CX V1 G6VF4F3 VD IGN6 4W8FN161XP, L0XXW6 6GN6 XG6 411NLN3X IN8 OXW6T, NFP 6GN6 4 CN4P DCN6 4F N 1VLFX1, XUNINFXP NFP CFV46VOX88. VFLX 4 L5V6GXP OT DNLX I46G OT GNFP NFP VD5FP OT XGLXU8 IX1X IX6 ; NFP 4 CNLX1CXP 1XPFVI4F3 GIV8X X6N18 6GXT IX1X, NFP GVI 6GXT LNOX 6V BX ; B56 TXBVFP 6G48 46 XX8OXP 4 46VFLXP G6VF4F3. N6 I8W44LG IX WV68WXP 6V 1X86, N8 855NC, DV1 NF GV51 ; NFP NC6X1 4F XG6 PNT 4 XBOXOX11XP UNI4F3 5W, N8 4D D1VO N PXXW O5C8BX1, NFP PF4D4F3 XG6 411NLN3X 5246X D5CC VD 3FX88NWX18. GVI V1 IGXF 6GXT 6VVU G6X41 NCWLX8, NFP VD IGN6 N3X, 8X0, V1 6N684VF 6GXT IX1X, 4 GN9X FV 4PXN. 4 VFCT UFVI 6GN6 6GXT LNOX NFP IXF6 C4UX XG6 NXC9X8 6GN6 VCBIXP WN86 XG6 PF4IVI8, NFP 6GN6, IV1PFXP 4F XG6 XC6GX VD OT 6LND846N884P4VF, 4 WN4P FV 6FX66N4VF VD G6TFN4F3. 

Submit Flag as: CodeWar{ SHA1 of decoded text with no punctuation, no space, all upper case }

Bỏ hết các dấu ., ,, ; và tạm thay các chữ số bằng các chữ cái chưa có trong đoạn text ta được

K LNF OXOXEBXE QKCQCX VE GQVFKFJ VD IGNQ KWSFNEQEXP LAXXWQ QGNQ XGQ KEENLNJX INS OXWQT NFP QGNQ K CNKP DCNQ KF N EVLFXE XUNINFXP NFP CFVKQVOXSS VFLX K LMVQGXP OT DNLX IKQG OT GNFP NFP VDMFP OT XGLXUS IXEX IXQ NFP K CNLXECXP EXPFVIKFJ GIVSX XQNES QGXT IXEX NFP GVI QGXT LNOX QV BX BMQ TXBVFP QGKS KQ XXSOXP K KQVFLXP GQVFKFJ NQ ISWKKLG IX WVQSWXP QV EXSQ NS SMMNC DVE NF GVME NFP NCQXE KF XGQ PNT K XBOXOXEEXP UNIKFJ MW NS KD DEVO N PXXW OMCSBXE NFP PFKDKFJ XGQ KEENLNJX MHKQX DMCC VD JFXSSNWXES GVI VE IGXF QGXT QVVU GQXKE NCWLXS NFP VD IGNQ NJX SXA VE QNQSKVF QGXT IXEX K GNYX FV KPXN K VFCT UFVI QGNQ QGXT LNOX NFP IXFQ CKUX XGQ NXCYXS QGNQ VCBIXP WNSQ XGQ PFKIVIS NFP QGNQ IVEPFXP KF XGQ XCQGX VD OT QLNDSKQNSSKPKVF K WNKP FV QFXQQNKVF VD GQTFNKFJ

Đây là mã hoá kiểu substitution, có thể dùng trang http://quipqiup.com/ để giải ra đoạn text dưới đây.

I CAN MEMERZER TILTLE OR HTONING OF WHAT IPSNARTRED CXEEPT THAT EHT IRRACAGE WAS MEPTY AND THAT I LAID FLAT IN A ROCNER EKAWANED AND LNOITOMESS ONCE I CUOTHED MY FACE WITH MY HAND AND OFUND MY EHCEKS WERE WET AND I LACERLED REDNOWING HWOSE ETARS THEY WERE AND HOW THEY CAME TO ZE ZUT YEZOND THIS IT EESMED I ITONCED HTONING AT WSPIICH WE POTSPED TO REST AS SUUAL FOR AN HOUR AND ALTER IN EHT DAY I EZMEMERRED KAWING UP AS IF FROM A DEEP MULSZER AND DNIFING EHT IRRACAGE UJITE FULL OF GNESSAPERS HOW OR WHEN THEY TOOK HTEIR ALPCES AND OF WHAT AGE SEX OR TATSION THEY WERE I HAVE NO IDEA I ONLY KNOW THAT THEY CAME AND WENT LIKE EHT AELVES THAT OLZWED PAST EHT DNIWOWS AND THAT WORDNED IN EHT ELTHE OF MY TCAFSITASSIDION I PAID NO TNETTAION OF HTYNAING

Sửa lại thứ tự chữ cái trong các từ (chú ý 3 chữ cái cuối trong từ không thay đổi) và thay thế 1 số chữ cái chưa chính xác chúng ta được

I CAN REMEMBER LITTLE OR NOTHING OF WHAT TRANSPIRED EXCEPT THAT THE CARRIAGE WAS EMPTY AND THAT I LAID FLAT IN A CORNER AWAKENED AND MOTIONLESS ONCE I TOUCHED MY FACE WITH MY HAND AND FOUND MY CHEEKS WERE WET AND I RECALLED WONDERING WHOSE TEARS THEY WERE AND HOW THEY CAME TO BE BUT BEYOND THIS IT SEEMED I NOTICED NOTHING AT IPSWICH WE STOPPED TO REST AS USUAL FOR AN HOUR AND LATER IN THE DAY I REMEMBERED WAKING UP AS IF FROM A DEEP SLUMBER AND FINDING THE CARRIAGE QUITE FULL OF PASSENGERS HOW OR WHEN THEY TOOK THEIR PLACES AND OF WHAT AGE SEX OR STATION THEY WERE I HAVE NO IDEA I ONLY KNOW THAT THEY CAME AND WENT LIKE THE LEAVES THAT BLOWED PAST THE WINDOWS AND THAT DROWNED IN THE LETHE OF MY DISSATISFACTION I PAID NO ATTENTION OF ANYTHING

Công việc còn lại chỉ là bỏ hết dấu cách và tính SHA1 là xong.

Flag: CodeWar{199da2eb356cc6f9ab91f86cbc468a53a7b77755}

Dev's Madness (375 point)

Hey dev, are you ready for some madness ?

Download file zip về, giải nén ra, chúng ta sẽ nhận được 1 thư mục có tên là gitpro, như vậy là bài này có liên quan đến git. Chạy git status, git branch, git log... kiểm tra 1 lượt thì chúng ta thấy có tổng cộng khoảng vài nghìn branch, mỗi branch checkout ra 1 vài branch khác. Có vẻ là từ branch master phải đi theo 1 chuỗi các branch nào đó. Để ý đến chữ cái đầu tiên của tên các branch, có thể khi ghép chúng lại với nhau ta sẽ được flag? Sau 1 hồi git log --graph, gitk, hoặc git reflog thì các bạn sẽ có thể tìm ra các branch đó là F85A1B1C, LF36AD26, A74200C7, G5DE52C4, H873C5B9, ECB3B7A0, R0C67CE4, EBB23A6E, ghép chữ cái đầu với nhau thì không được flag nhưng được 1 thông điệp là FLAGHERE. Thử check out sang 8 branch đó, ta lấy được 8 file nhưng cũng không có file nào chứa flag cả. Tuy nhiên có 1 file có file header của định dạng PNG. Vậy là chỉ cần tìm cách ghép 8 file này lại với nhau là có được 1 ảnh gì đó có thể chứa flag. Nhưng ghép kiểu gì đây, không lẽ thử tất cả 8! = 40320 trường hợp? Tất nhiên là không cần, trong 8 file đã có 1 file chứa header PNG chúng ta biết đó là part đầu tiên, nếu để ý sẽ thấy 1 file có dung lượng nhỏ hơn các file còn lại đó là part cuối cùng. Tóm lại là chỉ cần thử 6! = 720 trường hợp, 1 con số hoàn toàn khả thi. Và viết 1 đoạn script để ghép các file lại với nhau chúng ta tìm được bức ảnh như sau:

code-war-dev-madness

Dưới đây là một đoạn code đơn giản bằng Ruby để thực hiện việc ghép nối các file, các bạn có thể tham khảo:

branches = %w(F85A1B1C LF36AD26 A74200C7 G5DE52C4 H873C5B9 ECB3B7A0 R0C67CE4 EBB23A6E)

Dir.chdir 'gitpro'

branches.each_with_index do |branch, i|
  `git checkout -q #{branch}`
  `cp flag ../flag_#{i}`
end

Dir.chdir '..'
`mkdir -p out`

chunks = {}
Dir.glob('flag_*').each { |f| chunks[f] = File.read(f) }

first = chunks.select { |_, c| c.index 'PNG' }.keys[0]
last = chunks.min_by { |_, c| c.bytes.size }[0]

puts first
puts last

arr = ('flag_0'..'flag_7').to_a - [first, last]
arr.permutation(6).each_with_index do |a, i|
  `cat #{first} #{a.join(" ")} #{last} > out/#{i}.png`
end

Flag: Codewar{one_branch_is_not_enough}

Trust Me (250 point)

It's a virus ? Dare to run it ?

Đoạn code trong file js vốn là của Locky Virus đã được chỉnh sửa, chủ yếu là code rác, hàm E() sẽ có nhiệm vụ decode.

Chú ý đến dòng:

for (Hg = 0; Hg < r7_.length; Hg++) {

Ta thêm console.log(r7_) vào, rồi copy paste vào dev tool của trình duyệt để chạy. Ta sẽ nhận được kết quả

http://i0.kym-cdn.com/photos/images/newsfeed/000/096/044/trollface.jpg?f=1.jpg|0|1|0,https://pastebin-dot-com-file.text?f=RRPNHRvv|1|0|1

Các bạn có để ý thấy đường link pastebin chứ 😄

https://pastebin-dot-com-file.text?f=RRPNHRvv|1|0|1

Truy cập vào đường dẫn, https://pastebin.com/RRPNHRvv, ta sẽ nhận được 1 đống code javascript khác. Đây là JSFuck, bạn chỉ cần xoá cái () ở cuối cùng đi, paste vô dev tool để nhận kết quả:

function anonymous() {
    alert("Congratz ! kodeWar{your_js_skill_is_ghost}");f="CodeWar{real_js_flag_for_u_:D}";
}

Vậy là chúng ta đã có được flag rồi.

Flag: CodeWar{real_js_flag_for_u_:D}

Old Riddle (300 point)

There are 7 houses: 

- Each house has a different color. 
- The people living in the houses all have a different nationality. 
- Each person has a differnet favorite drink. 
- Each house is home to a different pet. 
- Each person prefers a different type of tabaco product. 
- Each person prefers a different type of food. 
- A different type of tree grows in front of each house. 
- Each person plays a different sport. 
- Different flowers grow in front of each house. 
- Each person drives a different type of car.

Here are the clues:

- There are two houses between the crocuses and the cats.
- The person drinking soda lives directly to the right of the gray house.
- The person smoking Chersterfields lives directly to the right of the person eating steaks.
- The horses live directly to the left of the person drinking coffee.
- The person with birch trees has cats.
- There is one house between the redwoods and the snakes.
- The person eating potatoes lives directly next to the brown house.
- There is one house between the Tennis player and the person eating spaghetties on the right
- There is one house between the Swede and the driver of the Porsche.
- The cactuses grow in front of house four.
- There are two houses between the black and pink house on the right
- The dahlias grow to the right of the person drinking icetea.
- There is one house between the Rugby player and the person eating eggs on the right
- The person playing Badminton smokes Prince.
- There is one house between the palm trees and the person smoking Cubans on the left
- The person eating cheese lives to the left of the brown house.
- The turtles live directly to the right of the person smoking Chersterfields.
- There are two houses between the black house and the house the British lives in on the right
- The eucalyptus trees do not grow in front of house four.
- There are two houses between the German and the redwoods on the left
- The Renault driver lives directly next to Lacrosse player.
- There are two houses between the VW driver and the person smoking Bluemaster on the left
- The cats live directly next to the blue house.
- There are two houses between the house of the person eating potatoes and the green house on the right
- The Rolls Royce driver lives to the right of the Volvo driver.
- The Swiss lives directly next to the Badminton player.
- The Rugby player lives directly to the left of the person smoking Dunhill.
- The person in house three drinks milk.
- There are two houses between the Baseball player and the person drinking wine on the right
- There are two houses between the tortoises and the dogs.
- There is one house between the dogs and the person drinking lemonade.
- There are two houses between the pink house and the house the Swede lives in on the left
- The British lives directly next to the orchids.
- There is one house between the house where the tulips grow and the red house.
- The person in house five does not drink wine.
- There is one house between the cats and the person eating chocolate on the right
- The VW driver lives directly to the left of the Ferrari driver.
- The Rolls Royce is not parked in front of house seven.
- There is one house between the crocuses and the cactuses.
- There is one house between the German and the Marlboro smoking person.
- There is one house between the willows and the person smoking Cubans on the right
- There are two houses between the Lacrosse player and the person drinking coffee on the left
- The Italian lives in the blue house.
- There are two houses between the lilies and the Tennis player on the left
- There is one house between the Spanish and the driver of the VW on the left.
- There are two houses between the turtles and the person eating eggs.
- The Italian lives to the left of the Badminton player.
- There is one house between the lilies and the Ferrari.
- The orchids grow to the left of the Basketball player.
- The nut trees grow directly next to the person drinking wine. 

Where does everybody live?. Can you solve this riddle ? 

Compute flag as: CodeWar{'lemonade'[i0] + 'marlboro'[i1] + 'chersterfields'[i2] + 'tulips'[i3] + 'horses'[i4] + 'greek'[i5] + 'basketball'[i6] + 'cats'[i7] + 'hyacinth'[i8] + 'cheese'[i9] + 'cactuses'[i10] + 'orchids'[i11]}

i0..i11 is number of the hourse that have that object

Đối với task này thì giải tay cũng không phải là 1 phương án quá tệ, tuy nhiên, chúng ta có thể sử dụng Z3 để xử lý. Z3 là một công cụ được phát triển bởi Microsoft. chuyên dùng giải các định lý, hệ phương trình, các bài toán có nhiều điều kiện, hoàn toàn phù hợp với bài toán của chúng ta.

Source code của Old Riddle có tại: https://gist.github.com/vigov5/c4725b095adbb5ea6c92cf4f92440e4d Các bước để mô hình hoá bài toán:

  • Định nghĩa các đối tượng thành các biến.
  • Thêm điều kiện cho đối tượng (biến): giá trị sẽ >= 1 và <= 7, và là số nguyên
  • Các biến này sẽ đôi một khác nhau trong từng nhóm của mình: màu sắc, quốc tịch, đồ uống,...
  • Đưa các điều kiện thành các biểu thức điều kiện: VD:
# There are two houses between the lilies and the Tennis player on the left
s.add(Tennis==lilies-3)
# The Italian lives in the blue house.
s.add(Italian==blue)
# There is one house between the German and the Marlboro smoking person.
s.add(Or(German==Marlboro+2, German==Marlboro-2))
  • Tiếp tục như vậy cho các điều kiện còn lại.

Phần Write-ups cho Code Puzzles của vòng thi online Code War 2017 xin được kết thúc ở đây. Hẹn gặp lại các bạn trong các bài viết hướng dẫn cho phần Code Contest, hay xa hơn nữa là phần write-ups cho các bài thi trong vòng chung kết sẽ diễn ra trong ít ngày tới. Rất mong các bạn sẽ tiếp tục theo dõi và ủng hộ Code War 2017.