CODEWITHSUNDEEP
outputminizinc
Desiderius Severus
Desiderius Severus

Reputation: 141

Minizinc "filling in gaps"

I would like to "complete" an array in MiniZinc as follows.

Say I have an array a=[A,H,J,D,C] which is associated to certain integers between 1 and 6 (injectively), e.g. n=[4,2,1,6,5] so here the 3 is missing. I would like to output the array a corresponding to an increasing ordering of n and filling in the missing element (3) by a fixed content, say XXX. In the example it would be

[A,H,XXX,J,D,C]

The way I considered for now is to create a new array of 6 variables, and checking for all of them if they are in a and assigning them at the right position, and putting XXX if the position do not appear. This makes my program terrible slower (about five times slower!).

Are there more efficient options to do so?

Upvotes: 0

Views: 71

Answers (1)

Axel Kemper
Axel Kemper

Reputation: 11322

You could move the selection logic to functions solely called from within the output section:

int: not_found = 0;
array[1..5] of string: a = ["A", "H", "J", "D", "C"];
array[1..5] of var int: n = [4, 2, 1, 6, 5];

%  inspired by https://stackoverflow.com/a/44846993/1911064
%  This assumes that the value does not occur more than once.
%  Constant not_found has to be 0!
function int: index_of(int: item, array[int] of var int: items) = 
    sum( [ if item == fix(items[i]) then i else not_found endif | i in index_set(items) ]
   );
   
function string: str_select(array[int] of string: a, array[int] of var int: n, int: i) =
    let {
      int: index = index_of(i, n);
      int: gaps = sum([ index_of(j, n) == not_found | j in 1..i-1 ]);
    } in
    " " ++ if index != not_found then show(a[i - gaps]) else "xxx" endif;

output [ str_select(a, n, j) | j in 1..6];

This approach does not lead to additional constraints. Therefore, it should not cause extra solution time.

Upvotes: 1

Related Questions