20
\$\begingroup\$

Let a counting tree be a rooted tree in which every node is labeled with the number of descendants it has.

We can represent such trees as ragged lists with each node being represented by a list containing its label followed by its children. For example the following is a counting tree:

[5,[2,[0],[0]],[0],[0]]

However the brackets themselves are redundant since the labels fully capture the structure of the counting tree. So we can represent them simply as lists of integers. The example above is:

[5,2,0,0,0,0]

However not all lists of integers represent a counting tree. For example:

[5,1,2,0,0,0]

This can't work because 2 must be a child of 1, but it needs more descendants.

Challenge

Take as input a non-empty list of non-negative integers and determine if it represents a counting tree as described above. Output one of two distinct consistent values, one if the input is a valid counting tree the other if it is not.

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

Test cases

Valid

[5,2,0,0,0,0]
[5,2,1,0,0,0]
[5,2,1,0,1,0]
[5,3,1,0,0,0]
[6,5,4,3,2,1,0]
[0]

Invalid

[0,0,0,0,0,0]
[5,2,1,1,0,0]
[5,2,0,1,0,0]
[5,3,1,0,1,0]
[6,2,1,0,0,0]
[5,3,1,0,0,1]
[5,2,3,0,0,0]
\$\endgroup\$
2
  • \$\begingroup\$ I may have misunderstood something, but here is raw array: [6, [3, [0], [0], [0]], [1, [0]]] with short form: [6, 3, 0, 0, 0, 1, 0]. Is it valid? \$\endgroup\$
    – lesobrod
    Commented Mar 21, 2023 at 18:02
  • \$\begingroup\$ @lesobrod Yes that's valid. The short form of a valid counting tree is always valid. \$\endgroup\$
    – Wheat Wizard
    Commented Mar 21, 2023 at 18:20

12 Answers 12

9
+200
\$\begingroup\$

Nekomata + -e, 13 bytes

qCᵉLR↔<a*$h→L

Attempt This Online!


Here is the original answer in an old version of Nekomata:

Nekomata + -e, 16 bytes

qCᵉLR↔$-ᵐP∀*$h→L

This is a new golfing language I'm working on. It's still in a very early stage of development.

I haven't made the first release, so the link above is to the latest commit.

This is a non-deterministic language inspired by Curry, Brachylog and other language. Functions in Nekomata may have multiple possible results, and the interpreter will choose the result via backtracking.

Explanation

A port of @Neil's Charcoal answer.

qCᵉLR↔$-ᵐP∀*$h→L

                    # Take [5,2,0,0,0,0] as an example
                    # The stack is initialized with an infinite cycle of the input
q                   # Non-deterministically choose a contiguous subsequence of the input
                    # Take [2,0,0] as an example
                    # The stack is now ..., [5,2,0,0,0,0], [2,0,0]
 C                  # Uncons; pop a list and push the tail and the head
                    # The stack is now ..., [5,2,0,0,0,0], [0,0], 2
  ᵉL                # Check if the length of the tail is equal to the head
                    # The stack is still ..., [5,2,0,0,0,0], [0,0], 2 since the check passes
    R               # Range from 1 to n
                    # The stack is now ..., [5,2,0,0,0,0], [0,0], [1,2]
     ↔              # Reverse
                    # The stack is now ..., [5,2,0,0,0,0], [0,0], [2,1]
      $             # Swap
                    # The stack is now ..., [5,2,0,0,0,0], [2,1], [0,0]
       -            # Subtract
                    # The stack is now ..., [5,2,0,0,0,0], [2,1]
        ᵐP          # Check if all elements of the list are positive
                    # The stack is still ..., [5,2,0,0,0,0], [2,1] since the check passes
          ∀         # Find all possible results of a non-deterministic computation
                    # The stack is now ..., [5,2,0,0,0,0], [[3,4,3,2,1],[2,1],[],[],[],[]]
           *        # Multiply; this will fail if the two lists has different lengths
                    # The stack is now ..., [[15,20,15,10,5],[4,2],[],[],[],[]]
            $       # Swap
                    # Note that there are infinite many copies of the input on the stack
                    # The stack is now ..., [[15,20,15,10,5],[4,2],[],[],[],[]], [5,2,0,0,0,0]
             h      # Head of a list
                    # The stack is now ..., [[15,20,15,10,5],[4,2],[],[],[],[]], 5
              →     # Increment
                    # The stack is now ..., [[15,20,15,10,5],[4,2],[],[],[],[]], 6
               L    # Check if the length of the list is equal to the number
                    # The check passes, so there is a result

