15
\$\begingroup\$

Background

K functions have a feature called projection, which is essentially partial application of values to a function. The syntax for projections is a natural extension of the regular function call syntax:

f[1;2;3]    / call a ternary function f with three arguments 1, 2, 3
f[1;2;]     / the third argument is missing,
            / so it evaluates to a unary derived function instead
f[1;2;][3]  / calling the derived function with 3 calls f with 1, 2, 3
            / so this is equivalent to calling f[1;2;3]

Projections can supply any number of arguments and missing slots, and omit trailing semicolons. The function is evaluated only when all missing slots are filled and the number of arguments is at least the function's arity. For the sake of this challenge, let's assume the arity of f is infinity, i.e. it is never actually evaluated.

The right side shows how ngn/k prettyprints projections. You can freely experiment with ngn/k online interpreter.

f[1]        / -> f[1]
f[1;2]      / -> f[1;2]
f[;2]       / -> f[;2]
f[;2][1]    / -> f[1;2]

A projection also decides the minimum number of arguments f will be actually called with. For example, f[1;] specifies that the first arg is 1 and the second arg will come later. It is different from f[1], and the two are formatted differently.

f[1]    / -> f[1]
f[1;]   / -> f[1;]

You can create projections out of projections too, which is the main subject of this challenge. Given an existing projection P and the next projection Q, the following happens:

  • For each existing empty slot in P, each (filled or empty) slot in Q is sequentially matched from left to right, replacing the corresponding empty slot in P.
  • If Q is exhausted first, the remaining slots in P are untouched.
  • If P is exhausted first, the remaining slots in Q are added to the end.
f[;;1;;]      / a projection with five slots, 3rd one filled with 1
f[;;1;;][2]   / -> f[2;;1;;]
              / 2 fills the first empty slot
f[;;1;;][2;3;4]    / -> f[2;3;1;4;]
              / 2, 3, 4 fills the first three empty slots
              / (1st, 2nd, 4th argument slot respectively)
f[;;1;;][2;;4]     / -> f[2;;1;4;]
              / the second empty slot (2nd arg slot) remains empty
f[;;1;;][2;;4;;6]  / -> f[2;;1;4;;6]
              / Q specifies five slots, but P has only four empty slots
              / so the 6 is added as an additional (6th overall) slot

Challenge

Given a series of projections applied to f, simplify it to a single projection as described above.

The input is given as a string which represents the function f followed by one or more projections, where each projection specifies one or more (filled or empty) slots. You may further assume that

  • the substring [] does not appear in the input (it means something slightly different),
  • each filled slot (specified argument) contains a single integer between 1 and 9 inclusive, and
  • the entire input does not have any spaces.

Standard rules apply. The shortest code in bytes wins.

Test cases

All the examples are replicated here, and a "stress test" is presented at the bottom.

Basic tests

f[1] -> f[1]
f[1;] -> f[1;]
f[1;2] -> f[1;2]
f[;2] -> f[;2]
f[;2][1] -> f[1;2]
f[1;2;3] -> f[1;2;3]
f[1;2;] -> f[1;2;]
f[1;2;][3] -> f[1;2;3]

f[;;1;;] -> f[;;1;;]
f[;;1;;][2] -> f[2;;1;;]
f[;;1;;][2;3;4] -> f[2;3;1;4;]
f[;;1;;][2;;4] -> f[2;;1;4;]
f[;;1;;][2;;4;;6] -> f[2;;1;4;;6]

Stress tests (input)

f[;1]
f[;1][;2]
f[;1][;2][3]
f[;1][;2][3][;;;4]
f[;1][;2][3][;;;4][;5]
f[;1][;2][3][;;;4][;5][6;]
f[;1][;2][3][;;;4][;5][6;][7]
f[;1][;2][3][;;;4][;5][6;][7;;]
f[1;;;;;;;;;;;;;]
f[1;;;;;;;;;;;;;][2][3]
f[1;;;;;;;;;;;;;][2][3][;;;;;4;;;;;;;;]
f[1;;;;;;;;;;;;;][2][3][;;;;;4;;;;;;;;][5;6;7;8;9;1][2;3;4;5][6;7]

Stress tests (output)

