Marquee sign letters

Question

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  

Leaderboards

var QUESTION_ID=183544,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

Haskell, 54 49 bytes

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.

Answer 2

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

Answer 3

Jelly, 7 bytes

,œ-@Kɗ/

Try it online!

Output: -separated string.

Answer 4

Perl 6, 44 40 bytes

-4 bytes thanks to Matthew Jensen

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

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

Answer 5

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

Answer 6

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.

Answer 7

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: }.@>.

Answer 8

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

Answer 9

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!

Answer 10

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}

Answer 11

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

Answer 12

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;
}

Answer 13

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.

Answer 14

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.

Answer 15

05AB1E, 11 bytes

-6 thanks to Kevin Cruijssen

ćsvDysSõ.;»

Try it online!

Answer 16

Red, 75 bytes

func[b][a: copy""foreach w b[foreach c a[replace w c""]print w append a w]]

Try it online!

Answer 17

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.

Answer 18

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.

Answer 19

Swift 4.2/Xcode 10.2, 244 242 239 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.

Answer 20

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
}

Answer 21

PHP, 87 bytes

for(;$w=$argv[++$i];print' ')for($b=$a;$l=$w[$$i++];)$b[$l]?$b[$l]--:++$a[$l]&&print$l;

Try it online!

Answer 22

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

Answer 23

PHP, UTF-8 aware (253 bytes)

<?php $p=[];for($i=1;$i<$argc;$i++){$a=$p;$b=[];for($j=0;$j<mb_strlen($s=$argv[$i]);$j++){$k=1;if(isset($a[$c=mb_substr($s,$j,1)]))if($a[$c]){$k=0;$a[$c]--;}if($k){echo $c;if(isset($b[$c]))$b[$c]+=$k;else $b[$c]=$k;}}$p=array_merge($p,$b);echo PHP_EOL;}

Answer 24

C# (Visual C# Interactive Compiler), 112 bytes

a=>{var b="";for(int i=0;;b+=a[i++])foreach(var z in b)if(a[i].Contains(z))a[i]=a[i].Remove(a[i].IndexOf(z),1);}

Try it online!

Answer 25

Perl 5 -p, 28 bytes

for$i(@h){s/$i//}push@h,/./g

Try it online!

Answer 26

Ruby, 52 bytes

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

Try it online!

Answer 27

K (ngn/k), 36 33 bytes

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

Try it online!

Answer 28

Stax, 7 bytes

é█üa%┐┤

Run and debug it

Output is newline separated.