smithzvk/hacker-rank-submission.lisp

## hacker-rank-submission.lisp

;; This file contains tools that can be used to package solutions to submit to
;; the hacker-rank even if they use programs from Quicklisp.  This is done by
;; using Quicklisp to grab the source (to be done), then using ASDF to track
;; down dependencies, then grabbing the entire source file and inserting it into
;; a single file for submission.  Your code is placed at the end of the file and
;; is read and evaluated from a string in a situation where the desired
;; libraries are instantiated.

;; This can be used with any ASDF reachable library (or this is at least the
;; goal), so you can use your own utility libraries as well so long as you don't
;; mind uploading them to a website.

;; To use it, merely place any systems that you would like loaded in a
;; ql:quickload form.  This is really sloppily done.  These forms are found by
;; searching your source for quickload forms with nothing but whitespace between
;; the form and the beginning of the line.  These libraries are then hunted down
;; and inserted at the beginning of the file irregardless of where you had the
;; quickload form.  Then use the function process-for-submission which will
;; produce a new file with the string "-submission" appended to the
;; pathname-name of the file.  This can be compiled using sbcl --noinform --eval
;; '(compile-file #p"<<filename>>")' --eval '(exit)' which is, I believe how the
;; HackerRank people do it, and it can be run via sbcl --noinform --load
;; '<<filename.fasl>>' which is, again, I believe how they do it on the server.

;; I know this is not very robust or clean, but it works for most purposes.  If
;; you know a better way of doing this, let me know.

(ql:quickload '(:cl-fad
                :cl-plumbing
                :naive-reader))

