/prog/ Challenge -- Hydrocarbons [Heroic]

The challenge: Develop a program that takes in the notation of a hydrocarbon in standard form, and outputs a correct ball-and-stick graphical representation of that hydrocarbon.

The Deadline: 2010-08-30 20:00

Your implementation will be judged based on the following guidelines:


1. Accuracy
2. Consistency
3. Run time
4. Clarity of output
5. Code readability
6. Overall functionality


Good Luck!

This code solves the problem of finding connected multigraphs without self-edges with C vertices of degree 4 and H vertices of degree 1. No pruning or further checking is done.

Returned are the edges of the C vertices. Adding the H edges and visualising the graph is left as an exercise for the reader.

#lang racket

(require racklog)

(define (main)
  (let/ec break
    (displayln "Amount of carbon atoms?")
    (define C (string->number (read-line)))
    (displayln "Amount of hydrogen atoms?")
    (define H (string->number (read-line)))
    (when (or (not (integer? C))
              (not (positive? C))
              (not (integer? H))
              (not (positive? H))
              (odd? H))
      (displayln "Invalid input")
      (break))
   
    (define C-bonds (/ (- (* C 4) H) 2))
   
    (define %bind
      (%rel (i j n a b)
        ((i j n a b)
         (%=:= n 0) !
         (%= b empty))
        ((i j n a b)
         (%>= i C) !
         %fail)
        ((i j n a b)
         (%or (%is 4 (hash-ref a i 0)) (%>= j C)) !
         (%let (i* j*)
           (%and
            (%is i* (+ i 1))
            (%is j* (+ i* 1))
            (%bind i* j* n a b))))
        ((i j n a b)
         (%is #t (< (hash-ref a j 0) 4))
         (%let (n* a-i a-ij b*)
           (%and
            (%is n* (- n 1))
            (%is a-i (hash-update a i add1 0))
            (%is a-ij (hash-update a-i j add1 0))
            (%bind i j n* a-ij b*)
            (%= b (cons (list i j) b*)))))
        ((i j n a b)
         (%let (j*)
           (%and
            (%is j* (+ j 1))
            (%bind i j* n a b))))))
   
    (define %connect
      (%rel (i j a b)
        ((i j a b)
         (%>= i C) !
         (%bind 0 1 (- C-bonds (- C 1)) a b))
        ((i j a b)
         (%>= j i) !
         %fail)
        ((i j a b)
         (%let (j*)
           (%and
            (%is j* (+ j 1))
            (%connect i j* a b))))
        ((i j a b)
         (%is #t (< (hash-ref a j 0) 4))
         (%let (i* a-i a-ij b*)
           (%and
            (%is a-i (hash-update a i add1 0))
            (%is a-ij (hash-update a j add1 0))
            (%is i* (+ i 1))
            (%connect i* 0 a-ij b*)
            (%= b (cons (list j i) b*)))))))
   
    (displayln (cdar (%which (b) (%connect 1 0 (make-immutable-hash empty) b))))
    (let loop ()
      (displayln "Press enter for another result")
      (let ((ln (read-line)))
        (when (not (eof-object? ln))
          (displayln (cdar (%more)))
          (loop))))))

(main)