Re-name all identifiers to a single letter

Question

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.

Answer 1

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!

Answer 2

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

Answer 3

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!

Answer 4

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!

Answer 5

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--!

Answer 6

Ruby, 69 65 60 bytes

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

Try it online!

Answer 7

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!

Answer 8

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

Answer 9

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
    ]
  ]
)

Answer 10

Raku, 76 bytes

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

Try it online!

Answer 11

Perl, 63 60 29 bytes

(+1 for -p)

s/\w+/$a{$&}||=chr$i+++97/ge

Run like:

$ perl -pe 's/\w+/$a{$&}||=chr$i+++97/ge' <<<"(rudolf)"

or even

$ perl -pe 's/\w+/$a{$&}||=chr$i+++97/ge' file

Ungolfed and explained

This is a simple replacement using the powerful /e modifier, which instructs perl to evaluate the replacement as code. It finds each identifier and checks it against a hash. If the hash is empty, it populates the next available letter, starting with ASCII code 97 (a):

s/                     # substitute
   (\w+)               # match: 1+ word characters
 /
   $letter{$1} ||=     # use existing letter or else assign …
      chr($i++ + 97)   # … a char w/ value of $i + 97, then increment $i
 /gex;                 # match globally and eval the replacement as code
                       # (this explanation uses /x for comments & spacing)

Running through the examples on a file containing each test case on its own line:

$ while IFS= read line; do 
    printf "%-30s  %s\n" "$line" \
      "$(perl -pe 's/\w+/$a{$&}||=chr$i+++97/eg' <<<"$line")"
  done < 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) (d d) d)
(aa not (ab ac ad) (ad ad))     (a b (c d e) (e e))
(((((do) re) mi) fa) so)        (((((a) b) c) d) e)
(do (re (mi (fa (so)))))        (a (b (c (d (e)))))
((mark sam) sam)                ((a b) b)

This prints the input in a 30-char column before printing the answer.