14
\$\begingroup\$

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 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]
\$\endgroup\$
6
  • 13
    \$\begingroup\$ Reports say that the guy who came with this format has since be fired. :-p \$\endgroup\$
    – Arnauld
    Dec 20, 2021 at 0:56
  • \$\begingroup\$ Suggest testcase: [0, 0, 0, 0] (cat of two valid license files). \$\endgroup\$
    – tsh
    Dec 20, 2021 at 1:29
  • \$\begingroup\$ But a valid license file may still be ambiguous. For example, both [2, 0, 0, 1, 0, 3, 1, 0, 0, 0, 0] -> 2{0(0 1 0 3);1{0(0)}(0)}(0) and [3, 0, 0, 1, 0, 3, 1, 0, 0, 0, 0] -> 3{0(0);1{0(3 1)}(0);0(0)}(0) are valid, and then [5, 0, 0, 1, 0, 3, 1, 0, 0, 0, 0, 0, 1, 0, 3, 1, 0, 0, 0, 0] is ambiguous. So, although we can do validation on it, it still does not work. \$\endgroup\$
    – tsh
    Dec 20, 2021 at 3:12
  • \$\begingroup\$ @tsh Depends on the definition of work :P But yeah, a fair warning: Do not attempt this at home or at work. \$\endgroup\$
    – Bubbler
    Dec 20, 2021 at 3:30
  • \$\begingroup\$ shorter ambiguous example: 3 0 ? 1 0 3 1 0 3 1 0 0 ? 1 0 can be 0 ? 1 -- 0 3 1 0 3 -- 1 0 0 ? 1 or 0 ? 1 0 3 -- 1 0 3 1 0 -- 0 ? 1 \$\endgroup\$
    – loopy walt
    Dec 20, 2021 at 4:25

11 Answers 11

7
\$\begingroup\$

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.
\$\endgroup\$
1
  • \$\begingroup\$ Nice observation \$\endgroup\$
    – Jonah
    Dec 20, 2021 at 7:43
3
\$\begingroup\$

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!

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

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.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 67 bytes

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

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.

Fυ

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.

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

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:

F…³Lη

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.

»»P¹

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

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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]>
//   ^?
```
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

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

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 before the P to convert all empty strings to 0, while keeping all other integers the same.
\$\endgroup\$
0
\$\begingroup\$

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.

\$\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.