Skyline Problem in Scheme

Hi,

I’ve solved another puzzle. The skyline problem.  I have to admit though, I started out totally wrong. I set out to write a solution that would only require a single pass over the list of buildings, which was really hard. It would have been doable if all buildings only overlapped with the last one. I spent a few hours going down that path before I realized I could do it so much simpler.

The solution is done in Scheme (<3) for once. On Stack Overflow there is a code-golf for the shortest solution but I didn’t manage to do that though. My solution counts 690 characters, so I can’t really compete with the current record of 40 characters.  I’m just glad I solved it!

(define buildings '((1 11 5) (2 6 7) (3 13 9) (12 7 16) (14 3 25) (19 18 22) (23 13 29) (24 4 28)))
(define solution '(1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0))

; Map a function over a vector.
; Function needs to parameters:
; The value and the index of the value.
(define (vector-map! proc v)
  (let map
    ((index 0))
    (vector-set! v index (proc (vector-ref v index) index))
    (if (< index (- (vector-length v) 1))
        (map (+ 1 index)))))

(define (create-skyline buildings)
  ; Determine total width.
  (let ((width 0)
        (skyline-vector '())
        (output '())
        (current-height -1))
    (map (lambda (building) 
           (set! width (max width (caddr building)))) buildings)
    ; Create the vector with the proper width.
    (set! skyline-vector (make-vector width 0))
    ; Loop over the buildings and update the vector.
    (map (lambda (building)
           (let update-vector 
             ((index (car building)))
             (vector-set! skyline-vector 
                          index
                          (max 
                           (vector-ref skyline-vector index) 
                           (cadr building)))
             (if (< index  (- (caddr building) 1))
                 (update-vector (+ 1 index)))))
         buildings)
    ; Iterate over vector and create list.
    (vector-map! (lambda (value position)
                   (if (and (not (eq? value current-height)) (not (equal? position 0)))
                       (begin (set! current-height value)
                              (set! output (append output (list position value))))))
                 skyline-vector)
    ; Add the last coordinate to the vector.
    (append output (list (vector-length skyline-vector) 0))))
(equal? solution (create-skyline buildings))
Advertisements

Format USB as exFat in Ubuntu 13.10 terminal

Hi, Today I was trying to get an thumbdrive to work on OSX, Windows and Ubuntu. Most people format their thumbdrive as NTFS to store files bigger than 4 GB. Luckily for us there is a thing called exFat which can store files up to 17 179 869 184 GB. I think that is pretty future-proof. So what did I do?

1. Install exfat utilities in Ubuntu

sudo apt-get update && sudo apt-get install exfat-utils

2. Create a fresh partition on the thumbdrive
Note that /dev/sdb is my thumbdrive. Yours can differ. To get information on your drive you can use df and locate your drive. /dev/sdb is your drive and /dev/sdbn where n is any natural number is your partition. You can disregard those because we’re going to delete all of them. So execute following command to open up fdisk.

sudo fdisk /dev/sdb

Now you should see the fdisk. You can type several commands in this little (old) program. You can see all of them by typing m.

3. Create a partition
We want to create one new partition, so we type n. It will ask for some values which you can simply press enter for the default values. Now we have a partition which is not saved yet. But first we have to set our flag. The current partition should be flagged Linux. You can see this by typing the fdisk command p. To change the flag to exFat we have to type in the command t.  Fdisk will now ask for a number indicating the flag you want to set. We want number 7. (You can see all the flags by typing L). 

If we have done all this we simply write away our settings by typing the command w in fdisk.
4. Create a filesystem (exFat)
Now we have a partition but no filesystem yet! Let’s do that:

sudo mkfs.exfat /dev/sdb1

Note that you should replace the /dev/sdb1 part with your partition identifier. If you have done this your USB stick is ready!

 

Enjoy!