f[;1]
f[;1;2]
f[3;1;2]
f[3;1;2;;;;4]
f[3;1;2;;5;;4]
f[3;1;2;6;5;;4]
f[3;1;2;6;5;7;4]
f[3;1;2;6;5;7;4;;]
f[1;;;;;;;;;;;;;]
f[1;2;3;;;;;;;;;;;]
f[1;2;3;;;;;;4;;;;;;;;]
f[1;2;3;5;6;7;8;9;4;1;2;3;4;5;6;7;]
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I'm confused by an apparent inconsistency between "Projections can supply any number of arguments and missing slots, and omit trailing semicolons. ", and "f[1;] specifies that the first arg is 1 and the second arg will come later. It is different from f[1]" \$\endgroup\$
    – Stef
    Sep 14, 2021 at 13:11
  • 1
    \$\begingroup\$ @Stef Would it be better if I delete "omit trailing semicolons" part from the former? \$\endgroup\$
    – Bubbler
    Sep 14, 2021 at 22:46
  • \$\begingroup\$ @Stef the first statement seems to assume finite arity (the way it actually works in k) and the second - infinite arity (to make this challenge simpler). so, i think here f[1;] and f[1] should be considered different. \$\endgroup\$
    – ngn
    Sep 14, 2021 at 22:49
  • \$\begingroup\$ @Stef also, "you can omit trailing semicolons" in the sense that even though f[1;] and f[1] (f having arity>1) are technically different, when all slots get filled it won't matter whether you started with f[1;] or f[1] \$\endgroup\$
    – ngn
    Sep 14, 2021 at 22:55

8 Answers 8

5
\$\begingroup\$

Stax, 37 34 32 bytes

Ñgí⌡²☼☺≈AU▀≤L♠╫$U∩─.ù·○╓╥ò±E♦τèZ

Run and debug it

-2 reducing splitting code

Explanation

