4
$\begingroup$

Let $\mathbb{X} = \mathbb{N} \cap [0, 255]$. I am given three vectors in $\mathbb{X}^3$ which I will denote by $v_i = [x_i, y_i, z_i]^T$ for $i \in \{1, 2, 3\}$. Now we have a binary operator $\bigoplus$ defined by $w = u \bigoplus v = \lfloor0.9 \cdot u\rfloor + \lfloor0.1 \cdot v\rfloor$, where $u$ and $v$ are in $\mathbb{X}^3$. Given a target vector $t \in \mathbb{X}^3$, the goal is to find a sequence of applications of $\bigoplus$ starting only with vectors $v_1, v_2, v_3$ that yield $t$. We are also given a promise that such a sequence of applications exists. How quickly can I find this sequence? It is worth noting that $\bigoplus$ is non-commutative and closed on $\mathbb{X}^3$. In my case, I am given specific values for $v_1, v_2, v_3,$ and $t$: $$\begin{align*}v_1 &=[150, 0, 255] \\ v_2 &= [255, 150, 0] \\ v_3 &= [0, 255, 150] \\ t &= [62, 63, 184]\end{align*}$$

The obvious thing to try was a memoization / search approach where we keep a data-structure containing each vector seen so far (initially containing only $v_1, v_2, v_3$) and recursively apply the operator on each pair of vectors stored in my data-structure until the target is found. However this appears to be much to time consuming as the number of possibilities grow super quickly. Is there any better approach that one might try? It doesn't help that there appears to be little structure - For example, starting with our three vectors, there appears to be many combinations that we cannot even form.

I am also interested in knowing what happens if we are not given the promise that $t$ can be obtained from a series of applications of $\bigoplus$ on our three vectors. If we are not given such a promise, is there any easy way to at least determine if such a sequence exists (even though finding it might be difficult)?

$\endgroup$
  • $\begingroup$ @D.W. Does the remainder of the question make sense to you? I can try and add additional details if any part of it is unclear. $\endgroup$ – user340082710 Oct 29 '15 at 22:33
  • $\begingroup$ Are you happy with any any sequence of applications that evaluates to $t$, or do you want to find the sequence that uses the minimal possible number of applications of $\oplus$? $\endgroup$ – D.W. Oct 29 '15 at 23:09
  • $\begingroup$ I am happy with any such sequence for the time being. $\endgroup$ – user340082710 Oct 29 '15 at 23:27
1
$\begingroup$

Here is a simple solution that I suspect will be fast enough. Use breadth-first search on a graph where the vertex set is $X^3$. In other words, each possible vector $w \in X^3$ is a vertex. The vertex $w$ has 6 edges out of it going to $w \oplus v_1$, $w \oplus v_2$, $w \oplus v_3$, $v_1 \oplus w$, $v_2 \oplus w$, $v_3 \oplus w$. Now use BFS to find the shortest path from $v_1$ or $v_2$ or $v_3$ to $t$. This can be done by initially marking $v_1,v_2,v_3$ as visited and having distance 0, initializing the queue to contain $v_1,v_2,v_3$, and then running BFS until you reach the goal vertex $t$.

Why does this work? Define $d(v,w)$ to be the distance from $v$ to $w$, i.e., the length of the shortest path from $v$ to $w$ in this graph. Define $d(w) = \min(d(v_1,w),d(v_2,w),d(v_3,w))$. Note that any path of length $d$ corresponds to an expression that uses $d$ applications of the $\oplus$ operator, and vice versa. Therefore, $d(t)$ -- the distance to the goal vertex $t$ -- represents the minimum number of applications needed to reach $t$, and the corresponding path yields an expression that evaluates to $t$ using the minimal number of applications of $\oplus$.

