AoCG2021 Day 20: Wonky license check

Question

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2018 Day 8.

---

The license file for an imaginary software system is defined as follows:

• The entire file is a sequence of non-negative integers.
• The entire file defines a tree of nodes.
• Each node in the tree has the following fields in the order:
  • Header, a single number indicating the number of child nodes.
  • Zero or more child nodes, as specified in the header.
  • Zero or more metadata entries (each being a single integer), as specified in the footer.
  • Footer, a single number indicating the number of metadata entries.

Hmm, does it really work? It should, because it is your job to validate the given license file!

An example of a valid license file:

2 0 10 11 12 3 1 0 99 1 2 1 1 1 2 3
A----------------------------------
  B----------- C-----------
                 D-----

A has two children (B, C) and three metadata entries. B has no children and three metadata entries. C has one child and one metadata entry, and so on. It is well-formed, so it is valid.

How about this?

2 1 0 0 1 1 0 0 1 1 0

The root node has 2 children and 0 metadata. Then we need to divide 1 0 0 1 1 0 0 1 1 into two nodes. But:

• 1 0 0 is not a valid node: it has 1 child and 0 metadata, but single 0 is not a valid node.
• 1 0 0 1 is not valid either: it has 1 child and 1 metadata, but again we are left with single 0.
• 1 0 0 1 1 is valid (1 child, 1 metadata, 0 0 being the child), but the rest 0 0 1 1 is not a valid node.
• 1 0 0 1 1 0 is not a valid node because 0 0 1 1 isn't.
• The first child cannot be longer than that because the second must have 1 metadata.

Therefore, the second example is not a valid license file.

Given a license file as an array of non-negative integers, determine if it is valid. You can choose to

• output truthy/falsy using your language's convention (swapping is allowed), or
• use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

Truthy:

[0, 0]
[1, 0, 0, 0]
[0, 99, 99, 99, 3]
[2, 0, 10, 11, 12, 3, 1, 0, 99, 1, 2, 1, 1, 1, 2, 3]

Falsy:

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

Answer 1

Ruby, 85 80 bytes

f=->l{a,*l,b=l;q=l.size;a==0?b==q:(1..q).any?{|x|f[l[0,x]]&&f[[a-1,*l[x,q],b]]}}

Try it online!

Let me explain:

The license is valid if:

• the first element is zero and the last element is the length of the list minus 2

or

• we can create 2 valid licenses by splitting the list in 2, removing the head from the first part and prepending it (minus 1) to the second part. A license in the format a x x x x x x y y y y y y y is valid if both x x x x x x and a-1 y y y y y y y are.

Answer 2

Python 3.8 (pre-release), 121 bytes

f=lambda a,l=1:any(f(a[:i])*f(a[i:],l-1)for i in range(len(a)))if l>1else[[]==a,a>[]<(s:=a[:~a[-1]])and f(s,s.pop(0))][l]

Try it online!

Answer 3

Curry (PAKCS), 49 bytes

f(0:x++[l])|length x==l=1
f(a:x++y)|a>0=f$a-f x:y

Try it online!

A port of @G B's answer.

This returns 1 if the license is valid, and nothing otherwise.

Though Curry has a Haskell-like syntax, its pattern matching is so powerful that this answer looks more similar to the Mathematica answer than the Haskell one.

Answer 4

Charcoal, 67 bytes

⊞υ⟦θ⟧Ｆυ¿ι«≔⊟ιη¿η«≔§η⁰ζ¿‹ζ⁼§η±¹⁻Ｌη²⊞υι¿ζＦ…³Ｌη⊞υ⁺ι⟦✂η¹κ¹⁺⟦⊖ζ⟧✂ηκ⟧»»Ｐ¹

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

⊞υ⟦θ⟧

Start by checking the whole licence as a list of one sublicence.

Ｆυ

Loop over the lists of sublicences.

¿ι«

If there are still sublicences to check:

≔⊟ιη

Remove one sublicence.

¿η«

