35
\$\begingroup\$

Imagine a very simple language. It has just 2 syntax features: () indicates a block scope, and any word consisting only of 1 or more lower case ASCII letters, which indicates a identifier. There are no keywords.

In this language, the value of identifiers is not important except when they appear multiple times. Thus for golfing purposes it makes sense to give them names that are as short as possible. A variable is "declared" when it is first used.

The goal of this challenge is to take a program, either as a string or as a ragged list, and make the identifiers as short as possible. The first identifier (and all its references) should be re-named to a, the next b then so on. There will never be more than 26 identifiers.

Each set of () encloses a scope. Scopes can access variables created in the parent scope defined before but not those created in child or sibling scopes. Thus if we have the program (bad (cab) (face)) the minimum size is (a (b) (b)). A variable belongs to the scope when it is first used. When that scope ends the variable is deleted.

In summary:

  1. If a variable name has appeared in the scope or enclosing scopes before, re-use the letter
  2. Else create a new letter inside the current scope
  3. At the end of a scope delete all variables created inside the scope.

Test cases

{
    "(rudolf)":                   "(a)",
    "(mousetail mousetail)":      "(a a)",
    "(cart fish)":                "(a b)",
    "(no and no)":                "(a b a)",
    "(burger (and fries))":       "(a (b c))",
    "(burger (or burger))":       "(a (b a))",
    "(let (bob and) (bob let))":  "(a (b c) (b a))",
    "(let (a (fish (let))))":     "(a (b (c (a))))",
    "(kor (kor kor) (kor kor))":  "(a (a a) (a a))",
    "((kor) kor)":                "((a) a)",
    "(aa (ab ac ad) (ad ad) ad)": "(a (b c d) (b b) b)",
    "(aa not (ab ac ad) (ad ad))":"(a b (c d e) (c c))",
    "(((((do) re) mi) fa) so)":   "(((((a) a) a) a) a)",
    "(do (re (mi (fa (so)))))":   "(a (b (c (d (e)))))",
    "((mark sam) sam)":           "((a b) a)",
}

IO

  1. You can take input as either a string or ragged array.
  2. You can give output either as a string or ragged array.
  3. However, you must use the same format for input and output. Specifically, you need to produce output in such a way that it would also be a valid input. Applying the function or program more than once always has the same result as applying it once.

Neither scopes nor variable names may be empty. Applying your program to its result again should be a no-op.

\$\endgroup\$
19
  • 2
    \$\begingroup\$ May we assume the input never contains empty scopes ()? And I presume empty variable names are not valid? \$\endgroup\$
    – pxeger
    Sep 12 at 13:57
  • 2
    \$\begingroup\$ Will all identifiers have more than one letter? \$\endgroup\$
    – Noodle9
    Sep 12 at 14:03
  • 2
    \$\begingroup\$ To be perfectly clear you should put that in your post. \$\endgroup\$
    – Noodle9
    Sep 12 at 14:14
  • 4
    \$\begingroup\$ Plural "letters" implies more than one. \$\endgroup\$
    – Noodle9
    Sep 12 at 14:48
  • 3
    \$\begingroup\$ @customcommander variables are introduced when they are first used, not earlier. So the ad in the sublist can't refer to the outer ad, as this one only comes into play later. \$\endgroup\$ Sep 13 at 22:31

10 Answers 10

14
\$\begingroup\$

tinylisp, 149 bytes

