2021 Google Hashcode 예선 후기

Google HashCode

구글 해시코드는 팀 프로그래밍 대회로 주로 휴리스틱 문제가 나온다. 매년 참가자수가 늘고 있고 올해는 9000개 이상의 팀이 1번 이상 제출을 하였고 전세계 170개 이상의 나라가 참여했다.

약 30~50팀(150명 제한)이 월드 파이널에 진출하게 되고 원래는 더블린에서 치뤘지만 작년부터는 코로나로 인해 온라인으로 치룬다.

작년에는 hojoon0205, queued_q, chunghan과 같이 참여 했는데 올해는 Juno와 둘이서 참여했다.

타임라인

문제

3시간 45분동안 대회가 진행되었다.

문제는 해시코드 사이트에서 볼 수 있다. 문제를 요약하면 신호등의 초록불 스케줄을 잘 관리해서 자동차가 잘 지나다닐수 있게 하라는 것이다. 도로가 연결된 상황과 길이가 주어지고 차량들의 이동경로가 있다. 교차로에서는 여러 도로중 하나만 불을 켤 수 있다. 점수는 도착 보너스 점수와 도착했을때 시간 점수의 합이다.

기본

가장 간단히 떠올릴 수 있는 방법은 실제 도로 교통망처럼 계속 번갈아가면서 신호등을 켜주는 것이다. 문제 설정상 1초에 1차량씩 지나갈수 있으므로 1초마다 켜주는 코드를 작성했다.

이렇게 7,885,741점을 얻을 수 있다.

여기서 A번을 손으로 풀어준다면 1001점을 더 얻어서 7,886,742점을 얻을 수 있는데 이 근방의 점수가 매우 많았다.

개선

이후에 생각을 하면서 여러가지 개선을 했다.

먼저 하나도 안쓰이는 도로는 켜주지 않는코드를 작성하면 1,039,874점의 개선이 이루어진다. (8,926,616)

그 다음으론 많이 사용하는 도로에 시간을 좀 더 많이 할당하는 코드를 작성했다. 이 때 어느 정도 많이 줄지에 대해서는 여러번 제출하면서 최적의 값을 찾아 나갔다. 이 방법으로 9백 30만에서 40만점까지 올렸고 당시 한국 3위의 기록이었다.

그러나 이 이후로 좋은 최적화 방법을 찾지 못하였다.

신호등이 켜지는 순서를 최적화해야하는 것은 생각했지만 마땅히 떠오르는 방법이 없었다. 정렬하거나 거꾸로 켜기 혹은 랜덤등을 활용해서 대회가 끝날때까지 약 20만점을 올렸다.

결과 및 후기

960만 447점을 얻었다.

퍼블릭 스코어보드에서 자세한 결과를 볼 수 있다. 우리팀은 ‘asdf’ 팀으로 세계 121위를 달성하여 월드 파이널에 진출하지는 못했다. 작년에는 세계 300등대였는데 그래도 나름 발전했다. 한국 순위도 작년엔 11위 올해는 8위다.

작년엔 한국에서 한 팀만 세계 대회에 나갔는데 올해는 세 팀이나 세계 대회에 나갈 것 같다. 작년에 세계 대회를 나간 팀의 멤버가 쪼개지고 추가하면서 더 강해진것 같다. 그리고 재작년에 세계 대회 나간 팀에 멤버 추가를 한 팀이 나간다.

신호등이 켜지는 순서를 최적화하는 걸 좀 더 일찍 고민하고 거기서 점수를 더 올렸으면 하는 아쉬움이 있다.

3/11에 Reply Challenge라는 비슷한 유형의 대회를 dtc03012님과 같이 나갈것 같은데 여기서 좋은 결과를 보여주는것이 목표다.