Suppose one day you are digging through your big box of unused computer cords and adapters (USB to USB mini, VGA to DVI, etc.). There are tangled cords everywhere making quite a mess, and you wonder if you could simplify things by attaching all the cords together in one long strand, and then just rolling it up.

The question is, is it possible to connect all of your cords and adapters in one long line like this? It's obviously not always possible, e.g. if you only had two cords with completely different plugs, they could not be connected together. But if you had a third cord that can connect to both of them, then you could string all your cords together.

You don't care about what type of plugs are on the ends of the all-cord strand. They don't need to plug into one another to form a loop. You only want to know if making the all-cord strand is possible, and if it is, how to do it.


Write a program or function that takes in a multiline string where every line depicts one of the cords you own. A cord is made up of one or more dashes (-), with a plug on either end. A plug is always one of the 8 characters ()[]{}<>.

So these are some valid cords:


But these are not:


When connecting cords, only plugs with the exact same bracket type can be connected together.

So these are some valid cord connections:


And these are invalid:


If all the cords in the input can be rearranged and attached together in one long strand, then output that strand to stdout on one line (with an optional trailing newline). When there are multiple solutions you can choose any one of them to output. If making a single strand is not possible, then output nothing (or output an empty string with an optional trailing newline).

For example, if the input is


the output could be


where all the cords are strung together.

However if the input were


the cords cannot be connected so there would be no output.

Note that cords can be flipped around as much necessary to make connections. e.g. [--> and <--] are effectively the same cord because they can make the same type of connections. Some outputs may depend on flipping the input cords.

For example


could have output


where the second cord is flipped, or


where the first cord is flipped.