How efficient is this? BFS run in time linear in the number of vertices plus the number of edges. Here we have $2^{24}$ vertices and $6 \times 2^{24}$ vertices. Therefore, in the worst case we perform something like $c \times 6 \times 2^{24}$ basic operations, where $c$ is a small constant. The performance in practice might be better than that, as there might not be any need to visit all possible vertices. The memory requirements are relatively limited. You can store the set of visited vertices in a 2MB bitmap; thus, checking whether a vertex has been visited before can be done by a single random-access lookup in this bitmap. You can store the queue in a single array of maximum size $3 \times 2^{24}$ bytes, i.e., 48MB; this is not very large large, and locality of access will be excellent. So I expect this algorithm to complete within seconds.


If this is not fast enough, it is probably possible to optimize it further using various techniques. For example, here is one candidate. Define $x-v = \{w \in X^3 : v \oplus w = x\}$ and $P(x) = \{v \in X^3 : \exists w \in X^3 . v \oplus w = x\}$. Define $S_j = \{w \in X^3 : d(w)=j\}$ and $T_k = \{w \in X^3 : d(w,t)=k\}$. Now you could consider an optimized iterative deepening algorithm, as follows:

  • For $d=1,2,3,\dots$:

    • For $k=\lfloor d/2 \rfloor, \lfloor d/2 \rfloor + 1, \lfloor d/2 \rfloor -1,\lfloor d/2 \rfloor +2,\dots,d,1$:

      • Set $j=d-k$. For each $v \in S_j$:

        • If $v \in P(t)$ and $t-v \cap T_k \ne \emptyset$, then choose any $w \in t-v \cap T_k$ and output $v \oplus w$ and halt.

We can compute the $S_j,T_k$'s using the technique above (BFS). The trick here is to use a clever data structure to store $T_k$. If we store $T_k$ in an octree or k-d tree, then testing whether $t-v$ has any intersection with $T_k$ is a stabbing query: we are given a $10 \times 10 \times 10$ cube and want to know if there's any point of $T_k$ that falls within the cube. This lookup can be done efficiently when $T_k$ is stored in an octree or k-d tree or similar data structure (basically in $O(\log |T_k|)$ time or so).

This requires more complex data structures, so I'm not sure that it will be worth it to implement. It's not clear whether the resulting solution will be faster or slower than simple BFS, but if simple BFS is too slow, this is another approach you could try.


This finds the sequence that evaluates to $t$ and uses the minimal possible number of applications of $\oplus$. If you just want any sequence (not necessarily minimal), it might be possible to find it faster. For example, you could use best-first search, where the "goodness" of a vertex is measured by its $L_{\infty}$ distance to $t$.


An aside: your operator $\oplus$ is not associative, but it is "almost so". In particular, $(u \oplus v) \oplus w$ is in general not equal to $u \oplus (v \oplus w)$ (due to the rounding), but it will be "close". Ignoring rounding, $$\begin{align*}(u \oplus v) \oplus w &= 0.81 u + 0.09v + 0.10w\\ u \oplus (v \oplus w) &=0.90 u + 0.09 v + 0.01 w,\end{align*}$$ so (again ignoring rounding) their difference is $0.09 u - 0.09 w$, which is in $[-23,23]^3$. Rounding might make it a bit larger, but not too much.

It might be possible to use this property to gain some additional speedup -- though I have not identified a specific way yet.

$\endgroup$
  • $\begingroup$ As you mentioned, the operator isn't associative. So why don't I need edges between things like $w \bigoplus (v_1 \bigoplus v_2)$? I feel like a vector like $(v_1 \bigoplus v_2) \bigoplus (v_1 \bigoplus v_2)$ can't be reached with the description you've provided. Unless I misunderstood, then this becomes the same approach that I described in my initial post. I will see if your optimization might help. $\endgroup$ – user340082710 Oct 30 '15 at 2:02
  • $\begingroup$ @ZacharyFrenette, you are right: I missed that. More thought needed -- the BFS solution isn't sufficient, as it stands. $\endgroup$ – D.W. Oct 30 '15 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.