늘모자란, 개발 :: [wargame.kr] baskin game

늘모자란, 개발

There is no vulnerability.
Just find the rules.

nc wargame.kr 10034


배스킨 라아빈스 써리~원

배스킨 라빈스 게임은 어릴적 UN의 맴버중 하나가 나와서 필승법이 있다고 예능 인터뷰때 했다고 해서 사기게임이라고 뇌리에 깊게 박혀있다.
실제로, 1:1에서는 배스킨라빈스 게임은 실수하지 않는한 먼저 하는 사람이 무조건 이기는 방법이 있다.

1:1 베스킨 라빈스를 제시하라. 단 필승법을 아는지 대충 떠 봐야한다. (그건 알아서. 귀찮아) 
먼저 시작한다면, 처음에는 1, 2를 외쳐라. 그 다음에는 [4개-상대방이 말한 갯수]만큼씩 외쳐라.

두번째 시작한다면, 어떻게든 당신이 마지막으로 외치는것이 4의 배수보다 1개 많도록 29, 25, 21, 17, 13, 9, 5개가 남도록 한다.
즉 당신이 2, 6, 10, 14, 18, 22, 26으로 끝을 내게 외쳐야 한다.

그 다음에는 마찬가지로 [4-상대갯수]를 말하면 이긴다.
출처: http://yews.tistory.com/entry/베스킨-라빈스-31-11승리전략 [생각의 화장실]


예를 들면 이런식으로 많이 나와 있다. 이런건데, 요점은 반드시 내가 말해야 하는 수가 있다는 것이다.
이런 배경지식을 가지고 시작해보자

Welcome to STITCH's baskinrobbinsN game!
Your Purpose is to win Baskin Robbins31 game from AI. 

Rule)
As you already know, it seems like real Baskin Robbins31 game. But maximum number is not 31.

ex) N=101 , count 10
It situation, You can saying up to ten at a time of number. because count is 10.
if you speaking 101 faster than AI , you lose because N is 101

you will input smaller than count...
you will input the numbers in order.

----------------------------------
hint) 
N = 31, count = 3
input your name -> ab
Hi! ab
user first!
input your number -> 1 2 3
user say -> 1 2 3
computer say -> 4 5 6
input your number -> 7
user say -> 7
computer say -> 8 9 10
input your number -> 11 12 13
user say -> 11 12 13
computer say -> 14
input your number -> 15 16
user say -> 15 16
computer say -> 17 18
input your number -> 19 20 21
user say -> 19 20 21
computer say -> 22
input your number -> 23
user say -> 23
computer say -> 24 25 26
input your number -> 27 28
user say -> 27 28
computer say -> 29 30
AI win!
----------
------------------------

**** Timeout is 150sec... ****
**** Total 31 round... ****
Good luck~




N = 2166, count = 133

input your name -> Hi! fantazm
computer first!
computer say -> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
input your number -> 


문제가 예시와 함께 잔뜩나온다. 근데 기존에 알던 배스킨게임이 아니다. 최대 수와 부를 수 있는 수자가 랜덤으로 주어진다.
사실 이 글을 쓰기전에 살짝 해봤는데 컴퓨터를 이길 수가 없다. 생각을 다시 해보기로 했다.
읽고 나니 드는 생각이 있다.

나온 문제에서 보면, 내가 불러야될 숫자는 정해져있다. 컴퓨터 턴이 되어도 절대 끝낼 수 없는 수를 불러야한다. 그럼 컴퓨터는 2164까지밖에 부를수있고, 부르더라도 나는 2165를 말하고 승리한다.

http://lg-sl.net/product/scilab/sciencestorylist/ALMA/readSciencestoryList.mvc?sciencestoryListId=ALMA2018040003&subjectId=ALL

https://blog.naver.com/jong1003min/220348353765

https://namu.wiki/w/%EB%B0%B0%EC%8A%A4%ED%82%A8%EB%9D%BC%EB%B9%88%EC%8A%A4%2031(%EA%B2%8C%EC%9E%84)

참고한 링크들을 보자. 왜 하필이면 4일까? 4가 28을 부를 수 있는 배수의 마지노선이기 때문이다. 즉.. 워게임이지만 알고리즘에 가까운 코딩문제인것 같다.

핵심은, 나머지를 구한후 필승 수열을 구하는것이다.
r = (N - 1) % (count + 1)


그리고 목표 수치도 N이 아니라 N-1을 불러야는게 핵심이다. 때문에 내가 한개 더 많이 말해야한다. (베스킨라빈스게임에서도 3까지 부를 수 있지만 4로 맞춰 말하면 이긴다)
따라서 count + 1 을 해서, 필승 수열을 만든다

solns = []
while r < N:
    solns.append(r)
    r += (count + 1)


이제 여기에 등장하는 숫자까지 맞춰서 말하면 이긴다.
코드를 다 올리는건 좀 아닌것 같고 문제 풀면서 정말 X같았던 점들만 좀 적어본다.

1. 아무리해도 이길수가 없다. 컴퓨터가 먼저 시작을 하기 때문이다. 그리고 기가 막히게도 컴퓨터는 이 필승수열의 첫번째 수를 말한다.. 진짜 한참 삽질했는데
처음에 이름을 입력받는데... 이 입력을 짝수로 하면 내가 먼저 시작하고, 홀수로 하면 컴퓨터가 먼저 시작한다. 아........ 이건 처음 수열을 만들때 0으로 시작할 경우, 일부러 컴퓨터에게 턴을 주는식으로 구현하면 된다.
2. 소켓이 짤려서 온다. 숫자가 길어지고, 정확히 1460 자 이상이 되면 개행한다. computer say -> 로 파싱하고 있다가 의문의 payload wrong을 만날 수 있는데, 게임이 시작되었고, 개행이 된채 숫자만 던졌다면 해당 숫자를 마지막으로 다시 계산해야한다

요컨데 이런식으로 온다.

computer say -> 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 (개행)
(탭) 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652

별도의 처리가 없으면 이때 1632를 마지막 숫자로 읽어서 시간낭비를 하게 된다.
다음과 같이 정규식으로 처리해주면 된다.

 ext = re.findall(r"^\s+((?:\d+ )*\d+)$", line)
 if len(ext):
    response = re.findall(r"^\s+((?:\d+ )*\d+)$", line)[0].split(" ")
 


socket.recv 같이 너무 작으면 개행을 막 두번씩 하기도 하니, 애초에 넉넉하게 잡고 수신해주면 좋을 것 같다.
2018/11/07 09:09 2018/11/07 09:09