(defpackage :hacker-rank-submission
  (:use :cl :iterate)
  (:export
   #:create-submission-file))

(in-package :hacker-rank-submission)


;; (defvar *files* nil)

;; (defclass gather-op (asdf:operation)
;;   ((files :initform nil :accessor files-of)))

;; (defmethod asdf:perform ((o gather-op) (c asdf:source-file))
;;   (map () (lambda (file) (push file *files*))
;;        #-(or ecl mkcl)
;;        (asdf:input-files o c)
;;        #+(or ecl mkcl)
;;        (loop :for i :in (asdf:input-files o c)
;; 	     :unless (string= (pathname-type i) "fas")
;; 	     :collect (compile-file-pathname (asdf::lispize-pathname i)))))

;; (defmethod asdf:perform ((operation gather-op) (c asdf:static-file))
;;   (declare (ignorable operation c))
;;   nil)

;; (defmethod asdf:operation-done-p ((operation gather-op) (c asdf:static-file))
;;   (declare (ignorable operation c))
;;   nil)

;; (defmethod asdf:output-files ((operation gather-op) (c asdf:component))
;;   (declare (ignorable operation c))
;;   nil)

;; (defmethod asdf:component-depends-on ((o gather-op) (c asdf:component))
;;   (declare (ignorable o))
;;   (list (cons 'gather-op
;;               (rest (first (asdf:component-depends-on
;;                             'asdf:compile-op c))))))

;; We then go through the files and process each apparent toplevel form by
;; wrapping it in a <eval-when> form.  By apparent toplevel form I mean the
;; forms that you get as you read a file.  This is actually a semantically
;; important unit in that a reader macro defined in one apparent toplevel form
;; can effect the later apparent toplevel forms, but not necessarily all of the
;; later toplevel forms as some of those may have been read at the same time as
;; the form with the reader macro definition.

(defun wrap-form (form)
  (format nil "~%(eval-when (:compile-toplevel :load-toplevel :execute)~%~A~%)"
          form))

(defun wrap-toplevel-forms (file)
  (with-output-to-string (out)
    (with-open-file (in file)
      (iter (for string = (handler-case
                              (naive-reader:read-form-string in)
                            (end-of-file () nil)))
        (while (and string (not (eql string ""))))
        (princ (wrap-form string) out)))))

;; With asdf:monolithic-concatenate-source-op
(defun gather-package-dependencies
    (component &key (output-file (make-pathname
                                  :name (concatenate
                                         'string
                                         (string-downcase (symbol-name component))
                                         "-processed")
                                  :type "lisp"
                                  :defaults *default-pathname-defaults*))
                    (if-exists :supersede))
  (asdf:oos 'asdf:monolithic-concatenate-source-op component :force t)
  (let* ((file (print (asdf:output-file 'asdf:monolithic-concatenate-source-op component)))
         (output (wrap-toplevel-forms file)))
    (if (eql output-file :string)
        output
        (with-open-file (out output-file :direction :output :if-exists if-exists)
          (princ output out)
          nil))))

;; This builds the system as necessary as a temporary file, then builds the
;; equivalent source file.
(defun concat-source-files (file output-file)
  (let* ((dependencies (with-open-file (in file)
                         (let ((loads (read in)))
                           (cond ((or (atom loads)
                                      (not (eql 'ql:quickload)
                                           (first loads)))
                                  ;; No dependencies
                                  nil)
                                 ((atom (second loads))
                                  ;; only one dependency
                                  (list (second loads)))
                                 (t
                                  ;; Many dependencies
                                  (second (second loads)))))))
         (cl-fad:*default-template* "TEMPORARY-FILES:%")
         (system-name (concatenate 'string (format nil "~A" (random 10000))
                                   "-submission"))
         (system
           (intern (string-upcase system-name) :keyword))
         (asd-file
           (cl-fad:with-output-to-temporary-file
               (out :generate-random-string
                    (lambda () (concatenate 'string system-name ".asd")))
             (print `(asdf:defsystem ,system :depends-on ,dependencies) out))))
    (let ((asdf:*central-registry*
            (cons (make-pathname :directory (pathname-directory asd-file))
                  asdf:*central-registry*)))
      (with-open-file (in file)
        (read in)
        (let ((concat (make-concatenated-stream
                       (make-string-input-stream
                        (gather-package-dependencies
                         system
                         :output-file :string))
                       in)))
          (with-open-file (out output-file :direction :output
                                           :if-exists :supersede)
            (cl-plumbing:connect-streams concat out
                                         :background nil :read-fn 'read-line)))))))

(defun create-submission-file (file &key output)
  (concat-source-files file output))

(defun submit-solution (file challenge)
  (declare (ignore file challenge))
  (lambda () (print 'test))
  (error
   "This is not implemented yet and won't be until there is some kind of public API."))

;; The other way.

;; By HackerRank rules, you can write files to the local directory.  This means
;; that we could simply include the code to write the files out and compile them
;; along with the code to load them and compile your code.  This is probably the
;; cleanest way to work within the constraints (in fact if I had known that this
;; was a weak point on the constraints, I would have done this to begin with).

;; Actually this hinges on the ability to write at compile time, which isn't
;; necessarily something that we are allowed to do, and the presence of those
;; written files at run time, something that we are not explicitly guaranteed.

;; (eval-when (:compile-toplevel :load-toplevel :execute)
;;   (let ((num 0))
;;     (defun make-file-name ()
;;       (format nil "~D.lisp" num)))

;;   (defun write-file (source)
;;     (with-open-file (out (make-file-name) :direction :output)
;;       (format out "~A~%" source))))

;; (write-file "(defun test () t)")


;; There are some other tools that are extremely useful if you are using
;; hackerrank.  HackerRank problems typically involve repeated invocation of
;; your program from the shell, which is then given some partial input and an
;; output is expected for your next move.  This is pretty darned annoying as
;; this seems to indicate that your submission has to be state free.  This is
;; not actually the case, as the HackerRank rules clearly indicate that you can
;; write a file which will be present on the next invocation of you program.  Is
;; this true?

;; What we need is a way to serialize all the state of the system and then
;; restart the system on the next invocation.

;; One interesting way to do this would be to dump a core and then find a way to
;; reload it on the next invocation.

;; The other obvious way to do this is to print out data and then read it in,
;; perhaps using something as sophisticated as a serialization library.

;; We could also use a problem to probe properties about the system.  See if we
;; can use Clommand.


;; What would be neat is if I used slime-calls-who to perform tree shaking.
;; This is not implemented in sbcl, but it can be faked by using
;; slime-who-calls, which is implemented.  This works for both functions and
;; macros.

;; To fake it, just search all symbols that are defined in a package (and that
;; belong to that package) and use slime-who-calls to figure out who calls them
;; and then, for each of those, record the symbol in question into it's
;; calls-who entry (in a hash).  After that, you have an inverted call.

;; Note that this only works within for within the same imp/version, though the
;; coding can (usually) be made to not use special functions for different imps,
;; which would make the call tree work.

;; This could really be the start of a bigger shake and bake (macro-expansion)
;; project.

	;; This file contains tools that can be used to package solutions to submit to
	;; the hacker-rank even if they use programs from Quicklisp. This is done by
	;; using Quicklisp to grab the source (to be done), then using ASDF to track
	;; down dependencies, then grabbing the entire source file and inserting it into
	;; a single file for submission. Your code is placed at the end of the file and
	;; is read and evaluated from a string in a situation where the desired
	;; libraries are instantiated.

	;; This can be used with any ASDF reachable library (or this is at least the
	;; goal), so you can use your own utility libraries as well so long as you don't
	;; mind uploading them to a website.

	;; To use it, merely place any systems that you would like loaded in a
	;; ql:quickload form. This is really sloppily done. These forms are found by
	;; searching your source for quickload forms with nothing but whitespace between
	;; the form and the beginning of the line. These libraries are then hunted down
	;; and inserted at the beginning of the file irregardless of where you had the
	;; quickload form. Then use the function process-for-submission which will
	;; produce a new file with the string "-submission" appended to the
	;; pathname-name of the file. This can be compiled using sbcl --noinform --eval
	;; '(compile-file #p"<<filename>>")' --eval '(exit)' which is, I believe how the
	;; HackerRank people do it, and it can be run via sbcl --noinform --load
	;; '<<filename.fasl>>' which is, again, I believe how they do it on the server.

	;; I know this is not very robust or clean, but it works for most purposes. If
	;; you know a better way of doing this, let me know.

	(ql:quickload '(:cl-fad
	:cl-plumbing
	:naive-reader))

	(defpackage :hacker-rank-submission
	(:use :cl :iterate)
	(:export
	#:create-submission-file))

	(in-package :hacker-rank-submission)


	;; (defvar files nil)

	;; (defclass gather-op (asdf:operation)
	;; ((files :initform nil :accessor files-of)))

	;; (defmethod asdf:perform ((o gather-op) (c asdf:source-file))
	;; (map () (lambda (file) (push file files))
	;; #-(or ecl mkcl)
	;; (asdf:input-files o c)
	;; #+(or ecl mkcl)
	;; (loop :for i :in (asdf:input-files o c)
	;; :unless (string= (pathname-type i) "fas")
	;; :collect (compile-file-pathname (asdf::lispize-pathname i)))))

	;; (defmethod asdf:perform ((operation gather-op) (c asdf:static-file))
	;; (declare (ignorable operation c))
	;; nil)

	;; (defmethod asdf:operation-done-p ((operation gather-op) (c asdf:static-file))
	;; (declare (ignorable operation c))
	;; nil)

	;; (defmethod asdf:output-files ((operation gather-op) (c asdf:component))
	;; (declare (ignorable operation c))
	;; nil)

	;; (defmethod asdf:component-depends-on ((o gather-op) (c asdf:component))
	;; (declare (ignorable o))
	;; (list (cons 'gather-op
	;; (rest (first (asdf:component-depends-on
	;; 'asdf:compile-op c))))))

	;; We then go through the files and process each apparent toplevel form by
	;; wrapping it in a <eval-when> form. By apparent toplevel form I mean the
	;; forms that you get as you read a file. This is actually a semantically
	;; important unit in that a reader macro defined in one apparent toplevel form
	;; can effect the later apparent toplevel forms, but not necessarily all of the
	;; later toplevel forms as some of those may have been read at the same time as
	;; the form with the reader macro definition.

	(defun wrap-form (form)
	(format nil "~%(eval-when (:compile-toplevel :load-toplevel :execute)~%~A~%)"
	form))

	(defun wrap-toplevel-forms (file)
	(with-output-to-string (out)
	(with-open-file (in file)
	(iter (for string = (handler-case
	(naive-reader:read-form-string in)
	(end-of-file () nil)))
	(while (and string (not (eql string ""))))
	(princ (wrap-form string) out)))))

	;; With asdf:monolithic-concatenate-source-op
	(defun gather-package-dependencies
	(component &key (output-file (make-pathname
	:name (concatenate
	'string
	(string-downcase (symbol-name component))
	"-processed")
	:type "lisp"
	:defaults default-pathname-defaults))
	(if-exists :supersede))
	(asdf:oos 'asdf:monolithic-concatenate-source-op component :force t)
	(let* ((file (print (asdf:output-file 'asdf:monolithic-concatenate-source-op component)))
	(output (wrap-toplevel-forms file)))
	(if (eql output-file :string)
	output
	(with-open-file (out output-file :direction :output :if-exists if-exists)
	(princ output out)
	nil))))

	;; This builds the system as necessary as a temporary file, then builds the
	;; equivalent source file.
	(defun concat-source-files (file output-file)
	(let* ((dependencies (with-open-file (in file)
	(let ((loads (read in)))
	(cond ((or (atom loads)
	(not (eql 'ql:quickload)
	(first loads)))
	;; No dependencies
	nil)
	((atom (second loads))
	;; only one dependency
	(list (second loads)))
	(t
	;; Many dependencies
	(second (second loads)))))))
	(cl-fad:default-template "TEMPORARY-FILES:%")
	(system-name (concatenate 'string (format nil "~A" (random 10000))
	"-submission"))
	(system
	(intern (string-upcase system-name) :keyword))
	(asd-file
	(cl-fad:with-output-to-temporary-file
	(out :generate-random-string
	(lambda () (concatenate 'string system-name ".asd")))
	(print `(asdf:defsystem ,system :depends-on ,dependencies) out))))
	(let ((asdf:central-registry
	(cons (make-pathname :directory (pathname-directory asd-file))
	asdf:central-registry)))
	(with-open-file (in file)
	(read in)
	(let ((concat (make-concatenated-stream
	(make-string-input-stream
	(gather-package-dependencies
	system
	:output-file :string))
	in)))
	(with-open-file (out output-file :direction :output
	:if-exists :supersede)
	(cl-plumbing:connect-streams concat out
	:background nil :read-fn 'read-line)))))))

	(defun create-submission-file (file &key output)
	(concat-source-files file output))

	(defun submit-solution (file challenge)
	(declare (ignore file challenge))
	(lambda () (print 'test))
	(error
	"This is not implemented yet and won't be until there is some kind of public API."))

	;; The other way.

	;; By HackerRank rules, you can write files to the local directory. This means
	;; that we could simply include the code to write the files out and compile them
	;; along with the code to load them and compile your code. This is probably the
	;; cleanest way to work within the constraints (in fact if I had known that this
	;; was a weak point on the constraints, I would have done this to begin with).

	;; Actually this hinges on the ability to write at compile time, which isn't
	;; necessarily something that we are allowed to do, and the presence of those
	;; written files at run time, something that we are not explicitly guaranteed.

	;; (eval-when (:compile-toplevel :load-toplevel :execute)
	;; (let ((num 0))
	;; (defun make-file-name ()
	;; (format nil "~D.lisp" num)))

	;; (defun write-file (source)
	;; (with-open-file (out (make-file-name) :direction :output)
	;; (format out "~A~%" source))))

	;; (write-file "(defun test () t)")


	;; There are some other tools that are extremely useful if you are using
	;; hackerrank. HackerRank problems typically involve repeated invocation of
	;; your program from the shell, which is then given some partial input and an
	;; output is expected for your next move. This is pretty darned annoying as
	;; this seems to indicate that your submission has to be state free. This is
	;; not actually the case, as the HackerRank rules clearly indicate that you can
	;; write a file which will be present on the next invocation of you program. Is
	;; this true?

	;; What we need is a way to serialize all the state of the system and then
	;; restart the system on the next invocation.

	;; One interesting way to do this would be to dump a core and then find a way to
	;; reload it on the next invocation.

	;; The other obvious way to do this is to print out data and then read it in,
	;; perhaps using something as sophisticated as a serialization library.

	;; We could also use a problem to probe properties about the system. See if we
	;; can use Clommand.



	;; What would be neat is if I used slime-calls-who to perform tree shaking.
	;; This is not implemented in sbcl, but it can be faked by using
	;; slime-who-calls, which is implemented. This works for both functions and
	;; macros.

	;; To fake it, just search all symbols that are defined in a package (and that
	;; belong to that package) and use slime-who-calls to figure out who calls them
	;; and then, for each of those, record the symbol in question into it's
	;; calls-who entry (in a hash). After that, you have an inverted call.

	;; Note that this only works within for within the same imp/version, though the
	;; coding can (usually) be made to not use special functions for different imps,
	;; which would make the call tree work.

	;; This could really be the start of a bigger shake and bake (macro-expansion)
	;; project.