language: Common Lisp (clisp) (clisp 2.47)
date: 122 days 5 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

(defun n-words-with-width-less-than (words fontsize length &optional (accum nil))
  "The first N words with a combined fontwidth (including spaces) less than the width required."
  (if (<= (* fontsize
             (+ (length accum) ;;Add the spaces.
                -1 ;;Minus one, since the last word needs no space after it.
                (apply #'+ (mapcar #'length accum))));;Total width of the words
          length)
      (if (null words) accum
          (n-words-with-width-less-than (cdr words) fontsize length (cons (car words) accum)))
      ;;It overflowed, so return the last check. (Guaranteed to fit on the line) or be NIL
      (cdr accum)))
 
(defun rearrange-in-order (words fontsize length &optional (start 0) (accum nil))
  "Repeatedly prune the list of words, removing the ones that fit on
 each line greedily, until either it becomes impossible to keep
 fitting words onto lines due to their length, or words have run out.
 Guaranteed to have the shortest possible height, due to its greediness."
  (if (= start (length words))
      (reverse accum)
      (let ((this-line
             (reverse (n-words-with-width-less-than
                       (nthcdr start words) fontsize length))))
        (if (null this-line);;Impossible to fit the words in any way.
            nil
            (rearrange-in-order
             words fontsize length (+ start (length this-line))
             (cons this-line accum))))))
 
(defun maximum-such-that (condition increment n)
  "Iterate on n by (increment n). Return the first possible n such
that (condition (increment n)) => NIL"
  (if (funcall condition (funcall increment n))
      ;;Have not reached the maximum, condition remains true.
      (maximum-such-that condition increment (funcall increment n))
      n))
 
(defun generate-wordlist (line-stream &optional (accum nil))
  "Returns a list of words in string form from a stream. Reads until EOF."
  (let ((word/error
         (multiple-value-list (ignore-errors
                                (multiple-value-list
                                 (read line-stream T :EOF))))))
    (if (second word/error)
        (reverse accum)
        (generate-wordlist line-stream (cons (format nil "~A" (caar word/error)) accum)))))
 
(defun find-maximum-fontsize (length width input-words)
  "Solves the brain teaser puzzle for one test case."
  (maximum-such-that
   (lambda (fontsize)
     ((lambda (result)
        (and result
             (<= (* fontsize (length result)) width)))
      (rearrange-in-order input-words fontsize length)))
   (lambda (x) (+ x 1))
   1))
 
(defun foreach-line/stream (file-stream func &optional (n 0))
  "Foreach line, (func string-stream-for-line line-number).
  Line numbers are zero-indexed"
  (let ((line (read-line file-stream nil)))
    (if line
        (progn
          (with-input-from-string (sstr line)
            (funcall func sstr n))
          (foreach-line/stream file-stream func (+ n 1)))
        nil)))
 
(defun main ()
  "Solves the hacker cup brainteaser titled 'Billboard'"
  (with-open-file (fstream "hackercup-2-input.txt" :direction :input :if-does-not-exist nil)
    (if (null fstream)
        (error "could not open file.")
        (progn
          (read-line fstream)
          (foreach-line/stream
           fstream
           (lambda (line-stream n)
             (format T "Case #~a: ~A~%"
                     (+ n 1)
                     (find-maximum-fontsize (or (read line-stream nil) 0)
                                            (or (read line-stream nil) 0)
                                            (generate-wordlist line-stream)))))))))
  • upload with new input
  • # 2:   show   clone   input   122 days 5 hours ago    Success
  • # 1:   hide   clone   input   122 days 5 hours ago

    result: Success     time: 0.02s    memory: 10608 kB     returned value: 0