AtCoderで"Racket"が使えるでんか！

記事名の「でんか」は僕の出身地である、香川県の方言(「さぬき弁」という)です。それも結構強めのさぬき弁です。
ざっくり言うと、東京での「じゃん」、関西での「やん」にあたります。
(東京)さっき食べてたじゃん
(関西)さっき食べてたやん
(香川)さっき食べとったでん
という感じです。
これを話したら「おでんくんみたい」と言われたことがあります。おでんくんみたいではなくない？

さて、AtCoderのルールのページを見ると、言語に"Racket"が追加されていました。

Racket

Racketと書かれると「何の言語？」となるかもしれませんが、これはSchemeから派生した言語です。
なんでそんなんに注目するねんというと、そもそも僕が普段競技プログラミングをSchemeで解く時に使っているツールが「DrRacket」というアプリなんです。

UIはこんな感じ

大学の授業でSchemeのコードを書く際に使っていたのもこれで、結構長い付き合いになります。
ただ、AtCoderのScheme処理系はこれまでGaucheというもののみであり、それはDrRacketに入っていません。よって、DrRacketでコーディング&テストをしていざAtCoderのコードテストをしてみても、一部の関数の有無が違ったりしてエラーになったことが過去に多々ありました。
そのため、慣れないvimでGaucheが動くようにしてみたりしていました。
frfrfrfr.hatenablog.com
しかしそのあとも結局vimはそんなに使わず。結構悩んでいました。

そんなところにRacketの追加！これは朗報では！
SchemeはLispの中でも小さい言語で、自分で関数作っていくみたいな思想が強いため、もともと用意されている関数が少ないんです。しかしこれで便利なモジュールとかも使って回答できるのでは？？？pythonとかのそういうのズルいんじゃ！！！

ということで、ちゃんとRacketを使えるのか、そしてモジュール使ったりできるのか、試してみました。

まず、設定いじって提出してみる

DrRacketでは、画面左下のところで言語を選べます。これまでは大学の授業で言われたまま「R5RS」にしていました。

これを「Determine language from source」に変更します。
そしてコードの頭に

#lang racket

と書くようにします。これでオッケーです。

せっかくなので、問題を1つ解いてみます。
atcoder.jp
これにします。

#lang racket
(define N (read))
(define M (read))
(define (readN n)
  (if (= n 0) '()
      (let ((ele (read)))
        (cons ele (readN (- n 1))))))
(define A (readN N))
(define B (readN M))
(define (solve ll)
  (if (or (null? ll) (null? (cdr ll))) ll
      (if (= (car ll) (cadr ll)) (solve (cddr ll))
          (cons (car ll) (solve (cdr ll))))))
              
(define (display-list ans-list)
  (if (null? ans-list) (newline)
      (begin
        (display (car ans-list))
        (if (not (null? (cdr ans-list))) (display " ") (display ""))
        (display-list (cdr ans-list)))))
(display-list (solve (sort (append A B) <)))

※我ながらかっこいい解き方ができました
これで提出すると・・・無事ACでした。そして実行時間は316ms。ちなみにGaucheにて同じアルゴリズムで提出すると・・・40ms。

単純な性能面では不利と言わざるを得ないですね。

ただ、勝負はここからだ！！！

モジュール使えるのか確認

そもそもどうやって使うんだっけ、というのを確認します。
docs.racket-lang.org
"require"で使うんですね。よしよし。

#lang racket
 
(require racket/date)
(printf "Today is ~s\n"
        (date->string (seconds->date (current-seconds))))

手元のDrRacketではちゃんと動きましたが、これがAtCoderの実行環境でも動くかを確認します。

どうだ！！！

やった！！！

あとは、AtCoderで使うと便利そうなモジュールを探し、実際に使えるか確認していけばよいことになります。ヒュー！！！

使えそうなモジュールを探す

こちらのページで、モジュールに入っている機能を見る方法が書いてあった。
ラケットモジュールのすべての機能のリストを見つける方法は？ - Javaer101
DrRacketの対話機能を使って

