17
\$\begingroup\$

Given as input a list of positive integers, your task is to determine if every integer present has exactly two neighbors in the list. The neighbors of a integer \$x\$ are the distinct integers that appear next to an \$x\$ anywhere in the list. For example in the list:

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

The number 3 has 3 neighbors 1, 4 and 2. So this input is not valid. The list

[1,2,3,1]

is valid because every number has exactly two neighbors.

This is a challenge, so in addition your code performing the task it must also be written so that when interpreted as a list of bytes, it passes the test itself. That is, every byte present in your source must have exactly two neighbors in your source.

You may take a list of positive integers for input in any reasonable method. Output one of two consistent distinct values. One value should only be output if the property is satisfied, the other if it is not.

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

Test cases

truthy

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

falsey

[1]
[1,2]
[1,2,1,2]
[1,3,4,4,3,2,1]
\$\endgroup\$
15
  • 2
    \$\begingroup\$ Is it required to handle the input of an empty list? \$\endgroup\$
    – Yousername
    Feb 7 at 0:02
  • 2
    \$\begingroup\$ @Fatalize All members in the empty list have 0 neighbors and 2, and any number for that matter. \$\endgroup\$
    – Wheat Wizard
    Feb 7 at 12:51
  • 3
    \$\begingroup\$ @WheatWizard Well you could use the definition: The set of neighbour counts of all elments is {2}. Which is not too far-fetched and would leave out the empty list. \$\endgroup\$
    – loopy walt
    Feb 7 at 21:29
  • 2
    \$\begingroup\$ Consider [1, 2, 3, 1]. It's truthy, but there are an infinite number of potential members that have zero neighbors. They aren't considered a problem because they are absent. A universal quantifier over the empty set is always true and an existential quantifier over it is always false. See, for another example, Java's Stream.allMatch(). \$\endgroup\$ Feb 7 at 21:48
  • 2
    \$\begingroup\$ @Fatalize The opposite of "every element of the list has 2 unique neighbors" is "some element of the list that doesn't have 2 unique neighbors". So for every falsy case, there must be an element of the list that witnesses that falsyness. The empty set has no such witness, and so it can't be falsy. \$\endgroup\$ Feb 10 at 1:29

9 Answers 9

20
\$\begingroup\$

Python, 2955 bytes

eval("(lalalalalalalalalalalalalalalalalalalalalalalalalalalalalalalalal("'[1 :37])mbmbmbmbmbmbmbmbmbmbmbmbmbmbmbmbmbmbmbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbm)]73: 1['"(lalalalalalalalalalalalalalalalalal("'[1 : : : : : : : : : : : : : : :37])mbdsdsdsdsds{u,inzp-+for*}<=2#eval("'"'[1 :3:3:3:3:3:3:3:3:3:3:3:3:3:3:37])mbds{s{s{s{s{s{s{s{s{s{s{s{s{s{s{s{s{s{s{sdsdbm)]73: 1['"'"(lave#2=<}*rof+-pzni,u{u{u{u{u{u{u{u{u{u{u{u{u{u{u{u{u{sdbmbmbmbmbmbmbmbmbmbmbmbmbmbmbm)]73: 1['"(l(l(l(l(l(l(l(l(l(l(l(l(l(l(l(l(l(l("'[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1['"(l(l(l(l(l(l(l(l(lave#2=<}*rof+-pzni,u,u,u,u,u,u,u,u,u,u,u,u,u,u,u,u,u,u,u,i,i,i,i,inzp-+for*}<=2#eval("'[1 :37])m)m)m)m)m)m)m)m)m)m)m)m)m)m)m)m)m)m)m)])])])])])]73: 1['"(lave#2=<}*rof+-pzninininininininininininininininininininznznznznznznznznzp-+for*}<=2#eval("'[1 : : : : : : : : : : : :37])mbds{u,inznzp-+for*}<=2#eval("'"'[1 :37])mbds{u,ininininininininininininininininininzpzpzpzpzpzpzpzpzpzni,u{sdbm)]73: 1['"'"(l(l(l(l(l(l(l(lave#2=<}*rof+-pzni,u{sdsdsdsdsdsdsdsdsdsdsdsdsdsdbm)]73: 1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1 :3:3:3:3:3:3:3:3:3: 1['"(lave#2=<}*rof+-+-+-+-+-+-+-+-+-+-+-+for*}<=2#eval("'[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 :37]7]7]7]7]7]7]7]7]73: 1['"(lave#2=<}*rof+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-pzni,u{sdsdsdsdsdsdsdsdsdsdsdsdsdsdbm)]73: 1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1 1['"'"(lave#2=<}*rof+-pzni,u{sdbm)]73:3:3:3:3:3:3:3:3:3:3:3:3:3:3:3:3:3:37])])])])])]73: 1['"(lave#2=<}*rof+-pzni,u,u,u,u,u,u,u,u,u,u,u,u,u,u,u,u,u,u{sdsdsdsdsdsdsdsdsdsdsdsdsdsdbm)]73: 1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1[1 1['"'"(lave#2=<}*rof+-pzni,u{sdbm)]73:3:3:3:3:3:3:3:3:3:3:3:3:3:3:3:3:3:37])])])])])])])])]73: 1['"(lave#2=<}*rof+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-pzni,u{s{s{s{s{u,inzp-+for*}<=2#eval("'[1 :37])])])])])])])])])]73: 1['"(lave#2=<}*rofofofofofofofofofofofofofofofofofofoforororororororororororororororororororororororororororof+-pzni,u{sdbm)]73: : : : : : : : : : : : : : :37])mbds{u{u{u{u{u{u{u{u{u{u{u{u{u{u{sdbm)]73: : : : : : : : : : : : : :37])mbds{u,inininininininininininininininininininznznznzp-+for*}<=2#eval("'[1 :37])mbds{s{s{s{s{s{s{s{sdbm)]73: 1['"(lave#2=<}*r*r*r*r*r*r*r*r*r*r*r*r*rof+-pzni,u{s{s{s{s{s{s{s{sdbm)]73: 1['"'"(lave#2=<}*}*}*}*}*}*}*}*}*}*rof+-pzni,u{sdbm)])])])])])])])])])])])])])])])])])])])m)m)m)m)m)m)m)m)]73: 1['"(lave#2=<}*rofofofofofofofofofofofofofofofofofofoforororororororororororororororororororororororororororof+-pzni,u{sdbm)]73: : : : 1['"'"(lave#2=<}*rof+-pzni,u{sdbmbmbmbmbds{u,inzp-+for*}<=2#eval("'"'[1 : : : : : : : : : : : : :37])mbds{u,inininininininininininininininininininininininininininzp-+for*}<=2#eval("'[1 : : : : : : : : : : : : : : :37])mbdsdsdsdsdsdsdsdsdsdbm)]73: 1['"(lave#2=<}<}<}<}<}<}<}<}<}<}<}<}<}<}<}<}<}<}<}<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<}*rof+-pzni,u{u{u{u{u{u{u{u{u{sdbm)]73: 1['"'"(lave#2=2=2=2=2=2=2=2=2=2=2=2=2=2=2=2=2=2=<}*rof+-pzni,u{sdbm)]73: 1['[1 : :37])

