6
$\begingroup$

Imagine you have two systems of delimiting. One with paired delimiters, [ and ]:

 [abc]

Then another system which uses a single interstitial delimiter, /:

 a/b/c

It's easy to see how to encode structure in the first case, as they nest cleanly:

[ab[cd[e]f]]

But let's say you are looking to encode arbitrary nested structures in the second scheme, using only some number of interstitial delimiters. Whatever the encoding winds up being, a/////b//c////d///e///f would be an example of "following the rules", while //a//b/c///d///e///f/// would not.

So you're basically able to put a unary-encoded integer from 0..∞ (let's say 0 is /, 1 is //) between your elements.

It's obviously possible to encode, though the results won't necessarily be pretty or visually intuitive. One way would be to consider you have two factors to record at each step.

  • Whether a nesting level is being entered or not for the ensuing token or if it's going to stay the same. So for a?b, we want to know ...a[b... or ...ab...

  • how much of a nesting drop the ensuing token has after it. So for d?e, we want to know e.g. ...d[e]... or ...d[e]]... or ...d[e]]]

The first is just a yes or no, and the second is a number which can range from 0 to however many nesting levels you've gotten so far. So multiply the nesting level to drop by 2, add 1 if you're going a level deeper in and leave it alone otherwise.

[ab[cd[e]f]] => a 0 b 1 c 0 d 3 e 4 f => a/b//c/d///e////f

That's pretty mechanical, but if I've got it right, I think it verifies it can be done.

But here's my question: Is there a known encoding for this kind of problem that would more intuitively convey the structure to a human reader, perhaps at the cost of making longer strings? Let's say a system that would decay such that simple cases like [ab[cd]e] could look more like a/b//c///d//e or similar, while still being able to encode everything distinctly?

I realize the quality I'm asking for is a bit "nebulous", but perhaps you see what I mean. One thing I don't like about the encoding I chose above is it imposes a left-to-right "leaning" property, when there isn't anything particularly left-like or right-like about the nesting properties being encoded. I wonder how that might be excised by making different choices.

$\endgroup$
  • $\begingroup$ Does it have to be a pre-existing single character? e.g. could I make up and define a character that fits this description? $\endgroup$ – ryan Jul 26 '17 at 0:37
  • $\begingroup$ @ryan I may have been misleading when I said "at the cost of using more delimiters" when what I meant to say was "at the cost of creating longer strings" (using more instances of the single delimiter set up in the problem statement, under the rules given). I've corrected that, sorry if it was confusing. If I were willing to use two different delimiters, I'd just use [ and ]! $\endgroup$ – HostileFork Jul 26 '17 at 2:41
  • $\begingroup$ "Whatever the encoding winds up being" ... "It's obviously possible to encode" -- not to me it's not, at least if we want to remain context-free. $\endgroup$ – Raphael Jul 27 '17 at 18:29
  • 1
    $\begingroup$ "Is there a known encoding for this kind of problem that would more intuitively convey the structure to a human reader" -- yes: parentheses. It's completely unclear why you'd want to avoid them. You'll have to decide whether you want to ask a theoretical or pragmatic/practical question. $\endgroup$ – Raphael Jul 27 '17 at 18:31
  • $\begingroup$ FWIW, there are ways to visually represent nesting structures, e.g. by connecting matching symbols with a half circle. $\endgroup$ – Raphael Jul 27 '17 at 18:35
2
$\begingroup$

I'll propose a new idea inspired by the everyday slinky. It might be more difficult to perceive exactly what the nesting is, but it might give you a better overall view. We can use a technique similar to the compression and decompression of slinkies:

slinky magic

Take for example the nesting: [a b c d [e f [g] h i] j k l m]. We can visualize it in two dimensions based on nest depth like so:

a b c d           j k l m

        e f   h i 

            g    

Or alternatively, the inverse:

            g    

        e f   h i

a b c d           j k l m

For either of these we need to determine which should be the compression and which should be the decompression (high vs low nests).

