# Marquee sign letters

Each day you put up a new word on a marquee sign with movable letters, buying just the letters you need to write it. You re-use letters you've bought for earlier words whenever possible. Given the words you want to write each day in order, output the letters you buy each day.

Example

Input:  ['ONE', 'TWO', 'THREE', 'SEVENTEEN']
Output: ['ENO', 'TW', 'EHR', 'EENSV']

Day 1: You start with no letters, so to write ONE, you buy all its letters E, N, O.
Day 2: The next day, you want to put up TWO (taking down the ONE). You already have an O from ONE, so you buy an additional TW.
Day 3: At this point, you have ENOWT. To write THREE, you need EHR. Note that you need to buy a second E in addition to the one you have.
Day 4: To write SEVENTEEN, you need 4 E's total of which you already have two (not three!), so you buy two more. You also have the T and one of the N's, so you buy the remaining letters: EENSV.

We've output letters sorted alphabetically in this example, but you may output them in any order.

Input: A non-empty list of non-empty strings of letters A-Z. You may use lowercase if you prefer. Lists of characters are fine for strings.

Output: Output or print the additional letters you need to buy each day. The letters for a day may be output in any order, but the days must come in the right order.

The letters from each day should be separated from other days so you can tell where a day ends. A trailing and/or leading separator is fine, both within a day or between days. Note that a day may have no letters bought, which should be reflected in the output (a space or empty line is OK, even for the last day).

Test cases

['ONE', 'TWO', 'THREE', 'SEVENTEEN']
['ENO', 'TW', 'EHR', 'EENSV']

['ONE', 'TWO', 'ONE', 'THREE']
['ENO', 'TW', '', 'EHR']

['ABC', 'AABC', 'ABBC', 'ABCC', 'AABBCC']
['ABC', 'A', 'B', 'C', '']

['SHORT', 'LOONG', 'LOOOONG', 'LOOOOOOONG', 'SHORT', 'LOOONG']
['HORST', 'GLNO', 'OO', 'OOO', '', '']

Here are all the inputs and outputs as separate lists:

[['ONE', 'TWO', 'THREE', 'SEVENTEEN'], ['ONE', 'TWO', 'ONE', 'THREE'], ['ABC', 'AABC', 'ABBC', 'ABCC', 'AABBCC'], ['SHORT', 'LOONG', 'LOOOONG', 'LOOOOOOONG', 'SHORT', 'LOOONG']]
[['ENO', 'TW', 'EHR', 'EENSV'], ['ENO', 'TW', '', 'EHR'], ['ABC', 'A', 'B', 'C', ''], ['HORST', 'GLNO', 'OO', 'OOO', '', '']]

And as space-separated strings (the trailing spaces in the outputs matter):

ONE TWO THREE SEVENTEEN
ONE TWO ONE THREE
ABC AABC ABBC ABCC AABBCC
SHORT LOONG LOOOONG LOOOOOOONG SHORT LOOONG

ENO TW EHR EENSV
ENO TW  EHR
ABC A B C
HORST GLNO OO OOO

• A wild leaderboard script has appeared in the userscript age :o – Quintec Apr 21 at 21:50
• Can we output as an an array of characters that need to be bought rather than a string of all the characters? e.g.: [['E', 'N', 'O'], ...] – Downgoat Apr 22 at 6:28
• Is the output SHORTLONGOOOOO valid for the last output? AKA using no delimiters? – Magic Octopus Urn Apr 22 at 18:15
• @Downgoat Yes, lists are chars are fine to output. – xnor Apr 22 at 21:23
• @MagicOctopusUrn No, you need delimiters, otherwise you can't tell what letters are for what day. – xnor Apr 22 at 21:23

import Data.List
g x=zipWith(\\)x$scanl(++)""$g x

Try it online!

We build the output list by calculating pairwise the list difference (\\) of the input list and the cumulative append of the output list (starting with "").

input list:                ONE       TWO       THREE        SEVENTEEN
cumulative append:         ""   +->  ONE  +->  ONETW   +->  ONETWHRE
list difference (output):  ONE -+    TW  -+    HRE    -+    SVEEN

With both Data.List and Data.Function in scope (e.g. by using the lambdabot environment), this can be shortened to 30 bytes:

fix.(.scanl(++)"").zipWith(\\)

Edit: -5 bytes thanks to @Sriotchilism O'Zaic.

# Python 2, 72 68 bytes

-4 bytes thanks to Jonathan Allan.

p=''
for r in input():
for x in p:r=r.replace(x,'',1)
print r;p+=r

Try it online!

## Commented

l=input()       # the list of words to write
p=''            # p contains all letters we own
for r in l:     # for each word ...
for x in p:   # for each letter we own ...
r=r.replace(x,'',1)   # remove one occurence from the current word
print r       # print the remaining word
p+=r          # add the remaining chars to p
• for r in input(): saves 4 bytes. – Jonathan Allan Apr 22 at 1:03

