プログラミングを上達させたい

プログラミングの勉強を始めた、情報学専攻の大学院生です。モチベーション維持のため、ブログに勉強したことを書いていきます。→就職。IT全然関係ない仕事をしています

AtCoder Beginners Selection を Scheme(Lisp)で解く 前編

競技プログラミングサイトAtCoder にて、「初心者の方はまずこの問題を解いてみよう!」という趣旨の
AtCoder Beginners Selection - AtCoder Beginners Selection | AtCoder
というページが出来ていました。


最近全然プログラミングやってなかったのと、図書館で借りたこの本

を読んでテンションがあがっていたのもあり、Schemeで問題を解いていくことにしました。
11問あるんですが、今回は一旦7問目まで。

1問目

PracticeA: はじめてのあっとこーだー(Welcome to AtCoder) - AtCoder Beginners Selection | AtCoder
Schemeでの標準入出力のやり方の確認、って感じですね。
(newline) を忘れずに。

(define a (read))
(define b (read))
(define c (read))
(define w (read))
(display (+ a b c))
(display " ")
(display w)
(newline)
2問目

ABC086A: Product - AtCoder Beginners Selection | AtCoder
if文が出てきます。

(define a (read))
(define b (read))
(display
 (if (= 0 (modulo (* a b) 2))
     "Even"
     "Odd"))
(newline)
3問目

ABC081A: Placing Marbles - AtCoder Beginners Selection | AtCoder
入力を数字として処理してます。

(define s (read))
 
(define one?
  (lambda (a) (= a 1)))
(define addOneIfOne
  (lambda (a) (if (one? a) 1 0)))
 
(define (num1count string counter)
  (if (< string 10)
      (+ counter (addOneIfOne string))
      (num1count (quotient string 10) (+ counter (addOneIfOne (modulo string 10))))))
 
(display (num1count s 0))                   
 
(newline)
4問目

ABC081B: Shift only - AtCoder Beginners Selection | AtCoder
N個の数字の入力、というのが出てきます。
それに関しては、今回の回答で作った、これが自然な書き方かと思います。

;read N-elements-list
(define read_list
  (lambda (n)
    (if (= n 0) '()
        (let* ((element (read)))
          (cons element (read_list (- n 1)))))))

リストとして入力してますが、"list->vector"という関数で配列にも簡単に変換できます。

しかし、カリー化?のやり方が思い出せず・・・面倒なので無理矢理書きました。
"list_min_check"という関数の引数として、ずっと"func"があるのダサいですよね。復習しなきゃ。

(define N (read))
 
;read N-elements-list
(define read_list
  (lambda (n)
    (if (= n 0) '()
        (let* ((element (read)))
          (cons element (read_list (- n 1)))))))
 
(define kaijo_check2_sub
  (lambda (n count)
    (if (= 1 (modulo n 2)) count
        (kaijo_check2_sub (quotient n 2) (+ count 1)))))
(define kaijo_check2
  (lambda (n) (kaijo_check2_sub n 0)))
 
(define list_min_check
  (lambda (init_or_min list func)
    (if (null? list) init_or_min
        (let ((car_val (func (car list)))
              (cdr_list (cdr list)))
          (if (> init_or_min car_val)
              (list_min_check car_val cdr_list func)
              (list_min_check init_or_min cdr_list func))))))
;funcをカリー化?するやつどうやるんやっけ
 
(display (list_min_check 50 (read_list N) kaijo_check2))
 
(newline)
5問目

ABC087B: Coins - AtCoder Beginners Selection | AtCoder
候補を生成して総当たり、で書きました。

;総当たり
(define A (read))
(define B (read))
(define C (read))
(define X (read))
 
(define first (lambda (list) (car list)))
(define second (lambda (list) (car (cdr list))))
(define third (lambda (list) (car (cdr (cdr list)))))
 
(define sum
  (lambda (list)
    (+ (* 500 (first list))
       (* 100 (second list))
       (* 50 (third list)))))
 
(define add1_nth_element
  (lambda (list n)
    (if (= n 1)
        (cons (+ 1 (car list)) (cdr list))
        (cons (car list) (add1_nth_element (cdr list) (- n 1))))))
 
(define next_list
  (lambda (list)
    (if (< (third list) C)
        (add1_nth_element list 3)
        (if (< (second list) B)
            (cons (first list) (cons (+ (second list) 1) (cons 0 '())))
            (if (< (first list) A)
                (cons (+ (first list) 1) '(0 0))
                '())))))
 
(define answer
  (lambda (list counter)
    (if (null? list) counter
        (let ((next (next_list list)))
          (if (= (sum list) X)
              (answer next (+ counter 1))
              (answer next counter))))))
 
(display (answer '(0 0 0) 0))
 
(newline)
6問目

ABC083B: Some Sums - AtCoder Beginners Selection | AtCoder
こちらも、全部試す作戦で。

;総当たり
(define N (read))
(define A (read))
(define B (read))
 
(define sum_kaku_keta
  (lambda (num count)
    (if (< num 10) (+ count num)
        (sum_kaku_keta (quotient num 10) (+ count (modulo num 10))))))
(define ketawa
  (lambda (num) (sum_kaku_keta num 0)))
 
(define check_clear
  (lambda (num)
    (let ((sum_keta (ketawa num)))
      (and (<= A sum_keta) (>= B sum_keta)))))
 
(define counter
  (lambda (list count)
    (if (null? list) count
        (let ((cd (cdr list))
              (cr (car list)))
          (if (check_clear cr)
              (counter cd (+ count cr))
              (counter cd count))))))
 
(define list_1_to_n
  (lambda (a b)
    (if (> a b) '()
        (cons a (list_1_to_n (+ a 1) b)))))
 
(display (counter (list_1_to_n 1 N) 0))
 
(newline)
7問目

ABC088B: Card Game for Two - AtCoder Beginners Selection | AtCoder
この問題が入った意図としては、「配列の操作(今回だとソート)」をさせるためでしょうか?

(define N (read))
 
;Nがたいして大きくないので挿入ソートで。大きい順ね。
(define insert
  (lambda (element list)
    (cond ((null? list) (cons element '()))
          ((>= element (car list)) (cons element list))
          (#t (cons (car list) (insert element (cdr list)))))))
    
 
(define read_insert_sort
  (lambda (list n)
    (if (= n 0) list
        (let* ((new_element (read)))
          (read_insert_sort (insert new_element list) (- n 1))))))
 
(define sum_two
  (lambda (alice bob list switch)
    (cond ((null? list) (- alice bob))
          ((= switch 1) (sum_two (+ alice (car list)) bob (cdr list) 2))
          (#t (sum_two alice (+ bob (car list)) (cdr list) 1)))))
 
(display (sum_two 0 0 (read_insert_sort '() N) 1))
 
(newline)


ひとまず解いたところまで。
久々にやると楽しい!!!
カリー化的なことが綺麗に書けない(し、それを気にせず汚く書ける)あたり、
まだ関数型言語脳になってるわけではないのでしょう。
頑張りたいところやでホンマ。
あと、これも読まなきゃ。


というわけで、下記の後編に続きます。
frfrfrfr.hatenablog.com