Merge pull request #7048 from Firedrake/rogerbw-challenge-190

Solutions for challenge #190

1 files changed, 275 insertions, 0 deletions

diff --git a/challenge-190/roger-bell-west/postscript/ch-2.ps b/challenge-190/roger-bell-west/postscript/ch-2.ps
new file mode 100644
index 0000000000..f3dc30db30
--- /dev/null
+++ b/challenge-190/roger-bell-west/postscript/ch-2.ps
@@ -0,0 +1,275 @@
+%!PS
+
+% begin included library code
+% see https://github.com/Firedrake/postscript-libraries/
+/quicksort.partition {
+    3 dict begin
+    /pivot arr hi lo add 2 idiv get def
+    /i lo 1 sub def
+    /j hi 1 add def
+    {
+        {
+            /i i 1 add def
+            arr i get pivot ge {
+                exit
+            } if
+        } loop
+        {
+            /j j 1 sub def
+            arr j get pivot le {
+                exit
+            } if
+        } loop
+        i j ge {
+            j
+            exit
+        } if
+        i j quicksort.swap
+    } loop
+    end
+} bind def
+
+/test.end {
+    ( ) print
+    test.count 0 gt {
+        (Passed ) print
+        test.pass (...) cvs print
+        (/) print
+        test.count (...) cvs print
+        ( \() print
+        test.pass 100 mul test.count idiv (...) cvs print
+        (%\)) print
+        (\r\n) print
+    } if
+} bind def
+
+/map { % array proc -> array
+    2 dict begin
+    /p exch def
+    [ exch
+      {
+          p
+      } forall
+    ]
+} bind def
+
+/apush.right { % [a b] c -> [a b c]
+    exch
+    [ exch aload length 2 add -1 roll ]
+} bind def
+
+/strjoin % [(a) (b) (c)] (j) -> (ajbjc)
+{
+    3 dict begin
+    /j exch def
+    dup 0 get /out exch def
+    /first true def
+    {
+        first {
+            pop
+            /first false def
+        } {
+            out j strconcat
+            exch strconcat
+            /out exch def
+        } ifelse
+    } forall
+    out
+    end
+} bind def
+
+/test {
+    /test.count test.count 1 add def
+    {
+        /test.pass test.pass 1 add def
+    } {
+        ( ) print
+        test.count (....) cvs print
+        (-fail) print
+    } ifelse
+} bind def
+
+/quicksort.main { % lo hi -> (null)
+    3 dict begin
+    /hi exch def
+    /lo exch def
+    /xit false def
+    lo 0 lt {
+        /xit true def
+    } if
+    hi 0 lt {
+        /xit true def
+    } if
+    lo hi ge {
+        /xit true def
+    } if
+    xit not {
+        /p quicksort.partition def
+        lo p quicksort.main
+        p 1 add hi quicksort.main
+    } if
+    end
+} bind def
+
+/safestring {
+    dup length string cvs
+} bind def
+
+/apop.left { % [a b c] -> [b c] a
+    dup 0 get exch
+    [ exch aload length -1 roll pop ] exch
+} bind def
+
+/test.start {
+    print (:) print
+    /test.pass 0 def
+    /test.count 0 def
+} bind def
+
+/strconcat % (a) (b) -> (ab)  
+{ exch dup length
+  2 index length add string
+  dup dup 4 2 roll copy length
+  4 -1 roll putinterval
+} bind def
+
+/apop.right { % [a b c] -> [a b] c
+    [ exch aload length 1 add 1 roll ] exch
+} bind def
+
+/deepeq {
+    2 dict begin
+    /a exch def
+    /b exch def
+    a type b type eq {
+        a type /dicttype eq {
+            a length b length eq {
+                <<
+                    a {
+                        pop
+                        true
+                    } forall
+                    b {
+                        pop
+                        true
+                    } forall
+                >>
+                true exch
+                {
+                    pop
+                    dup a exch known {
+                        dup b exch known {
+                            dup a exch get exch b exch get deepeq not {
+                                pop false
+                            } if
+                        } {
+                            false
+                        } ifelse
+                    } {
+                        false
+                    } ifelse
+                } forall
+            } {
+                false
+            } ifelse
+        } {
+            a type dup /arraytype eq exch /stringtype eq or {
+                a length b length eq {
+                    true
+                    0 1 a length 1 sub {
+                        dup a exch get exch b exch get deepeq not {
+                            pop false
+                            exit
+                        } if
+                    } for
+                } {
+                    false
+                } ifelse
+            } {
+                a b eq
+            } ifelse
+        } ifelse
+    } {
+        false
+    } ifelse
+    end
+} bind def
+
+/keys { % dict -> array of dict keys
+    [ exch
+      {
+          pop
+      } forall
+    ]
+} bind def
+
+/quicksort.swap {
+    2 dict begin
+    /bi exch def
+    /ai exch def
+    arr ai get
+    arr bi get
+    arr exch ai exch put
+    arr exch bi exch put
+    end
+} bind def
+
+/quicksort { % [ a c b ] -> [ a b c ]
+    1 dict begin
+    /arr exch def
+    arr length 0 gt {
+        0 arr length 1 sub quicksort.main
+    } if
+    arr
+    end
+} bind def
+
+
+% end included library code
+
+/decodedlist {
+    7 dict begin
+    /s exch def
+    /stack [ [ s safestring ] ] def
+    /out 0 dict def
+    {
+        stack apop.left /ent exch def /stack exch def
+        ent apop.right /tail exch def /ent exch def
+        tail length 0 eq {
+            out ent true put
+        } {
+            tail 0 1 getinterval (0) deepeq not {
+                /stack stack [
+                    ent aload pop
+                    tail 0 1 getinterval
+                    tail 1 tail length 1 sub getinterval
+                ] apush.right def
+            } if
+            tail length 2 ge {
+                tail 0 2 getinterval cvi dup 1 ge exch 26 le and {
+                    /stack stack [
+                        ent aload pop
+                        tail 0 2 getinterval
+                        tail 2 tail length 2 sub getinterval
+                    ] apush.right def
+                } if
+            } if
+        } ifelse
+        stack length 0 eq {
+            exit
+        } if
+    } loop
+    /alphazero (A) 0 get 1 sub def
+    [
+        out keys {
+            { cvi alphazero add /tmp 1 string def tmp exch 0 exch put tmp safestring } map () strjoin
+        } forall
+    ] quicksort
+    end
+} bind def
+
+(decodedlist) test.start
+(11) decodedlist [ (AA) (K) ] deepeq test
+(1115) decodedlist [ (AAAE) (AAO) (AKE) (KAE) (KO) ] deepeq test
+(127) decodedlist [ (ABG) (LG) ] deepeq test
+test.end