Attempt This Online!

D'oh!

How (if you can be bothered)

The long string slices down to

lambda s:{sum([(u,m)in zip(s[:-1]+s[1:],s[1:]+s)for u in{*s}])for m in s}<={2}

It was generated (by computer program) by walking up and down the string

[1 :37])mbds{u,inzp-+for*}<=2#eval(

wasting just the right amount of time to get the right characters at the chosen spacing.

A few more details:

Lets do a small example:

Let's assume our program is

abracadabra

The basic idea is arrange the unique letters in some order, UNQ = abrcd, say, and then do something like ababrbrcdabrcrbadadadababrbrcda. Because this was created by walking up and down UNQ every letter has at most two neighbours. Now, if we slice this with step = 3 we recover abracadabra: AbaBrbRcdAbrCrbAdaDadAbaBrbRcdA. Note that in order to break parity we needed UNQ to be of odd length and to wrap around.

With the wrapping around all the spare neighbour slots we might have hoped to harness in the next step are used up. We'll see in a moment that that is a bit of a problem:

We still need to wrap our magic string in an eval statement and do the slicing.

But if we try something like eval("ababrbrcdabrcrbadadadababrbrcda"[ : :3]) then the characters touching the quotation marks are over-booked. They already had two neighbours, so the quotation mark is one too many.

We can try and solve this by integrating the wrapper code into UNQ: UNQ = "[ :3])brcdeval(

It almost works, but, of course, the single quotation mark will cause all sorts of problems when wrapping around. We could try a similar trick to the one we have already tacitly used to manage the double colon in the slicing expression: instead of [::3] (: has three neighbours) use [ : :3]. But with the colon we have used up the "neutral" space character already. We could try and use tab or even newline but there is one slightly neater way: use two kinds of quotes: single and double. UNQ = "[ :3])brcdeval(' Then at every other wrap-around we have to add one wiggle over the quotes: "...'"'"....'".....'"'"....' etc. Python will concatenate this into one single string that contains a few occurrences of the character pair '".

