AoCはいいぞ
クリスマスも近づいてきていますが、皆様いかがお過ごしでしょうか。
主に技術系の界隈では、「アドベントカレンダー」として、12月のはじめからクリスマスまで、毎日記事が投稿されるといった風習1がありますが、海外で有名な、Advent of Codeと呼ばれるイベントをご存知でしょうか。
Advent of Code (以下AoC)は、2015年から毎年開催されている、12月1日から25日まで、毎日プログラミングの問題が出題され、それを解いていくというイベントです。必ず1から順番に解く必要がなく、自分の好きなタイミングで、好きな問題にチャレンジすることができます (過去の年の問題にも取り組めます！)
上のページにアクセスして、GitHubやGoogleでサインインすることで、問題に取り組むことができます。
日本ではあまり有名ではありませんが、海外ではSNSなどで毎年話題になっていて、私も去年から、知り合いの海外のプログラマに勧められて始めました。今ではすっかり夢中になっているので、今回はAoCについて、実際に問題を解いたりしながら紹介できればと思います。
(問題をクリアしていくと、AAがどんどんきれいになっていきます...！)
どんな問題を解くの?
この説明を聞いて、AtCoderに代表されるような、競技プログラミングをイメージされた方も多いかと思いますが、そのようなプログラミングコンテストとは少し違うと思っています。
問題の解き方としては、入力のテキストが与えられるので、それを問題に従って答えを計算するプログラムを書き、その答えを入力することで正誤判定をするという感じです。
ローカルでコードを書いて答えを得るので、どのプログラミング言語でも問題を解けるという利点があります。
問題ページのスクリーンショット
また他にも面白い点として、一日に問題が2問出されることがあると思います。1問目を解くと、応用問題として、1問目で書いたコードを少し改変させて、より難しい問題に取り組む必要があります。(記事の後半で実際に解いた記録を書きます！)
そのため、1問目の実装の進め方で、2問目のコードの改変が楽になったり地獄になったりするのが面白いです。
その他の魅力
その他の魅力として、以下のようなものが挙げられます。
海外での人気が非常に高い
SNSでは、この時期になると AoCの話題をよく見るようになり、日夜問題の解法の共有や、問題に関するネタ画像(meme)が上げられています。そこで他の人のコードを見ると、「こんなやり方もあったのか」と勉強になります。
複雑なアルゴリズム知識を必要としない
計算量に気をつけないと一生終わらない問題などもありますが、基本的にプログラミングコンテストと異なり、実行時間の制限などがないので、私のようなアルゴリズム初心者でも安心して取り組むことができます。個人的にはAoCはどちらかというと、プログラミングの問題というより、パズルに近いと感じています。
25言語チャレンジ
個人的なことですが、自分は今年のAoCは、毎日違うプログラミング言語で解いています(後日GitHubでソースは公開するつもりです！) こうやって問題が言語に依存しないこともいいところですよね。
現在一日目から、 Go → Ruby → PHP → C++ → JavaScript → Common Lisp → Java → Vim Script → Python と進めていて、そろそろ扱える言語が足りなくなってきたので、新しい言語を勉強しようかなと思っています...
実際に解いてみるよ(Day1編 Golang)
では実際に問題を解説しながら解いてみたいと思います。問題のネタバレがあるので、自力で解きたい人は以下注意です
今回は、記事として書きやすい問題として、Day1 とDay7を解いた記録を取り上げます。
1問目
問題文は長いですが、要するに以下のような感じです。
1abc2
pqr3stu8vwx
a1bbad
このような各行に対して、一番左と右にある数をくっつけた数字を作り、数字が一つしかない場合はその数字で2桁の数字を作ります。つまり上の入力は下のようになります。
12
38
11 ← 行に1しかないため
そしてこの数字の和を求めます。数字以外の文字を消して、左端と右端の数字をとってあげればよさそうですね
// アルファベットを削除
func removeNonNumeric(input string) string {
re := regexp.MustCompile("[^0-9]+")
return re.ReplaceAllString(input, "")
}
func main() {
//省略
for scanner.Scan() {
// 各行ごとに処理
line := scanner.Text()
numbers := removeNonNumeric(line)
if len(numbers) == 0 {
continue
// 数字が一個しか見つからなかったら
} else if len(numbers) == 1 {
i, err := strconv.Atoi(numbers + numbers)
if err != nil {
panic(err)
}
res += i
} else {
first := numbers[0:1]
last := numbers[len(numbers)-1:]
i, err := strconv.Atoi(first + last)
if err != nil {
panic(err)
}
res += i
}
}
fmt.Println(res)
}
これで1問目はOKです。これを解くことで、2問目の内容が表示されます。
2問目
2問目はどうやら、行中の、"one", "two"といった単語も、数字に変換してから同様の処理をしてあげる必要があるようですね。
「なるほど、じゃあ"one"などの単語を全部 replaceすれば簡単じゃないか」と思ってコードを書いたところ、不正解になってしまいました。どうすればいいでしょう。
とサンプルの入力を試していると、あることに気が付きました。"twone" のような文字列が与えられたときに、"two"と"one"があるため、"21" である必要があるのに、"tw1" となってしまいます。どうやら1から順番に置換をしていて、単語の重なりを気にしていなかったのが原因のようです。
これを何とかするためには、置換するときに、両隣の置換に影響を与えないようにしたい、ということを考えると、上のコードで、各行に以下の前処理をはさめば良さそうですね。
func replaceNumberToDigit(input string) string {
res := input
// 置換パターン
dicts := map[string]string{
"one": "o1e",
"two": "t2o",
"three": "t3e",
"four": "4",
"five": "f5e",
"six": "s6",
"seven": "s7n",
"eight": "e8t",
"nine": "n9e",
}
// GoでMapのKeyどうやって取るんだっけ...
numbers := []string{"one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}
for _, number := range numbers {
res = strings.Replace(res, number, dicts[number], -1)
}
return res
}
これでDay1は完了しました。めでたしめでたし。
実際に解いてみるよ(Day7編 Java)
1問目
(掛け金などの入力もありますが、本質的ではないので省略します) 要するにポーカーの持ち札が以下のように与えられたときに、役の強さ(役が同じ場合は、先頭のカードから強さを比較して決める)を比べて、ソートしてあげる必要があります。また、実際のポーカーと異なり、ファイブカードという役もあります。
(注意: T → 10)
32T3K
T55J5
KK677
KTJJT
QQQJA
1問目に関しては、以下のような二重配列を作っておいて、各配列ごとにソートして、最後に一重配列にまとめていきました。
[[ファイブカードの役一覧], [フォーカードの役一覧], ..... [役無し手札一覧]]
同じ役同士の強さの比較は簡単ですが、役の判定が難しそうなところです。役判定は強い役が優先される(例えば、フルハウスの手札がスリーカード扱いされてはいけない)ことと、役の構成要素は、2枚以上の同じ札であるということを考えると、以下のように書けます。
//略
public int getRank(String hand){
int[] counts = new int[15];
int pairs = 0; // ペアの数
int threes = 0; // 3枚組の数
int fours = 0; // 4枚組の数
int fives = 0; // 5枚組の数
// カードの種類ごとに分類、カウント
for (char c : hand.toCharArray()) {
counts[getCardValue(c, false)]++;
}
// 分類したものに対して、ペアや3枚組の数を数える
for (int count : counts) {
if (count == 2) pairs++;
if (count == 3) threes++;
if (count == 4) fours++;
if (count == 5) fives++;
}
if (fives == 1) return 7; // ファイブカード
if (fours == 1) return 6; // フォーカード
if (threes == 1 && pairs == 1) return 5; // フルハウス
if (threes == 1) return 4; // スリーカード
if (pairs == 2) return 3; // ツーペア
if (pairs == 1) return 2; // ワンペア
return 1; // ノーペア
}
//略
役の構成要素である、ペアや3枚組の数を数えて、強い順に条件判定すればよさそうですね。
2問目
2問目が少し難しかったです。「"J" をジャックのかわりに、カード自体は最弱だが、どんなカードにもなれるワイルドカードとして扱う」というルールが追加されます。(同じ役同士の強さ比較では、どんなカードに変身したとしてもそのまま"J"として扱われます)
カード単体の強さ判定は、Jを最弱にするだけでOKですが、役の判定が難しそうです。カードの種類は13種類で、手札もたった5枚なので、Jをすべてのカードのパターンで試して、最も強い役になるものを選ぶという手法もありますが、あまり良い解き方ではない気がします...
そこで今回自分が考えた手法は、ワイルドカードを、手札にあるワイルドカード以外のカード全種類に置き換えてあげるということです。
具体的には
Q Q K A J
の手札に対して、ワイルドカード以外には、Q, K, A の札があるので、"J" を一旦 "QKA" に置換して役を考えます。
しかし、このままでは上の例だと、本来スリーカードとして扱われるべきなのに、フルハウスとして扱われてしまいます。そのため、役の判定も少し書き換えてあげる必要がありそうです。
そうやってワイルドカードがある場合の条件分岐について考えると、ワイルドカードがある場合、ワンペアの役はペアが4個できる、フルハウスの場合3つ組が2つできるなどといった性質が見つかるので、それをコードに落とし込んでいくと、以下のようになります。
// 省略
public int getRank(String hand){
int[] counts = new int[15];
int pairs = 0;
int threes = 0;
int fours = 0;
int fives = 0;
for (char c : hand.toCharArray()) {
counts[getCardValue(c, false)]++;
}
for (int count : counts) {
if (count == 2) pairs++;
if (count == 3) threes++;
if (count == 4) fours++;
if (count == 5) fives++;
}
// 新しい条件分岐
if (fives >= 1) return 7;
if (fours >= 1) return 6;
if ((threes == 1 && pairs == 1) || threes == 2) return 5;
if (threes >= 1) return 4;
if (pairs == 2) return 3;
if (pairs == 1 || pairs == 4) return 2;
return 1;
}
// 文字列の重複を削除
private String removeDuplicates(String input) {
char[] characters = input.toCharArray();
LinkedHashSet<Character> charSet = new LinkedHashSet<>();
for (char c : characters) {
charSet.add(c);
}
StringBuilder sb = new StringBuilder();
for (Character character : charSet) {
sb.append(character);
}
return sb.toString();
}
public int getRankPart2(String hand) {
// 全部Jの場合の例外処理
if (hand.equals("JJJJJ")) {
return 7;
}
String newHand = hand;
// 手札内のJ以外の全種類のカード
String tmp = removeDuplicates(hand.replaceAll("J", ""));
// ワイルドカードをtmpに置き換えて、役を調べる
newHand = hand.replaceAll("J", tmp);
return getRank(newHand);
}
// 省略
こんな感じでDay7も解けました。めでたしめでたし。
終わりに
といったように、AoCはパズル感覚で解くことができ、プログラミングの練習になります。また、多くの海外のプログラマとの交流の機会があります！
年末シーズン、時間のある方はぜひAoC2023に挑戦してみてください！