Play dominoes using strings

Challenge

Given two lists of strings $A$ and $B$, both of length $n\ge 1$. For any $i\in \{1,\dots ,n\}$, by $A_i$ and $B_i$ we represent the $i$-th string from $A$ and $B$, respectively. Associative infix binary operator $+$ represents string concatenation.

Output any $k_1,\dots ,k_m$ for some $m\ge 1$ such that

$$A_{k_1}+\dots +A_{k_m}=B_{k_1}+\dots +B_{k_m}$$

Test cases

Outputs are 1-indexed.

A: ["a", "ab", "bba"]
B: ["baa", "aa", "bb"]
K: [3, 2, 3, 1]

A: ["aa", "ba", "c"]
B: ["a", "ab", "ac"]
K: [1, 2, 2, 3]

A: ["", "", "da", "dc", "db"]
B: ["adbdc", "d", "", "", ""]
K: [2, 1, 3, 5, 4]

The string $A_{k_1}+\dots +A_{k_m}$ in the first case is "bbaabbbaa", in the second case is "aababac", and in the third case is "dadbdc". Note that there may be multiple solutions.

Rules

• Input can be in any format you like (list of strings, list of lists of characters, etc). You can also use list of lists of integers instead of list of strings if you prefer.
• Output can also be in any format you like. List $k$ represents the list of indices of $A$ and $B$. It can be 0-indexed or 1-indexed. You can also output the list of pairs $[(A_{k_1},B_{k_1}),\dots ,(A_{k_m},B_{k_m})]$ instead.
• Output is not allowed to contain the calculated string $A_{k_1}+\dots +A_{k_m}$ only (you can output it along with list $k$ if you want, but $k$ is mandatory).
• Output cannot be an empty list.
• In case there are multiple solutions, output any valid solution.
• You can assume that:
  • $A$ and $B$ are non-empty and have the same length.
  • For each $i,j\in \{1,\dots ,n\}$, if $A_i=A_j\wedge B_i=B_j$ then $i=j$.
  • At least one solution exists.
• This is code-golf, the shortest program wins.

Sandbox

Any suggestions/improvements?

posted over 3 years ago

CC0

Hakerh400‭

1591 reputation 4 55 164 63