POPL 25 Problems

#lang racket

(provide (all-defined-out))

;p1
(define (my-last lst)
  (foldr (lambda (x acc) (if (null? acc) x acc)) null lst))

;p2
(define (my-but-last lst)
  (let ((reversed (my-reverse lst)))
    (cond
      [(null? reversed) '()]
      [(<= (length reversed) 2) lst]
      [else (list (second reversed) (first reversed))])))


;p3
(define (element-at lst k)
  (cond
    [(null? lst) null]
    [(= k 1) (car lst)]
    [else (element-at (cdr lst) (- k 1))]))

;p4
(define (my-length lst)
  (foldl (lambda (x acc) (+ acc 1)) 0 lst))

;p5
(define (my-reverse lst)
  (foldl (lambda (x acc) (cons x acc)) '() lst))

;p6
(define (palindrome? lst)
  (equal? lst (my-reverse lst)))

;p7
(define (my-flatten lst)
  (if (null? lst)
      null
      (if (list? (car lst))
          (append (my-flatten (car lst)) (my-flatten (cdr lst)))
          (cons (car lst) (my-flatten (cdr lst))))))

;p8
(define (compress lst)
  (cond
    [(null? lst) null]
    [(null? (cdr lst)) lst]
    [(equal? (car lst) (car (cdr lst))) (compress (cdr lst))]
    [else (cons (car lst) (compress (cdr lst)))]))

;p9
(define (pack lst)
  (if (null? lst)
      null
      (let ([p (pack (cdr lst))])
        (if (null? p)
            (list (list (car lst)))
            (if (equal? (caar p) (car lst))
                (cons (cons (car lst) (car p)) (cdr p))
                (cons (list (car lst)) p))))))

;p10
(define (encode lst)
  (map (lambda (x) (cons (my-length x) (list (car x)))) (pack lst)))

;p11
(define (encode-modified lst)
  (map (lambda (x) (if (= (my-length x) 1)
                       (car x)
                       (cons (my-length x) (list (car x)))))
       (pack lst)))

;p12
(define (decode lst)
  (apply append (map (lambda (x)
                       (if (pair? x)
                           (make-list (car x) (cadr x))
                           (list x)))
                     lst)))

;p13
(define (encode-direct lst)
  (define (encode-helper lst current count result)
    (cond
      [(null? lst)
       (my-reverse (cons (if (= count 1)
                          current
                          (list count current))
                      result))]
      [(equal? (car lst) current)
       (encode-helper (cdr lst) current (+ count 1) result)]
      [else
       (encode-helper (cdr lst)
                      (car lst)
                      1
                      (cons (if (= count 1)
                                current
                                (list count current))
                            result))]))

  (if (null? lst)
      '()
      (encode-helper (cdr lst) (car lst) 1 '())))

;p14
(define (dupli lst)
  (if (null? lst)
      null
      (cons (car lst) (cons (car lst) (dupli (cdr lst))))))

;p15
(define (repli lst n)
  (if (null? lst)
      null
      (append (make-list n (car lst)) (repli (cdr lst) n))))

;p16
(define (drop lst n)
  (if (= n 1)
      '()
      (let loop ((lst lst) (count 1))
        (cond
          [(null? lst) '()]
          [(= count n) (loop (cdr lst) 1)]
          [else (cons (car lst) (loop (cdr lst) (+ count 1)))]))))

;p17
(define (split lst n)
  (if (null? lst)
      (list null null)
      (if (= n 0)
          (list null lst)
          (let ([s (split (cdr lst) (- n 1))])
            (list (cons (car lst) (car s)) (cadr s))))))

;p18
(define (slice lst i k)
  (if (null? lst)
      null
      (if (or (< k 1) (< i 1))
          null
          (if (<= k 0)
              null
              (if (<= i 1)
                  (cons (car lst) (slice (cdr lst) 1 (- k 1)))
                  (slice (cdr lst) (- i 1) (- k 1)))))))

;p19
(define (rotate lst n)
  (if (null? lst)
      lst
      (let* ((len (length lst))
             (n-normalized (modulo n len))
             (split-result (split lst n-normalized)))
        (append (cadr split-result) (car split-result)))))

;p20
(define (remove-at lst k)
  (if (null? lst)
      null
      (if (= k 1)
          (cdr lst)
          (cons (car lst) (remove-at (cdr lst) (- k 1))))))

;p21
(define (insert-at x lst k)
  (if (null? lst)
      (list x)
      (if (= k 1)
          (cons x lst)
          (cons (car lst) (insert-at x (cdr lst) (- k 1))))))

;p22
(define (my-range i k)
  (if (<= i k)
      (range i (+ k 1))
      (my-reverse (range k (+ i 1)))))

; helper function for p23
(define (list-ref lst i)
  (if (null? lst)
      (error 'list-ref "index out of bounds")
      (if (= i 0)
          (car lst)
          (list-ref (cdr lst) (- i 1)))))

;p23
(define (rnd-select lst n)
  (if (or (null? lst) (= n 0))
      null
      (let* ([len (length lst)]
             [i (random len)]
             [x (list-ref lst i)])
        (cons x (rnd-select (remove-at lst (+ i 1)) (- n 1))))))

;p24
(define (lotto-select n m)
  (if (or (< n 0) (< m 0) (> n m))
      '()
      (rnd-select (my-range 1 m) n)))

;p25
(define (rnd-permu lst)
  (rnd-select lst (length lst)))