blob: 5801a52c8577488d3e032d626ae22f254ced82eb (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#!/usr/bin/env -S mira -exec
matrix == [[num]]
main = lay ( "matrix:":(map show mat)
++ [ ""
, "tour: " ++ show besttour
, "length: " ++ show (length mat besttour)
]
)
where
arg = $* ! 1
mat = (mkrandmat . numval) arg, if (and . map digit) arg
= readmat arg, otherwise
tour t = t ++ [t ! 0]
besttour = (minby (length mat) . map tour . perms) [0 .. #mat - 1]
length :: matrix -> [num] -> num
length mat tour = (sum . map get . zip2 tour . tl) tour
where
get (i,j) = mat ! j ! i
mkrandmat :: num -> matrix
mkrandmat n = [ [ f i j (rand ! (i * n + j)) | i <- [1..n] ] | j <- [1..n] ]
where
rand = (map ((+) 1 . (mod 9) . code) . readb) "/dev/random"
f i j = const 0, if i == j
= id, otherwise
readmat :: [char] -> matrix
readmat = map (map numval . words) . lines . read
words :: [char] -> [[char]]
words [] = []
words (x:xs) = []:words xs, if x = ' '
= (x:y):ys, otherwise
where
(y:ys) = words xs, if xs ~= []
= []:[], otherwise
perms :: [*] -> [[*]]
perms [] = [[]]
perms x = [ a:y | a <- x; y <- perms (x -- [a]) ]
minby :: (* -> num) -> [*] -> *
minby f (x:xs) = g x (f x) xs
where
g v mv [] = v
g v mv (x:xs) = g x mx xs, if mx < mv
= g v mv xs, otherwise
where
mx = f x
|