> (require モジュール名)
> (module->exports 'モジュール名)

でできます。

ちゃんと出た

面倒だが、よさそうなモジュールがあれば逐一この方法で確認していく、という手段を取ります。
モジュール一覧をネットで探してもなかなか見つからず・・・でしたが、DrRacketのFile→Open require pathを選んで出てきたこの画面で"racket/"と検索すると・・・

dateもある！

ズラッと出てきました。
あとは、名前的から内容を推測して、内容確かめ→使ってみる、というローラー作戦をします。

racket/list

Lispと言えばリスト。リストと言えばLisp。
普段、自分で基礎的な関数を組み上げて作っているものがズバリそのままあったりした。

> (require racket/list)
> (module->exports 'racket/list)
'((0
   (append* ())
   (append-map ())
   (argmax ())
   (argmin ())
   (cartesian-product ())
   (combinations ())
   (cons? (#<module-path-index:racket/private/list-predicates>))
   (count ())
   (drop ())
   (drop-common-prefix ())
   (drop-right ())
   (dropf ())
   (dropf-right ())
   (eighth ())
   (empty ())
   (empty? (#<module-path-index:racket/private/list-predicates>))
   (fifth ())
   (filter-map ())
   (filter-not ())
   (first ())
   (flatten ())
   (fourth ())
   (group-by ())
   (in-combinations ())
   (in-permutations ())
   (index-of ())
   (index-where ())
   (indexes-of ())
   (indexes-where ())
   (last ())
   (last-pair ())
   (list-prefix? ())
   (list-set ())
   (list-update ())
   (make-list ())
   (ninth ())
   (partition ())
   (permutations ())
   (remf ())
   (remf* ())
   (rest ())
   (second ())
   (seventh ())
   (shuffle ())
   (sixth ())
   (split-at ())
   (split-at-right ())
   (split-common-prefix ())
   (splitf-at ())
   (splitf-at-right ())
   (take ())
   (take-common-prefix ())
   (take-right ())
   (takef ())
   (takef-right ())
   (tenth ())
   (third ())))
'((0 (add-between ()) (check-duplicates ()) (range ()) (remove-duplicates ())))

n番目を持ってくるもの

10番目までは実装されています。便利〜

> (define a '(1 2 3 4 5 6 7 8 9 10))
> (second a)
2
> (sixth a)
6
> (tenth a)
10

与えられたリストの順列や部分集合を全て列挙する

これまで自分でがんばって作ってきたのに・・・あるんじゃん！！！

> (permutations '(1 2 3))
'((1 2 3) (2 1 3) (1 3 2) (3 1 2) (2 3 1) (3 2 1))
> (combinations '(1 2 3))
'(() (1) (2) (1 2) (3) (1 3) (2 3) (1 2 3))
> (combinations '(1 2 3) 2)
'((1 2) (1 3) (2 3))

これを使って前の記事の回答を書き直してみます。
Schemeでの、組み合わせの生成などについて(AtCoder Regular Contest 114のA問題) - プログラミングを上達させたい
だいぶスッキリしました。以前書いたGaucheでの提出回答より文字数が500Byteくらい少なくなりました！

#lang racket
 
(require racket/list)

(define N (read))
(define (readN n)
  (if (= n 0) '()
      (let ((ele (read)))
        (cons ele (readN (- n 1))))))

(define (check ele list)
  (if (null? list) #t
      (and (> (gcd ele (car list)) 1) (check ele (cdr list)))))

(define (make-num list)
  (if (null? list) 1 (* (car list) (make-num (cdr list)))))

(define Plist '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47))

(define (solve kouho list)
  (define (sub ele-list ans)
    (if (null? ele-list) ans
        (let ((nownum (make-num (car ele-list))))
          (if (check nownum list) (sub (cdr ele-list) (min ans nownum))
              (sub (cdr ele-list) ans)))))
  (sub kouho (make-num Plist)))
(display (solve (cdr (combinations Plist)) (readN N)))
(newline)

これは使っていきたい。

リスト内で探したい要素が何番目にあるか

これも、これまでなら自分で自作関数を作っていたものです。

> (index-of '(1 2 3 4 5) 3)
2

乱数的なやつ その1

リスト内の順番を適当に並び替えてだしてくれる関数もありました。マラソン系で使えるかも？

> (shuffle '(1 2 3 4 5))
'(1 2 5 4 3)
> (shuffle '(1 2 3 4 5))
'(5 3 4 2 1)

乱数的なやつ その2

randomというモジュールもありました。

> (require racket/random)
> (module->exports 'racket/random)
'()
'((0 (crypto-random-bytes ()) (random-ref ()) (random-sample ())))
> (random-ref 10)
3
> (random-ref 10)
1

集合(Set)

かなり豊かなモジュールのようです。
docs.racket-lang.org
というかそもそもRacketのbaseにもset-union(和集合)やset-intersect(積集合)が入っているようです。
ちなみに差集合っぽい名前であるこの関数は、"引数のものに奇数回現れる要素を抽出"というかっこいい動作をするとのこと。

> (set-symmetric-difference (set 1) (set 1 2) (set 1 2 3))
(set 1 3)

これ使うと、例えば冒頭の問題とかめっちゃ簡単に解けますね→解いてみました。

まず、リスト内のものを半角スペースを間に挟んだ文字列に変える、list->strという関数を作りました。
※もともとlist->stringという関数がありますが、これは"charのリスト"が引数でないと動きません

(define (list->str ll)
  (if (null? ll) ""
      (foldl (lambda (num str) (string-append str " " (number->string num))) (number->string (car ll)) (cdr ll))))

このように動作します。

> (list->str '())
""
> (list->str '(1 2 3))
"1 2 3"

これと、和集合+積集合+差集合を使うことで最終的にこのように書けました！スッキリ！

#lang racket
(define N (read))
(define M (read))
(define (readN n)
  (if (= n 0) '()
      (let ((ele (read)))
        (cons ele (readN (- n 1))))))
(define A (list->set (readN N)))
(define B (list->set (readN M)))
              
(define (list->str ll)
  (if (null? ll) ""
      (foldl (lambda (num str) (string-append str " " (number->string num))) (number->string (car ll)) (cdr ll))))
(display (list->str (sort (set->list (set-symmetric-difference (set-union A B) (set-intersect A B))) <)))
(newline)

冒頭の正解から、さらに150Byte減らせました。

format

出力するときの記述をスッキリさせられそうです！

> (require racket/format)
> (module->exports 'racket/format)
'()
'((0 (~.a ()) (~.s ()) (~.v ()) (~a ()) (~e ()) (~r ()) (~s ()) (~v ())))

あと、string系の問題もスッキリ書けそうですね→解いてみました。

Vectors

いつか書きたい。普段あまり使わないんだよな・・・

racket/function

よさげ？と思った内の一つ。
docs.racket-lang.org
でも、今はまだいいやと思ったので一旦保留。

終わりに

自分のコーディング環境がDrRacketであることを考えると、今後AtCoderの提出はGaucheではなくRacketでやった方がよさそうです。
やっていくぞ！！！！