fork download
copy 
  1. (def wall 9999)
  2. (def floor 2000)
  3. (def GOAL 0)
  4.  
  5. (def p [151 160 137 91 90 15 131 13 201 95 96 53 194 233 7 225
  6.         140 36 103 30 69 142 8 99 37 240 21 10 23 190 6 148
  7.         247 120 234 75 0 26 197 62 94 252 219 203 117 35 11 32
  8.         57 177 33 88 237 149 56 87 174 20 125 136 171 168 68 175
  9.         74 165 71 134 139 48 27 166 77 146 158 231 83 111 229 122
  10.         60 211 133 230 220 105 92 41 55 46 245 40 244 102 143 54
  11.         65 25 63 161 1 216 80 73 209 76 132 187 208 89 18 169
  12.         200 196 135 130 116 188 159 86 164 100 109 198 173 186 3 64
  13.         52 217 226 250 124 123 5 202 38 147 118 126 255 82 85 212
  14.         207 206 59 227 47 16 58 17 182 189 28 42 223 183 170 213
  15.         119 248 152 2 44 154 163 70 221 153 101 155 167 43 172 9
  16.         129 22 39 253 19 98 108 110 79 113 224 232 178 185 112 104
  17.         218 246 97 228 251 34 242 193 238 210 144 12 191 179 162 241
  18.         81 51 145 235 249 14 239 107 49 192 214 31 181 199 106 157
  19.         184 84 204 176 115 121 50 45 127 4 150 254 138 236 205 93
  20.         222 114 67 29 24 72 243 141 128 195 78 66 215 61 156 180
  21.         151 160 137 91 90 15 131 13 201 95 96 53 194 233 7 225
  22.         140 36 103 30 69 142 8 99 37 240 21 10 23 190 6 148
  23.         247 120 234 75 0 26 197 62 94 252 219 203 117 35 11 32
  24.         57 177 33 88 237 149 56 87 174 20 125 136 171 168 68 175
  25.         74 165 71 134 139 48 27 166 77 146 158 231 83 111 229 122
  26.         60 211 133 230 220 105 92 41 55 46 245 40 244 102 143 54
  27.         65 25 63 161 1 216 80 73 209 76 132 187 208 89 18 169
  28.         200 196 135 130 116 188 159 86 164 100 109 198 173 186 3 64
  29.         52 217 226 250 124 123 5 202 38 147 118 126 255 82 85 212
  30.         207 206 59 227 47 16 58 17 182 189 28 42 223 183 170 213
  31.         119 248 152 2 44 154 163 70 221 153 101 155 167 43 172 9
  32.         129 22 39 253 19 98 108 110 79 113 224 232 178 185 112 104
  33.         218 246 97 228 251 34 242 193 238 210 144 12 191 179 162 241
  34.         81 51 145 235 249 14 239 107 49 192 214 31 181 199 106 157
  35.         184 84 204 176 115 121 50 45 127 4 150 254 138 236 205 93
  36.         222 114 67 29 24 72 243 141 128 195 78 66 215 61 156 180])
  37.  
  38. (defn fade
  39.   [t]
  40.   (* t t t (+ (* t (- (* t 6) 15.0)) 10.0)))
  41.  
  42. (defn lerp
  43.   [t a b]
  44.   (+ a (* t (- b a))))
  45.  
  46. (defn grad
  47.   [hash x y z]
  48.   (let [h (bit-and hash 15)
  49.         u (if (< h 8) x y)
  50.         v (if (< h 4) y (if (or (= h 12) (= h 14)) x z))]
  51.     (+ (if (= (bit-and h 1) 0) u (- u))
  52.        (if (= (bit-and h 2) 0) v (- v)))))
  53.  
  54. (defn noise
  55.   [x y z]
  56.   (let [X (bit-and (long x) 255)
  57.         Y (bit-and (long y) 255)
  58.         Z (bit-and (long z) 255)
  59.         xx (- x (long x))
  60.         yy (- y (long y))
  61.         zz (- z (long z))
  62.         u (fade xx)
  63.         v (fade yy)
  64.         w (fade zz)
  65.         A (+ (p X) Y)
  66.         AA (+ (p A) Z)
  67.         AB (+ (p (+ A 1)) Z)
  68.         B (+ (p (+ X 1)) Y)
  69.         BA (+ (p B) Z)
  70.         BB (+ (p (+ B 1)) Z)]
  71.     (lerp w
  72.           (lerp v
  73.                 (lerp u
  74.                       (grad (p AA) xx yy zz)
  75.                       (grad (p BA) (- xx 1) yy zz))
  76.                 (lerp u
  77.                       (grad (p AB) xx (- yy 1) zz)
  78.                       (grad (p BB) (- xx 1) (- yy 1) zz)))
  79.           (lerp v
  80.                 (lerp u
  81.                       (grad (p (+ AA 1)) xx yy (- zz 1))
  82.                       (grad (p (+ BA 1)) (- xx 1) yy (- zz 1)))
  83.                 (lerp u
  84.                       (grad (p (+ AB 1)) xx (- yy 1) (- zz 1))
  85.                       (grad (p (+ BB 1)) (- xx 1) (- yy 1) (- zz 1)))))))
  86.  
  87. (def dungeon 
  88.   (vec (concat
  89.      (repeat 61 wall)
  90.      (flatten
  91.        (interleave
  92.          (partition 58 (last (take (+ (rand-int 10) 10) (iterate #(assoc % (rand-int (* 58 58)) GOAL)
  93.            (vec (map #(if (< % 0.11) 2000 9999)
  94.              (repeatedly (* 58 58) #(noise (* (rand-int 50000)0.01) (* (rand-int 50000) 0.01) (* (rand-int 50000) 0.01)))))))))
  95.          (repeat [wall wall])))
  96.      (repeat 59 wall))))
  97. (defn find-goals [m]
  98.   (into {} (for [x (keep-indexed #(if (= %2 0) %1) dungeon)] [x 0])))
  99.  
  100. (defn find-walls [m]
  101.   (into {} (for [x (keep-indexed #(if (= %2 wall) %1) dungeon)] [x wall])))
  102.  
  103. (defn find-floors [m]
  104.   (into {} (for [x (keep-indexed #(if (= %2 floor) %1) dungeon)] [x floor])))
  105.  
  106. (defn step-value [d x]
  107.   (if (> d floor)
  108.     d
  109.    (if (> (dec d) (val x))
  110.      (inc (val x)))))
  111.  
  112. (defn step [m x]
  113.   (if (= (val x) wall)
  114.     [{(key x) wall}]
  115.     (let [n (m (- (key x) 60))
  116.           s (m (+ (key x) 60))
  117.           w (m (- (key x) 1 ))
  118.           e (m (+ (key x) 1 ))
  119.           rv
  120.           (filter #(distinct? (val (first %)) wall nil)
  121.                   [{(- (key x) 60) (step-value n x)}
  122.                    {(+ (key x) 60) (step-value s x)}
  123.                    {(- (key x) 1 ) (step-value w x)}
  124.                    {(+ (key x) 1 ) (step-value e x)}])]                                                           
  125.       rv)))                          
  126.  
  127. (defn merge-maps [a b]
  128.   (merge-with min a b))
  129.  
  130. (defn dijkstra
  131.   ([m]
  132.      (dijkstra m (find-walls m) (find-goals m)))
  133.   ([m closed open]
  134.      (if (empty? open)
  135.        (merge-with min closed (into {} (map #(assoc % 1 9999) (find-floors m))))
  136.        (recur
  137.         m
  138.         (merge-with min closed open)
  139.         (let [ms (flatten (map #(step (fn [index] (or (closed index) (m index))) %) open))]
  140.           (reduce merge-maps {} ms))))))
  141.  
  142. (defn -main
  143. 	[& args]
  144. 	(time (do ;(println (str (into (sorted-map) (dijkstra dungeon))))
  145. 	      (println (clojure.string/replace (reduce #(str %1 (if (= (val %2) wall) "####" (format "%4d" (val %2) ))) "" (into (sorted-map) (dijkstra dungeon))) #"(.{240})" "$1\n"))
  146. 	      )))
  147. (-main)
Success #stdin #stdout 2.02s 389120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
################################################################################################################################################################################################################################################
########  36  35  34  33  32  31  30  29  28  27  28  29  30  31  32  33  34  35  36############################   5   6####  14  13  12  11################################################  10   9  10####  30  29  28  27  26  27  26########
####  36  35  34  33  32  31  30  31  30####  26  27####  31  32  31  32  33  34####  38########################   4####  16  15####  11  10  11########  18############################  10####   8   9############  27####  25####  25########
####  35  34  33  32  31  30  29########  26  25  26  27########  30####  34####  38  37  38  39  40########   4   3   4########  11  10   9  10  11####  17############################   9   8   7   8   9  10####  26  25  24  23  24  25####
########  33  32####  30  29  28########  25  24  25  26####  28  29####  35  36  37  36####  40  41############   2####   2########   9   8############  16  15  14########  13  12  11  10####   6   7   8############  26####  22############
############  31  30  29  28  27  26  25  24  23  24  25####  27########  36####  36  35  34####################   1   0   1   2   3####   7   8####  16  15  14  13####  11########  12########   5############################  21############
################  31  30  29########  24  23  22  23  24  25  26  27################  34  33  32  31########   3   2   1   2####   4   5   6   7####  15  14  13  12  11  10####   8####   6   5   4########################  19  20  21  22####
########################  30############  22  21  22  23########  26  27  28  29########  32  31  30################   2   3   4####   6   7   8   9########  12  11  10   9   8   7   6   7####   3   4####################  18########  23####
############################################  20  21  22  23  24  25####  29####################  29########   9   8####   4############   8####  10####  14  13  12  11  10   9####   5########   2####################  16  17  18############
############################################  19  20  21  22  23############  23############  29  28############   7   6   5########  10   9  10  11  12  13  14####  12########   5   4   3   2   1   2################  15  16  17####  19####
############################################  18  19  20  21############  21  22########  29  28  27################   7   6   7   8   9  10  11  12  13####  13  12########   7   6########   1   0   1   2############  14  15  16  17  18####
########################################  16  17  18  19  20########  19  20  21  22  23########  26####  32  31  30########   8   9  10  11####  13  14  13  12  11  10   9   8####   4   3   2   1   2####  10####  12  13  14  15############
################  21  20####  22####  16  15  16################  17  18########  21  22  23####  25  26########  29  30  31####  10  11  12  13####  15####  13  12  11  10########   5####   3############   9  10  11####  13####  19  18####
########  22####  20  19  20  21########  14####  16  15####  15  16  17  18  19  20  21  22  23  24  25  26  27  28####  32####  11####  13  14####  16####  14  13  12  11  12  13####   5   4   5   6   7   8   9####  11  12  13####  17####
########  21########  18################  13########  14  13  14  15  16############  22####  22########  27########  31  32####  12  13  14########  17  16  15  14  13  12  11####   9####   5####   7   8####  10   9  10####  14  15  16####
####  21  20  19####  17  16####  14  13  12  11  10####  12  13  14  15########  18####  20  21  22  23####  30  29  30####################  18  17  16  15  14  13  12  11  10   9   8   7   6   7####   9  10   9   8   9########  16########
############  18  17  16  15  14  13########  10   9  10  11  12  13  14  15  16  17  18  19  20####  24  25####  28  29  30  31####  22  23####  18####  16####  14  13  12####  10########   7   8   9####   9   8   7   8   9  10####  12####
########  20  19####  17  16####  12####  10   9   8####  12  13  14########  17  18####  20  21####  25  26  26  27####  29  30####  21  22####  19  18  17  16  15  14  13####################   8   9####   8   7   6####  10   9  10  11####
####  22  21  20####  18  17####  11  10   9####   7   8############  20  19################  22  23########  25  26  27  28  29####  20####  22####  19####  17  16  15  14################   6   7####   8   7   6   5########   8   9########
####  23  22  21####  19  18  19########   8   7   6   7   8   9####  19  18####  18  19  20  21########  23  24  25  26  27####  18  19  20  21################  17########   1   2####   4   5   6####   7####   5   4   5   6   7   8   9####
####  24  23########  20  19  20####  10   9####   5   6   7   8   9####  17  16  17########  20  20  21  22  23  24  25########  17####  19  20############  19  18####   1   0   1   2   3   4   5   6   6   5   4   3########   8   9  10####
########  24  25############################   3   4   5########  10  11####  15  16  17  18  19  19  20  21####  25####  16  15  16  17  18  19  18  17  18############   2####   2   3   4####   6########   6####   2   1   0########  11####
####   9########   6   5####   2   1   0   1   2   3########  10####  12####  14####  16####  19  18  19  20  21####  16  15  14####################  16  17  18  19  20####   4   3   4####   8####   5   6   5   6####   2########  13  12####
####   8   7   6   5   4   3   2   2   1   2   3   4   5####   9  10  11  12  13  14  15  15####  17####  19########  15  14  13  12  11  12  13  14  15########  20####   6   5####   5   6   7####   4####   4   5############################
####   7   6   5############   1   2   2############   6   7   8########  13####  15####  14  15  16  17  18  19####  16  15####  11  10########  15  16  17  18########################   7########   3   2   3   4   5   6########   9  10####
########   5   4   3   2   1   0####   3   4####   8########   9  10  11  12  13####  12  13  14  15  16  17  18  19################   9   8########  17  18####   4################   6####   4   3   2   1   2   3   4   5   6   7   8   9####
############   5   4   3   2   1####   4   5   6   7   8   9####  11############  12  11  12  13  14  15########  20################   8   7   6################   3   4####   7   6   5   4   3   2   1   0   1   2   3####   7   8   9  10####
########   7   6########   3   2   3   4########   8   9  10########  12  13  12  11  10  11  12  13########  22  21################   7####   5####   1   0   1   2   3####   8####   6   5   4   3   2####   2   3   4############  10  11####
####   9   8   7####   5   4########   5####   9   9  10####  11  10  11  12  11####   9  10############  24  23  22################   6   5   4   3   2   1   2################  12####   6   5########   4   3   4   5   6   7   8   9  10####
########   9   8####   6####  10####   6   7   8########  11  10   9  10  11  10   9   8####################  24################################   4####   2   3########  13  12  11  10####   6############   4########   7   8####  10  11####
####  11  10   9   8   7   8   9   8   7   8####  12####  10####   8   9  10   9   8   7########################  14############  25  24  25  26########   3   4########  12  11  10   9   8   7   8############  18############  12  11  12####
####  12  11  10   9   8   9  10   9   8   9  10  11  10   9   8   7   8   9########   6   7####   9  10  11  12  13################  23####  27  28  29####   5########  13  12############   8   9  10####  18  17  16  15  14  13############
####  13########  10   9####  11####   9  10  11####  11####   7   6   7####   3   4   5   6   7   8############  14####  21  20  21  22####  28########   7   6   7####  14  13  12  11  10   9####  11  12####  16  17####  15################
####  14  15####  11####  15####################  13  12####   6   5####   1   2####   6   7####   9  10  11  12####  19####  19  20########################   7   8####  15  14  13####  11####  13  12  13  14  15####  17  16  17  18  19####
####  15####  13  12  13  14  14####  12####  15  14  13####   5   4####   0################  11  10  11  12########  18  17  18  19  20####  20  19################  16  15  14  13  12  11############  14####  15  16  17####  18  19  20####
####  16  15  14  13####  14  13  12  11############  14####   4   3   2   1   2########   7####  11####################  16  17  18  19########  18############################  14####  10   9  10####  14####  14  15####  20  19  20  21####
####  17  16####  14####  13  12####  10  11  12  13########   5   4   3####   3   4   5   6   7####  11############  14  15############  15  16  17  18################  13  12####  10   9   8   9####  13####  13  14  15########  21########
####  18########  14  13  12  11  10   9####  13####   7   8####   5####   5   4####   6   7   8   9  10####  15  14  13################  14  15  16  17####################  11  10   9   8   7####  13  12  11  12  13  14####################
####  19####  16  15  14####  10   9   8########   5   6####  11####   9####   5   6####   8####  10########  15####  12################  13  14  15########  18####  14  13####   9   8####   6   7########  10  11  12  13  14  15############
####  20########################   8   7   6   5   4####  11  10   9   8   7   6   7   8   9####  11  12  13  14####  11  10   9  10  11  12############  16  17####  13  12####   8   7   6   5####   9   8   9####  13####  15################
####  21############################   6   5   4   3   4####  11  10####   8   7   8####  10  11########  14  15########   9   8####  12################  15########  12  11  10   9########   4   5####   7   8################################
############################   9   8####   4   3   2############  11  10   9   8   9  10####  12####  16  15  16  17####   8   7   8####  10####  12####  14  15  16####  12####  10####   2   3####   5   6   7####  15########  18  19########
################   9  10   9   8   7   6   5####   1   0####   4####  11############  11  12  13  14  15  16####  18########   6####   8   9  10  11  12  13  14####  14  13########   2   1   2   3   4############  14  15  16  17####  19####
################   8####   8   7   6####   4   3   2   1   2   3   4####  15  14  13  12####  12  13  14  15########   3   4   5   6   7################  14####  16  15####   3   2   1   0   1   2####   6####  14  13  14  15####  17  18####
################   7   6####   6   5   4   5####   3####   3   4####  17  16  15  14####  10  11  12########   0   1   2   3   4   5   6####  18  17  16  15  16########   7####   3####   1####   3   4   5########  12  13  14####  16  17####
####################   5############   3   4   5   4########   5############  16########   9  10####   3   2   1   2   3####   5####################  17####  17  18####   6   5   4   5####   5   4   5####   9####  11  12  13  14  15  16####
################   5   4   3   2   1   2   3   4   5   6   7   6   7   8########  10   9   8####   5   4   3   2   3   4####   6   7   8####################  18####   8   7####   5   6   7   6####   6   7   8   9  10########  15  16  17####
####################   3   2   1   0   1   2####   6####   8####   8   9  10  10   9   8   7   6####   4   3############   8   7####################  16  17########   9####   7   6   7   8####   8   7   8   9  10  11  12########  17########
################   5   4   3########   2   3   4   5################################   7   6   5   4   3   2   3########   9   8####################  15################   9   8   7####   9########   8   9  10  11  12########################
####################   5   4############   4   5   6####  10  11########   9   8####   6   5   4####   2   1############  10################  16####  14  13  12  11  10   9####   8####  10  11  10   9####  11################################
####################   6   5########  10########   7   8   9  10  10   9   8   7   6   5   4   3   2   1   0############  11  12  13####  16  15  14  13  12  11  10####   8   7   8############  11############################################
############   9   8   7   6   7   8   9########   8####  10  11############   8   7   6   5####   3   2################  12  13  14  15####  14  13  12  11####   9   8   7   6   7   8   9####  11  12########################################
########  11  10   9   8########   9  10################  11  12############   9####   7   6   7########  34############  13####  15  15####  13  12  11  10   9########   6   5####   9  10   9  10  11  12####################################
########  12  11  10################  11  12########  13  12####  20############   9   8   7   8####  32  33  34########  14####  15  14  13  12  11########   8####   6   5   4   5########   8####  12  13  14################################
####  14  13  12####  16  17  18########  13  14  15  14########  19############  10   9   8   9####  31  32################  17  16  15########  10####   8   7####   5####   3####   5####   7   8####  14  15################################
########  14  13  14  15  16  17  18  19############  15  16  17  18########  23####  10####  10####  30####################  18####  16  17####   9   8   7   6   5   4   3   2####   4   5   6   7########  16  17  18########################
####  16  15  14  15  16  17  18  19  20  19  18  17  16  17####  19  20  21  22####  11  12########  29  28  27  26####  20  19############  11  10   9####   7   6########   1   2   3   4############  18  17####  19########################
####  17  16  15####  17########  20  21  20  19  18  17########  20  21####  23  24############  29  28  27  26  25########  20####  24####  12  11  10################   1   0   1   2####################  18  19############################
########  17  16  17  18########  21  22  21########  18  19####  21  22  23  24  25  26  27####  30########  25  24  23  22  21  22  23  24########################   3   2   1   2############################  20############################
################################################################################################################################################################################################################################################

"Elapsed time: 368.915001 msecs"
https://ideone.com/YnhoF3
Dijkstra stuff. 60x60
language:
Clojure (clojure 1.10.0)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!