8
\$\begingroup\$

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 , 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
\$\endgroup\$
6
  • 3
    \$\begingroup\$ So we take a (directed?) graph and find the shortest path? \$\endgroup\$ – user Mar 19 at 16:49
  • 1
    \$\begingroup\$ Pretty much yup \$\endgroup\$ – user197974 Mar 19 at 16:50
  • \$\begingroup\$ Looks similar to a hackerrank question I tried solving earlier. If your question is take from a similar website, do credit it. \$\endgroup\$ – Razetime Mar 19 at 17:20
  • 2
    \$\begingroup\$ @Razetime I did not take this question from hakerrank. I came up with it myself. \$\endgroup\$ – user197974 Mar 19 at 17:39
  • 5
    \$\begingroup\$ "Pretty much yup" + "You may take input in any form that is convenient" = Can I take the connections as an adjacency matrix? \$\endgroup\$ – Jonah Mar 20 at 3:39
5
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Doesn't work if the adapters are in the wrong order. Try it online! \$\endgroup\$ – xigoi Mar 19 at 17:32
  • \$\begingroup\$ @xigoi Fixed, thanks! \$\endgroup\$ – caird coinheringaahing Mar 19 at 17:35
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ (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))|m \$\endgroup\$ – tsh Mar 21 at 22:44
1
\$\begingroup\$

Charcoal, 40 bytes

⊞υθFυFζF›⁼§ι±¹§κ⁰№ι§κ¹⊞υ⁺ι§κ¹I⊖⌊EΦυ№ιηLι

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

⊞υθ

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

Fυ

Loop over all chains of adapters tried so far.

Fζ

Loop over all of the adapters.

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

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.

I⊖⌊EΦυ№ιηLι

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

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
1
\$\begingroup\$

Wolfram Language (Mathematica), 13 bytes

GraphDistance

Try it online!

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

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.