If this sublicence is not trivially illegal, then:

≔§η⁰ζ

Get the number of its sublicences.

¿‹ζ⁼§η±¹⁻Ｌη²

If this is a valid licence with no sublicences, then...

⊞υι

... push the remaining sublicences to the list to scan.

¿ζ

Otherwise if this licence has sublicences, then:

Ｆ…³Ｌη

For each potential first sublicence:

⊞υ⁺ι⟦✂η¹κ¹⁺⟦⊖ζ⟧✂ηκ⟧

Append the first sublicence and the licence adjusted for the removal of the first sublicence to the list of licences to scan.

»»Ｐ¹

Otherwise, all sublicences validated and so this licence is valid.

Answer 5

JavaScript (ES6),  94  92 bytes

This is using GB's great insight.

Returns 0 or 1.

f=a=>a[a[n=a.length,0]+n-!!n]==n-2|a.some((_,i)=>f(a.slice(1,i))&&f([a[0]-1,...a.slice(i)]))

Try it online!

Answer 6

TypeScript Types, 378 bytes

//@ts-ignore
type a<T,N,C=[],P=[],Q=[...P,C]>=T extends[infer A,...infer R]?a<R,N,[...C,A],P>|a<R,N,[A],Q>:N extends Q["length"]?Q:[N,Q]extends[0,[[]]]?T:never;type b<D,N,M=[]>=N extends M["length"]?D:D extends[...infer D,{}]?b<D,N,[...M,0]>:never;type c<C>=C extends(infer C)[]?0 extends M<C>?0:1:0;type M<D>=D extends[infer C,...infer I,infer M]?1 extends c<a<b<I,M>,C>>?1:0:0

Try It Online!

Ungolfed / Explanation

// Returns all the ways an array can be chunked into Count subarrays
type Chunkify<Unchunked, Count, CurChunk=[], PrevChunks=[], AllChunks=[...PrevChunks,CurChunk]> =
  // Get the first element of Unchunked
  Unchunked extends [infer El, ...infer Rest] 
    // Return a union of:
    ?
      // Continue this chunk
      | Chunkify<Rest, Count, [...CurChunk, El], PrevChunks>
      // Start a new chunk
      | Chunkify<Rest, Count, [El], AllChunks>
    // Unchunked is empty.
    // If AllChunks.length == Count,
    : Count extends AllChunks["length"]
      // Return AllChunks
      ? AllChunks
      // Otherwise, if Count == 0 and AllChunks == [[]],
      : [Count, AllChunks] extends [0, [[]]]
          // Return []
        ? Unchunked
        // Invalid chunking
        : never

type RemoveMetadata<
  Data,
  MetadataCount,
  RemovedCount=[]
> =
  // If RemovedCount == MetadataCount,
  MetadataCount extends RemovedCount["length"]
    // Return Data
    ? Data
    // Otherwise, pop the last element off of Data
    : Data extends [...infer Initial, {}]
      // Recurse, incrementing RemovedCount
      ? RemoveMetadata<Initial, MetadataCount, [...RemovedCount, 0]>
      // Data is empty, but we still need to strip more metadata; return never
      : never

type ValidateLicenses<Chunkifications> =
  // Map over Chunkifications, extracting the chunks as a union
  Chunkifications extends (infer Chunks)[]
    // Return 0 if any of Chunks are invalid licenses
    ? 0 extends ValidateLicense<Chunks> ? 0 : 1
    // Invalid
    : 0

type ValidateLicense<Data> =
  Data extends [infer ChildCount, ...infer InnerData, infer MetadataCount]
    // Return 1 if any of the ways to chunk RemoveMetadata<InnerData, MetadataCount> into ChildCount chunks are valid lists of licenses
    ? 1 extends ValidateLicenses<Chunkify<RemoveMetadata<InnerData, MetadataCount>, ChildCount>> ? 1 : 0
    // Invalid
    : 0

