구글 어시스턴트(Google Assistant) 팀과 안드로이드 오토(Android Auto) 팀이 음성 명령으로 운전할 수 있는 새로운 프로토타입 자동차를 함께 만들고 있다. 초기 프로토타입은 자동차 시뮬레이터에 연결된 휴대폰을 통해 동작한다. 그런데 불행히도 초기 테스터 중 한 명이 휴대폰을 변기에 떨어뜨려 마이크가 고장 나는 바람에, 새 기능을 사용하기가 더 어려워졌다. 그래도 이 기회를 놓치고 싶지 않아서, 어떻게든 사용하기 위해 당신의 도움이 필요하다.

초기 프로토타입은 \mathbf{R}행 \mathbf{C}열의 단순한 격자 위에서 움직이며, 북(north), 남(south), 동(east), 서(west)라는 4가지 아주 단순한 음성 명령만 이해한다. 각 명령은 차가 해당 방향으로 정확히 한 칸 이동을 시도하게 만든다. 하지만 마이크 문제 때문에, 시스템은 북과 남을 서로 혼동할 수 있고, 또 별도로 동과 서도 서로 바꿔 들을 수 있다. 즉 north 명령을 내리면 북 또는 남으로 움직일 수 있고, south 명령을 내리면 남 또는 북으로 움직일 수 있으며, east와 west도 마찬가지로 둘 중 어느 쪽으로든 움직일 수 있다. 모든 경우에서 두 가지 이동 결과는 같은 확률(1/2)로 발생한다.

테스터는 각 칸이 벽(wall)이거나, 위험(hazard)이거나, 혹은 비어 있도록 격자를 구성했다. 어떤 명령이 차를 벽으로 이동시키거나 격자 밖으로 나가게 한다면, 대신 아무 일도 일어나지 않는다. 어떤 명령이 차를 위험 칸으로 이동시키면, 차는 그 이후로는 더 이상 어떤 명령도 실행할 수 없다.

테스터는 빈 칸들 중 일부를 '흥미로운 출발점(interesting starts)'으로, 다른 일부를 '흥미로운 도착점(interesting finishes)'으로 표시해 두었다. 어떤 흥미로운 출발점과 흥미로운 도착점의 쌍이 운전 가능(drivable)하다는 것은, 출발점에서 시작해 음성 명령으로 차를 운전하여, 도착점에서 끝날 확률이 최소 1 - 10^{-{10^{100}}}가 되도록 하는 전략이 존재한다는 뜻이다. 전략은 이전 명령들의 결과에 따라 어떤 명령을 내릴지, 그리고 언제 멈출지를 선택할 수 있다. 차가 위험 칸으로 들어가면 그 즉시 움직임을 멈추므로 도착점에 도달할 수 없다는 점에 유의하라. 테스터는 모든 운전 가능한 쌍의 목록을 구하는 데 당신의 도움이 필요하다.

#10465 upload 1 done 1 how_to_reg 1

헤이 구글, 운전해! timer 60s memory 2048MB

#10465

헤이 구글, 운전해! 60s 2048MB