\$\endgroup\$
6
  • 1
    \$\begingroup\$ This is really clever. I had originally thought, "oh, the only submissions will be esos where you can write a program with all unique characters". You proved me wrong. I would be curious to see the generating prog. \$\endgroup\$
    – Jonah
    Feb 7 at 16:49
  • \$\begingroup\$ @Jonah It's really ugly. You'd have to confirm first that I will not be held responsible for any permanent brain damage you may suffer from looking at it. \$\endgroup\$
    – loopy walt
    Feb 7 at 17:18
  • \$\begingroup\$ Perhaps a short summary of how the algo works instead? \$\endgroup\$
    – Jonah
    Feb 7 at 18:51
  • 1
    \$\begingroup\$ @Jonah Haha! Did I manage to scare you off? I'll see what I can do for an explanation. \$\endgroup\$
    – loopy walt
    Feb 7 at 19:00
  • 1
    \$\begingroup\$ Do you have enough freedom in ordering the string [1 :37])mbds{u,inzp-+for*}<=2#eval( to golf the constant 37 down to a smaller number? \$\endgroup\$
    – Nitrodon
    Feb 7 at 21:35
10
\$\begingroup\$

Jelly, 12 bytes

ṢƝQ⁺€FċⱮ=2PṢ

Try it online!

Inspired by AndrovT's port of my original solution, and come to think of it, basically ports Kevin Cruijssen's solution from before porting that. While Vyxal and 05AB1E have a nice single-byte palindromize builtin, Jelly's is a digraph, and flanking the program with Πwould effectively comment the whole thing out (though it is still nominally accessible as a function, for the same byte count).

 Ɲ              For each pair of adjacent elements in the input,
Ṣ               yield it sorted.
  Q             Uniquify the list of pairs
   ⁺            then do it again
    €           to each pair.
       Ɱ  P     For every element of the input,
      ċ         is its number of occurrences in that list
     F          flattened
        =2      equal to 2?
           Ṣ    Sort the result (no-op).

My original solution, for posterity:

Jelly, 14 13 bytes

¹ŒḄ,ƝQFċⱮ=4P¹

Try it online!

-1 porting AndrovT's Vyxal answer back

 ŒḄ              Palindromize the input, making all adjacencies bidirectional.
   ,ƝQ           Find the unique pairs of adjacent elements.
        Ɱ  P     For every element of the input,
       ċ         is its number of occurrences in that list
      F          flattened
         =4      equal to 4?
¹           ¹    No-ops.
\$\endgroup\$
1
  • 2
    \$\begingroup\$ @Jonah "Note the trailing space." I guess I could use a different no-op for visual clarity though! \$\endgroup\$ Feb 7 at 1:51
9
\$\begingroup\$

Vyxal, 20 11 bytes

∞2lUfvO4=A∞

Try it Online!

This is valid because all characters except are used exactly once and is both at the beginning and the end.

Now uses the same approach as @Unrelated String's Jelly answer.

∞2lUfvO4=A∞
∞            # palindromize
 2l          # overlapping pairs
   U         # uniquify
    f        # flatten
     vO      # for each in number input count how many times it occurs
       4=    # is equal to four?
         A   # are all true?
          ∞  # palindromize
\$\endgroup\$
7
\$\begingroup\$

05AB1E, 16 12 11 bytes

ûü2Ù˜s¢4QPû

-4 bytes thanks to @CommandMaster.
-1 byte porting AndrovT's Vyxal answer, which is based on @UnrelatedString's Jelly answer, so make sure to upvote both of them as well!

Try it online or verify all test cases or verify its own source.

Explanation:

û           # Palindromize the (implicit) input-list
 ü2         # Get all overlapping pairs of this list
   Ù        # Uniquify the pairs
    ˜       # Flatten it
     s      # Swap the (implicit) input-list to the top of the stack†
      ¢     # Count how many times each value of the input occurs in the list
       4Q   # Check for each count whether it's equal to 4 (1 if 4; 0 otherwise)
         P  # Get the product to check if all are truthy
          û # No-op palindromize (1 or 0 will remain as is)
            # (after which the result is output implicitly)

† Could be just I (push input), but with a swap it's easier to write the source verifier. 🤷

\$\endgroup\$
3
  • \$\begingroup\$ The code in verify its own source seems to ignore the actual input and just output 1. This should work, I believe \$\endgroup\$ Feb 7 at 15:00
  • 2
    \$\begingroup\$ Additionally, I don't see why wü2€êÙ˜I¢<Pw can't work for 12 bytes. \$\endgroup\$ Feb 7 at 15:06
  • \$\begingroup\$ @CommandMaster Ah, I accidentally left the X in the verifier after I removed the U and used a Duplicate instead. And thanks for the -4 to combine the check and edge case! \$\endgroup\$ Feb 7 at 16:12
4
\$\begingroup\$

Brachylog, 21 20 bytes

s₂ᶠ{|↔ᵐ}ᵇcdhᵍlᵛ2∨?Ės

Try it online!

This code is self-validating because all symbols are used only once, except s used at the very beginning and very end.

3 bytes lost to deal with the empty list.