The flag -e set the interpreter to CheckExistence mode, which prints True if the computation has any result, and False otherwise. We don't care what the result really is.

\$\endgroup\$
2
  • 4
    \$\begingroup\$ Interesting new language! I’m interested in having a wiki/tutorial once it’s in a stable state. \$\endgroup\$
    – Fatalize
    Commented Feb 21, 2023 at 8:49
  • 2
    \$\begingroup\$ @Fatalize The language is still far from stable, but I've start writing a tutorial: github.com/AlephAlpha/Nekomata/blob/main/doc/Tutorial.md \$\endgroup\$
    – alephalpha
    Commented Feb 26, 2023 at 11:17
8
\$\begingroup\$

Vyxal, 17 bytes

ʀėṠ:Ẋ'ɖ↔ꜝnF;?ḣL≠∨

Try it Online!

Outputs a falsy value if it is a counting tree and a truthy if it's not.

Uses the fact that it is a counting tree iff

  1. the first number is equal to the length of the rest of the list
  2. for each pair of values a, b at indices i, j respectively the inclusive ranges [i, i+a] and [j, j+b] are either disjoint or one is a subset of the other

Get all inclusive ranges.

ʀ   # elementwise inclusive range from 0
 ė  # enumerate
  Ṡ # elementwise sum

Get all pairs and keep only those that don't satisfy 2.

:         # duplicate
 Ẋ        # cartesian product
  '     ; # filter by:
          #                        [[1,2,3],[3,4]]
   ɖ↔     #   scan by intersection [[1,2,3],[3]]
     ꜝ    #   keep truthy          [[1,2,3],[3]]
      n   #   push argument        [[1,2,3],[3]], [[1,2,3],[3,4]]
       F  #   set difference       [[3]]
          #   empty are falsy, non-emtpy are truthy

Check if 1. is not satisfied and combine the two.

?     # push input
 ḣ    # head extract
  L   # length
   ≠  # not equal
    ∨ # or
\$\endgroup\$
0
6
\$\begingroup\$

Curry (PAKCS), 36 bytes

f[0]=1
f(a:b++c)=f b*f(a-length b:c)

Attempt This Online!

\$\endgroup\$
6
\$\begingroup\$

Python, 63 bytes

f=lambda T,*t:T!=len(t)or T>0<f(T-(x:=t[0]+1),*t[x:])|f(*t[:x])

Attempt This Online!

Returns False for trees and True for fakes.

\$\endgroup\$
6
\$\begingroup\$

Charcoal, 28 23 bytes

∧⁼§θ⁰⊖Lθ⬤θ⬤✂θ⁺ικκ±¹¬›λμ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a counting tree, nothing if not. Explanation: Based on @AndrovT's approach, the first element must be one less than the length, then given any element e, the next e elements must all be less than the sequence from e down to 1, although the code actually extracts the elements in reverse so that within their slice they must not exceed their 0-based index.

   θ                    Input array
  § ⁰                   First element
 ⁼                      Equals
       θ                Input array
      L                 Length
     ⊖                  Decremented
∧                       Logical And
         θ              Input array
        ⬤               All elements satisfy
            θ           Input array
           ✂            Sliced from
              ι         Current value
             ⁺          Plus
               κ        Current index
                κ       To current index
                 ±¹     In reverse
          ⬤             All elements satisfy
                     λ  Inner value
                   ¬›   Is not greater than
                      μ Inner index
                        Implicitly print

Example: For the input [5,2,1,0,1,0], the length is 6 so the first element must be 5, then the subsequent 5 elements must be less than 5,4,3,2,1; the 2 elements after the 2 must be less than 2,1 and the 1 element after each 1 must be less than 1. (Trivially the 0 elements after each 0 satisfy the property as well.)

Previous 28-byte approach:

Fθ«⊞υιW∧υ¬↨υ⁰≧⁻¬⊟υυ¬υ»¿∨υ⊖ⅈ⎚

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a counting tree, nothing if not. Explanation:

