12
\$\begingroup\$

Risky is a new language of mine, which features an interesting form of tacit programming. In this challenge, you'll take a Risky program as input, and visualize the parsing.

No knowledge of Risky is needed for this challenge, but it's a pretty interesting language so I'd recommend trying it :p.

Task

Risky's parsing is based purely on the length of the program. It follows three rules:

  1. If the program consists of one operator, it is parsed as a nilad
  2. If the program consists of an even number of operators, the first operator is parsed as a monad and the rest is parsed as its argument
  3. Otherwise, the middle operator is parsed as a dyad, and both sides are parsed as arguments

This is recursive; the argument(s) to a monad or dyad are parsed as if they are their own programs.

This forms a tree of operators. For example, the program -1+!2 would look roughly like this:

  +
 / \
-   !
|   |
1   2

Your task will be to represent this by offsetting the operators lower in the tree, showing the structure of the program. For example:

  +
-  !
 1  2

All of the operators stay in order, but are vertically offset in order to show the structure.

Input

Input will consist of a string of operators. If you want, you can assume the input doesn't contain any invalid Risky operators, though it would not affect the parsing.

Output

You can output a visualization of the program in one of four ways:

Top-to-bottom:

      +
-      [
   +      ?
 !  !   2  0
  1  }   ]  [

Bottom-to-top:

  1  }   ]  [
 !  !   2  0
   +      ?
-      [
      +

Left-to-right:

(Using a shorter program for the next two to save space)

   2
  ?
 +
   1
  [
!

Right-to-left:

   !
 [
1
  +
 ?
2

Both LTR are RTL can be flipped upside down if you prefer.

Test cases

Note that the above examples can be used as more complicated test cases. For the top/bottom ones, -!1+!}+[2]?0[ is the program shown. For the rest, it's ![1+?2.

Program: 1

1

Program: -1

-
 1

(Top-to-bottom)

Program: 1+1

1 1
 +

(Bottom-to-top)

Progam: -1+2

  1
 +
  2
-

(Left-to-right)

Program: !!!!!

 !
!
  !
 !
!

(Right-to-left)

Other

This is , so shortest answer (in bytes) per language wins!

\$\endgroup\$
5
  • \$\begingroup\$ Left-to-right and right-to-left look weird (I feel like one of them is wrong). \$\endgroup\$
    – Bubbler
    Jun 14 at 2:00
  • \$\begingroup\$ Is left to right upside-down allowed? like putting a monad on the top left corner and having subtrees extend to the right \$\endgroup\$
    – hyper-neutrino
    Jun 14 at 2:00
  • \$\begingroup\$ @Bubbler One is upside down relative to the other. I'll allow them upside down though (to answer \@hyper-neutrino's question). \$\endgroup\$ Jun 14 at 2:01
  • \$\begingroup\$ I cannot understand the !!!!! example, ! is a monad, but it does not have an argument, on which number does it operate? \$\endgroup\$
    – wasif
    Jun 14 at 2:07
  • 1
    \$\begingroup\$ @Wasif The top of the tree is on the right side, so it is a dyad with two sub-trees each containing a monad with one nilad under it. See this \$\endgroup\$
    – hyper-neutrino
    Jun 14 at 2:11
10
\$\begingroup\$

APL (Dyalog Extended), 35 bytes

↑{⊃{0~⍨⍺-1-∊1⍵0⍵}/-⌽⍬⊂⍛,1↓⊤1+≢⍵}↑¨⊢

Try it online!

Takes a string and puts each command on its own line top to bottom, indenting from left to right.

The algorithm

Given the length of the input n, the indentation pattern (the length of each line) looks like the following:

f(1) = [1]
f(2n + 2) = let prev = f(n) in [1] ++ (2+prev) ++ [2] ++ (2+prev)
f(2n + 1) = let prev = f(n) in (1+prev) ++ [1] ++ (1+prev)

If we add 1 to the input, the recursive formula becomes nicer (with adjusting the base case):

g(1) = []
g(2n + 1) = let prev = g(n) in [1] ++ (2+prev) ++ [2] ++ (2+prev)
g(2n) = let prev = g(n) in (1+prev) ++ [1] ++ (1+prev)

which means we can use single reduction on the binary representation to get the job done.

The code

↑{⊃{0~⍨⍺-1-∊1⍵0⍵}/-⌽⍬⊂⍛,1↓⊤1+≢⍵}↑¨⊢  Input: s

⊤1+≢⍵    Binary representation of 1+n
⌽⍬⊂⍛,1↓  Remove leading 1, prepend an empty list, and reverse
-        Negate the bits (for golfing purposes)
⊃{...}/  Reduce from right to left... (⍵: prev list, ⍺: next bit)
  ∊1⍵0⍵    Shorthand for 1,⍵,0,⍵
  ⍺-1-     Add ⍺-1 (-1 if zero bit, -2 if one bit)
  0~⍨      Remove zero if present
           which gives -1,(⍵-2),-2,(⍵-2) for 1 bit and
           (⍵-1),-1,(⍵-1) for 0 bit

 {...}     Compute negative padded lengths
↑     ↑¨⊢  Pad each char on the left side and rectify
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Very nice. "which means we can use single reduction on the binary representation to get the job done" -- what was the insight that connected the formula to immediately knowing it was equivalent to a reduction on the binary number? \$\endgroup\$
    – Jonah
    Jun 14 at 6:28
  • 3
    \$\begingroup\$ @Jonah A recursive formula is a left-to-right reduce in binary if both f(2n) and f(2n+1) recursively call f(n) once and nothing else. Thinking in the reverse direction, going from f(n) to f(2n) is appending a zero bit, and going to f(2n+1) is appending a one bit. \$\endgroup\$
    – Bubbler
    Jun 14 at 6:33
  • \$\begingroup\$ Ah of course, thanks! \$\endgroup\$
    – Jonah
    Jun 14 at 6:40
8
\$\begingroup\$

J, 67 bytes

g=:(0,1+$:@<:)`([:(,0,])1+$:@<.@-:)`0:@.(=&1+2&|)
f=:' '&,.#"1~1,.~g@#

Try it online!

This produces an upside-down left-to-right tree, which should be valid per the comments. For example, f '-1+!2' produces:

 - 
  1
+  
 ! 
  2

the idea

  • First notice the numerical pattern in the number of space indents:

    1 -> 0            
    2 -> 0 1          
    3 -> 1 0 1        
    4 -> 0 2 1 2      
    5 -> 1 2 0 1 2    
    6 -> 0 2 3 1 2 3  
    7 -> 2 1 2 0 2 1 2
    
  • Then notice that all the heavy lifting can be put into a recursive function that does nothing but implement the function described by the above table, since it's easier to work with integers than strings. This is g.

  • Zip a space and the input like so:

     -
     1
     +
     !
     2
    
  • Finally, use the output of g and J's copy verb # to expand the spaces of that zip as needed.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Upside-down left-to-right trees were ruled to be acceptable in the comments, so I think this is good :) \$\endgroup\$
    – hyper-neutrino
    Jun 14 at 3:49
6
\$\begingroup\$

Jelly, 32 bytes

⁹ð:2ß‘},`j⁹ð’ß‘}⁹;ðḂ?Ị?
Lç0⁶ẋż¹Y

Try it online!

-2 bytes thanks to caird coinheringaahing

This uses essentially the same approach as Jonah, so upvote their answer as well. I came up with this solution independently, but Jonah's answer helped me consolidate a similar idea (to generate the indent array and convert that to indentation), and although I pretty much knew how I wanted to do it already, it helped me see that it was the correct approach and how to go about it.

⁹ð:2ß‘},`j⁹ð’ß‘}⁹;ðḂ?Ị?   Helper Link (dyad); given x and y, return the length x indentation array with minimum indentation y
                     Ị?   If x is insignificant (abs(x) <= 1)
⁹                         Return just y
                   Ḃ?     Otherwise, if x is odd (x % 2)
 ð:2ß‘},`j⁹ð              Dyadic chain for odd case:
  :2                      - floor divide by 2
    ß‘}                   - recursively apply this function to floor(x / 2) and (y + 1)
       ,`                 - pair that result with itself (exploit symmetry)
         j⁹               - join on y
           ð’ß‘}⁹;ð       Otherwise, if x is even, then dyadic chain for even case:
            ’             - decrement x
             ß‘}          - apply this link to (x - 1) and (y + 1)
                ⁹;        - prepend y