# Jelly, 7 bytes

,œ-@Kɗ/

Try it online!

Output: -separated string.

# Perl 6, 44 bytes

{$!=@;.map:{kxxv$!=.comb.Bag∖($⊎=$!):}}

Try it online!

Outputs as a list of lists of characters.

### Explanation

{                                      } # Anonymous codeblock
$!=@; # Initialise$! to an empty list
.map:{                          }  # Map each item in the input to
.comb                # The string split to characters
.Bag            # In a Bag
∖           # Set minus
($⊎=$!)    # The accumulated Bag of results
$!= # And save the result for the next item kxxv : # Then decompose the Bag into a list • A reason for the downvote would be appreciated – Jo King Apr 21 at 18:38 • Not the downvoter, but I'm gonna say this output format strays too far. Something like Bag(E(2), N, S, V) would need to actually show two E's to be OK. – xnor Apr 21 at 18:59 • What, really? That's just the default print formatting. The return result is an unordered list that contains those characters (and can contain multiple of the same character). I'll update the output formatting to better reflect this, but the downvote seems ridiculous. – Jo King Apr 21 at 19:15 • Downvoter, could you please explain, is this about I/O or something else? About the bag format, I don't know Perl, is this common for I/O in Perl golfs? Looking at the docs (cached because site is down), they seem to me to be more like dicts with counts, akin to Python's collections.Counter which I didn't intend to allow as output. Can one easily iterate over bag elts with multiplicity, cast to a list/array, display with multiplicity, etc? – xnor Apr 21 at 20:06 • Downvote was a mistake, was meant to be up. – Jonathan Allan Apr 22 at 0:28 # Haskell, 44 bytes import Data.List foldl1(\a x->a++',':(x\\a)) Try it online! Output is a string like ONE,TW,HRE,SVEEN with commas between days. • What a nice use of the output format to avoid needing to fold the \. And an unexpected foldl1 base case too. – xnor Apr 27 at 3:43 # JavaScript (Node.js), 59 bytes a=>a.map(h=>([...t].map(c=>h=h.replace(c,'')),t+=h,h),t='') Try it online! Quite straightforward solution. For each word h, remove letters we already have. Here is an explained version of that code: f = list => { // the string that accumulates all the letters already bought let accu = ''; // for every word in the list return list.map( word => { // for every letter already bought [...accu] // remove the letter from the word .map(char => { return word = word.replace(char,'') }); // add not bought letters to accumulator accu += word; // the reduced word (without already bought letters) should be added to result map // this represents the letters to buy today return word }, accu) } console.log(f(['ONE', 'TWO', 'THREE', 'SEVENTEEN'])) console.log(f(['ONE', 'TWO', 'ONE', 'THREE'])) console.log(f(['ABC', 'AABC', 'ABBC', 'ABCC', 'AABBCC'])) console.log(f(['SHORT', 'LOONG', 'LOOOONG', 'LOOOOOOONG', 'SHORT', 'LOOONG'])) • You can save 1 byte by borrowing the only worthwhile trick from my otherwise overcomplicated solution. – Arnauld Apr 22 at 7:45 # J, 29 bytes -29 bytes thanks to FrownyFrog! (],a.<@#~0>.-&(1#.a.=/;))/@|. Try it online! # Original Post ## J, 58 bytes [:}.@>[:(],<@(/:~@({.@>@-.&(((e.<@#[){:)\));))&.>/<@a:,~|. Try it online! Thanks to ngn for help improving the "subtract letters while respecting repetition part". Not a great fit for J, but an illuminating exercise. Let's begin by constructing a helper verb wo ("without") that removes all chacters in one string from another, while respecting repetitions. wo=.{.@>@-.&(((e. <@# [) {:)\) There is a fun idea here: We make each repeated instance of a character unique, by repeating it the required number of times. Thus if our original string is ABBA it becomes: ┌─┬─┬──┬──┐ │A│B│BB│AA│ └─┴─┴──┴──┘ A third A would become AAA and so on. This is accomplished by the phrase ((e. <@# [) {:)\, which takes each prefix \, looks at the final element {: of it, and constructs a mask of all elements in that prefix that match e. that final element, and then filters and boxes just those elements <@#. With our inputs both "unique-ified" we can now safely use normal set minus -. while still respecting repetition. We then open each result and take only the first element to "undo" our repetitions: {.@> Plugging this helper verb in, our overall solution (which simply inlines it) becomes: [: }.@> [: (] , <@(/:~@wo ;))&.>/ <@a: ,~ |. Essentially, all we do here is setup our problem as a single reduction. We start be reversing the input |. and appending to it ,~ an ace a:, or empty box, which will be the initial value of our final result, like so: ┌─────────┬─────┬───┬───┬──┐ │SEVENTEEN│THREE│TWO│ONE│┌┐│ │ │ │ │ ││││ │ │ │ │ │└┘│ └─────────┴─────┴───┴───┴──┘ We stick the following verb between each element to effect the reduction: (] , <@(/:~@wo ;))/ This says: take the right input ] (ie, our result) and append to it , the left input (this is ONE on the first iteration, TWO on the 2nd, etc) without wo the raze of ; the right input (ie, without any previous letters so far used), but before appending sort it /:~ and box it again <@. At the end of all this we'll have the result we want, a list of boxes, but all inside one big additional box, and still with the empty box at the front. Thus we open to remove the outer box and kill the first element: }.@>. • [:}.@>|.(],a.<@#~0>.-&(1#.a.=/;))&.>/@,<@a: – FrownyFrog Apr 22 at 15:28 • A simple (],a.<@#~0>.-&(1#.a.=/;))/@|. also works unless I'm missing an edge case. – FrownyFrog Apr 22 at 18:47 • As far as I can tell, sorting is nowhere in the requirements. – FrownyFrog Apr 22 at 21:10 • Updated and now that I've had time to absorb it, just wanted to say again: That's damn nice J! – Jonah Apr 23 at 3:12 # JavaScript (ES6), 66 65 bytes a=>a.map(b=s=>[...s].filter(c=>x==(x=x.replace(c))?b+=c:0,x=b+0)) Try it online! ### Commented $$\b\$$ is a string holding all available letters (and also some invalid characters, but this is irrelevant to the algorithm). For each new word, we create a copy of $$\b\$$ in $$\x\$$. Each letter $$\c\$$ of a word is either used by removing it from $$\x\$$ or bought by appending it to $$\b\$$. Only bought letters are returned. a => // a[] = input a.map(b = // initialize b to the callback function of this map() // it will be coerced to a string that does not contain // any letter in uppercase s => // for each entry s in a[]: [...s].filter(c => // for each character c in s: x == ( // check whether x is changed when x = x.replace(c) // c is replaced with 'undefined' ) ? // if so: b += c // append c to b and keep c : // else: 0, // discard c x = b + 0 // coerce b to a string and save it in x ) // end of filter() ) // end of map() # C++ (gcc), 177 170 bytes -5 bytes thanks to @anatolyg's tip, -2 bytes to small things I noticed. #import<random> #define v std::vector<std::string> v a(v p){std::vector<int>o(91),b;int j=-1;for(auto i:p){b=o;p[++j]="";for(int c:i)--b[c]<0?p[j]+=c,++o[c]:0;}return p;} Explanation #import<random> adds both <string> and <vector> for half the bytes. First creates a 91-element vector of 0s (only indices 65-90 are used to store letter occurences), and another vector of the same type but not set to a value. Iterates through each element of the input (the days): gets the currently owned letters, gets the letters that are needed for the day, overrides the input at the index with the needed amount and updates the owned letters. Returns the overridden input. Try it online! • You can do #define v std::vector<std::string and remove using namespace std to reduce byte count by 6 bytes. – anatolyg Apr 22 at 15:31 # C# (Visual C# Interactive Compiler), 123 bytes a=>{var b="";for(dynamic i=0,e,f;i<a.Count;b+=a[i++]=f)foreach(var c in((e,f)=(b.ToList(),"")).f+a[i])f+=e.Remove(c)?"":c;} Try it online! Anonymous function that outputs by modifying an input array. // a: input array of strings a=>{ // b: cumulative letters var b=""; for( // i: loop index of string // e: copy of cumulative letters for manipulation // f: characters missing from current string dynamic i=0,e,f; // iterate over each string in a i<a.Count; // add missing letters of the day to // cumulative missing letters and // update array for output b+=a[i++]=f ) // iterate current string with character c foreach(var c in // tuplized variable assignment // e=b.ToList() // set e to a copy of the cumulative letters // f="" // initially there are no letters needed for the day ((e,f)= (b.ToList(),"")).f+a[i] ) // conditionally add c to missing letters for the day f+=e.Remove(c)?"":c; } # R, 119 112 106 103 bytes -7 bytes from aliasing the two longer function names and now taking user input from scan() -6 bytes to only call strsplit() once at the beginning -3 bytes to get rid of the aliasing again and assign two variables in one call (Also edited the byte count which was erroneously low earlier) a=scan(,'');b=a=strsplit(a,'');for(i in 2:length(a))b[[i]]=vecsets::vsetdiff(a[[i]],unlist(b[1:i-1]));b This is my very first PPCG submission of any kind! So I have no idea what I'm doing both in terms of golfing and in terms of posting etiquette. The output is a list of vectors which may or may not meet the terms of the challenge. :-P As for the code itself, it takes user input via scan() and compares each new day's letters to the cumulatively owned letters, as in other solutions. If there are shorter alternatives to unlist and strsplit for converting strings into vectors of individual characters that would be cool to know. I also used the vsetdiff function in Carl Withoft's vecsets package to get the set difference of the letters needed for the next day and the current letters owned. # Python 2, 102 100 bytes from collections import* c=Counter l=c() for x in map(c,input()):y=x-l;l+=y;print list(y.elements()) Try it online! -2 bytes, thanks to Embodiment of Ignorance # Japt, 15 14 bytes £Q®X=rZPPÃQ±XX Try it £Q®X=rZPPÃQ±XX :Implicit input of array £ :Map each X Q® : Map each Z in Q (initially a quotation mark) X= : Reassign to X rZ : Replace Z with P : The empty string P : With the default global flag disabled Ã : End map Q±X : Append X to Q X : Return X • @Downvoter, please have the decency to leave a comment. – Shaggy Apr 22 at 16:18 # Red, 75 bytes func[b][a: copy""foreach w b[foreach c a[replace w c""]print w append a w]] Try it online! # PowerShell, 71 bytes$args|%{$w=$_;$p|% t*y|%{$w=$w-replace"^(.*?)$_(.*)",'$1$2'};$w;$p+=$w} Try it online! Takes input words$args and iterates over them. Each iteration we set the current word $w, then loop over our$pool of already-purchased letters. Each inner loop, we perform a regex -replace on our current $word, so that we're replacing just the first instance of the letter from our$pool. Once we've gone through all letters in the pool, we output what's remaining $w (i.e., what we need to purchase), and then tack those letters onto our pool$p+=$w for the next word. # Excel VBA, 127 bytes Function z(w) z="" For Each x In w.Cells v=x.value For y=1To Len(z) v=Replace(v,Mid(z,y,1),"",1,1) Next z=z&v Next End Function Takes input in the form of an excel range. # C (gcc), 118 bytes m(a,r,q,u)char**a,*r,*q,*u;{for(;*a;a++,memcpy(r,q,255))for(memcpy(q,r,255),u=*a;*u;u++)*u=r[*u]-->0?32:(q[*u]++,*u);} Try it online! As a little bonus it takes the stock in r at the start as an array. Outputs the input null-terminated null-terminated-string list a with all pre-owned letters replaced with spaces. # 05AB1E, 11 bytes -6 thanks to Kevin Cruijssen ćsvDysSõ.;» Try it online! • Your 15-byter works, but I would replace the trailing J with ». Also, you can save 4 bytes by replacing vyð.;}ðK with Sõ.; 11 bytes. – Kevin Cruijssen Apr 23 at 8:29 • Ahhhh... I needed S to make it vectorize. – Magic Octopus Urn Apr 24 at 12:34 # Swift 4.2/Xcode 10.2, 244242239 238 bytes a.reduce(([Character:Int](),[String]())){c,l in let b=l.reduce(into:[Character:Int]()){$0[$1,default:0]+=1}.map{($0,max(0,$1-(c.0[$0] ?? 0)))};return(c.0.merging(b){$0+$1},c.1+[b.map{String(Array(repeating:$0.0,count:$0.1))}.joined()])}.1

