Problem

Find the max and min of sum of all permutations of [1..9] satisfying the following condition:

1
2
3
4
5
6
sum
== a[1] + a[2] + a[3]
== a[3] + a[4] + a[5]
== a[5] + a[6] + a[7]
== a[7] + a[8]
where sum = a[0] + a[1]

A permutation satisfying that condition is a = [9,4,1,8,3,2,5,6,7], and sum is 13.

Solution

Originally, I thought I need some kind of constraint programming, but the problem size is small enough that I can brute-force it… The complete code looks fairly succinct.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import Data.List

candidates = permutations [1..9]

predicate list =
and $
[ sum == (list !! 1 + list !! 2 + list !! 3)
, sum == (list !! 3 + list !! 4 + list !! 5)
, sum == (list !! 5 + list !! 6 + list !! 7)
, sum == (list !! 5 + list !! 6 + list !! 7)
, sum == (list !! 7 + list !! 8)
]
where sum = get_sum list

get_sum list = list !! 0 + list !! 1

main =
mapM_ print $ map ((,) <$> id <*> get_sum) $ filter predicate candidates