3.5 KiB

Raw Permalink Blame History

Solution of 2024-p9

Part 1:
Part 2: defragging whole files

Now, this was a bit more challenging than the others

This binds data to the test input

  (setq data "2333133121414131402")

This instead binds data to the actual input

 (with-temp-buffer
     (insert-file-contents "input")
     (goto-char (point-min))
     (replace-regexp "^" "\"")
     (goto-char (point-min))
     (replace-regexp "$" "\"")
     (goto-char (point-min))
     (insert "(setq data ")
     (goto-char (point-max))
     (insert ")")
     (eval-buffer))

This creates a index of the disk: each element is (file index . length), where file index is nil if the node is empty

(setq disk-index (-map-indexed (lambda (index el)
                               (if (eq 0 (% index 2))
                                   (cons (/ index 2) el)
                                 (cons nil el)))
                             (-map #'string-to-number (split-string data "\\|.+" t))) )

This creates the disk image from the index

  (defun disk-from-index (d-index)
    (-mapcat (lambda (x) (-repeat (cdr x) (car x))) d-index))

  (setq disk (disk-from-image disk-index))

Part 1:

The recursive approach

This works for the test input but stack overflows for the actual input since elisp does not have tail call optimization

(defun defrag (disk)
  (let ((i (-find-index #'not disk))
        (j (-find-last-index #'identity disk))        )
    (if (> i j) disk
      (defrag (-replace-at j nil (-replace-at i (nth j disk) disk))))))

The while-loop approach

This works, but is quite horrible

(defun defrag-loop (disk)
  (let ((i (-find-index #'not disk))
        (j (-find-last-index #'identity disk))        )
    (while (<= i j)
      (setq disk (-replace-at j nil (-replace-at i (nth j disk) disk)))
      (setq i (-find-index #'not disk)
            j (-find-last-index #'identity disk))))
  disk  )

The reduce-with-a-copy approach

  (defun defrag-reduce (disk)
    (-reduce-r-from (lambda (el acc)
                     (if (not el) acc
                       (let ((i (-find-index #'not acc))
                             (j (-find-last-index #'identity acc)))
                         (if (> i j) acc
                           (-replace-last el nil (-replace-at i el acc))))))
                   disk disk))

And, compute!

  (-reduce #'+ (-map-indexed (lambda (i file) (* i file)) (-non-nil (defrag-reduce disk))))

  6241633730082

Part 2: defragging whole files

This is fun, now we start from the index

  (defun defrag-index (d-index)
    (-reduce-r-from (lambda (el acc)
                     (if (not (car el)) acc
                       (let ((i (-find-index (lambda (ell)
                                               (and (not (car ell)) (>= (cdr ell) (cdr el)))) acc))
                             (j (-find-last-index (lambda (e) (equal e el)) acc)))
                         (if (or (not i) (> i j)) acc
                           (-insert-at i el (-replace-at i (cons nil (- (cdr (nth i acc)) (cdr el))) (-replace-last el (cons nil (cdr el)) acc)))))))
                   d-index d-index))

And compute

  (-reduce #'+ (-map-indexed (lambda (i file) (if file (* i file) 0)) (disk-from-index (defrag-index disk-index))))

6265268809555

3.5 KiB Raw Permalink Blame History