27
\$\begingroup\$

In set theory, the natural numbers \$\mathbb{N} = \{0, 1, 2, 3, ...\}\$ are usually encoded as pure sets, that is sets which only contain the empty set or other sets that are pure. However, not all pure sets represent natural numbers. This challenge is about deciding whether a given pure set represents an encoding of natural number or not.

The encoding of natural numbers works in the following way1:

  • Zero is the empty set: \$ \text{Set}(0) = \{\} \$
  • For a number \$n > 0\$: \$ \text{Set}(n) = \text{Set}(n-1) \cup \{\text{Set}(n-1)\}\$

Thus, the encodings of the first few natural numbers are

  • \$ 0 \leadsto \{\}\$
  • \$ 1 \leadsto \{0\} \leadsto \{\{\}\}\$
  • \$ 2 \leadsto \{0,1\} \leadsto \{\{\},\{\{\}\}\}\$
  • \$ 3 \leadsto \{0,1,2\} \leadsto \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\$
  • \$ 4 \leadsto \{0,1,2,3\} \leadsto \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\}\$

The Task

  • Given a string representing a pure set, determine whether this set encodes a natural number according to the above construction.
  • Note, however, that the elements of a set are not ordered, so \$\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\$ is not the only valid representation of \$3\$ as e.g. \$\{\{\{\}\},\{\},\{\{\{\}\},\{\}\}\}\$ represents the same set.
  • You may use [], () or <> instead of {}.
  • You may assume the sets are given without the , as separator.
  • You can assume there won't be any duplicate elements in the input, e.g. {{},{}} is not a valid input, and that the input is well-formed, e.g. no {{},, {,{}} or similar.

Test Cases

True:

