11
\$\begingroup\$

Given a list of positive integers as input you are to determine if there is a way to pair up the elements such that:

  • All but one element is in a pair
  • No element is in more than one pair
  • Every pair is of equal elements
  • No two pairs have elements separated by the same distance in the original list

For example if the input is:

[2,2,1,2,3,3,1]

Then we can choose the following pairs:

[2,2,1,2,3,3,1] <- Input
  [2,  2]       % Separated by 2
    [1,      1] % Separated by 4
        [3,3]   % Separated by 1

The first 2 is the element which is not in a pair.

Very importantly, when you take the list of code points of your program it must satisfy the property. Answers which do not are invalid.

This is the goal is to minimize the size of your source code as measured in bytes while satisfying the constraints.

To decide, your program should output one of two fixed values. The first if the solution there is a pairing of the input list as described and the second of the two values if there is not.

Test cases

Pairing possible

[1]
[1,1,1]
[1,1,1,1,1]
[2,2,1,1,1]
[2,2,1,2,1]
[2,2,1,2,3,3,1]
[2,2,2,1,2,3,3]

Pairing not possible

[]
[1,1]
[1,2,3]
[1,1,1,1]
[2,2,1,2,3]
[2,2,1,3,3]
[1,1,1,1,1,1]
[2,2,2,2,1,3,3]
\$\endgroup\$
9
  • 2
    \$\begingroup\$ "Given a list of positive integers" - but what if "the list of code points of your program" contains zero (i.e. the program contains a null character)? \$\endgroup\$
    – pxeger
    Jul 8 at 14:39
  • 2
    \$\begingroup\$ I'm not sure I understand the relation of the title to the actual task. "Unique" in what way? Does the pattern resemble a "Rainbow" in any way? \$\endgroup\$ Jul 8 at 15:41
  • 2
    \$\begingroup\$ Just curious: why this constraint "All but one element is in a pair"? \$\endgroup\$
    – Jonah
    Jul 8 at 19:47
  • 2
    \$\begingroup\$ To clarify, if P is a valid program (minus the restriction) and # a comment character, then P#P is a valid program with the restriction? \$\endgroup\$
    – Jonah
    Jul 8 at 21:09
  • 1
    \$\begingroup\$ @Jonah I think you want P#reverse P. If your program is ab then ab#ab is not a valid program, it doesn't pass the restriction. \$\endgroup\$
    – Wheat Wizard
    Jul 8 at 21:11

3 Answers 3

4
\$\begingroup\$

J, 151 bytes

(1=1#.2|1#.=)*.1 e.[:(~.@;-:;)&>@,@{<@(i.@!@#<@(2|@-/\]}.~2|#)@A.])@I.@=NB. .BN=@.I@)].A@)#|2~.}]\/-@|2(@<#@!@.i(@<{@,@>&);:-;@.~(:[.e 1.*)=.#1|2.#1=1(

Try it online!

What the hell, I'll kick things off with this grotesquerie of brute force. Looking forward to seeing more clever solutions....

\$\endgroup\$
3
  • \$\begingroup\$ You can definitely make the comment a lot shorter. As a proof of concept notice that every pair currently has an odd distance between them. Towards the end of the program there are two @s which are an even distance away from eachother So instead of connecting those across the comment boundary just connect them to each other and drop their pairs from the comment. This breaks the all odd property by decreasing a bunch of the pair sizes but it all works out \$\endgroup\$
    – Wheat Wizard
    Jul 8 at 22:18
  • \$\begingroup\$ Try it online! \$\endgroup\$
    – Wheat Wizard
    Jul 8 at 22:18
  • \$\begingroup\$ Thanks, will update when back. It seems to be competitive you need a separate program to minimally extend your base program…. \$\endgroup\$
    – Jonah
    Jul 8 at 22:58
2
\$\begingroup\$

Pyth, 67 63 bytes

&ff&{IaMY!fnF@LQZYcR2.PTlT-LUQUQ%lQ2 " 2%UU-TTP.2RcYZ@Fnf!YMaI{

Try it online! -- Truthy test suite -- Falsey test suite

(Outputs 1 for true and [] for false)


The " near the middle of the program is the unpaired character. Everything after it is part of a string literal.

Most characters in the main program have a twin in the string literal. Below are the exceptions:

Character Index A Index B Distance
& 0 3 3
f 1 2 1
L 14 27 13
Q 15 31 16
l 24 33 9
Q 29 34 5

Explanation

-LUQUQ - Build a list of lists of indexes, each list containing all but one index of the input

f ... cR2.PTlT - for each list, generate all permutations, and split into chunks of size 2

f ... !fnF@LQZY - for each permutation, check whether the indexes of each pair correspond to equal elements of the input...

&{IaMY - ... and that the differences between each pair is unique

If no permutation for any list of indexes satisfies those conditions, the & short-circuits and [] is returned. Otherwise...

%lQ2 - ...return the length of the input mod 2

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 43 bytes

ā<œ.Δ¨2ôDÆÄDÙQiè€ËP]gÉqÉg]PË€èiQÙÄÆô2¨Δ.œ<ā

Try it online.

The base program is 22 bytes: ā<œ.Δ¨2ôDÆÄDÙQiè€ËP]gÉ - try it online or verify all test cases.
(Although could be 21 bytes if just truthy/falsey would have been allowed instead of two consistent values, where the truthy results are still 1, but the falsey results would be either "" or 0.)

Unfortunately, it only contains D as duplicated used character, and everything else is unique. So we'll just add a trailing q (the unique character) and the reversed program minus the two Ds.

Explanation:

ā                    # Push a list in the range [1, (implicit) input-length]
 <                   # Decrease each by 1 to the range [0,length)
  œ                  # Get all permutations of this list
   .Δ                # Get the first list that's truthy for (or -1 if none are):
     ¨               #  Remove the last index
      2ô             #  Split all other indices into pairs
        D            #  Duplicate this list
         Æ           #  Reduce each inner pair by subtracting
          Ä          #  And then taking their absolute values
           DÙQi      #  If this list of absolute differences is unique:
           D         #    Duplicate
            Ù        #    Uniquify
             Q       #    Check if both lists are still the same
              i      #    Pop, and if this is truthy:
               è     #   Index the pairs into the (implicit) input-list
                €Ë   #   Check if for each pair of values if they're the same
                  P  #   Check if this is truthy for all of them
    ]                # Close the if-statement and find_first-loop
     g               # Pop and push the length (2 for the -1 results)
      É              # Check if this length is odd
       q             # Stop the program, making everything after it no-ops
                     # (and implicitly output the result)
Ég]PË€èiQÙÄÆô2¨Δ.œ<ā # No-ops
\$\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.