Try it online!

The letters are not arranged in alphabetical order, it is not forbidden by the rules.

# Scala, 68 bytes

(c:Seq[String])=>c./:(Seq(""))((a,n)=>a:+n.diff(a./:("")(_+_))).tail

Try it online!

/: is short-hand for foldLeft operator, a is aggregation, ultimately returns the result we want, n is next element

## Un-golfed

def NewLettersPerDay(c: Seq[String]): Seq[String] = {
c.foldLeft(Seq(""))((agg, next) => {
val existingLetters = agg.reduce(_+_)
val newDayLetters = next.diff(existingLetters)
agg :+ newDayLetters
}).tail
}

# Charcoal, 18 bytes

ＥθΦι¬⊙…θκ‹№…ιμλ№νλ

Try it online! Link is to verbose version of code. Explanation:

θ                  Input array
Ｅ                   Map over strings
ι                Current string
Φ                 Map over characters
θ            Input array
…             Truncated to length
κ           Outer index
¬               Logical Not
⊙              Any element exists where
№         Count of
λ     Current letter in
ι       Outermost word
…        Truncated to
μ      Current letter index
‹          Is less than
№    Count of
λ  Current letter in
ν   Innermost word
Implicitly print each day's bought letters on their own line

Try it online!

# Ruby, 52 bytes

->l{r="";l.map{|x|r.chars{|c|x[c]&&x[c]=''};r+=x;x}}

Try it online!

# K (ngn/k), 36 bytes

{*+""{(a;x,a:&0|-/#''='(y;x@:1))}\x}

Try it online!

# Stax, 7 bytes

é█üa%┐┤

Run and debug it

Output is newline separated.