language: Common Lisp (clisp) (clisp 2.47)
date: 121 days 22 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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

;;Solution to facebook hacker cup Billboard brain teaser.
;;author: sea <http://sea4ever.users.sourceforge.net>
;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.
 
;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.
 
;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
(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   121 days 22 hours ago    Success
  • # 1:   hide   clone   input   121 days 22 hours ago

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