We could try both out:

  1. High level is compression, low level is decompression:

    a b c d e f g h i j k l m

  2. Low level is compression, high level is decompression:

    a b c d e f g h i j k l m

Personally I think option two is more visually representative because the large space between the upper levels represents the lack of deeper nests clearly and the condensed space represents the densely packed nests more easily.


Further we could make a formal algorithm. Let's assume input is given as a (value, depth) pair = $(x_i, d_i)$. Let $d_m$ denote the maximum depth of all values in the sequence. For the deepest level, we will pad the elements with 0 spaces, and the highest level we will pad the elements with $2^{d_m - 1}$ spaces on both sides. The only caveat is that we do not pad the left most value on the left and not the right most value on the right. Take the example: [[ab[cd[efg]h][ij]k]lm].

a    b   c  d efg h  i  j   k      l        m

The big problem with this is that it does not guarantee a unique encoding. If you do want a unique encoding with a similar approach but maybe not as visually comprehensive, follow the same algorithm only padding the left side and starting at 1, rather than 0 spaces. So [[ab[cd[efg]hij]k]lm] becomes:

a    b  c  d e f g  h  i  j    k        l        m

Although keep in mind this only is unique for a sequences of depths, not necessarily unique nestings. For example [ab][cd][ef][gh] would be considered the same as [abcdefgh] because they're all at the same depth.

$\endgroup$
  • $\begingroup$ Interesting metaphor, I'll have to think about it--do you have a more formal algorithm showing how to translate a nesting to an encoding, and a proof it doesn't alias different structures to the same encoding? $\endgroup$ – HostileFork Jul 28 '17 at 0:30
  • $\begingroup$ @HostileFork, I've updated it a little bit, maybe that helps. $\endgroup$ – ryan Jul 28 '17 at 6:32
  • $\begingroup$ For example [ab][cd][ef][gh] would be considered the same as [abcdefgh] because they're all at the same depth. - For the purposes of the problem I state, this isn't a problem; the input sequence isn't a legal input. $\endgroup$ – HostileFork Jul 28 '17 at 7:27
  • $\begingroup$ @HostileFork, well that's good then. Perhaps this method will help then. You could also adapt a similar approach with different amounts of spacing or different functions to the compression/decompression. $\endgroup$ – ryan Jul 28 '17 at 17:19
4
$\begingroup$

\n and \t would get the job done as best as I could tell. In memory they're each only a character, but visually they offer a lot more. You then have an encoding scheme of \n then $x$ \t characters where $x$ is the nesting level. So this:

[a b [c d [e] f]]

in memory becomes:

a\nb\n\tc\n\td\n\t\te\n\tf

visually becomes:

a
b
    c
    d
        e
    f

As Evil mentions, you could similarly remove \n and \t between characters at the same level to achieve something like this:

ab
    cd
        e
    f
$\endgroup$
  • $\begingroup$ Is it really needed to put delimeter between the elements at the same depth? As I understand delimeter is not part of the alphabet. $\endgroup$ – Evil Jul 25 '17 at 23:54
  • $\begingroup$ @Evil, what do you mean? If we didn't have the delimiter between c and d for example then it would appear (visually) that d is the same level as a and b, then this method would fall apart. $\endgroup$ – ryan Jul 26 '17 at 0:00
  • 1
    $\begingroup$ ab\n\tcd\n\t\te\n\tf it would look ok imnvho. $\endgroup$ – Evil Jul 26 '17 at 0:02
  • $\begingroup$ Ah, I see what you're saying, yes that would look good as well. I'll update it. $\endgroup$ – ryan Jul 26 '17 at 0:05
  • 1
    $\begingroup$ It's an interesting point that two characters enables a simpler scheme which still only fills in interstitial spots. So I'll bear that in mind. But the game I laid out is the one I am actually interested in with this question: using a single delimiter character, representing unary numbers, and whether there's a more visually natural way of doing it than the mechanical method I outline. $\endgroup$ – HostileFork Jul 26 '17 at 0:24

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.