How to iterate the result of combination padlock until condition fulfilled, then break, without creating cartesian product first?

Question

For example, suppose I have a combination padlock, which can be simulated with 2d array:

const array_2d=[
    ["HUGE","TALL","TINY"],
    ["BLUE","CYAN","DARK","GOLD","GRAY"],
    .
    .
    .
    (other wheels)
    ["BIRD","FISH","GOAT","MOTH"]
];

which each inner array represents a wheel of the lock. In the business code I would like to iterate the result until some conditions fulfilled, for example, in simple here, move the wheel until a combination has 3 or more "A",ie:

TALL ... ... ... CYAN GOAT

How to write loops that iterates the result of those combinations of wheels:

HUGE BLUE ... ... ... BIRD
HUGE BLUE ... ... ... FISH
.
.
.
HUGE CYAN ... ... ... BIRD
HUGE CYAN ... ... ... FISH
.
.
.

until condition fulfilled (3 or more "A"):

TALL ... ... ... CYAN GOAT

?

I don't want to create cartesian product first and then iterating those cartesian product result, because in business code the incoming data may be very large, and there may have many wheels. I tried (simplify the case to 3 wheels only):

const array_2d=[
  ["HUGE","TALL","TINY"],
  ["BLUE","CYAN","DARK","GOLD","GRAY"],
  ["BIRD","FISH","GOAT","MOTH"]
];
for(let i=0;i<array_2d.length;i++){
  let str="";
  for(let j=0;j<array_2d[i].length;j++){
    str+=array_2d[i][j]+" ";
  }
  if(str.split("A").length-1>=3){
      document.write(str+"<br/>");
      break;
  }
}

which the expected result is:

TALL GRAY GOAT

but the actual result is:

BLUE CYAN DARK GOLD GRAY

which is not working.

Well it is working; the result you get satisfies your condition. It just happens to be the first one that does. Are there more criteria than this? Do you need the *shortest* combination? — kelsny, Sep 29 '22 at 03:41

A1exandr Belan · Answer 1 · 2022-09-29T05:46:04.377

Usually you can use the regular cartesian array creator and filter result by conditions. But if the number of arrays is increasing, it's better to use the generator function to create next value.

Here are both solutions, a live demo:

const array_2d=[["HUGE","TALL","TINY"], ["BLUE","CYAN","DARK","GOLD","GRAY"],["BIRD","FISH","GOAT","MOTH"]];

const condition = (arr) => [...arr].every((term) => term.includes('A'));

// Solution
const cartesian = (...a) => a.reduce((a, b) => a.flatMap(d => b.map(e => [d, e].flat())));
  
const result = cartesian(...array_2d).filter(condition);

console.log('Regular solution:\n', result);


// Generator solution
function* cartesianGen(head, ...tail) {
  const remainder = tail.length > 0 ? cartesianGen(...tail) : [[]];
  for (let r of remainder) for (let h of head) yield [h, ...r];
};

const codeGen = cartesianGen(...array_2d);

let code = {};
do {
  code = codeGen.next();
  if (condition(code.value)) break;
} while (!code.done);

console.log('Generator solution:\n', code.value);

.as-console-wrapper { max-height: 100% !important; top: 0 }

How to iterate the result of combination padlock until condition fulfilled, then break, without creating cartesian product first?

1 Answers1