From 947c639ec646b67d1e434759a80eebfffedafe8d Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Sun, 24 Sep 2017 23:25:42 -0700 Subject: 4005 https://www.reddit.com/r/ProgrammingLanguages/comments/727va7/a_comparison_of_lisps/dnh2q6u --- html/nqueens.mu.html | 202 ++++++++++++++++++++++++++------------------------- nqueens.mu | 4 + 2 files changed, 107 insertions(+), 99 deletions(-) diff --git a/html/nqueens.mu.html b/html/nqueens.mu.html index 0e10c100..6180c160 100644 --- a/html/nqueens.mu.html +++ b/html/nqueens.mu.html @@ -59,105 +59,109 @@ if ('onhashchange' in window) {

- 1 # http://rosettacode.org/wiki/N-queens_problem
- 2 # port of the Arc solution at http://arclanguage.org/item?id=19743
- 3 # run with tracing turned on:
- 4 #   ./mu --trace nqueens.mu
- 5 
- 6 container square [
- 7   rank:num
- 8   file:num
- 9 ]
-10 
-11 def nqueens n:num, queens:&:list:square -> result:num, queens:&:list:square [
-12   local-scope
-13   load-ingredients
-14   # if 'queens' is already long enough, print it and return
-15   added-so-far:num <- length queens
-16   {
-17   ¦ done?:bool <- greater-or-equal added-so-far, n
-18   ¦ break-unless done?
-19   ¦ stash queens
-20   ¦ return 1
-21   }
-22   # still work to do
-23   next-rank:num <- copy 0
-24   {
-25   ¦ break-unless queens
-26   ¦ first:square <- first queens
-27   ¦ existing-rank:num <- get first, rank:offset
-28   ¦ next-rank <- add existing-rank, 1
-29   }
-30   result <- copy 0
-31   next-file:num <- copy 0
-32   {
-33   ¦ done?:bool <- greater-or-equal next-file, n
-34   ¦ break-if done?
-35   ¦ curr:square <- merge next-rank, next-file
-36   ¦ {
-37   ¦ ¦ curr-conflicts?:bool <- conflict? curr, queens
-38   ¦ ¦ break-if curr-conflicts?
-39   ¦ ¦ queens:&:list:square <- push curr, queens
-40   ¦ ¦ sub-result:num <- nqueens n, queens
-41   ¦ ¦ result <- add result, sub-result
-42   ¦ ¦ queens <- rest queens
-43   ¦ }
-44   ¦ next-file <- add next-file, 1
-45   ¦ loop
-46   }
-47 ]
-48 
-49 def conflict? curr:square, queens:&:list:square -> result:bool [
-50   local-scope
-51   load-ingredients
-52   result1:bool <- conflicting-file? curr, queens
-53   return-if result1, result1
-54   result2:bool <- conflicting-diagonal? curr, queens
-55   return result2
-56 ]
-57 
-58 def conflicting-file? curr:square, queens:&:list:square -> result:bool [
-59   local-scope
-60   load-ingredients
-61   curr-file:num <- get curr, file:offset
-62   {
-63   ¦ break-unless queens
-64   ¦ q:square <- first queens
-65   ¦ qfile:num <- get q, file:offset
-66   ¦ file-match?:bool <- equal curr-file, qfile
-67   ¦ return-if file-match?, 1/conflict-found
-68   ¦ queens <- rest queens
-69   ¦ loop
-70   }
-71   return 0/no-conflict-found
-72 ]
-73 
-74 def conflicting-diagonal? curr:square, queens:&:list:square -> result:bool [
-75   local-scope
-76   load-ingredients
-77   curr-rank:num <- get curr, rank:offset
-78   curr-file:num <- get curr, file:offset
-79   {
-80   ¦ break-unless queens
-81   ¦ q:square <- first queens
-82   ¦ qrank:num <- get q, rank:offset
-83   ¦ qfile:num <- get q, file:offset
-84   ¦ rank-delta:num <- subtract qrank, curr-rank
-85   ¦ file-delta:num <- subtract qfile, curr-file
-86   ¦ rank-delta <- abs rank-delta
-87   ¦ file-delta <- abs file-delta
-88   ¦ diagonal-match?:bool <- equal rank-delta, file-delta
-89   ¦ return-if diagonal-match?, 1/conflict-found
-90   ¦ queens <- rest queens
-91   ¦ loop
-92   }
-93   return 0/no-conflict-found
-94 ]
-95 
-96 def main [
-97   nqueens 4
-98   $dump-trace [app]
-99 ]
+  1 # http://rosettacode.org/wiki/N-queens_problem
+  2 # port of the Arc solution at http://arclanguage.org/item?id=19743
+  3 # run with tracing turned on:
+  4 #   ./mu --trace nqueens.mu
+  5 
+  6 container square [
+  7   rank:num
+  8   file:num
+  9 ]
+ 10 
+ 11 def nqueens n:num, queens:&:list:square -> result:num, queens:&:list:square [
+ 12   local-scope
+ 13   load-ingredients
+ 14   # if 'queens' is already long enough, print it and return
+ 15   added-so-far:num <- length queens
+ 16   {
+ 17   ¦ done?:bool <- greater-or-equal added-so-far, n
+ 18   ¦ break-unless done?
+ 19   ¦ stash queens
+ 20   ¦ return 1
+ 21   }
+ 22   # still work to do
+ 23   next-rank:num <- copy 0
+ 24   {
+ 25   ¦ break-unless queens
+ 26   ¦ first:square <- first queens
+ 27   ¦ existing-rank:num <- get first, rank:offset
+ 28   ¦ next-rank <- add existing-rank, 1
+ 29   }
+ 30   result <- copy 0
+ 31   next-file:num <- copy 0
+ 32   {
+ 33   ¦ done?:bool <- greater-or-equal next-file, n
+ 34   ¦ break-if done?
+ 35   ¦ curr:square <- merge next-rank, next-file
+ 36   ¦ {
+ 37   ¦ ¦ curr-conflicts?:bool <- conflict? curr, queens
+ 38   ¦ ¦ break-if curr-conflicts?
+ 39   ¦ ¦ queens:&:list:square <- push curr, queens
+ 40   ¦ ¦ sub-result:num <- nqueens n, queens
+ 41   ¦ ¦ result <- add result, sub-result
+ 42   ¦ ¦ queens <- rest queens
+ 43   ¦ }
+ 44   ¦ next-file <- add next-file, 1
+ 45   ¦ loop
+ 46   }
+ 47 ]
+ 48 
+ 49 # check if putting a queen on 'curr' conflicts with any of the existing
+ 50 # queens
+ 51 # assumes that 'curr' is on a non-conflicting rank, and checks for conflict
+ 52 # only in files and diagonals
+ 53 def conflict? curr:square, queens:&:list:square -> result:bool [
+ 54   local-scope
+ 55   load-ingredients
+ 56   result1:bool <- conflicting-file? curr, queens
+ 57   return-if result1, result1
+ 58   result2:bool <- conflicting-diagonal? curr, queens
+ 59   return result2
+ 60 ]
+ 61 
+ 62 def conflicting-file? curr:square, queens:&:list:square -> result:bool [
+ 63   local-scope
+ 64   load-ingredients
+ 65   curr-file:num <- get curr, file:offset
+ 66   {
+ 67   ¦ break-unless queens
+ 68   ¦ q:square <- first queens
+ 69   ¦ qfile:num <- get q, file:offset
+ 70   ¦ file-match?:bool <- equal curr-file, qfile
+ 71   ¦ return-if file-match?, 1/conflict-found
+ 72   ¦ queens <- rest queens
+ 73   ¦ loop
+ 74   }
+ 75   return 0/no-conflict-found
+ 76 ]
+ 77 
+ 78 def conflicting-diagonal? curr:square, queens:&:list:square -> result:bool [
+ 79   local-scope
+ 80   load-ingredients
+ 81   curr-rank:num <- get curr, rank:offset
+ 82   curr-file:num <- get curr, file:offset
+ 83   {
+ 84   ¦ break-unless queens
+ 85   ¦ q:square <- first queens
+ 86   ¦ qrank:num <- get q, rank:offset
+ 87   ¦ qfile:num <- get q, file:offset
+ 88   ¦ rank-delta:num <- subtract qrank, curr-rank
+ 89   ¦ file-delta:num <- subtract qfile, curr-file
+ 90   ¦ rank-delta <- abs rank-delta
+ 91   ¦ file-delta <- abs file-delta
+ 92   ¦ diagonal-match?:bool <- equal rank-delta, file-delta
+ 93   ¦ return-if diagonal-match?, 1/conflict-found
+ 94   ¦ queens <- rest queens
+ 95   ¦ loop
+ 96   }
+ 97   return 0/no-conflict-found
+ 98 ]
+ 99 
+100 def main [
+101   nqueens 4
+102   $dump-trace [app]
+103 ]

diff --git a/nqueens.mu b/nqueens.mu index 95955784..87ce90b6 100644 --- a/nqueens.mu +++ b/nqueens.mu @@ -46,6 +46,10 @@ def nqueens n:num, queens:&:list:square -> result:num, queens:&:list:square [ } ] +# check if putting a queen on 'curr' conflicts with any of the existing +# queens +# assumes that 'curr' is on a non-conflicting rank, and checks for conflict +# only in files and diagonals def conflict? curr:square, queens:&:list:square -> result:bool [ local-scope load-ingredients -- cgit 1.4.1-2-gfad0