Explanation

s₂ᶠ                    Find all sublists of 2 consecutive elements
   {|↔ᵐ}ᵇc             Append the list of reversed sublists to it
          d            Remove duplicate sublists
           hᵍ          Group by the first element of each sublist
             lᵛ2       Verify that each group has length 2
                ∨?Ė    Else: the input is the empty list
                   s   Sublist of the empty list, always succeeds (only here for self-validation constraint)
\$\endgroup\$
3
\$\begingroup\$

Husk, 18 bytes

IΠmo=4`#ΣuẊe§+h↔¹I

Try it online!

Outputs 1 if every integer present has exactly two neighbors, 0 otherwise.
Could be 17 bytes with output as truthy (nonzero) or falsy (zero).

                 I  # identity = leave input unchanged
I                   # identity = leave output unchanged
 Π                  # get the product of
  m                 # mapping over the input:
   o                #   composition of 2 functions:
      `#            #     number of instances
    =4              #     equals 4          
        Σ           # among all elements from
         u          # unique 
          Ẋe        # adjacent pairs
            +       # in the concatenation of
             h      # the head (omit last item)
              ↔     # and the reverse
               ¹    # of the input
\$\endgroup\$
3
\$\begingroup\$

Pyth, 24 bytes

!!smn2l{fPI<1T.-R]dC,tQQ

Try it online!

Outputs False for truthy and True for falsy. Self validating since each character is used only once except the start and end which are repeated once.

Explanation

!!smn2l{fPI<1T.-R]dC,tQQQ    # implicitly add Q
                             # implicitly assign Q = eval(input())
   m                    Q    # map Q over lambda d
                   C,tQQ     #   take all pairs of adjacent elements in Q
              .-R]d          #   remove d from each pair once if possible
        f                    #   filter for pairs that are no longer pairs by looking at
         PI<1T               #     T[:-1] == T[:-1][:-1]
       {                     #   deduplicate
    n2l                      #   number of remaining elements != 2
  s                          # sum (if any elements did not have two neighbors the sum will be non zero)
!!                           # not not (takes 0 to False and non zero to True)
\$\endgroup\$
1
\$\begingroup\$

Nibbles, 13 bytes (26 nibbles)

|$!=2,|`$.!>>@_:`<$?$@ ~39

This corresponds to the Nibbles program with bytes:

93 c0 1a d9 ec 9c 04 51 e3 d4 f3 40 93

Output is falsy (empty) if all elements have exactly 2 neighbours, truthy (nonempty list of elements that do not have exactly 2 neighbours) otherwise.

|$!=2,|`$.!>>@_:`<$?$@  # main program:
|                       # filter
 $                      # the input
                        # keeping elements for which
     ,|                 #   the number of
       `$.!>>@_:`<$     #   of all adjacent pairs
                   ?$@  #   that contain them
  !=2                   #   is not equal to 2
  
       `$.!>>@_:`<$     # adjacent pairs:
       `$               # get unique elements of
         .              #   map over
          !>>@_:        #   all adjacent pairs
                `<$     #      sorting them
                
~39                     # finally append nibbles 0 9 3

enter image description here

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

Javascript, 202 199 bytes

a=>{let o=1;a.forEach(i=>{let n=[];a.forEach((j,y)=>{if(j==i){if(y!=0)if(!n.includes(a[y-1]))n.push(a[y-1]);if(y!=a.length-1)if(!n.includes(a[y+1]))n.push(a[y+1])}});if(n.length!=2){o=0;}});return o}

Gets an array as input and return 1 for true and 0 for false

Ungolfed version:

let x = a => {
  let o = 1;
  a.forEach((i) => {
    let n = [];
    a.forEach((j, y) => {
      if (j == i) {
        if (y != 0) if (!n.includes(a[y - 1])) n.push(a[y - 1]);
        if (y != a.length - 1) if (!n.includes(a[y + 1])) n.push(a[y + 1]);
      }
    });
    if (n.length != 2) {
      o = 0;
    }
  });
  return o;
};

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ I think you missed the additional self-validating restriction: "... it must also be written so that when interpreted as a list of bytes, it passes the test itself. That is, every byte present in your source must have exactly two neighbors in your source." With a quick look I can see a has at least 4 neighbors. \$\endgroup\$
    – Wheat Wizard
    Feb 10 at 13:34
  • \$\begingroup\$ @WheatWizard Oops, yeah I didnt understand that. It is really hard to do it in languages like js, c, c++, ... \$\endgroup\$ Feb 10 at 13:37
  • \$\begingroup\$ I Dont have any idea of how doing this... \$\endgroup\$ Feb 10 at 13:38
  • \$\begingroup\$ The python answer should give an idea for how this could be done in JS. \$\endgroup\$
    – Wheat Wizard
    Feb 10 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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