type T0 = ValidateLicense<[0, 0]>
//   ^?
type T1 = ValidateLicense<[1, 0, 0, 0]>
//   ^?
type T2 = ValidateLicense<[0, 99, 99, 99, 3]>
//   ^?
type T3 = ValidateLicense<[2, 0, 10, 11, 12, 3, 1, 0, 99, 1, 2, 1, 1, 1, 2, 3]>
//   ^?
```

Answer 7

Rust, 156 bytes

fn f(a:&[usize])->bool{let l=a.len();l>1&&((a[0]<1&&a[l-1]==l-2)||a[0]>0&&(2..l).any(|i|f(&a[1..i])&&f(&{let mut z=a[i..].to_vec();z.insert(0,a[0]-1);z})))}

Try it online!

Making use of @G B's approach.

Answer 8

Pari/GP, 81 bytes

f(a)=#a&&if(a[1],sum(i=2,#a,f(a[2..i])*f(concat(a[1]-1,a[i+1..#a]))),a[#a]+2==#a)

Try it online!

A port of @G B's answer.

Answer 9

Haskell, 101 93 bytes

This uses G B's observation.

h(x:y)|x>0=or[h$take n y|n<-[0..l y],h$x-1:drop n y]
h y@(0:_)=last y==l y-2
h _=1<0
l=length

-8 bytes thanks to alephalpha

Try it Online!

Answer 10

05AB1E, 44 41 bytes

"ćUX_iRćsgQë.œ2ùεεNiX<š}}}εε®.V}0ìP}à"©.V

Port of @GB's Ruby answer.

Results in 1 for truthy and 0/"" for falsey (only 1 is truthy in 05AB1E).

Try it online or verify (almost) all test cases (the largest truthy test case times out because of .œ).

Explanation:

"..."          # Push the string below
     ©         # Store it in variable `®` (without popping)
      .V       # Execute it as 05AB1E code
               # (after which the result is output implicitly)

ć              # Head extracted; pop and push remainder-list and first item separately
 U             # Pop and store this first item in variable `X`
X_i            # If `X` is 0:
   R           #  Reverse the remainder-list
    ć          #  Extract head again (or extract tail actually)
     s         #  Swap so the remainder-list is at the top
      g        #  Pop and push the length of this remainder-list
       Q       #  Check if it's equal to the extracted tail
  ë            # Else:
   .œ          #  Get all possible partitions of the remainder-list
     2ù        #  And only keep those consisting of two partition-parts
       ε       #  Map over each partition:
        ε      #   Inner map over both partition-parts:
         Ni    #    If it's the second part:
           X<  #     Push `X` and decrease it by 1
             š #     Prepend it in front of the partition-part
          }    #    Close the if-statement
        }      #   Close the inner map
       }       #  Close the outer map
        ε      #  Map over the partitions again:
         ε     #   Inner map over both partition-parts again:
          ®    #    Push string `®`
           .V  #    And execute it as 05AB1E code as recursive call
         }     #   After the inner map:
          0ì   #   Prepend a 0 in front of each result
            P  #   Get the product of this result to check if all were truthy
        }      #  After the outer map:
         à     #  Get the maximum to check if any were truthy

Some notes:

• 05AB1E lacks any recursive methods, but with "..."©.V and ®.V we can mimic this behavior.
• You may be wondering why we first close the maps and then do the exact same maps again at }}εε? We do this to first create the correct partitions, before we do the recursive calls, otherwise variable X will be incorrectly overwritten by the inner recursive call. In @GB's Ruby answer, the variables a and b are within scope of the function, whereas in my full program, the X (which is basically variable a) would be overwritten in the inner calls.
• ć results in an empty string if the list is empty, which is why we use the 0ì before the P to convert all empty strings to 0, while keeping all other integers the same.

Answer 11

Wolfram Language (Mathematica), 62 bytes

-3 bytes thanks to @att.

_f=1<0
f[0,x___,l_]:=l==Tr[1^{x}]
f[a_,x__/;f@x,y__]:=f[a-1,y]

Try it online!

A port of @G B's answer.