2t1T.][/  {';/m{s{c{c{B}z?}?ms+k';*:}'fs+
2t1T.][/                                  get all argument bodies
          {';/m                           split all on semicolons
               {s{c{c{B}z?}?ms+k          reduce by:
                s                          swap with prev
                 {c{c{B}z?}?m              map elements in prev to:
                  c{      }?                if non-empty, leave elem as is
                    c{B}z?                  else remove first element of next and push
                                            (pushes [] if empty)
                             s+           append the rest elements
                                ';*       join with semicolons
                                   :}     put in square brackets
                                     'fs+ prepend 'f'   

Stax, 37 bytes

Ö☺τσj↔₧♂√V{▐9,=☺|╢Δ‼$≥ä₧ÿºÉ/♂y╩▲S╞♫┘{

Run and debug it

uses an assign at index builtin, slightly longer.

\$\endgroup\$
5
\$\begingroup\$

05AB1E, 46 bytes

¦¤¡¨ε¦';¡}Å»U0ìD_OXg-(©di®Å0«}0X.;}θ';ý0K"f[ÿ]

05AB1E is not the right language for this challenge.. :/

Try it online or verify all test cases.

Explanation:

Step 1: Transform the input to something more usable: Try it online.

¦                  # Remove the leading "f" from the (implicit) input-string
 ¤                 # Get its last character "]" (without popping)
  ¡                # Split it on this "]"
   ¨               # Remove the trailing empty item
    ε              # Map over each inner string
     ¦             #  Remove the leading character (the "[")
      ';¡         '#  Split it on ";"
    }              # Close the map

We now have a list of lists of digits and empty strings.

Step 2: Reduce this list of lists according to the challenge: Try it online.

Å»                 # Cumulative left-reduce (which unfortunately keeps track of steps):
  U                #  Pop and store the current list in variable `X`
   0ì              #  Prepend a 0 before each item in the result-string
                   #  (so all empty strings become 0s)
   D_O             #  Get the amount of 0s in this list (duplicate; ==0; sum)
      Xg           #  Push the length of the current list `X`
        s-         #  Subtract the amount of 0s from this length
          ©        #  Store it in variable `®` (without popping)
           di    } #  Pop, and if this value is >= 0:
             ®Å0   #   Push a list with `®` amount of 0s
                «  #   And append this to the result-list
    0X.;           #  Then replace each zero ("0","00","000",etc.) in this list one by
                   #  one with the values from list `X`
 }θ                # And after the cumulative left-reduce, pop and keep the last list

Step 3: Format this resulting list to a format similar as the input:

';ý               '# Join the list with ";" delimiter
   0K              # Remove all 0s from the string
     "f[ÿ]        "# Push string "f[ÿ]", where `ÿ` is automatically replaced with the
                   # string
                   # (after which the result is output implicitly)
\$\endgroup\$
4
\$\begingroup\$

Python 3.8 (pre-release), 126 bytes

lambda s,D=[]:f'f[{";".join([D:=[j or next(i,"")for j in D]+[*i]for k in s[2:-1].split("][")if(i:=iter(k.split(";")))]*0+D)}]'

Try it online!

Ungolfed:

def f(s):
  D=[]
  for k in s[2:-1].split(']['):
    i = iter(k.split(';')) # next projection
    D = [j or next(i,'') for j in D] # replace empty slots with arguments from i
    D += [*i] # add the rest of i
  return 'f['+';'.join(D)+']'
\$\endgroup\$
1
4
\$\begingroup\$

K (ngn/k), 65 59 bytes

{"f[",|x,|y/{.![a*+\a:~#'x;x],(1+!#y)!y}/y\'-1_'1_z\}."];["

Thanks to ngn for cutting 4 bytes here and here.

Try it online!

K (k9 2021.09.01), 54 bytes

{"f[",|x,|y/{!?(?x*+\x!:~#'x),?+\y!1}/y\'1_z\x_}."];["
\$\endgroup\$
3
\$\begingroup\$

Jelly, 33 bytes

ṣ”[Ṗ€ṣ€”;VṆ€k$ḟ0;ɗ"Ẏɗ/j”;ḟ0Ø[j”f;

A monadic Link that accepts a list of characters and yields a list of characters.

Try it online!

How?

ṣ”[Ṗ€ṣ€”;VṆ€k$ḟ0;ɗ"Ẏɗ/j”;ḟ0Ø[j”f; - Link: list of characters, S
ṣ”[                               - split (S) at '['
   Ṗ€                             - pop (i.e. remove ']' from) each
     ṣ€”;                         - split each at ';'
         V                        - evaluate as Jelly code
                                     -> list of projections with zeros at empty slots
                     /            - reduce by:
                    ɗ             -   last three links as a dyad, f(P, Q):
             $                    -     last two links as a monad, f(P):
          Ṇ€                      -       logical NOT each
            k                     -       partition (P) after truthy indices (of that)
                                            -> P split after each empty slot
                  "               -     zip (across [t in that] and [q in Q]) with:
                 ɗ                -       last three links as a dyad, f(t, q):
               0                  -         zero
              ḟ                   -         (t) filter discard (zeros)
                ;                 -         concatenate (q)
                   Ẏ              -     tighten (to a flat list)
                      j”;         - join with ';'
                         ḟ0       - filter discard zeros
                           Ø[j    - "[]" join (that)
                              ”f; - 'f' concatenate (that)
\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 92 bytes

v=>v.match(/(?<=[[;])\d*|\[/g).map(g=n=>1/n?o[++i]?g(n):o[i]=n:i=-1,o=[])&&`f[${o.join`;`}]`

Try it online!

-1 byte by Arnauld.

\$\endgroup\$
0
2
\$\begingroup\$

Scala, 183 bytes

_.drop(2).init split "\\]\\["map(_ split ";")reduce{(p,q)=>val(b,a)=((q,q take 0)/:p){case((q,p),x)=>if(q.size<1|x!="")(q,p:+x)else(q drop 1,p++q.take(1))}
a++b}mkString("f[",";","]")

Try it in Scastie!

A pretty horrible solution, but I'll work on it later. Explanation coming soon.

_                  //The input
 .drop(2)          //Drop the "f["
 .init             //Drop the "]" at the very end
  split "\\]\\["   //Split the projections up
  map(_ split ";") //Split each projection into its parts
  reduce{ (p, q) => //Reduce the projections by this function, which does the real work
   val(b,a)=((q,q take 0)/:p){case((q,p),x)=>if(q.size<1|x!="")(q,p:+x)else(q drop 1,p++q.take(1))}
a++b}mkString("f[",";","]")
\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 131 bytes

(f.(\d;)*(;(\d;)*)*)(;[^]]*].(?<-3>;)*(?(3)^))(\d);?
$1$6$5
}`\[\]

}`(f(.(\d|((?=;)))(?=[];]))*);?(].(?<-4>;)*)([^]]+)?
$1$#6$*;$6

Try it online! Explanation: Uses .NET balancing groups to shuffle arguments into slots. The first two lines shuffle arguments from the second application into free slots in the first. The middle two lines delete an empty application resulting from the first two lines. The last two lines append trailing arguments or slots from the second application to the first, however the test assumes that there are no arguments left to shuffle or empty applications, which is why an extra loop is needed.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.