?

Log in

No account? Create an account
Code Review Request: Studious Student - Жить не можем без проблем! [entries|archive|friends|userinfo]
Жить не можем без проблем!

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Code Review Request: Studious Student [Jan. 11th, 2011|04:46 pm]
Жить не можем без проблем!

ru_lisp

[kit1980ukr]
Решил вернуться к изучению Common Lisp, в рамках чего порешал задачки на квалификации Facebook Hacker Cup.

Под катом мое решение задачи "Studious Student".
Прошу посмотреть код и подсказать, что можно сделать лучше (быстрее, проще).

Краткое условие задачи (оригинальное условие сейчас уже не посмотришь, к сожалению):

Во входном файле в первой строке - количество тестов N.
В каждой последующей строке - первое число - количество слов M, далее M разделенных пробелами слов.
Для каждого теста вывести лексикографически минимальную комбинацию всех слов для данного теста.
1 <= N <= 100
1 <= M <= 9
В каждом слове максимум 10 символов.
Лимит времени - 6 минут на весь входной файл (плюс еще надо успеть скопировать и отправить результаты).

Тесты-примеры:

example.in:

5
6 facebook hacker cup for studious students
5 k duz q rc lvraw
5 mybea zdr yubx xe dyroiy
5 jibw ji jp bw jibw
5 uiuy hopji li j dcyi

example.out:

cupfacebookforhackerstudentsstudious
duzklvrawqrc
dyroiymybeaxeyubxzdr
bwjibwjibwjijp
dcyihopjijliuiuy


Алгоритм я использовал очень простой (с небольшой вариацией) - генерация всех перестановок слов, конкатенация слов для этой перестановки и выбор из всех минимальной строки (вариант просто отсортировать исходный список не пройдет, например, для "za z").


;;;; Facebook Hacker Cup - 2011
;;;; Qualification Round
;;;; Studious Student
;;;;
;;;; Sergey Dymchenko <kit1980@gmail.com>
;;;;
;;;; Language: Common Lisp
;;;; Tested with SBCL 1.0.29 - http://www.sbcl.org/
;;;; sbcl --noinform --load lisp-file < in-file > out-file
;;;;
;;;; Libraries used:
;;;; Alexandria - http://common-lisp.net/project/alexandria/
;;;; split-sequence - http://www.cliki.net/SPLIT-SEQUENCE

(eval-when (:compile-toplevel :load-toplevel :execute)
  (require 'alexandria)
  (require 'split-sequence))

(defun minimal-string (s-list)
  (let ((minimal-string (apply #'concatenate 'simple-base-string s-list)) 
        current-string)
    (alexandria:map-permutations 
     #'(lambda (ss) 
         (if (string< (first ss) minimal-string)
             (progn 
               (setf current-string (apply #'concatenate 'simple-base-string ss))
               (if (string< current-string minimal-string)
                   (setf minimal-string current-string))))) 
     s-list :copy nil)
    minimal-string))

(defun case-string-to-list (s)
  (split-sequence:split-sequence 
   #\Space s
   :start 1 :remove-empty-subseqs t))

(defun solve ()
  (let ((n (read)))
    (dotimes (i n) 
      (format t "~a~%" (minimal-string (case-string-to-list (read-line))))))
  0)

(solve)
(quit)


Программа работает, но не очень быстро: на максимальном входном файле (100 тестов по 9 слов по 10 символов в каждом) на моем компьютере считает чуть больше 4 минут. Попытки добавления (declare (optimize (speed 3) (safety 0)) и указания типов ни к чему хорошему не привели...
linkReply

Comments:
From: dmitry_vk
2011-01-11 05:58 pm (UTC)
В общем, тут алгоритм простой - сортируем строки по критерию a + b < b + a. На лиспе все выливается в вызов sort с соответствующим :test.
(Reply) (Thread)
[User Picture]From: kit1980ukr
2011-01-11 06:26 pm (UTC)
Слова до 10 символов могут быть.

А вообще да, можно с сортировкой.
Критерий сортировки такой - дополняем строку меньшей длины ее последним символом, и сравниваем получившиеся строки, как обычно.

Т.е. для "za z" сравниваем za и zz, а для "yz y" - сравниваем yz и yy.

Вроде бы будет работать и для строк произвольной длины, еще не проверял.

Но это как бы не слишком очевидно. Т.е. интересно не решение конкретной задачи (для чего и этой программы хватило), а как, грубо говоря, приблизить скорость выполнения к скорости выполнения программы на C++ с этим же алгоритмом.

Ну и вообще по коду. Например, require() is deprecated. А как заменить?
(Reply) (Parent) (Thread)
From: dmitry_vk
2011-01-11 06:49 pm (UTC)
>Слова до 10 символов могут быть.

Хорошо, но это ничего не меняет в алгоритме.

Ваш критерий сортировки не пойдет.
Например, ac acb. acb < acc, поэтому по предложенному вами алгоритму будет acbac. Хотя тут правильное решение - acacb.

На вторую часть и третью части вопроса - как можно ускорить данную программу и что можно улучшить - я постараюсь ответить позднее, так как тут нужен анализ.
(Reply) (Parent) (Thread)
[User Picture]From: kit1980ukr
2011-01-11 07:04 pm (UTC)
Да, точно.
Спасибо.
(Reply) (Parent) (Thread)
[User Picture]From: incrab
2011-01-13 09:18 am (UTC)
К меньшему из слов нужно добавлять не последнюю букву, а само меньшее слово целиком.
Мне видится что так сортировка будет работать правильно.

Вот примерный код на scala, к сожалению не знаком с CL:

    def compare(a: String, b: String) = {
        @tailrec
        def compareRec(posA: Int, posB: Int): Int = {
            if (posA == a.length) {
                if (posB == b.length)
                    0
                else
                    compareRec(0, posB)    
            } else {
                if (posB == b.length)
                    compareRec(posA, 0)
                else {
                    val diff = a.charAt(posA) - b.charAt(posB)
                    if (diff == 0)
                        compareRec(posA + 1, posB + 1)
                    else
                        diff
                }
            }
        }
        compareRec(0, 0)
    }
(Reply) (Parent) (Thread)
[User Picture]From: lispnik
2011-01-12 05:35 am (UTC)

Вместо require нужно использовать ASDF:

(asdf:oos 'asdf:load-op :alexandria)

и тому подобное.

(Reply) (Parent) (Thread)