Lç0⁶ẋż¹Y                  Main Link (monad)
L                         Length of the input
 ç0                       Apply the helper link to that (x) and 0 (y)
   ⁶ẋ                     Return a list of whitespace, each row having number of spaces equal to the indentation level
     ż                    Zip with / interleave
      ¹                   (identity is applied to the right argument of the above to prevent the 2,1 chain with `Y`)
       Y                  Join on newlines
\$\endgroup\$
1
3
\$\begingroup\$

Charcoal, 34 33 bytes

FΦ↨⊕Lθ²κ≔⁺…⟦¹⟧ι⁺⊕ι⁺⁺υ⟦⁰⟧υυEυ◧§θκι

Try it online! Link is to verbose version of code. Explanation: Based on @Bubbler's answer, so prints downwards indenting from left to right.

FΦ↨⊕Lθ²κ

Take the length of the input plus 1, convert to binary, and loop over the bits after the first.

≔⁺…⟦¹⟧ι⁺⊕ι⁺⁺υ⟦⁰⟧υυ

Concatenate two copies of the current list (predefined to be the empty list) together with [0] in between, then add 1 more than the bit to all the elements, then concatenate [1] to the beginning of the list if the bit is 1, and save that as the current list.

Eυ◧§θκι

Pad each element of the input according to the calculated indentation.

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