Fθ«

Loop over the input integers.

⊞υι

Push them to the predefined empty list.

W∧υ¬↨υ⁰

While the list ends in 0...

≧⁻¬⊟υυ

... remove the trailing 0 and decrement the remaining elements.

¬υ

Count the number of counting trees found.

»¿∨υ⊖ⅈ⎚

Check that there was exactly one counting tree and that it ended with the last element.

\$\endgroup\$
2
  • \$\begingroup\$ Love this, great insight. \$\endgroup\$
    – Jonah
    Commented Feb 19, 2023 at 21:18
  • \$\begingroup\$ @Jonah Although actually a port of AndrovT's approach is 5 bytes shorter. Oh well. \$\endgroup\$
    – Neil
    Commented Feb 20, 2023 at 0:59
3
\$\begingroup\$

Retina 0.8.2, 61 bytes

\d+
$*
+%`^((1)*)1(1*),(\1(?!1)(?<-2>,1*)*)(?(2)^)
$4¶$3
^¶*$

Try it online! Link includes test cases. Explanation: Port of @alephalpha's Curry answer.

\d+
$*

Convert to unary.

+%`^((1)*)1(1*),(\1(?!1)(?<-2>,1*)*)(?(2)^)
$4¶$3

Repeatedly split each rooted tree into its first branch and remaining branches.

^¶*$

Check that there are only twigs left.

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

05AB1E, 19 bytes

ŒʒćsgQ}εāR‹}˜P*ćsgQ

Inspired by @Neil's top Charcoal, which is a port of @AndrovT's Vyxal answer.

Try it online or verify all test cases.

Explanation:

Π          # Get all sublists of the (implicit) input-list
 ʒ          # Filter it by:
  ć         #  Extract head; pop and push remainder-list and first item seperately
   s        #  Swap so the remainder-list is at the top of the stack
    g       #  Pop and push its length
     Q      #  Check if the length of the remainder-list and first item are equal
 }ε         # After the filter: map over each remaining sublist:
   ā        #  Push a list in the range [1,length] (without popping the list)
    R       #  Reverse it to [length,1]
     ‹      #  Element-wise less-than check: [a<length,b<length-1,...,y<2,z<1]
  }˜        # After the map: flatten the list of checks
    P       # Product to check if all were truthy
     *      # Multiply this 1/0 to each value in the (implicit) input-list
      ćsgQ  # Do a similar check as before within the filter on the input-list itself
            # (after which the result is output implicitly)

I've been unable to find anything shorter for *ćsgQ which works for both the [0,0,0,0,0,0] and [6,2,1,0,0,0] test cases. Checking whether the input-list is in the filtered list of sublists is an equal-bytes alternative:

ŒéʒćsgQ}¤IʪεāR‹}˜P

Try it online or verify all test cases.

Additional explanation:

 é          # Sort the sublists by length (shortest to longest)

  ¤         # Push the last sublist after the filter (without popping the list of lists)
   IÊ       # Check that it's NOT equals to the input-list
     ª      # Append this 0 or 1 to the list of sublists
            # (`āR‹` will succeed for 0 and fail for 1)
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 64 bytes

T=t=>t.shift()!=t.length|C(t)
C=$=>$>C&&C($.splice($[0]+1))|T($)

Try it online!

Code with comments:

isTree = tree =>
  tree[0] + 1 === tree.length &&
  isChildren(tree.slice(1))
isChildren = children =>
  children.length === 0 ||
    isTree(children.slice(0, children[0] + 1)) &&
    isChildren(children.slice(children[0] + 1))

Changing != into - makes it 64 bytes by returning truthy vs. falsy.

-1-2 byte by l4m2.

\$\endgroup\$
4
  • \$\begingroup\$ c+c>c => c>'' \$\endgroup\$
    – l4m2
    Commented Feb 20, 2023 at 6:32
  • 3
    \$\begingroup\$ Why did you post a separate answer instead of editing your incorrect answer? \$\endgroup\$
    – Neil
    Commented Feb 20, 2023 at 8:41
  • \$\begingroup\$ Maybe even c>T possible if T starts with $ \$\endgroup\$
    – l4m2
    Commented Feb 20, 2023 at 9:15
  • \$\begingroup\$ @Neil Since the previous one is simply incorrect. And this is a completely rewritten instead of a bug fix. \$\endgroup\$
    – tsh
    Commented Feb 21, 2023 at 1:50
