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

12
\$\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\$
3
  • 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
8
\$\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
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
6
\$\begingroup\$

Prolog (SWI), 81 bytes

\X,[I]-->[H],{\(X,H,I),Z=X;(Z=X;append(X,[H],Z)),nth1(I,Z,H)},(\Z;[]).
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.

Ungolfed Code

rename_item(InScopeVars),
  [ProcessedItem]
  -->
    [NextItem],
    {
      % Case 1: NextItem is a sublist
      % 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(InScopeVars,NextItem,ProcessedItem),

      % Since NextItem was not a new variable we don't change what is in scope
      NewInScopeVars=InScopeVars
    ;
      % Case 2: NextItem is a variable
      (
        % Case 2.1: NextItem is in scope (note this is not checked till later)
        NewInScopeVars=InScopeVars
      ;
        % Case 2.2: NextItem is not in scope so we need to add it to scope
        append(InScopeVars,[NextItem],NewInScopeVars)
      ),
      % Attempt to get the index of NextItem in the scope.
      % If this fails then we backtrack to Case 2.2 and add NextItem to the scope.
      nth1(ProcessedItem,NewInScopeVars,NextItem)
    },
    (
      % Attempt to rename the next remaining item in the list
      rename_item(NewInScopeVars)
    ;
      % If that fails then we are done!
      []
    ).

rename -->
  % We don't need to pass [] since appending to an unbound variable defaults to
  % appending to the empty list
  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:

103 bytes

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

Try it online!

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

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
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Sep 14 at 23:09
3
\$\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\$

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

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.