(load library
(d G(q((L N)(i(c()(h L))(i L(c(G(h L)N)(G(t L)N))L)(i(contains? N(h L))(c(last-index N(h L))(G(t L)N))(G L(insert-end(h L)N
(q((L)(G L(

The last line is an anonymous function that takes a nested list and returns a nested list. The returned list uses nonnegative integers instead of letters, which seems to be allowed by this comment.

Try it online! Or, verify all test cases.

Ungolfed

(load library)

(def _rename
 (lambda (expr names)
  (if (type? (head expr) List)
   (if expr
    (cons
     (_rename (head expr) names)
     (_rename (tail expr) names))
    nil)
   (if (contains? names (head expr))
    (cons
     (last-index names (head expr))
     (_rename (tail expr) names))
    (_rename expr
     (insert-end (head expr) names))))))

(lambda (expr) (_rename expr nil))

Here's a 167-byte version that uses letters instead of numbers:

(load library
(d G(q((L N)(i(c()(h L))(i L(c(G(h L)N)(G(t L)N))L)(i(contains? N(h L))(c(single-char(a(last-index N(h L))97))(G(t L)N))(G L(insert-end(h L)N
(q((L)(G L(

Try it online!

\$\endgroup\$
5
  • 3
    \$\begingroup\$ The most appropriate language for this challenge \$\endgroup\$
    – justhalf
    Sep 13 at 17:07
  • \$\begingroup\$ I want to see this answer applied to itself \$\endgroup\$
    – mousetail
    Sep 14 at 10:49
  • 1
    \$\begingroup\$ @mousetail Here you go \$\endgroup\$
    – DLosc
    Sep 14 at 16:20
  • \$\begingroup\$ @mousetail That doesn't look necessary; in fact, it kind of looks like DLosc wrote this ungolfed and then used the program to golf itself \$\endgroup\$
    – pigrammer
    Oct 11 at 14:32
  • \$\begingroup\$ @pigrammer I should mention that the output of this program, while syntactically valid in tinylisp, will do nothing but error, since integers are not valid functions. \$\endgroup\$
    – DLosc
    Oct 11 at 16:29
9
\$\begingroup\$

Python, 79 bytes

f=lambda _,**s:[i==[*i]and f(i,**s)or s.setdefault(i,chr(97+len(s)))for i in _]

Attempt This Online!

Thanks to @loopy walt.

Whython, 66 bytes

f=lambda _,**s:[s.setdefault(i,chr(97+len(s)))?f(i,**s)for i in _]

Attempt This Online!

Port of the above.

Whython, 72 bytes

f=lambda a,s={}:s.setdefault(a,chr(97+len(S:={**s})))?[f(i,S)for i in a]

Attempt This Online!

My original solution

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

Prolog (SWI), 81 70 bytes

\X,[I]-->[H],{copy_term(X,Z),\(Z,H,I);nth1(I,X,H)},(\X;[]).
a--> \_,!.

Try it online!

Instead of using predicates, I use definite clause grammar (DCG) notation. DCG notation is syntactic sugar in Prolog that allows for more writing more concise code for sequence processing. The basic way my program operates is that it iterates through the input and output list using DCG notation to bind the first item of the remainder of the input list to NextItem and the first item of the remainder of the output list to ProcessedItem. Then the program handles each potential case for NextItem and binds ProcessedItem to the appropriate value. Finally, the program attempts to process the following items, or, if none are found, terminates.

I stumbled onto an 11 byte golf of my program when I realized my original code was broken. The issue was that when parsing a sublist, the inner scope would leak into the outer scope since InScopeVars was having new variables placed into it by nth1/3, instead of by the intended append/3. I found a way to exploit this behavior though with the copy_term/2 predicate, which unifies the second argument with a copy of the first argument but with fresh variables (e.g. copy_term(X,Z) where X=[aa|SomeVar] unifies Z with [aa|SomeNewVar]). This allows us to create a copy of the scope to use when handling a sublist where its uninitialized tail can be used without the inner scope leaking, thereby allowing us to use nth1/3 for both appending and finding the index.

Ungolfed Code

rename_item(InScopeVars),
  [ProcessedItem]
  -->
    [NextItem],
    {
      % Case 1: NextItem is a sublist
      % This predicate sets InScopeVarsCopy to a copy of InScopeVars,
      % but replaces all Prolog variables in it with newly instantiated ones.
      % This means any unifications that occur in the following rename_item call
      % will not affect InScopeVars
      copy_term(InScopeVars, InScopeVarsCopy),
      % DCGs are syntactic sugar for predicates with an additional two arguments:
      % the input sequence and the output sequence.
      % This fails if NextItem is not a list, in which case we'll
      % do Case 2 instead.
      rename_item(InScopeVarsCopy, NextItem, ProcessedItem)
    ;
      % Case 2: NextItem is a variable
      % We unify ProcessedItem with the index of NextItem in the list InScopeVars.
      % Note that since InScopeVars initially uninitialized,
      % it gets unified with [NextItem|UninitializedVariable].
      % On later calls, if NextItem appears in InScopeVars then ProcessedItem is
      % unified with the index of NextItem.
      % Otherwise the head of the uninitialized tail of InScopeVars is set to
      % NextItem, and NextItem's new index in InScopeVars is unified with
      % ProcessedItem.
      nth1(ProcessedItem, InScopeVars, NextItem)
    },
    (
      % Attempt to rename the next remaining item in the list
      rename_item(InScopeVars)
    ;
      % If that fails then we are done!
      []
    ).

rename -->
  % Due to the way the nth1/3 predicate works, passing in an
  % uninitialized variable for the initial scope is in essence passing in an
  % infinite list of uninitialized variables.
  % As we encounter new (not Prolog) variables in the input program they will be
  % unified with the first uninitialized (Prolog) variable in the scope.
  rename_item(_),
  % Once we get the first solution, we use the cut to prevent backtracking
  !.

Before I realized that it was permitted to output numbers instead of letters I wrote the following program, which I've modified to use some of the golfs I later found:

92 bytes

\X,[I]-->[H],{copy_term(X,Z),\(Z,H,I);nth1(N,X,H),C is 96+N,name(I,[C])},(\X;[]).
a--> \_,!.

Try it online!

\$\endgroup\$
6
\$\begingroup\$

C (clang), 208 bytes

a[26];b[26];c;d;e;f;g;h;i(*j){for(;f=*j;j++)if(f/47)c=c?:j;else{if(c){for(*j=g=d=0;a[d]*!g;wcscmp(a[d],c)?d++:g++);g||(a[d]=c,b[e=d]=h);putchar(d+97);}for(c=!putchar(f);f==41&b[e]==h;a[e--]=0);h+=f%17-47%f;}}

Try it online!

-1 byte thanks to Noodle9!

-2 bytes thanks to ceilingcat!

-1 byte thanks to c--!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Suggest o=o?:s instead of o=o?o:s. \$\endgroup\$
    – Noodle9
    Sep 12 at 19:38
5
\$\begingroup\$

Prolog (SWI), 101 bytes

This version uses 1-26 instead of a-z (alternative version for a-z below). Had to (re)learn about Prolog dictionaries for this one, I like them!

[H|T]+[I|U]+A/N:-(H@>[],H+I+A/N;I=A.get(H)),T+U+A/N;I is N+1,T+U+A.put(H,I)/I.
A+A+_.
A+B:-A+B+_{}/0.

Try it online!

(The H@>[] part is a bit hacky, it's a list check (is_list(H)) that works on TIO, but there's probably a way to get rid of it, as neither are necessary in my ungolfed solution. Please correct me!)

Ungolfed, commented

f([H|T],[NewH|NewT],Dict,N):-
% Case 1) No dict update needed
  ( f(H,NewH,Dict,N); % First element is a list (matches f([H|T]... or f([]...)
    NewH=Dict.get(H)), % First element is an atom
  f(T,NewT,Dict,N);
% Case 2) If first part failed, need to update the dictionary
  NewH is N+1,
  NewDict = Dict.put(H,NewH),
  f(T,NewT,NewDict,NewH).
f([],[],_,_).

% Wrapper predicate for recursive predicate
A+B:-f(A,B,_{},0).

a-z solution, 114 bytes

[H|T]+[I|U]+A/N:-(H@>[],H+I+A/N;I=A.get(H)),T+U+A/N;Z is N+1,name(I,[Z]),T+U+A.put(H,I)/Z.
A+A+_.
A+B:-A+B+_{}/96.

Try it online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Sep 14 at 23:09
4
\$\begingroup\$

Ruby, 69 65 60 bytes

f=->l,*r{l.map{|x|x*0==[]?f[x,*r]:""<<97+(r|=[x]).index(x)}}

Try it online!

\$\endgroup\$
4
\$\begingroup\$

K (ngn/k), 65 54 bytes

{$[x~*x;`s$`c$97+(s::?s,x)?x;[t:s;r:o'x;s::t;r]]};s:!0

Try it online!

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

Rust, 277 bytes

enum N{A(String),B(Vec<N>)};fn f(a:&[N],b:&mut Vec<String>)->Vec<N>{a.iter().map(|j|match j{N::A(j)=>N::A(('a'..='z').map(|i|i.to_string()).nth(b.iter().position(|a|a==j).unwrap_or_else(||{b.push(j.clone());b.len()-1})).unwrap()),N::B(j)=>N::B(f(j,&mut b.clone()))}).collect()}

Playground Link

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

JavaScript (Node.js), 109 bytes

s=>s.replace(/\w+|\S/g,m=>m>')'?v[m]=v[m]||Buffer([v[0]++]):(v=m<')'?S.push(v)&&{...v}:S.pop(),m),S=[v=[97]])

Attempt This Online!

Ungolfed and Explained

str => str.replace(
  /\w+|\S/g,                          // replace each variable name or bracket
  m => m > ')' ?                      // if match is a variable
    v[m] = v[m] || Buffer([v[0]++]) : // lookup the new var name, otherwise assign new
    (
      v = m < ')' ?                   // otherwise, if match is opening bracket
        S.push(v) && {...v} :         // push current var dict to stack
        S.pop(),                      // otherwise pop var dict
      m                               // return matched bracket (no-op)
    ),
  S = [                               // initialise stack
    v = [                             // initialise var dict
      97                              // v[0] = char code of next var name
    ]
  ]
)
\$\endgroup\$
2
\$\begingroup\$

Raku, 76 bytes

sub f($x,%h?){$x~~Str??(%h{$x}//=chr 97+%h)!!$x.map:{f $^a,$_}with %h.clone}

Try it online!

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