{}
{{}}
{{},{{}}}
{{{}},{}}
{{},{{}},{{},{{}}}}
{{{},{{}}},{},{{}}}
{{{{}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
{{{{{}},{}},{{}},{}},{{}},{},{{},{{}}}}
{{},{{}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{{}},{}},{{},{{}},{{},{{}}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}

False:

{{{}}}
{{{{}}}}
{{{{}},{}}}
{{},{{}},{{{}}}}
{{{},{{}}},{{}}}
{{{{{}}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{{}}}}}
{{{{{}},{}},{{{}}},{}},{{}},{},{{},{{}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}

Related: Natural Construction (Output the set encoding of a given natural number.)
1 See https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers

Improve this question
\$\endgroup\$
13
  • 13
    \$\begingroup\$ The test cases look like a program in a (yet) unimplemented esolang :) \$\endgroup\$
    – Galen Ivanov
    Commented Dec 20, 2018 at 20:04
  • 2
    \$\begingroup\$ can the input be a data structure (nested lists) instead of a string? \$\endgroup\$
    – ngn
    Commented Dec 20, 2018 at 21:12
  • 3
    \$\begingroup\$ I thought it was Brain-flak for a moment. \$\endgroup\$
    – Belhenix
    Commented Dec 20, 2018 at 22:21
  • 5
    \$\begingroup\$ @ngn No, input needs to be a string. \$\endgroup\$
    – Laikoni
    Commented Dec 21, 2018 at 9:25
  • 4
    \$\begingroup\$ @KirillL. Technically these answers weren't valid to begin with as the challenge always stated "Given a string representing a pure set", though I do see the point that allowing nested data structures allows for interesting golfing opportunities. However, I find it hard to decide where to draw the line on what is an allowed data structure and what isn't to avoid abuse of a too lenient input format, so I decided to restrict inputs to strings for the sake of simplicity and unambiguousness. \$\endgroup\$
    – Laikoni
    Commented Dec 21, 2018 at 22:00

12 Answers 12

Reset to default
13
\$\begingroup\$

JavaScript (Node.js), 53 48 44 bytes

f=a=>(a=eval(a)).every(e=>a[e.length]&&f(e))

Try it online! Test cases mostly shamelessly stolen from @Arnauld's answer. Explanation: If a set represents a natural number, then the natural number it represents must be equal to the size of the set, and (given that the elements are guaranteed distinct) the elements must be the representations of the natural numbers less than it, and these must therefore have shorter lengths. This is trivially true of the empty set of course. Edit: Saved 5 bytes thanks to @Arnauld. Saved 4 bytes thanks to @Cowsquack.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ !e[a.length-1] should save 3 bytes \$\endgroup\$
    – Arnauld
    Commented Dec 20, 2018 at 23:55
  • 1
    \$\begingroup\$ @Arnauld Or better still, a[e.length]&& for 5 bytes! \$\endgroup\$
    – Neil
    Commented Dec 21, 2018 at 0:55
  • \$\begingroup\$ @JoKing Ugh, I just copied Arnauld... string input costs 14 bytes :-( \$\endgroup\$
    – Neil
    Commented Dec 21, 2018 at 15:12
  • \$\begingroup\$ Surely, g=(A,a=eval(A))=>a.every(e=>a[e.length]&&g(e)) would work? \$\endgroup\$
    – user41805
    Commented Dec 22, 2018 at 18:58
  • \$\begingroup\$ @Cowsquack Ah, nice, that actually saves 4 bytes, thanks! \$\endgroup\$
    – Neil
    Commented Dec 22, 2018 at 21:18
7
\$\begingroup\$

Python 3, 69 58 44 bytes

11 bytes thanks to Erik the Outgolfer.

14 bytes thanks to Mr. Xcoder.

f=lambda s:all(len(e)<len(s)*f(e)for e in s)

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ @Mr.Xcoder done \$\endgroup\$
    – Leaky Nun
    Commented Dec 20, 2018 at 22:17
  • \$\begingroup\$ Oh wow, nice improvement! \$\endgroup\$
    – Mr. Xcoder
    Commented Dec 20, 2018 at 22:18
  • \$\begingroup\$ @Mr.Xcoder and then now I realize that it's the same as Neil's answer... so techincally Neil defeated me \$\endgroup\$
    – Leaky Nun
    Commented Dec 20, 2018 at 22:19
6
\$\begingroup\$

Wolfram Language (Mathematica), 60 59 bytes

E!=(If[Sort@#===Range[t=Tr[1^#]]-1,t,E]&//@ToExpression@#)&

Try it online!

The core of this solution is the function

If[Sort@#===Range[t=Tr[1^#]]-1,t,E]&

which converts a list of the form {0,1,2,...,n-1} in any order into the output n (in particular, it converts {} to 0), and converts anything else into the real number E.

Call this function f. Given an input such as "{{{}},{}}", we do the following:

  1. Convert the string into a Mathematica expression.
  2. Apply f at every level, getting f[{f[{f[{}]}], f[{}]}].
  3. Evaluating all the f's will produce a natural number for an input representing it. For example, f[{f[{f[{}]}], f[{}]}] = f[{f[{0}], 0}] = f[{1, 0}] = 2. Anything else will produce E.
  4. We test if the result is a natural number by checking if it's not E.
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Brachylog (v2), 9 bytes

↰ᵐo.t~k|Ė

Try it online!

As usual for a , this is a full program. Input from standard input, using square brackets. Output to standard output as true. versus false..

Explanation

Although I said above that this is a full program, it's actually more interesting than that; it's both a full program and a function. When used as a full program, it prints true. if the set is a natural number, or false. if it isn't. When used as a function, it "normalizes" a natural number (i.e. normalizes all its elements and sorts them into order by value; this program uses lists internally, not sets), or "throws an exception" (actually a failure, as this is Prolog) if the input isn't a natural number.

The full program behaviour is easy enough to explain: it's purely implicit in Brachylog's treatment of full programs that don't contain I/O instructions. The behaviour in question is "run the function, taking its input from standard input, and asserting that its output matches the description given by the first command-line argument; if the assertion fails or the program throws an exception, print false., otherwise print true.". In this case, the command-line argument is missing (i.e. "anything goes"), so the exception/no-exception behaviour of the function gives the output.

As for the function behaviour:

↰ᵐo.t~k|Ė
↰ᵐ          Map a recursive call to this function over the list
  o         Sort the list
   .   |    Assert that the following operation need not change the list:
    t         Take the last (i.e. greatest) element of the list
     ~k       Append an arbitrary element to the resulting list
   .   |    Output the unchanged list
       |    Exception handler: if the above threw an exception,
        Ė     Assert that the input is empty, and output an empty list

A natural number is defined as containing two parts: the elements of the natural number below, unioned with the number itself. Thus, all its elements are also natural numbers. We can recognise a natural number by a) verifying that all its elements are natural numbers, b) verifying that the set's largest element is identical to the set without its largest element.

When we're using lists rather than sets (thus the square brackets), we need to put them into a consistent order for equality comparisons to work (in this case, sorted by "value"). Brachylog's default sort order will sort a prefix of a list before the list itself, which conveniently means that it'll sort natural numbers by numerical value. So we can just recursively sort all our numbers to get them into a consistent order. In fact, via the function we're defining recursively, we can achieve both results at the same time: recursively sorting the number's elements, and verifying that it's a natural number.

The function thus has four main parts. ↰ᵐ is the recursive call, ensuring that each element is a natural number, and converting it each element to a normalized form. o the normalizes the number itself (its elements are already normalized, so all we have to do is to sort it). Then .t~k| ensures we have the structure we want by checking that the largest element and other elements are the same. An empty list (i.e. 0) doesn't have a last element, so will get an assertion failure with t; the |Ė handles this case, via giving an explicit fallback in the case where the input list is empty.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Jelly, 8 bytes

߀Ṣ
ÇṖƤƑ

Since the input has to be a string, this submission is only valid as a full program.

Try it online! or verify all test cases

How it works

߀Ṣ   Helper link. Argument: A (array)

߀    Recursively map the helper link over A.
  Ṣ   Sort the result.

This yields a canonical representation of the input, consisting solely of sorted arrays.

ÇṖƤƑ  Main link. Argument: A (array)

Ç     Call the helper link to canonicalize the array.
   Ƒ  Fixed; call the link to the left and test if it returns its argument unchanged.
 ṖƤ       Pop prefix; for each non-empty prefix of the result, remove its last element.
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Jelly, 7 bytes

Ẉ<La߀Ạ

This is a port of Leaky Nun's Python answer.

Since the input has to be a string, this submission is only valid as a full program.

Try it online! or verify all test cases

How it works

Ẉ<La߀Ạ  Main link. Argument: A (array)

Ẉ        Width; compute the length of A's elements.
  L      Yield the length of A.
 <       Compare them, yielding an array of Booleans.
    ߀   Recursively map the main link over A.
   a     Take the logical AND of the Booleans and the results of the map.
      Ạ  All; yield 1 if and only if all ANDs yielded 1.
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 36 40 bytes

(Sort//@#//.{a__,{a__}}:>{a})!={}!={{}}&

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 26 24 27 bytes

{{o'!x}[#x]~{x@<x:o'x}x}`j?

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jelly, 10 bytes

ẈṢ‘⁼Jȧ@ßƇƑ

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Japt, 9 bytes

Port of Neil's JS solution. Please upvote that if you're upvoting this.

e@Ê>XÊ©ßX

Try it or run all test cases

              :Implicit input of array U
e             :Does every element in U return true
 @            :When passed through the following function as X
  Ê           :Length of U
   >          :Greater than
    XÊ        :Length of X
      ©       :Logical AND with
       ßX     :A recursive call of the programme with X passed as the new value of U
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Red, 81 bytes

func[a][p: 1 foreach e to-block a[p: p *(pick[1 0](length? e)< length? a)* f e]p]

Try it online!

Similar to Leaky Nun's Python 3 answer

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 52 bytes

If[Max[#0/@#]<(l=2Length@#),l]&@*ToExpression/*EvenQ

Try it online!

Improve this answer
\$\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.