물리학자 슈뢰딩거(Schrödinger)는 자신의 집에 침범한 고양이를 잡으려 한다. 이 고양이는 복도의 한 쪽에 있는 7개의 방 중 한 곳에 있는 것으로 생각된다. 그런데 고양이는 하루가 지날 때마다 원래의 방에서 왼쪽 또는 오른쪽 방으로 한 칸 이동한다고 한다. 슈뢰딩거는 다음과 같은 규칙으로 고양이를 잡아보려고 생각해보았다.
규칙 1 : 슈뢰딩거는 7개의 방 중 '하루에 한 곳의 문'만 열어 고양이의 위치를 알 수 있다.
규칙 2 : 문을 열었을 때 고양이가 없다면 문을 닫아야 한다.
규칙 3 : 본문에서 보았듯이 고양이는 하루가 지날 때마다 왼쪽 혹은 오른쪽 방으로 한 칸 이동한다. 예를 들어, 고양이가 2번 방에 있고, 그 날 발견되지 않았다면 다음 날 1번 방 혹은 3번 방에 있게 된다. 1번 방에 있었다면 다음 날 2번 방에 있게 된다.
고양이를 발견하기 위해 최소 몇 일이 걸리는지 구하시오.
이 퍼즐은 The guardian지에 소개된 퍼즐 중 하나입니다.
24개의 풀이가 있습니다.
문제가 아무래도 1일을 원하는거 같진 않아서 좀더 파고들었는데 고양이의 시작위치와 어디로 움직이든간에 무조건 찾을수 있는 횟수가 있습니다 고양이가 내가 문을 열 위치를 알고 피하려고 해도 잡힐수밖에 없는 횟수가 10회로 나왔습니다
일단 두가지 상황으로 나누었습니다 1. 시작할때 고양이와 나의 거리가 짝수다 2. 마찬가지로 고양이와의 거리가 홀수다 이게 중요한 이유가 고양이는 계속 1 혹은 -1의 변화를 주기때문에 내가 한칸씩 이동한다면 고양이와 나와의 거리는 항상 짝수 혹은 홀수 로 지정되기 때문이죠
만약 고양이와 나와의 거리가 짝수라면 내가 한칸씩 한쪽으로 계속 이동한다면 고양이도 1칸씩 이동하므로 0 혹은 짝수의 거리를 두게됩니다
2번방에서 시작하여 6번방까지 이동시 짝수거리에 있는 고양이는 벽에막혀 전부 잡히게되죠 그리고 남은 방들에 고양이가 있을 확률은 홀수방에만 존재합니다 1, 3, 5, 7번방이죠
1번상황의 고양이들은 종료된거죠
여기서 6번문을 다시한번 엽니다 그러면 고양이는 무조건 이동을 해야하므로 홀수방에있을 가능성은 0가되고 짝수거리의 방만에 존재할 확률이 남게되죠 6번은 내가 다시열었으니 2번과 4번만 남게됩니다 그럼 짝수거리에 있는 고양이를 몰살하는법은 위에 말했었죠 다시 왼쪽으로 한칸씩 이동하면 2번방에도착시 다른방에 고양이가 남아있을 확률은 0에 수렴하는게 아닌 정확히 0이 됩니다
밑에는 사실 다 잡는 모델을 돌려볼까 하다가 생각해보니 잡힐거같다 싶어서 하다만 코드인데
그냥 올려봅니다
class Room(object) :
search = 0
def __init__(self, initvalue = 0) :
self.r = dict()
self.count = 0
self.searchPct = 0
for i in range(1,8) :
self.r[i] = initvalue
def select_room(self, select) :
newRoom = Room(1)
newRoom.r[1] = self.r[2]/2
newRoom.r[2] = self.r[1] + self.r[3]/2
newRoom.r[3] = self.r[2]/2 + self.r[4]/2
newRoom.r[4] = self.r[3]/2 + self.r[5]/2
newRoom.r[5] = self.r[4]/2 + self.r[6]/2
newRoom.r[6] = self.r[5]/2 + self.r[7]
newRoom.r[7] = self.r[6]/2
newRoom.searchPct = self.searchPct + newRoom.r[select]
newRoom.r[select] = 0
newRoom.count = self.count + 1
return newRoom
seqData = list()
seqData.append(Room(1/7))
for i in range(0,20) :
bPass = False
while bPass == False :
select = int((input("오픈할 방 번호를 입력 (1~7)"))[0])
if select >= 1 and select <= 7 :
bPass = True
else :
bpass = False
seqData.append( seqData[i].select_room(select) )
print(" 회차 1번방 2번방 3번방 4번방 5번방 6번방 7번방 발견확률")
for iter in seqData :
print("{} 회차".format(iter.count)
+ " {0:6.3f} ".format(iter.r[1]*100)
+ " {0:6.3f} ".format(iter.r[2]*100)
+ " {0:6.3f} ".format(iter.r[3]*100)
+ " {0:6.3f} ".format(iter.r[4]*100)
+ " {0:6.3f} ".format(iter.r[5]*100)
+ " {0:6.3f} ".format(iter.r[6]*100)
+ " {0:6.3f} ".format(iter.r[7]*100) + " :8.3f}".format(iter.searchPct*100))
처음에는 4번방 고정으로 확인하는 전략으로 해봤고 더 줄일 수 없을까 하다가 1,2,3,4,5,6,7,6,5,4,3,2,1,2,3,4, .....와 같은 전략으로 시도해봤습니다.
근데 고양이가 안잡히고 루프가 무한으로 도는 문제가 발생하길래 이게 뭐지...하다가 김연태님의 풀이에 감동받고 왜 그런지 이해했습니다.
사람이 처음 열어보기 시작하는 방의 위치와 고양이가 처음 있던 방의 위치 사이의 거리가 홀수일경우에 위와 같은 전략으로는 절대 안잡히기 때문이더라구요 - 짝수일 경우는 오히려 금방 잡힙니다.
2, 3, 4, 5, 6, 6, 5, 4, 3, 2 순서대로 확인하도록 설정했고 최소 1번 최대 10번만에 잡히게 됩니다.
이하 코드는 김연태님의 전략을 바탕으로 비트연산을 이용해서 c로 작성해봤습니다.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
char start_point, random_move, choice;
unsigned char doors = 1;
int count[1000];
srand((unsigned)time(NULL)); // 현재 시간으로 랜덤함수를 초기화
for (int k = 0; k < 1000; k++) // 고양이를 찾는 과정을 1000번 반복
{
start_point = rand() % 7; // 시작위치 정해주기
printf("\n\n 처음위치 : %d번방\n\n", 7 - start_point); // 시작위치 정해주기
doors = 1; // 시작위치 정해주기
doors <<= start_point; // 시작위치 정해주기
for (int i = 0; i < 100; i++) // 방문을 최대 100번까지 열어보면서 고양이를 찾음
{
printf("\n");
printf("%d번째 시행 중\n", k + 1);
for (int j = 6; j >= 0; --j) // 현재 고양이의 위치를 출력
{ // 현재 고양이의 위치를 출력
printf("%d", (doors >> j) & 1); // 현재 고양이의 위치를 출력
} // 현재 고양이의 위치를 출력
printf("\n"); // 현재 고양이의 위치를 출력
choice = i % 10 + 1; // 확인할 방 번호를 정하는 전략
if (choice > 5) // 확인할 방 번호를 정하는 전략
choice = 11 - choice; // 확인할 방 번호를 정하는 전략
printf("%d번방을 열어볼까?\n", 7 - choice);
if ((doors >> choice) & 1) // 방문을 열어보는 행위
{
printf("%d번 방이네\n %d번 만에 찾았다.", 7 - choice, i + 1);
count[k] = i+1; // 시행횟수를 배열로 저장
break; // 찾으면 종료
}
else
printf("어라 없네.\n");
random_move = rand() % 2; // 랜덤무브가 1이면 왼쪽, 0이면 오른쪽으로 이동
if (doors == 1) // 7번방에 있을때는 왼쪽으로 이동
{
doors <<= 1;
printf("cat moved to left\n");
}
else if (doors == 64) // 1번방에 있을때는 오른쪽으로 이동
{
doors >>= 1;
printf("cat moved to right\n");
}
else // 랜덤무브가 1이면 왼쪽, 0이면 오른쪽으로 이동
{
if (random_move == 0)
doors >>= 1;
else
doors <<= 1;
printf("%s", random_move ? "cat moved to left\n" : "cat moved to right\n");
}
/* 여기까지 고양이가 이동하는 코드*/
for (int j = 6; j >= 0; --j) // 현재 고양이의 위치를 출력
{ // 현재 고양이의 위치를 출력
printf("%d", (doors >> j) & 1); // 현재 고양이의 위치를 출력
} // 현재 고양이의 위치를 출력
printf("\n"); // 현재 고양이의 위치를 출력
}
}
printf("\n\n\n");
float mean = 0.0;
for (int t = 0; t < 1000; t++)
{
printf("%d\n", count[t]); // 지금까지의 시행횟수들을 출력
mean += count[t]; // 시행횟수들을 모두 더해주어 평균 계산
}
printf("평균 횟수 : %f", mean / 1000.0);
return 0;
}
.
.
.
1000번째 시행 중 0010000 2번방을 열어볼까? 어라 없네. cat moved to right
0001000
1000번째 시행 중 0001000 2번방을 열어볼까? 어라 없네. cat moved to left 0010000
1000번째 시행 중 0010000 3번방을 열어볼까? 3번 방이네 7번 만에 찾았다.
.
.
.
9
6
1
9
6
10
5
10
1
.
.
.
1000번 시행해서 평균 5.5번 근처
이론대로 최대 10번만에 잡힙니다.
문제의 답은 1일 입니다. 운이 좋아 7개중 하나에 고양이가 들어있다면 최소 1일이 걸리기 때문이죠. 그러나 그럴 확률이 얼마나 될지 한번 알아보겠습니다.
본 문제에는 numpy를 사용하였습니다.
먼저 고양이가 이동하고 문을 여는 알고리즘을 만들어보겠습니다.
import numpy as np
Room=list(range(1,8))
move=[-1,1]
start=np.random.choice(Room)
day = 1
search = np.random.choice(Room)
#방의 각 끝칸에서는 이동할 수 있는 방향이 고정되는 것을 고려해줍니다.
while start != search:
if start==1:
start = start+1
elif start==7:
start = start-1
else:
start = start + np.random.choice(move)
day = day+1
이제 day를 출력해보면 알겠지만 숫자가 매번 바뀌므로 정확한 답을 구할 수 없습니다. 정답이 없는 걸까요? 정확한 값을 구할 수는 없지만 확률적으로는 근사한 값을 얻을 수 있습니다. 대표값으로 평균을 사용한다면, 대략적으로 고양이를 몇 일 만에 찾아내는지 알 수가 있죠.
평균을 사용하기 위해서는 여러 번의 시행이 필요합니다. 즉, 다차원의 슈뢰딩거가 고양이 찾기를 시도하는 알고리즘을 만들어 보겠습니다. if문 없이 numpy로 코딩했습니다.
Drst = 10000 #시행횟수(1만명의 슈뢰딩거가 고양이 찾기를 시도합니다)
start=np.random.choice(Room,Drst)
day = np.ones(Drst)
search = np.random.choice(Room,Drst)
while sum(start == search) != Drst:
start[start != search]=start[start != search]+np.random.choice(move,len(start[start != search]))
start[start == 0]=2
start[start == 8]=6
search[start != search] = np.random.choice(Room,len(start[start != search]))
day[start != search]=day[start != search]+1
np.mean(day)
이 평균값도 매번 달라지지만 1만번을 시행했으니 어느정도 유사하게 나올 겁니다. 저의 경우 3.157이 나왔습니다. 즉, 적어도 4일은 찾아야 평균적으로 찾을 수 있겠네요. 하지만 문제는 최소 몇 일인지 찾는 것이므로 np.min(day)로 최소값을 찾아보면 하루가 걸리는 걸 알 수 있습니다. 그런데 평균 3.15일이 걸리니까 4일 안밖으로 추정할 수 있을까요? 이것은 평균의 함정입니다.
import matplotlib.pyplot as plt
plt.figure(figsize=(20,10))
plt.hist(day,bins=10)
plt.show()
히스토그램을 그리게 되면 해당 분포가 정규분포가 아닌 것을 확인할 수 있습니다. 따라서, 앞서 말씀드린 대로 평균을 대표값으로 사용하기에는 문제가 있습니다. 많은 경우가 1에 치우쳐져 있죠. 즉, 의외로 빨리 찾을 가능성이 높다는 얘기입니다.
sum(day<=1)를 통해 하루만에 찾는 경우만 찾아봐도 30%가 넘는 것을 확인 할 수 있습니다. 그리고 sum(day<=2)를 통해 이틀이면 반이 넘는 확률로 고양이를 찾는 것을 알 수 있습니다. (이때, 확률은 사람마다 다르게 나올 수 있습니다.)
따라서, "우리는 이 문제는 최소 하루면 찾지만 이틀이면 50%이상의 확률로 고양이를 찾을 것이다." 라고 할 수 있겠네요.
그렇다면 여기서 매번 무작위로 문을 여는 것이 좋을까요? 아님 고정된 문을 매일 여는 것이 좋을까요? 고정된 문을 연다면 몇번째 문을 계속 여는 것이 좋을까요?
답은 매번 무작위로 문을 여는 것이 발견할 확률이 더 높습니다. (자세한 설명은 생략합니다. 실험해보시면 금방 알 수 있습니다.)
이번 문제가 재밌는 점은 슈뢰딩거의 고양이를 알고리즘으로 옮겨서 때로는 확률론적 접근이 필요하다는 것을 보여주는 것 같습니다. 따라서, 슈뢰딩거의 고양이를 찾아보시고 문제를 푸신다면 더 흥미로우시리라 생각됩니다.
julia
김연태 님 방법을 BFS 탐색하여 검증하였습니다
let # main
posCat = [[i] for i = 1:7]
sel = (2:6..., 6:-1:2...)
counter = 1
while !isempty(posCat)
pos = popfirst!(posCat)
pos[end] == sel[mod1(length(pos), 10)] ?
( println("고양이 이동경로: ", pos); counter = max(counter, length(pos)) ) :
pos[end] == 1 ? push!(posCat, vcat(pos, 2)) :
pos[end] == 7 ? push!(posCat, vcat(pos, 6)) :
push!(posCat, vcat(pos, pos[end]+1), vcat(pos, pos[end]-1))
end
println("\nMax: ", counter)
end # main end
고양이 이동경로: [2]
고양이 이동경로: [4, 3]
고양이 이동경로: [4, 5, 4]
고양이 이동경로: [6, 5, 4]
고양이 이동경로: [4, 5, 6, 5]
고양이 이동경로: [6, 7, 6, 5]
고양이 이동경로: [6, 5, 6, 5]
고양이 이동경로: [4, 5, 6, 7, 6]
고양이 이동경로: [6, 7, 6, 7, 6]
고양이 이동경로: [6, 5, 6, 7, 6]
...
고양이 이동경로: [5, 4, 3, 2, 3, 2, 1, 2, 1, 2]
고양이 이동경로: [5, 4, 3, 2, 1, 2, 3, 2, 1, 2]
고양이 이동경로: [5, 4, 3, 2, 1, 2, 1, 2, 1, 2]
고양이 이동경로: [7, 6, 7, 6, 5, 4, 3, 2, 1, 2]
고양이 이동경로: [7, 6, 5, 6, 5, 4, 3, 2, 1, 2]
고양이 이동경로: [7, 6, 5, 4, 5, 4, 3, 2, 1, 2]
고양이 이동경로: [7, 6, 5, 4, 3, 4, 3, 2, 1, 2]
고양이 이동경로: [7, 6, 5, 4, 3, 2, 3, 2, 1, 2]
고양이 이동경로: [7, 6, 5, 4, 3, 2, 1, 2, 1, 2]
Max: 10
#슈뢰딩거의 고양이
import random
c=random.randrange(1,8)#고양이의 초기 위치(1~7번방)
#고양이의 초기위치는 알 수 없다
day=1
print('초기위치: ',c)
while True:
#슈뢰딩거는 매일 무작위로 방을 선택한다고 가정(오늘은 n번방에 없어도 다음날에는 있을 수 있음)
u=random.randrange(1,8)#슈뢰딩거가 선택한 방
print('슈뢰딩거 ',u)
if c==u:
print(day,'일째에 고양이를 발견했습니다')
break
else:
ranc=random.randrange(1,3)
#왼쪽
if c==1:
c+=1
print('고양이 ',c)
#오른쪽
elif c==7:
c-=1
print('고양이 ',c)
#왼쪽
elif ranc==1:
c+=1
print('고양이 ',c)
#오른쪽
elif ranc==2:
c-=1
print('고양이 ',c)
day+=1
음... 최소는 운이 좋아서 1/7확률로 고양이를 바로 찾는 경우이고 운이 아주 안좋을 경우 어떤알고리즘을 쓰던지에 관계없이 고양이가 슈뢰딩거가 열 문을 알고 피하는것 처럼 움직인다면 잡기 어렵지 않을까요? (물론 영원히 그럴 확률은 0에 수렴하므로 언젠가는 잡히겠지만)
최소: 처음 문을 연 곳에 고양이가 있는 경우 (1/7의 확률) 최대: 무한히 못 잡음 -> 처음 문 연 곳 바로 옆에 고양이가 계속 다른 방향으로 이동을 유지하는 경우 1st: v * 0 0 0 0 0 2nd: 0 v * 0 0 0 0 3rd: 0 0 v * 0 0 0 4th: 0 0 0 v * 0 0 5th: 0 0 0 0 v * 0 6th: 0 0 0 0 0 v * 7th: 0 0 0 0 0 * v 8th: 0 0 0 0 * v 0 ...
최소: 처음 문을 연 곳에 고양이가 있는 경우 (1/7의 확률)
최대: 무한히 못 잡음 ->
처음 문 연 곳 바로 옆에 고양이가 계속 다른 방향으로 이동을 유지하는 경우
1st: v * 0 0 0 0 0
2nd: 0 v * 0 0 0 0
3rd: 0 0 v * 0 0 0
4th: 0 0 0 v * 0 0
5th: 0 0 0 0 v * 0
6th: 0 0 0 0 0 v *
7th: 0 0 0 0 0 * v
8th: 0 0 0 0 * v 0
...{.python}
최소: 처음 문을 연 곳에 고양이가 있는 경우 (1/7의 확률)
최대: 무한히 못 잡음 ->
처음 문 연 곳 바로 옆에 고양이가 계속 다른 방향으로 이동을 유지하는 경우
1st: v * 0 0 0 0 0
2nd: 0 v * 0 0 0 0
3rd: 0 0 v * 0 0 0
4th: 0 0 0 v * 0 0
5th: 0 0 0 0 v * 0
6th: 0 0 0 0 0 v *
7th: 0 0 0 0 0 * v
8th: 0 0 0 0 * v 0
...
최소: 처음 문을 연 곳에 고양이가 있는 경우 (1/7의 확률)
최대: 무한히 못 잡음 ->
처음 문 연 곳 바로 옆에 고양이가 계속 다른 방향으로 이동을 유지하는 경우
1st: v * 0 0 0 0 0
2nd: 0 v * 0 0 0 0
3rd: 0 0 v * 0 0 0
4th: 0 0 0 v * 0 0
5th: 0 0 0 0 v * 0
6th: 0 0 0 0 0 v *
7th: 0 0 0 0 0 * v
8th: 0 0 0 0 * v 0
...
어떤 분이 피드백을 주셔서 코드를 바꿔서 올립니다. 그분 말대로 예외처리를 잘못해서 고양이가 끝 방에 있을 때 움직이는게 문제가 생겼더군요. 확률을 토대로 만든 최적의 방법을 찾는 코드입니다. 확률을 토대로 만들어서 그런지 매번 최적의 방법이 바뀝니다 ㅋ. 그리고 최소 횟수는 확률의 신이 찾아주셔서 1회로 성공할때이고 최대 횟수는 무한입니다. 참고로 searchTime은 방을 찾는 최대 횟수이고 calcTime은 확률 계산의 횟수를 말하는 겁니다. 자바입니다.
public class SchrodingerCat {
static boolean[] room = new boolean[7];
static int where;
static final int searchTime = 100; // 최대 탐지 횟수는 100회라 가정하자
static int[] way = new int[searchTime]; //방을 여는 방법을 담는 배열이다.
static final int calcTime = 100000; //가중치를 계산 하는 횟수이다. 큰수의 법칙에 따라 이 수가 크면 클수록 결과치에 유사하게 될것으로 추정된다.
static int[] weight = new int[7]; // 가중치의 합을 담는 변수이다.
static int calcWeight = -1; // 가중치 계산시 필요한 변수이다.
public static void main(String[] args) {
SchrodingerCat object = new SchrodingerCat();
for(int i = 0; i < searchTime; i++) {
object.findWay();
}
object.printWay();
}
public SchrodingerCat() {
for(int i = 0; i < searchTime; i++) {
way[i] = -1;
}
}
public void resetCat() { // 고양이의 시작위치의 초기화를 담당하는 함수이다.
where = (int)(Math.random() * 7);
room [where] = true;
}
private void moveCat() {
room[where] = false;
while(true) { //고양이의 이동을 정의했다. 그리고 만약 배열을 초과하게 되면 오류가 발생하므로 try catch로 그 경우 다시 계산하도록 만들었다.
int moving = (int)(Math.random()*2);
try {
if (moving == 0) {
room[where + 1] = true;
where++;
}
else {
room[where - 1] = true;
where--;
}
break;
}
catch (Exception e) {
// System.out.println("debug:moveCatException");
}
}
}
private void resetWeightArray() {
for(int i = 0; i < 7; i++) {
weight[i] = 0;
}
}
private int calcWeightMethod() { //가중치가 얼마인지 계산해주는 함수
int i = 0;
while((way[i] != -1)&&(i < searchTime)) {
i++;
}
// System.out.println("debug:calcWeightMethod");
return i;
}
private void findWay() { //고양이를 찾기 시작하는 함수이다. 이때 2가지의 경우로 분류하였다. 찾아낸 경로에서 성공했을 때와 그렇지 않을때 2가지이다.
this.resetWeightArray();//가중치를 초기화 하는 함수
for (int num = 0; num < 7; num++) { // 몇번째 가중치에 저장할지 선택하고 반복하는 for문
for(int i = 0; i < calcTime; i++) {
this.resetCat();
boolean doSecondProcess = this.savedWay();
calcWeight = this.calcWeightMethod();
int secondWeight = 0;
if (doSecondProcess) {
secondWeight = this.newWay(num);
}
int sumWeight = calcWeight + secondWeight;
if(sumWeight == searchTime) { //만약 오버 했다면 가중치를 높인다.
sumWeight += searchTime / 2;
}
weight[num] += sumWeight;
}
}
this.judgeWay(); // 무엇이 제일 가중치가 작은지 판단하고 방법배열에 저장하는 함수
// System.out.println("debug:findway success");
}
private boolean savedWay() {
int i = 0;
boolean failInSavedWay = true;
try {
while(way[i] != -1) {
if(where == way[i]) {
// System.out.println("debug:savedWay success");
failInSavedWay = false;
break;
}
i++;
this.moveCat();
}
}
catch (Exception e) { }
return failInSavedWay; //만약 이미 찾은 경로에서 성공할경우에는 경로의 크기만큼을 가중치에 넣자 만약 calcTime동안 모두 성공하면 종료해야된다.
}
private int newWay(int num) {
int second = 1;
if (where == num) {
return second;
}
this.moveCat();
while(true) {
second++;
if(where == (int)(Math.random() * 7)) {
break;
}
this.moveCat();
}
// System.out.println("debug:newWay success");
return second;
}
private void judgeWay() {
int small = 0;
for(int i = 0; i < 7; i++) { //무엇이 제일 작은 가중치인지 비교하자
boolean smallist = (( weight[i]<= weight[0])&&(weight[i]<= weight[1])&&(weight[i]<= weight[2])&&(weight[i]<= weight[3])&&(weight[i]<= weight[4])&&(weight[i]<= weight[5])&&(weight[i]<= weight[6]));
if(smallist) {
small = i;
}
}
// System.out.println("debug:Wayarray saved");
way[calcWeight] = small; // 제일 작은 가중치를 가진 배열의 방법을 저장한다.
}
private void printWay() {
for(int i = 0; i < searchTime; i++) {
// if(way[i] == -1) { //-1로 하여 break를 한 이유는 100회 전에 방법이 끝났을 경우 끝으로 그만 출력하지 위해서 이다;
// break;
// }
System.out.printf("%d ",way[i] + 1); // 컴퓨터는 0-6번방으로 인식하지만 사람은 1-7번방으로 인식하므로 +1을 하였음
}
}
}
perl v5.20.2 built for MSWin32-X64-multi thread
탐색기법에 따라 최대 탐색시간이 어마어마하게 차이가 납니다.
나름대로 머리를 써서 최적의 탐색기법을 찾아내려고 했지만 해답과는 거리가 먼 방법이었던걸로...
코드를 잘못짰는지 최적의 탐색기법에서 10일이면 찾는다는 고양이를 최대 14일까지 걸려서 찾게되었습니다.
오히려 최대 탐색시간이 제일 짧은 것은 다른 탐색방법인데, 뭐가 잘못됐는지 아시는분은 수정부탁드립니다.
수정1. 다른 답안 추가. 평균값과 최대탐색시간 사이를 적당히 타협한 답안인듯.
#해쉬 정렬 참고 : https://perlmaven.com/how-to-sort-a-hash-in-perl
#퀴즈 해답 : https://www.theguardian.com/science/2017/jul/03/did-you-solve-it-are-you-smarter-than-a-cat
use strict; #착한 펄린이는 꼭 씁니다.
use warnings; #착한 펄린이는 꼭 씁니다.
my $cat=int(rand(7)+1);
#my @checka=(1);
#1번 문만 계속 여는 경우 100만번시도 평균탐색시간 24일 최대탐색시간 <500일
#my @checka=(4);
#4번 문만 계속 여는 경우 100만번시도 평균탐색시간 7.3일 최대탐색시간 <100일
#my @checka=(1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,6,6,6,5,5,5,4,4,4,3,3,3,2,2,2);
#초기 탐색기법 100만번시도 평균탐색시간 8.3일 최대탐색시간 <200일
#my @checka=(1,1,2,2,3,3,4,4,5,5,6,6,7,7,6,6,5,5,4,4,3,3,2,2);
#개선 탐색기법1 100만번시도 평균탐색시간 6.27일 최대탐색시간 <100일
#my @checka=(1,3,5,7,6,4,2);
#개선 탐색기법2 100만번시도 평균탐색시간 6.31일 최대탐색시간 <100일
#my @checka=(1,2,3,4,5,6,7,7,6,5,4,3,2,1);
#개선된 탐색기법3 100만번시도 평균탐색시간 6.57일 최대탐색시간 12일
my @checka=(2,3,4,5,6,6,5,4,3,2);
#최적의 탐색기법 100만번시도 평균탐색시간 5.49일 최대탐색시간 14일
#my @checka=(2,2,3,4,5,6,6);
#다른 답안 100만번시도 평균탐색시간 5.74일 최대탐색시간 12일
my $check;
my $day=1;
my %checkday;
for(my $i=0;$i<1000000;$i++)
{
$cat=int(rand(7)+1);
while($day<10000)
{
$check=$checka[$day%($#checka+1)];
if($check==$cat)
{
$checkday{"$day"}++;
$day=1;
last;
}
$day++;
$cat=&catmove($cat);
}
}
#표시용
foreach my $key (sort { $a <=> $b } keys %checkday)
{
printf "$key :\t$checkday{$key}\n";
}
my $valuesum=0;
my $average=0;
while( (my $key, my $value) = each %checkday )
{
$valuesum=$valuesum+$value;
$average=$average+($key*$value);
}
print "sum:$valuesum\n";
$average=$average/$valuesum;
print "ave:$average\n";
sub catmove
{
my $cat=shift;
if($cat==1)
{
return 2;
}
elsif($cat==7)
{
return 6;
}
else
{
if(int(rand(2))==1)
{
return $cat+1;
}
return $cat-1;
}
}
고양이의 위치를 모르는 이상 랜덤으로 하지 않으면 절대 풀 수 없는 문제이므로 랜덤을 이용했습니다.
그리고 단 한번으로는 평균치를 잘 알 수 없기 때문에 여러번 돌려서 나온 총합을 나눴습니다.
대략 6으로 나오네요
라고 생각을 했지만 김태연님의 풀이를 보고 반례를 찾아봤습니다. 절대 빠져나가지 못 하겠더군요.
이 코드는 단지 랜덤을 이용해서, 실제로 해보니까 대략 6으로 나오기도 했습니다
from random import randint
def schrodinger(cat = randint(1,7),day = 0):
if cat == randint(1,7):
return day
return schrodinger(cat+((-1,1)[randint(0,1) == 1 or cat == 1],-1)[cat == 7],day+1)
1000--------------------
6.072 0.030036449432373047
10000-------------------
6.129 0.27518296241760254
100000------------------
6.00382 2.2395598888397217
1000000-----------------
6.002009 21.9481143951416
아래는 김태연님의 풀이를 바탕으로 짜본 코드입니다.
from random import randint
def schrodinger():
cat = randint(1,7);day = 1
for x in [2,3,4,5,6,6,5,4,3,2]:
if x == cat:
return day
cat += ((-1,1)[randint(0,1) == 1 or cat == 1],-1)[cat == 7]
day += 1
최소는 하루인거 같네요
from random import randint, choice
def move_cat():
move_count = [-1, 1]
return choice(move_count)
def open_door():
return randint(1, 7)
cat = randint(1, 7)
door = None
count = 0
while cat != door:
if cat == 1:
cat += 1
elif cat == 7:
cat -= 1
else:
cat += move_cat()
door = open_door()
count += 1
print(count)
import random
room = [0,0,0,0,0,0,0]
cat = random.randint(0,6)
room[cat] = 1
def catmoving(room):
for x, y in list(enumerate(room)):
if y == 1:
room[x] = 0
moving = random.choice([-1,1])
if x + moving <= 6 and x + moving >= 0:
room[x+moving] = 1
else:
room[x-moving] =1
def findcat(room):
count = 0
while True:
number = int(input("Which room do you want to open? Choose between 1~7: ")) -1
if number > 6 or number < 0:
print("You have to choose between 1 and 7!")
else:
if room[number] == 0:
print("This room is empty!")
count += 1
catmoving(room)
else:
print("You found the cat!")
print("It took %s times fo find a cat." %count)
break
findcat(room)
매시행마다 고양이가 한 방에서 오른쪽 혹은 왼쪽으로 이동하고, 사용자가 입력한 방 번호에 따라 고양이 존재 여부를 출력하고 찾는데 걸린 시행횟수를 출력하는 프로그램입니다.
import random
cat = random.randint(1,7)
sch = random.randint(1,7)
day = 1
if cat == sch:
print('{} day'.format(day))
else:
while 1:
day += 1
while 1:
move = random.randint(-1,1)
if move != 0:
break
cat += move
if cat < 1:
cat += 2
elif cat > 7:
cat -= 2
sch = random.randint(1,7)
if sch == cat:
print('{} days'.format(day))
break
컨닝했습니다.
제가볼 때 이 문제는 생각보다 훨씬 더 어렵습니다. 어떤 방법을 제시하고
이 방법으로 열어 보면 k번 안에는 반드시 찾을 수 있다.
k보다 작은 횟수로 열어서 반드시 찾을 수 있는 방법은 존재하지 않는다.
를 증명해야 하는데 2번은 아무도 안 하셨습니다. 저도 못할 거 같습니다만^^;
시뮬레이션:
from random import randint, choice
def find_cat():
cat = randint(1, 7)
open_seq = [2, 3, 4, 5, 6, 6, 5, 4, 3, 2]
dirs = [None, [1], [-1, 1], [-1, 1], [-1, 1], [-1, 1], [-1, 1], [-1]]
#print(' 1 2 3 4 5 6 7 ')
for i, room_no in enumerate(open_seq):
#print(' _ ' * (cat - 1) + ' c ' + ' _ ' * (7 - cat), 'open', room_no)
if cat == room_no:
return i + 1
else:
cat += choice(dirs[cat])
print('failed with', open_seq)
exit()
#print(find_cat())
print(max(find_cat() for _ in range(10000)))
고양이가 10번 움직이는 모든 경우를 검증:
def find_cat(open_seq, cat_seq):
for open_no in open_seq:
if open_no == cat_seq.pop(0):
return True
return False
def cat_seq_lst(n, seq):
dirs = [None, [1], [-1, 1], [-1, 1], [-1, 1], [-1, 1], [-1, 1], [-1]]
if not n:
return [seq]
res = []
for dir in dirs[seq[-1]]:
res += cat_seq_lst(n - 1, seq + [seq[-1] + dir])
return res
open_seq = [2, 3, 4, 5, 6, 6, 5, 4, 3, 2]
for start in range(1, 8):
for cat_seq in cat_seq_lst(len(open_seq), [start]):
if not find_cat(open_seq, cat_seq):
print('invalid open sequence:', open_seq)
print('valid open sequence:', open_seq)
아직 실력이 부족해서 슈뢰딩거가 랜덤으로 방을 열경우를 생각하고 알고리즘을 구현해보았습니다. 몇퍼센트 확률로 몇일째 고양이를 찾는지를 구현해 보았습니다.
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.Set;
//물리학자 슈뢰딩거(Schrödinger)는 자신의 집에 침범한 고양이를 잡으려 한다. 이 고양이는 복도의 한 쪽에 있는 7개의 방 중 한 곳에 있는 것으로 생각된다. 그런데 고양이는 하루가 지날 때마다 원래의 방에서 왼쪽 또는 오른쪽 방으로 한 칸 이동한다고 한다. 슈뢰딩거는 다음과 같은 규칙으로 고양이를 잡아보려고 생각해보았다.
//규칙 1 : 슈뢰딩거는 7개의 방 중 '하루에 한 곳의 문'만 열어 고양이의 위치를 알 수 있다.
//규칙 2 : 문을 열었을 때 고양이가 없다면 문을 닫아야 한다.
//규칙 3 : 본문에서 보았듯이 고양이는 하루가 지날 때마다 왼쪽 혹은 오른쪽 방으로 한 칸 이동한다. 예를 들어, 고양이가 2번 방에 있고, 그 날 발견되지 않았다면 다음 날 1번 방 혹은 3번 방에 있게 된다. 1번 방에 있었다면 다음 날 2번 방에 있게 된다.
//고양이를 발견하기 위해 최소 몇 일이 걸리는지 구하시오.
//이 퍼즐은 The guardian지에 소개된 퍼즐 중 하나입니다.
public class ex01 {
public static void main(String[] args) {
int total = 100000000;// 총 테스트 횟수
int[] room = new int[7];// 고양이가 있을 방의 개수
int day = 1;// 몇일만에 고양이를 찾았는지 카운트
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
Random random = new Random();
int catIndex = random.nextInt(7);// 처음 고양이가 있을 방
room[catIndex] = 1;// 고양이가 있으면 1 아니면 0
for (int i = 0; i < total; i++) {// 횟수의 확률을 구하기 위해서 사용
while (true) {
int manIndex = random.nextInt(7);// 사람이 처음 방을 고르는 수
if (room[manIndex] == 1) {
Count(map, day);
day = 1;
break;
} else {
day++;
MoveCat(room, catIndex);
}
}
}
Print(map, total);
}
public static void Count(Map<Integer, Integer> map, int day) {
if (map.get(day) != null) {
map.put(day, map.get(day) + 1);
} else {
map.put(day, 1);
}
}
public static void Print(Map<Integer, Integer> map, int total) {
Set<Integer> ketSet = map.keySet();
Iterator<Integer> iterator = ketSet.iterator();
while (iterator.hasNext()) {
int key = iterator.next();
int value = map.get(key);
System.out.println("day : " + key + " count : " + value + " " + (double) value / total * 100 + "%");
}
}
public static int[] MoveCat(int[] room, int index) {
switch (index) {
case 0:
room[index] = 0;
room[index + 1] = 1;
break;
case 1:
case 2:
case 3:
case 4:
case 5:
Random random = new Random();
int nextMove = random.nextInt(2); // 0이면 -1칸이동 1이면 +1칸이동
if (nextMove == 0) {// 0이므로 -1칸이동
room[index] = 0;
room[index - 1] = 1;
} else {// 1이므로 +1칸이동
room[index] = 0;
room[index + 1] = 1;
}
case 6:
room[index] = 0;
room[index - 1] = 1;
break;
}
return room;
}
}
제 나름의 해석입니다. 일단 이 문제를 풀기 위해서는 한칸씩 방을 이동한다면, 고양이가 슈뢰딩거를 피하는 방법은 단 하나입니다. 슈뢰딩거 쪽으로 이동해서 슈뢰딩거랑 교차되는 방법 뿐입니다. 교차란 무엇일까요? 슈뢰딩거가 x날에 n번 방을 뒤질때 고양이가 n+1에 있고, x+1 날에 슈뢰딩거는 n+1을 뒤지고 고양이는 n으로 이동하는 거죠. 만약, 반대로 고양이가 슈뢰딩거에게 멀어지는 것을 선택한다면, 방은 무한하지 않기 때문에 끝에서 결국 잡히게 됩니다. 교차만이 슈뢰딩거를 피할 유일한 방법입니다.
그런데 교차가 될라면, n+1 방에 , 즉 슈뢰딩거가 뒤지는 방에 1 떨어진 곳에 위치해야 하는 것입니다. 현재 슈뢰딩거는 1칸씩 이동 중이고, 고양이 또한 한칸씩 이동하므로, 짝홀을 바꿀 방법이 없습니다. 홀수 만큼 떨어진 고양이만이 교차를 사용할 수 있습니다. 만약에 짝수라면 반드시 잡히게 됩니다. 이게 이 문제의 가장 핵심적 풀이 요소입니다.
간단한 예시를 들죠 당신이 2,3,4 순서대로 방을 뒤질 것이고, 당신이 2를 뒤질때 고양이가 4번에 있다고 가정해 보져. 4번에 있는 고양이는 안 잡힐라면 이동 선택지는 오로지 5번으로 이동하는 것 밖에 없습니다. 고양이가 3번으로 이동하면 다음 날 3번을 뒤진 슈뢰딩거에게 발각됩니다. 즉 고양이는 갈 수 있는 방향이 한 쪽으로 고정됩니다. 방이 무한하다면 무한이 도망갈 수 있겠지만, 방은 무한하지 않고 결국 고양이는 가만히 있을 수가 없으므로 마지막 방에서 거꾸로 되돌아와 잡히는 수 밖에 없습니다. 이는 4번이 아니라 6번에 있어도 마찬가지입니다. 시간을 늦출 뿐이죠.
그렇다면 교차로 회피한 홀수 거리 고양이들은 어떻게 잡을까요? 슈뢰딩거가 짝수 번째의 고양이를 모두 잡은 이후에는 무조건 홀수 거리에만 존재할 수 있습니다. 그래야 교차가 가능하니까요. 그렇지 않다면 벌써 잡혓겟죠. 여기서 트릭은 고양이가 반드시 움직여야 한다는 것입니다. 가만히있는건 불가능합니다. 슈뢰딩거는 원하는 위치를 계속 뒤질 수 있고요. 따라서 슈뢰딩거가 최대 방의 바로 전 방에서 한번 더 뒤진다면 최대 반벙의 고양이는 최대 방의 바로 전으로 이동하게 되어서 잡히고, 남은 슈뢰딩거랑 홀수 거리가 떨어진 고양이들은 +-1로 인해서 짝수 거리로 바뀌게 된다는 것이죠
이제 처음 짝수 사냥의 역으로 돌아갈 때가 되었습니다. 짝수 거리의 고양이들은 피할 방법이 없습니다. 교차가 불가능하니까요. 설사 반대쪽으로 도망간다 할 지라도, 결국은 방의 끝에서 돌아와야 하고, 잡히게 되어 있습니다.
이를 수식화 하면 다음과 같습니다. (시작방+1) 부터 (끝방-1) 까지 뒤지고,(끝방-1)에서 (시작방+1) 까지 뒤지면 되지요. 시작방과 끝빵이 빠지므로 뒤지는 숫자는 (총 방의 수-2) 가 되고, 이렇게 두번 뒤지므로 (총 방의 수-2)2 가 최대 뒤지는 수의 양입니다. 이 문제에서는 방이 7 개 있으므로, (7-2)2=10 즉 10개가 뒤지는 수가 됩니다. 방 뒤지는 순서는 2,3,4,5,6,6,5,4,3,2 가 되겠네요.
이제 파이썬 코드로 이 가설을 입증하는 일만 남았습니다. max_room으로 최대 방의 개수를 정하고 max_try로 여러번 시도해 봅니다. 파이썬 코드로 수색할 지역을 max_room 을 기반으로 리스트에 추가해 줍시다. 만약 한번이라도 이 리스트를 전부 뒤졌는데 고양이를 못 찾았다면 오류를 출력하도록 코딩합니다. random으로 임의의 방에 배정된 고양이는 random으로 움직이며, 구석의 방(1번방과 7번방) 에 있는 경우를 제외학곤 -1,0,1중 하나를 출력하는 랜덤함수에서 0은 랜덤 재시도, -1은 왼쪽 이동, 1은 오른쪽 이동으로 설정해줍시다.
실행 결과로는 아무것도 나오지 않습니다. 한번도 실패하지 않앗다는 뜻이죠. 이제 max_try를 여러번 해보거나 max_room을 조정해서 여러 시도를 해 봅시다. max_try를 아무리 늘려도 실패하는 일은 없음이 확인됩니다.
밑은 실제로 그렇게 작성한 python 코드입니다. 혹시 몰라서 디버깅을 위해 고양이의 이전 위치와 수색한 위치는 모두 기억하며, 실패했을 경우 어떻게 이동햇는지도 출력하도록 되어 있습니다. 물론 쓸 일은 없었습니다.
import random
max_room=10
max_try=1000000
catLocation=0
search_try=0
searchList=[]
doubleSearch=max_room-1
for i in range(2,doubleSearch):
searchList.append(str(i))
searchList.append(str(doubleSearch))
for j in range(doubleSearch,1,-1):
searchList.append(str(j))
max_search=len(searchList)
print("수색 지점 : ",searchList)
print("최대 수색 횟수 :",max_search)
for i in range(max_try):
catLocation=random.randrange(1,max_room)
findtry=0
catLocationList=[]
recentSearchList=[]
while True:
while True:
catDirection=random.randrange(-1,1)
if catLocation==1:
catLocation+=1
break
elif catLocation==max_room:
catLocation-=1
break
elif catDirection==1:
catLocation+=1
break
elif catDirection==-1:
catLocation-=1
break
elif catDirection==-0:
continue
else:
print("오류 발생")
catLocationList.append(str(catLocation))
if findtry<=max_search:
if searchList[findtry]==str(catLocation):
# print("수색 성공")
findtry=0
break
else:
recentSearchList.append(searchList[findtry])
findtry+=1
else:
print("수색 실패")
print("고양이 위치 목록 : ",catLocationList)
print("수색 위치 목록 : " ,recentSearchList)
findtry=0
break
# 슈뢰딩거의 고양이 찾기
import random
def cat():
num = input('고양이는 몇 번 방에 있을까요? (1 ~ 7): ')
cat_num = random.randint(1, 2) # 처음의 고양이의 위치
print(cat_num)
while int(num) != cat_num: # 맞추지 못하면 계속 반복
if int(num) == cat_num:
break
else: # 못 맞췄으니 고양이 위치 변경
if cat_num == 1:
cat_num += 1
elif cat_num == 7:
cat_num -= 1
else:
change = random.randint(1, 2)
if change == 1:
cat_num += 1
else:
cat_num -= 1
print(cat_num)
num = input('고양이는 몇 번 방에 있을까요? (1 ~ 7): ')
print('축하드립니다. 찾았습니다!')
cat()
public class Schrodinger {
private static final int ROOM_CNT = 7;
private static boolean[] rooms = new boolean[ROOM_CNT];
private static int cat_position = 0;
public Schrodinger() {
cat_position = new Random().nextInt(7);
System.out.println();
for (int i = 0; i < ROOM_CNT; i++) {
rooms[i] = (i == cat_position) ? true : false;
}
}
public static void main(String[] args) {
Schrodinger schrodinger = new Schrodinger();
schrodinger.findCat();
}
private void findCat() {
int flag = 0, count = 0, idx = cat_position, select = 0;
boolean find = false;
while(!find) {
count++;
select = new Random().nextInt(7);
find = (select == idx) ? true : false;
flag = new Random().nextInt(2);
if(flag % 2 == 0) idx = (idx == ROOM_CNT-1) ? idx - 1 : idx + 1;
else idx = (idx == 0) ? idx + 1 : idx -1;
rooms[cat_position] = false;
rooms[idx] = true;
cat_position = idx;
System.out.print("\n'" + count + "번째 날' 고양이 위치 :");
for (int i = 0; i < rooms.length; i++) {
System.out.print("[" + (rooms[i] ? "야옹" : "-") + "]");
}
}
System.out.println("\n\n< 고양이 찾기 >"
+ "\n - 방의 개수\t: " + ROOM_CNT + " 개"
+ "\n - 고양이 위치\t: " + (cat_position+1) + " 번방"
+ "\n - 찾은 기간\t: " + count + " 일");
}
}
김연태님 풀이 참고했습니다
import random
num = 100000
num_count = [0] * 10
for i in range(num):
cat_position = random.randrange(1,8)
my_guess = [2,3,4,5,6,6,5,4,3,2]
cur = 0
while True:
guessing = my_guess[cur % 10]
cur += 1
if guessing == cat_position:
print(cur)
num_count[cur-1] += 1
break
cat_move = random.randrange(1,3)
if cat_position == 1:
cat_position += 1
elif cat_position == 7:
cat_position -= 1
elif cat_move == 1:
cat_position += 1
else :
cat_position -= 1
print(num_count)
재미삼아 만들어본 고양이 잡기 게임입니다 생각해보니 궂이 room과 room_show를 둘다 만들 필요는 없었네요 ㅎㅎ;;
from random import randint
import os
room = [ 0 for i in range(7)]
room_show = ['*' for i in range(7)]
cat = randint(1, 7)
room[cat - 1] = 1
os.system('cls')
print(room_show)
##열어보자
while True:
open = int(input('몇 번째 문을 여시겠습니까?'))
if room[open - 1] == 1:
room_show = ['*' for i in range(7)]
room_show[open - 1] = '&'
os.system('cls')
print(room_show)
print("야옹!")
break
## 고양이 move
decide = randint(1,2)
if cat == 1:
cat = 2
elif cat == 7:
cat = 6
elif decide == 1:
cat = cat - 1
elif decide == 2:
cat = cat + 1
##이동 후 고양이
room = [ 0 for i in range(7)]
room[cat -1] = 1
room_show = ['*' for i in range(7)]
room_show[open - 1] = 0
os.system('cls')
print(room_show)
김연태 님의 전략을 따라 풀었습니다. 2 -> 3 -> 4 -> 5 -> 6 -> 6 -> 5 -> 4 -> 3 -> 2로 이동하는 것을 통해 아무리 오래 걸려도 10일이면 고양이를 잡을 수 있습니다. 다음은 소스 코드입니다.
import random
cat = random.randint(1, 7)
human = 2
i = 1
cnt = 0
while cat != human:
cat += (1 if round(random.random()) == 0 else -1)
if cat == 0: cat = 2
if cat == 8: cat = 6
human = int(-abs(i - 5.5) + 6.5)
print(f'{i}일차: 고양이는 {cat}번 방에 있고, 사람은 {human}번 방의 문을 열었다.')
if cat != human: i += 1
cnt += 1
if not cnt: print('1일차: 고양이는 2번 방에 있고, 사람은 2번 방의 문을 열었다.')
print(f'{i}일차에 고양이와 사람 모두 {cat}번 방에 있었다.')
print('고양이를 잡았다!')
다음은 실행 결과입니다. 난수를 사용하므로 항상 이 결과가 나오는 것은 아닙니다.
1일차: 고양이는 5번 방에 있고, 사람은 2번 방의 문을 열었다.
2일차: 고양이는 6번 방에 있고, 사람은 3번 방의 문을 열었다.
3일차: 고양이는 5번 방에 있고, 사람은 4번 방의 문을 열었다.
4일차: 고양이는 6번 방에 있고, 사람은 5번 방의 문을 열었다.
5일차: 고양이는 5번 방에 있고, 사람은 6번 방의 문을 열었다.
6일차: 고양이는 4번 방에 있고, 사람은 6번 방의 문을 열었다.
7일차: 고양이는 5번 방에 있고, 사람은 5번 방의 문을 열었다.
7일차에 고양이와 사람 모두 5번 방에 있었다.
고양이를 잡았다!