Find the Best Set of Adapters

Question

I'm trying to plug this really old phone into my computer but the phone seems to use a very obscure plug. Luckily I have some adapters. Unfortunately, I can't figure out which of them to use to connect my phone to my computer. Can you find the smallest number of adapters that can link my phone and computer?

Input

A pair of strings representing the phone and the computer's port type and a list of pairs of strings where the pair A, B transforms an input of type A to type B. Example:

("A", "D")
[
  ("A", "B"),
  ("C", "D"),
  ("B", "C"),
]

The first pair ("A", "D") is the desired connection. The rest are adapters.

Challenge

Output the number of adapters required to connect the phone to the computer. In the above example, the answer would be 3 as all 3 adapters would be required.

Test Cases

Phone, Computer
TypeA -> TypeB
TypeC -> TypeD
Output

A, D
A -> B
B -> C
C -> D
3

A, Z
A -> B
B -> C
C -> D
D -> Z
X -> Y
Y -> Z
4

A, B
A -> B
X -> Y
Y -> Z
1

A, C
A -> B
B -> C
C -> A
2

A, C
A -> A
B -> B
C -> C
A -> B
B -> C
2

Rules

• Standard loopholes disallowed
• This is code-golf, shortest code wins
• You can assume it is possible to make the connection
• The port on the phone and computer will not be of the same type
• There may be adapters of type A -> A
• It is not guaranteed that all of the adapters will be possible to use
• You may take input in any form that is convenient

Answer 1

Jelly, 13 bytes

ṗJ$Ẏy@ƒ⁼⁵ɗƇẈṂ

Try it online!

Full program taking a list of pairs L (e.g. ['AB', 'BC', 'CD', 'DZ', 'XY', 'YZ']) as the first argument, the source as the second and the target as the third.

How it works

Brute-force approach.

ṗJ$Ẏy@ƒ⁼⁵ɗƇẈṂ - Main link. Takes L on the left and S on the right
  $           - Group the previous 2 links into a monad f(L):
 J            -   Yield the indices of L; [1, 2, 3, ..., len(L)]
ṗ             -   Get the n'th Cartesian power of L for each n in this range
   Ẏ          - Flatten into a list of lists
         ɗƇ   - Keep those for which the following is true:
      ƒ       -   Reduce the list by the following, starting with S:
    y@        -     Translate, according to the pair mapping
       ⁼⁵     - Does the final result equal T?
           ẈṂ - Get the length of the shortest element

Answer 2

J, 28 bytes

1 :'[:#+./ .*^:(1-u{])^:a:~'

Try it online!

Perhaps stretching the definition of convenient input, I take the adapter list as an adjacency matrix, and the target connection as a boxed pair of indexes (the noun being modified).

The test cases include an (ungolfed) conversion step, so if this is not allowed it can be easily corrected, though the byte count will about double.

main idea

Simply multiply the adjacency matrix by itself until the cell representing the target adapter becomes 1, keeping track of the intermediate matrices.

The length of that list is the minimal number of adapters.

J, 30 byte using a verb rather than adverb

[:#(,{.+/ .*{:)@]^:(-.@{{:)^:_

Try it online!

Answer 3

Wolfram Language (Mathematica), 13 bytes

GraphDistance

Try it online!

...and here's the built-in.

Answer 4

JavaScript (ES6), 78 bytes

Expects (target, list)(source), where list is an array of string pairs.

(b,c,m)=>g=(a,n)=>a==b?m<n?m:m=n:c.map(p=>p[0]==a?p[g(p[1],p[0]=-~n),0]=a:0)|m

Try it online!

Commented

(                      // outer function:
  b,                   //   b   = target plug
  c,                   //   c[] = list of connectors
  m                    //   m   = minimum number of connections
) =>                   //
g = (                  // inner recursive function:
  a,                   //   a = current plug
  n                    //   n = number of connections
) =>                   //
  a == b ?             // if a = b:
    m < n ? m          //   update m to min(m, n)
          : m = n      //   (the update is forced if m is still undefined)
  :                    // else:
    c.map(p =>         //   for each pair p[] in c[]:
      p[0] == a ?      //     if the input plug of p is a:
        p[             //
          g(           //       recursive call:
            p[1],      //         set a to the output plug p[1]
            p[0] = -~n //         increment the number of connections and
                       //         invalidate p[0] so that it's not used again
          ),           //       end of recursive call
          0            //
        ] = a          //       restore p[0] to a afterwards
      :                //     else:
        0              //       do nothing
    ) | m              //   end of map(); yield m

Answer 5

Charcoal, 40 bytes

⊞υθＦυＦζＦ›⁼§ι±¹§κ⁰№ι§κ¹⊞υ⁺ι§κ¹Ｉ⊖⌊ＥΦυ№ιηＬι

Try it online! Link is to verbose version of code. Explanation:

⊞υθ

Start a breadth-first search using the computer's port.

Ｆυ

Loop over all chains of adapters tried so far.

Ｆζ

Loop over all of the adapters.

Ｆ›⁼§ι±¹§κ⁰№ι§κ¹

Can this adapter be plugged in to provide a port not yet seen in this chain?

⊞υ⁺ι§κ¹

If so then save this new chain to the search list.

Ｉ⊖⌊ＥΦυ№ιηＬι

Print the shortest number of adapters that result in the desired output port.

Answer 6

Java, 474 bytes

(s,e,a)->{java.util.Map<String,java.util.List<String>>m=new java.util.HashMap();java.util.Map<String,Integer>d=new java.util.HashMap();for(String[]c:a)m.computeIfAbsent(c[0],k->new java.util.ArrayList()).add(c[1]);java.util.List<String>l=new java.util.LinkedList();l.add(s);d.put(s,0);while(l.size()!=0){String c=l.remove(0);for(String n:m.getOrDefault(c,new java.util.ArrayList<>()))if(d.get(c)+1<d.getOrDefault(n,(int)1e9)){d.put(n,d.get(c)+1);l.add(n);}}return d.get(e);}

This runs a single breadth-first search (BFS) while keeping track of the distances to each node.

Try it online!

Answer 7

JavaScript (Node.js), 73 bytes

(b,c,m)=>g=(a,n=0)=>a==b?m<n?m:m=n:c[n]&&c.map(p=>p[0]==a&&g(p[1],n+1))|m

Try it online!

Mainly based on Arnauld's answer.

c[n] means n < c.length. Since the question claim that "You can assume it is possible to make the connection", it is safe to give up search if we already used c.length adapters but not reach destination yet.