2
\$\begingroup\$

Haskell, 85 65 bytes

-20 bytes thanks to @Wheat Wizard

h(n:w)=f(n:take n w)&&h(drop n w)
h _=1>0
f(n:w)=h w&&n==length w

Attempt This Online!

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

tinylisp 2, 88 bytes

(d F(\(L)(? L(*(<(h L)(# L))(F(](h L)(t L)))(F([(h L)(t L))))1
(\(L)(*(F L)(=(h L)(#(t L

The submission is the anonymous function in the second line.

You can try it at Replit. Example session:

tl2> (d F(\(L)(? L(*(<(h L)(# L))(F(](h L)(t L)))(F([(h L)(t L))))1
F
tl2> (\(L)(*(F L)(=(h L)(#(t L
(() (L) (* (F L) (= (h L) (# (t L)))))
tl2> (d G _)
G
tl2> (G (list 5 2 1 0 1 0))
1

Explanation

Our recursive helper function, F, analyzes a list as follows:

  • Is it empty? Return 1 (truthy).
  • Otherwise, split the list, conceptually, into head (first element) and tail (remaining elements).
    • Is the head greater than or equal to the list's total length? (This means the root of this subtree doesn't have enough children.) Return 0 (falsey).
    • Split the tail at the index given by the head. Recurse over each of these sublists. Return 1 if both results are 1; otherwise return 0.
(d F(\(L)(? L ... 1)))
(d F                 ) ; Define F as
    (\(L)           )  ; Lambda function taking list L
         (? L      )   ; If L is nonempty
              ...      ; (see below)
                  1    ; Else, return 1

(*(<(h L)(# L))(F(](h L)(t L)))(F([(h L)(t L))))
(*                                             ) ; Multiply these (logical AND):
  (<(h L)(# L))                                  ; 1. Head of L < length of L
               (F             )                  ; 2. Recursive call on:
                 (]          )                   ;    Take
                   (h L)                         ;    (head of L) elements
                        (t L)                    ;    from tail of L
                               (F             )  ; 3. Recursive call on:
                                 ([          )   ;    Drop
                                   (h L)         ;    (head of L) elements
                                        (t L)    ;    from tail of L

F verifies that a list represents a "forest" of zero or more counting trees concatenated. Our main function also needs to verify that we have exactly one counting tree. To do so, we first call F on the list, and then check whether the head is exactly equal to the length of the tail.

(\(L)(*(F L)(=(h L)(#(t L)))))
(\(L)                        ) ; Lambda function taking list L
     (*                     )  ; Multiply these (logical AND):
       (F L)                   ; 1. Call F on L
            (=             )   ; 2. These are equal:
              (h L)            ;    Head of L
                   (#(t L))    ;    Length of tail of L
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 75 bytes

Returns \$0\$ for valid, or \$1\$ for invalid.

f=([v,...a],s=v)=>v+1&&a.length!=s|f(a.slice(v=a[0]),s-++v)|f(a.slice(0,v))

Try it online!

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

Wolfram Language (Mathematica), 147 bytes

(a=#;l=Length@a;And@@(IntervalMemberQ[#1,#2]||Length@IntervalIntersection[#1,#2]==0&@@@Subsets[Interval@{#,#+a[[#]]}&/@Range@l,{2}])&&a[[1]]==l-1)&

Try it online!

I was looking at the problem in terms of interval arithmetic, and it seems got the same algorithm as @AndrovT. Unfortunately, Mathematica has almost no shorthands for cool functions, so code looks huge (

Explained:

(*Total logic And*)
And @@
 (*In True case intervals must be disjointed or nested*)
 (IntervalMemberQ[#1, #2] || 
     Length@IntervalIntersection[#1, #2] == 0 & @@@
   (*All subsets length 2*)
   Subsets[
    (*All intervals i + array[i]*)
    Interval@{#, # + a[[#]]} & /@ Range@l
    , {2}])
        (*Is first element equal length of the rest*)
        && a[[1]] == l - 1 &
\$\endgroup\$

Your Answer

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

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