/* Bridges to Somewhere problem in Picat. Problem from PuzzlOR Bridges to Somewhere (August 2009) http://puzzlor.editme.com/bridges """ The five residents of Hometown live in houses represented by the letters "A" through "E" as shown on the left side of Figure 1. The offices where they will be working are represented by their matching letters on the island of Worktown. Because a river lies between Hometown and Worktown, the residents are unable to get to work. They have in their budget enough funds to build two bridges that could connect Hometown to Worktown. The locations where these bridges could be built are indicated by the brown 1x3 hashed tiles. The two bridges can only be built in these approved areas. Once the bridges are built, the residents would then be able to commute to work. A commuter will always take the shortest path from home to work and can only travel in up, down, left or right directions (no diagonals). Each tile represents a 1-km-by-1-km distance. As an example, if bridge four were built, resident "E" would have to travel 10 km to reach his workplace. Hometown Bridge Worktown 0,0,0,0,0, 0,0,0, 0,0,0,0,0, 1 0,0,0,A,0, 1,1,1, 0,B,0,0,0, 2 0,B,0,0,0, 0,0,0, 0,0,0,0,0, 3 0,0,0,0,0, 0,0,0, 0,0,0,0,0, 4 0,0,0,0,0, 0,0,0, 0,0,0,0,0, 5 0,0,C,0,0, 0,0,0, 0,0,0,A,0, 6 0,D,0,0,0, 2,2,2, 0,0,0,0,0, 7 0,0,0,0,0, 0,0,0, 0,0,0,0,0, 8 0,0,0,0,0, 0,0,0, 0,C,0,0,0, 9 0,E,0,0,0, 3,3,3, 0,0,0,0,0, 10 0,0,0,0,0, 0,0,0, 0,0,0,0,0, 11 0,0,0,0,0, 4,4,4, 0,E,0,D,0, 12 0,0,0,0,0, 0,0,0, 0,0,0,0,0, 13 Question: Which two bridges should be built in order to minimize the total commuting distance of all residents? """ This is a port of the MiniZinc model http://hakank.org/minizinc/bridges_to_somewhere.mzn Solution (which is unique modulo symmetry) tot_dist: 58 bridges: [1, 3] Distances: A: 12 using bridge 1 (at row 2) B: 9 using bridge 1 (at row 2) C: 12 using bridge 2 (at row 10) D: 15 using bridge 2 (at row 10) E: 10 using bridge 2 (at row 10) Extra: If we where allowed to build 2 bridges at any place, then the optimal value is still 58 and the places are (up to symmetry) the following positions (rows) [2, 9] [3, 9] [2, 10] [3, 10] Extra 2: We can do a little better if we build 3 bridges with a total distance 56 km. tot_dist: 56 bridges: [1, 2, 3] Distances: A: 12 using bridge 1 (at row 2) B: 9 using bridge 1 (at row 2) C: 10 using bridge 2 (at row 7) D: 15 using bridge 2 (at row 7) E: 10 using bridge 3 (at row 10) There is an alternative solution using bridge 1, 2, and 4 tot_dist: 56 bridges: [1, 2, 4] Distances: A: 12 using bridge 1 (at row 2) B: 9 using bridge 1 (at row 2) C: 10 using bridge 2 (at row 7) D: 15 using bridge 2 (at row 7) E: 10 using bridge 3 (at row 12) With 4 bridges (go3/0) we don't gain anything. This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp. main => go. % % 2 bridges to build % % totDist = 58 % x = [1,3] % bix = [1,1,2,2,2] % % A: 12 using bridge 1 (at row 2) % B: 9 using bridge 1 (at row 2) % C: 12 using bridge 2 (at row 10) % D: 15 using bridge 2 (at row 10) % E: 10 using bridge 2 (at row 10) % go => NumBridgesToBuild = 2, build_bridges(NumBridgesToBuild,_TotDist), nl. % % 3 bridges to build % % totDist = 56 % x = [1,2,3] % bix = [1,1,2,2,3] % % A: 12 using bridge 1 (at row 2) % B: 9 using bridge 1 (at row 2) % C: 10 using bridge 2 (at row 7) % D: 15 using bridge 2 (at row 7) % E: 10 using bridge 3 (at row 10) % go2 => NumBridgesToBuild = 3, build_bridges(NumBridgesToBuild,_TotDist), nl. % % 4 bridges to build % % totDist = 56 % x = [1,2,3,4] % bix = [1,1,2,2,3] % % A: 12 using bridge 1 (at row 2) % B: 9 using bridge 1 (at row 2) % C: 10 using bridge 2 (at row 7) % D: 15 using bridge 2 (at row 7) % E: 10 using bridge 3 (at row 10) % go3 => NumBridgesToBuild = 4, build_bridges(NumBridgesToBuild,_TotDist), nl. % % % build_bridges(NumBridgesToBuild,TotDist) => NumP = 5, % number of people NumB = 4, % number of bridges % NumB = 13, % number of bridges (extra: build at bridge at any place) % How many bridges to build % NumBridgesToBuild = 2, % position of home/work pos(Pos), % x-coordinate of the bridges bridges(Bridges), % all_bridges(Bridges), % distances from home -> bridges (first cell) Dist1 = [ [abs(Pos[P,1] - Bridges[B])+ abs(Pos[P,2] - 6) : B in 1..NumB] : P in 1..NumP], println(dist1=Dist1), % distances from bridges (last cell) -> work Dist2 = [ [abs(Pos[P,3] - Bridges[B]) + abs(Pos[P,4] - (-1)) : B in 1..NumB] : P in 1..NumP], println(dist2=Dist2), str(Str), % % decision variables % % which bridges to build X = new_list(NumBridgesToBuild), X :: 1..NumB, % which is the nearest bridge BIx = new_list(NumP), BIx :: 1..NumB, % total distance TotDist #= sum( % MiniZinc version: % [min([Dist1[P,X[B]] + 1 + Dist2[P,X[B]] : B in 1..NumBridgesToBuild]) % % But Dist1[P,X[B]] is not allowed in Picat, % so we have to rewrite it using matrix_element/4 [min([T : B in 1..NumBridgesToBuild, matrix_element(Dist1,P,X[B],T1),matrix_element(Dist2,P,X[B],T2),T#=T1+1+T2]) : P in 1..NumP] ), % which bridge is the nearest (as index in x) ? foreach(P in 1..NumP) min_index(BIx[P], [T : B in 1..NumBridgesToBuild, matrix_element(Dist1,P,X[B],T1),matrix_element(Dist2,P,X[B],T2),T#=T1+1+T2]) end, % symmetry breaking all_different(X), increasing(X), Vars = X ++ BIx, solve($[min(TotDist)],Vars), println(totDist=TotDist), println(x=X), println(bix=BIx), nl, foreach(P in 1..NumP) BB = min([Dist1[P,X[B]] + 1 + Dist2[P,X[B]] : B in 1..NumBridgesToBuild]), printf("%w: %d using bridge %d (at row %d)\n",Str[P], BB, BIx[P], Bridges[X[BIx[P]]]) end, nl. % I assume that the indices are ordered and unique min_index(Mi, X) => MinX #= min(X), element(Mi,X,MinX). % % Data % % % 1 2 3 4 5 1 2 3 4 5 % 0,0,0,0,0, 0,0,0, 0,0,0,0,0, % 1 % 0,0,0,A,0, 1,1,1, 0,B,0,0,0, % 2 % 0,B,0,0,0, 0,0,0, 0,0,0,0,0, % 3 % 0,0,0,0,0, 0,0,0, 0,0,0,0,0, % 4 % 0,0,0,0,0, 0,0,0, 0,0,0,0,0, % 5 % 0,0,C,0,0, 0,0,0, 0,0,0,A,0, % 6 % 0,D,0,0,0, 2,2,2, 0,0,0,0,0, % 7 % 0,0,0,0,0, 0,0,0, 0,0,0,0,0, % 8 % 0,0,0,0,0, 0,0,0, 0,C,0,0,0, % 9 % 0,E,0,0,0, 3,3,3, 0,0,0,0,0, % 10 % 0,0,0,0,0, 0,0,0, 0,0,0,0,0, % 11 % 0,0,0,0,0, 4,4,4, 0,E,0,D,0, % 12 % 0,0,0,0,0, 0,0,0, 0,0,0,0,0, % 13 % pos(Pos) => Pos = [ % home work [ 2,4, 6,4], % A [ 3,2, 2,2], % B [ 6,3, 9,2], % C [ 7,2, 12,4], % D [10,2, 12,2] % E ]. % x coordinates for the bridges bridges(Bridges) => Bridges=[2,7,10,12]. % Testing: what if we can build 2 bridges at any places? % x coordinates for the bridges all_bridges(Bridges) => Bridges=[1,2,3,4,5,6,7,8,9,10,11,12,13]. str(Str) => Str=["A","B","C","D","E"].