05AB1E, 26 25 bytes

A port of Jonah's J answer.

-1 byte thanks to Kevin Cruijssen!

S¯¸λNÈi>0šë0N2÷₅>.ø]Igèú»

Try it online!

S                     # split input into list of characters
 ¯¸                   # push [[]]
   λ          ]       # starting with a(0)=[], calculate a(n) for n=0,1,... according to:
    NÈi               #   if n is even:
       >              #     each value of a(n-1) incremented by 1
        0š            #     prepend a 0
      ë               #   else:
       0              #     push a 0
        N2÷           #     floor(n/2)
           ₅          #     a(floor(n/2))
            .ø        #     surround the 0 with a(floor(n/2))
               Ig     # push the length of the input()
                 è    # index into the infinite list of indentations
                  ú   # pad each character of the input with the right number of spaces
                   »  # join by newlines
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can replace the õS with ¯ for -1. \$\endgroup\$ Aug 5 at 10:16
2
\$\begingroup\$

Haskell, 97 bytes

f x|n<-length x,odd n,(p,q:r)<-splitAt(n`div`2)x=g p++[q]:g r
f(x:y)=[x]:g y
f[]=[]
g=map(' ':).f

Try it online!

Defines f :: String -> [String]. Upside-down left-to-right output.

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

JavaScript (V8), 223 bytes

f=(c,d=(s,x=0,y=0,u=s.substr.bind(s),l=s.length,h=l/2|0)=>l==1?{[x]:y}:l%2==0?{[x]:y,...d(u(1),x+1,y+1)}:{[x+h]:y,...d(u(0,h),x,++y),...d(u(++h),x+h,y)},r=d(c))=>Object.entries(r).map(k=>" ".repeat(k[1])+c[k[0]]).join("\n")

Try it online!


Maps the input source into a lookup of token index and indentation amount, then transforms it into a proper string in the inverted left-to-right format.

Indented:

f = (
    c,
    // Helper method that calculates the indentation.
    d = (s, x = 0, y = 0, u = s.substr.bind(s), l = s.length, h = l / 2 | 0) =>
        l == 1
            // Case 1: Nilad
            ? { [x]: y }
            : l % 2 == 0
                // Case 2: Monad + Arguments
                ? { [x]: y, ...d(u(1), x + 1, y + 1) }
                // Case 3: Dyad
                : {
                    [x + h]: y,
                    ...d(u(0, h), x, y + 1),
                    ...d(u(h + 1), x + h + 1, y + 1),
                },
    r = d(c)
) =>
    // We take advantage of the fact that the object entries are automatically sorted.
    Object.entries(r)
        .map((k) => " ".repeat(k[1]) + c[k[0]])
        .join("\n");
\$\endgroup\$
1
\$\begingroup\$

JavaScript (V8), 162 157 bytes

d=>(j=(r,b="")=>r.map(o=>o.map?j(o,b+" "):b+o).join`
`)((p=(r,x=r.length)=>x>1?x%2?[p(r.slice(0,z=x/2)),r[z|0],p(r.slice(z+1))]:[r[0],p(r.slice(1))]:[r])(d))

Try it online!

Explanation:

Parses using recursion, and puts arguments into arrays. Then, it takes the result, and recursively indents anything in an array. Left-to-right, upside-down.

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