(Note that in general flipping the entire output is valid because it's the same as initially flipping every cord individually.)

The lengths of the cords in the output should of course match the lengths of the corresponding input cords. But the cords may be reordered and flipped around as much as you want in order to make the all-cord strand. The input will always contain at least one cord.

The shortest code in bytes wins.

Test Cases

Cases with output:






could give

could give

could give

Cases without output:






  • 6
    \$\begingroup\$ big box of unused computer cords and adapters That makes me feel better - I'm not the only one. Actually I have several of these boxes. \$\endgroup\$ – Digital Trauma Dec 7 '15 at 6:05
  • \$\begingroup\$ but what if you plug a cord into itself? \$\endgroup\$ – anOKsquirrel Dec 7 '15 at 16:01
  • \$\begingroup\$ Are the cords guaranteed to all be valid? \$\endgroup\$ – R. Kap Apr 15 '16 at 22:22
  • \$\begingroup\$ @R.Kap Yes they are \$\endgroup\$ – Calvin's Hobbies Apr 15 '16 at 22:46

Unreadable, 3924 bytes

This is the first time I implemented somewhat of a call-stack-like structure in Unreadable.

(The first version of this was over 5300 bytes, just to give an idea of how much I golfed this.)



Consider this example input:


Throughout most of the execution, the tape is laid out as follows:

  • Cells 0 to 5 are locations for various variables.

  • Cell 6 onwards contain all information about the set of cables in your box:

    tape layout example

  • The remaining cells after the “zero terminator” contain the stack. Each “stackframe” is a single cell that points to the first cell of a cable (the “start plug” cell). In the above example, when the program decides it has found a solution, the stack will contain 6 (referring to >--{, the first cable) and 21 (referring to {---], the mirror of the second cable).

The program proceeds in three main stages:

  1. Read the entire input and generate the above structure, including all the mirrored cables.
  2. Try out all combinations (but stop if a solution is found).
  3. If a solution was found, output it.

The first stage (read input and generate cables structure) only uses cells #1 (which I’ll call p) and #2 (which I’ll call ch) and operates in a while loop as follows:

  • While condition: increment p by 6, read the next character (start plug) into cell *p, and check that it isn’t -1 (EOF).

  • Read subsequent characters into *(p+2), and count them in *(p+1), until we encounter anything other than - (hyphen). At that point, *(p+1) will contain the number of hyphens (cable length) and *(p+2) the last non-hyphen character (the end plug). (We also copy the hyphen characters to cell #5 so we can access this ASCII code later in the output stage.)

  • In a while loop, find the mirror plug and store it at *(p+3), then increment p by 2, until *p is zero. The loop looks like this in pseudocode:

    while (ch = *p) {
        *(p+3) = (ch -= 40) ? (ch -= 1) ? (ch -= 19) ? (ch -= 31) ? ch-32 ? *p-2 : *p+2 : *p+2 : *p+2 : *p-1 : *p+1
        p += 2
  • This loop will always perform two iterations (the start plug and end plug) and store the results in the fourth and sixth cell of this cable. Now, if you paid attention, you realize that the sixth cell is indeed the correct location for the mirrored end plug, but the mirrored start plug is in the cell labeled “boolean indicating original cable”. This is OK because we only need this cell to be a non-zero value.

  • Since p has just been incremented a total of 4, it’s now pointing at the cell labeled “boolean indicating cable is in use”. Set *(p+3) to the value of *(p-1). This puts the mirrored start plug in the right place.

  • Read (and discard) one more character (which we expect to be a newline, but the program doesn’t check for that).

p initially starts out at 0 but is incremented by 6 inside the while condition, thus the cable data starts at cell #6. p is incremented by 4 inside the loop body, and thus a total of 10 for each cable, which is exactly what we need.

During the second stage, cells #0–4 are occupied by variables that I’ll call a, p, q, m, and notdone. (Cell #5 still remembers the ASCII code of the hyphen.)

To get ready for stage 2, we need to set *p back to 0 (the cell labeled “zero terminator”) so that it can act as the terminator for the list of cables; we also set q (which is our stack pointer) to p+1 (i.e. the cell after the “zero terminator”; this is where the stack starts); *q to 1 (the first item on the stack; why 1 will become apparent later); and notdone to 1. All this is done in a single statement:

*p = (notdone = *(q = p+1) = 1)-1

The second stage is also a while loop. Its condition is simply notdone. In each iteration of that while loop, any one of the following four things could happen:

  1. We find that all cables are marked “in use”. This means we’ve found a solution (which is represented by the current stack contents).
  2. We can advance *q to another eligible cable (which we promptly mark as “in use” along with its twin) and then recurse (i.e. create a new stackframe).
  3. We cannot advance *q because no further eligible cable exists, so we need to backtrack (remove a stackframe and mark the previous cable and its twin as no longer “in use”).
  4. We cannot advance *q because no further eligible cable exists and we cannot backtrack because we have reached the bottom of the stack. This means there is no solution.

The loop body checks for each of these four conditions in this order. Here are the details:

  1. Set m and p to 1 and in a while loop, increment p by 5 (thus iterating through the cables) and check if *(p+4) (“in use”) is set. If it isn’t, set m to 0. At the end of that loop, m tells us if all the cables are in use. If so, set notdone to 0 to terminate the main loop. Otherwise, continue at step 2 below.

  2. Set p to *q (the cable at the top of the stack) and in a while loop similar to the above, increment p by 5 to iterate through the cables. Starting at *q ensures we only consider those that we haven’t already considered before; however, remember that the initial value for a new stackframe is 1, so the first cable looked at is the one at cell 6, which is indeed the first cable.

    For each cable, we need to check *(p+4) to ensure that it’s not already in use, and also that either *(q-1) is zero (meaning we’re at the bottom of the stack, so there’s no constraint on the start plug), or *p (the cable’s start plug) is equal to *(*(q-1)+2) (the end plug of the cable just below on the stack). We check for equality by setting a to *(*(q-1)+2) and m to *p+1 and then decrementing both in a while loop. The +1 is because m is decremented inside the while condition, so it is decremented once more than a. If a is zero at the end of this, the two plugs are equal.

    Thus, if either *(q-1) was zero or the equality comparison succeeded, the cable is eligible. Set *q to p to replace the cable at the top of the stack with the new one; set m to the same to indicate that we found a matching cable; and then decrement p. That decrement is a little trick to cause the while loop (iterating through the cables) to terminate early; it will increment p by 5 again, thus taking it to the cell containing this cable’s “in use” flag, and we know that’s zero because we just checked that. Finally, after the cable-iterating while loop, we check if m is non-zero. If so, we found a matching cable and p is pointing at the “in-use” flag for that matching cable. Set it to 1 to mark it as in use. Also set *(*(p-1) ? p+5 : p-5) to 1 to mark its twin as in use. Finally, increment q and set the new *q to 1 to create a new stackframe.

  3. If, after the cable-iterating while loop, we find m to be zero, there are no more matching cables, so we need to backtrack. Decrement q to move down the stack and check if it’s still pointing at a cable (a non-zero value). If so, mark that cable and its twin as no longer in use. (We store the value of *q in p to make this expression shorter in code.)

  4. If, after decrementing q, we find that it points at a zero value, then that is the “zero terminator”, which means we’ve underrun the stack. We conclude that there is no solution. We set notdone to 0 to terminate the main loop.

The third stage is the output stage. There are two things that can happen:

  • the main loop found a solution that we need to output, or
  • the main loop concluded there is no solution and we output nothing.

Conveniently, if there was no solution, p is zero because we set it to the value of *q before checking that for zero; and if there was a solution, p is pointing at the “zero terminator” because it just iterated through the cables, so we can now use p to iterate through the stack. So just iterate through the stack, outputting for each cable the start plug (*(*p)), the hyphens (by decrementing *(*p+1) in a while loop; and using the hyphen ASCII code stored in cell #5), and the end plug (*(*p+2)). Never mind that this destroys the cable-length information; we don’t need that anymore.


CJam, 67


Try it online

Note: the link is using the latest code from the repository (pushed but not yet released), as it contains a bug fix.


The program simply tries all permutations and all orientations of the cords.

qN%             read the input and split into lines
e!              generate all permutations
{…}%            map each permutation of cords
  _,            get the number of cords (n)
  2,m*          generate all patterns of n bits (cartesian power of [0 1])
  \f{…}         for each bit pattern and the cord permutation
    .{…}        apply the block to each bit and cord (flipping cords for bit 0)
      _         duplicate the cord
      {…}%      map each character of the cord
        "…"_    push the string of all the plugs (and 2 dashes) and duplicate it
        @#      get the index of the character in the string
        1^      XOR with 1
        =       get the character at this new index (plugs get toggled)
      W%        reverse the cord
                 the stack now has the bit, the original cord and the flipped cord
      ?         if the bit is 1, use the original cord, else use the flipped one
    _           duplicate the array of cords
    2ew         get all pairs of adjacent cords
    {…}%        map each pair of cords
      ~\        dump the 2 cords on the stack and swap them
      W=        get the right plug of the first cord
      #         find its position in the second cord (if 0, we have a match)
    0-          remove all the zeros
    {…}&        if the array is not empty (i.e. we have a mismatch)
      ;         pop the array of cords
  ~             dump all the results for this permutation on the stack
                 (to avoid nested arrays)
1<              get the first result (if any) from the array of all results
  • \$\begingroup\$ Perhaps an explanation of how it works exactly? \$\endgroup\$ – Timwi Apr 18 '16 at 18:16
  • \$\begingroup\$ @Timwi ok, I also golfed it a little more \$\endgroup\$ – aditsu Apr 18 '16 at 20:32
  • \$\begingroup\$ This solution is invalid as it does not produce any output for the input (-] ]-> >-} }-) )-[ [-< <-{ {-(. \$\endgroup\$ – R. Kap Apr 19 '16 at 4:34
  • \$\begingroup\$ @R.Kap it does solve that input, but that particular online interpreter has a timeout (and is quite silent about it). You can try it here instead (and give it several minutes) or use the java interpreter (fastest) \$\endgroup\$ – aditsu Apr 19 '16 at 5:26
  • \$\begingroup\$ In fact, the interpreter I linked above will probably take a long time to solve that input. The java interpreter solves it in less than 1.5 min on my computer. \$\endgroup\$ – aditsu Apr 19 '16 at 5:39

JavaScript (ES6), 206

Recursive function

f=(l,a=l.pop(),x=x=>(z='<>[]{}()')[z.indexOf(x)^1])=>l[0]?l.some((b,i)=>r=[b,x([...b].pop())+b.slice(1,-1)+x(b[0])] .some(b=>r=a[0]==[...b].pop()?b+a:b[0]==[...a].pop()?a+b:0)&&(l=[...l],l[i]=r,f(l)))?r:'':a

More readable



f=(l,a=l.pop(),x=x=>(z='<>[]{}()')[z.indexOf(x)^1])=>l[0]?l.some((b,i)=>r=[b,x([...b].pop())+b.slice(1,-1)+x(b[0])] .some(b=>r=a[0]==[...b].pop()?b+a:b[0]==[...a].pop()?a+b:0)&&(l=[...l],l[i]=r,f(l)))?r:'':a


,['[-------]',']-------[','[-------]','[---------]'] // shortened a little,
  console.log(t+' : "'+f(t)+'"\n')
<pre id=O></pre>


Javascript, 800 Bytes

Far from an optimized solution, but here's a quick hack together in javascript (no fancy ecma5 or anything, because I don't know it).

function a(r){function t(r,t){var n=r.slice();return n.splice(t,1),n}function n(r){var t,n={"[":"]","]":"[",">":"<","<":">","(":")",")":"(","{":"}","}":"{"},e=r.split("").reverse();for(t=0;t<e.length;t++)n.hasOwnProperty(e[t])&&(e[t]=n[e[t]]);return e.join("")}function e(r,t){return r.unshift(t),r}var h,u,f=[];if(1==r.length)return r[0];for(h=0;h<r.length;h++){var l=r[h],i=t(r,h),c=l.charAt(0),g=l.charAt(l.length-1);for(u=0;u<i.length;u++){var o=i[u],s=o.charAt(0),p=o.charAt(o.length-1);c==p&&f.push(e(t(i,u),o+l)),g==s&&f.push(e(t(i,u),l+o)),o=n(o),s=o.charAt(0),p=o.charAt(o.length-1),c==p&&f.push(e(t(i,u),o+l)),g==s&&f.push(e(t(i,u),l+o))}}if(f.length<1)return!1;for(h=0;h<f.length;h++){if(1===f[h].length)return f[h][0];f[h]=a(f[h])}for(h=0;h<f.length;h++)if(f[h]!==!1)return f[h];return!1}

Ungolfed, here it is... I'm sure at least 2 for loops are unnecessary here and that checking for a single element input at the top and a single element match at the bottom is stanky... but it seems to work and processes the test inputs.

function a(inputs)
	var i, ii, matches = [];
	if (inputs.length == 1) {
		return inputs[0];
	// For each of the elements in inputs (e1)
	for (i = 0; i < inputs.length; i++) {
		var e1 = inputs[i],
			others = except(inputs,i),
			e1s = e1.charAt(0),
			e1e = e1.charAt(e1.length-1);
		// Compare to each of the other elements in inputs (e2)
		for (ii = 0; ii < others.length; ii++) {
			// get the start and end of the elements to compare (e1s,e1e,e2s,e2e)
			var e2 = others[ii],
				e2s = e2.charAt(0),
				e2e = e2.charAt(e2.length-1);
			// if any of them match up (e1s == e2e || e1s == e2s || e1e == e2s || e1e = e2e)
			// Make a new array of inputs containing the joined elements (as a single element) and all other elements which might join with them
			if (e1s == e2e) {
			if (e1e == e2s) {
			e2 = flip(e2);
			e2s = e2.charAt(0);
			e2e = e2.charAt(e2.length-1);
			if (e1s == e2e) {
			if (e1e == e2s) {

	if (matches.length < 1) {
		return false;

	for (i = 0; i < matches.length; i++) {
		if (matches[i].length  === 1) {
			return matches[i][0];
		} else {
			matches[i] = a(matches[i]);

	for (i = 0; i < matches.length; i++) {
		if (matches[i] !== false) {
			return matches[i];

	return false;

	function except(list,idx)
		var newList = list.slice();
		return newList;
	function flip(s) {
		var replacements = {
		}, i, a = s.split('').reverse();
		for (i = 0; i < a.length; i++) {
			if (replacements.hasOwnProperty(a[i])) {
				a[i] = replacements[a[i]];

		return a.join('');
	function addTo(arr,newEl)
		return arr;


Python 3, 217 bytes

from itertools import*
all(any(c[-1]!=d[0]for c,d in zip(q,q[1:]))or print(''.join(q))for p in permutations(open(0))for q in product(*[(c[:-1],a[a.find(c[-2])^1]+c[-3:0:-1]+a[a.find(c[0])^1])for c in p]))

(Demo on Ideone)

  • \$\begingroup\$ How does this take input? \$\endgroup\$ – R. Kap Apr 16 '16 at 4:49
  • \$\begingroup\$ @R.Kap On stdin, one cord per line. \$\endgroup\$ – Anders Kaseorg Apr 16 '16 at 4:50
  • \$\begingroup\$ It does not seem to, at least when I ran it. \$\endgroup\$ – R. Kap Apr 16 '16 at 4:50
  • \$\begingroup\$ Also, how fast can it find the correct answer for (-] ]-> >-} }-) )-[ [-< <-{ {-(? \$\endgroup\$ – R. Kap Apr 16 '16 at 4:51
  • \$\begingroup\$ @R.Kap See the demo on Ideone for an example of it taking input and producing output. (It may not work on Windows, if that’s what you’re trying to do?) It runs ~instantly on your test case. There are of course cases that will take exponential time, though. \$\endgroup\$ – Anders Kaseorg Apr 16 '16 at 4:56

Lua, 477 bytes

function r(s)return s:reverse():gsub("[()%[%]{}<>]",{["("]=")",[")"]="(",["["]="]",["]"]="[",["{"]="}",["}"]="{",["<"]=">",[">"]="<"})end
function a(c,b)for i, v in next,b do
m=c:sub(-1,-1)n=v:sub(1,1)o=r(c):sub(-1,-1)p=r(v):sub(1,1)l=table.remove(b,i)if m==n then
return a(c..v,b)elseif o==n then
return a(r(c)..v,b)elseif m==p then
return a(c..r(v),b)elseif o==p then
return a(r(c)..r(v),b)end
return#b>0 and""or c

Accepts cords as command line arguments


Python 3.5, 448 432 427 424 286 311 bytes:

(+25 since there was a bug where the output may be longer than it should be for some inputs)

def g3(z):
 B=z.split();M='i[::-1].translate({41:40,40:41,125:123,123:125,62:60,60:62,93:91,91:93})';f=B+[eval(M)for i in B if eval(M)not in B];d=[f.pop(0)]
 for h in d:
  try:[d.append([f.pop(f.index(c))for c in f if h[-1]==c[0]][0])if len(d)<len(B)else E]
 return''.join(d)if len(d)>=len(B)else''

Works perfectly! except for inputs with 7 or more values. It takes a long time for those, most likely because it must go through all those permutations of the input plus the input reversed. I will try to fix this if and when I can, but for now, this seems to be good enough. All is good now! If only I could somehow use that try-except block in list comprehension, it could be a little shorter, and look much nicer. Nonetheless, it now works for all the test cases, and, best of all, it uses no imports! :)

Try it online! (Ideone) (284 bytes here)

(Tip: To try it, just select "fork", and then input your choices, space-separated, and select "run")


Basically, what's happening is...

  1. A list, B, is created from the input by splitting it at the whitespace into its component "cords".
  2. M is a string I created which, when evaluated, returns a list based on B which contains all the cords, but this time backwards.
  3. The list created from M is ultimately concatenated with B itself to create a list, f, with all possible orientations of the "cords".
  4. Another list, d is created, which will be initialized with the first value (value f[0]) of f.
  5. Finally, all the values in d are iterated through, and each value's last character is compared with the first character of each element in f, and when a match is found, that character is popped (or removed) and returned from list f. This happens until a IndexError is raised, or the length of list d exceeds B and a NameError is raised after the call to E,both of which are handled, and then list d's contents are joined into a string and returned as long as the length of list d is more than or equal to the length of list B. Otherwise, an empty string is returned (''), since d not being the same length as B signifies that all the "cords" in list B cannot be joined into one long "cord".
  • \$\begingroup\$ @KennyLau What did you change? From what I can see, you just added <!-- language: lang-python -->.What does that change? \$\endgroup\$ – R. Kap Apr 16 '16 at 9:33
  • \$\begingroup\$ That can enable syntax highlighting for your code. \$\endgroup\$ – Leaky Nun Apr 16 '16 at 9:39
  • \$\begingroup\$ @KennyLau Wow, that's cool. I was wondering how I would do that on PPCG. Now I know! Thank you! :) \$\endgroup\$ – R. Kap Apr 16 '16 at 9:43

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.