# The greedy cutter

iBug recently got a long bar made of composite, yet valuable materials. The bar is so long that iBug can't easily sell it for credits, so he wants to cut it. The bar is made of such fragile and magic materials that, if a part is broken, all parts of the bar made of the same material will break, too, making it hard to cut arbitrarily.

iBug wants to cut the bar into as many pieces as possible. He also loves very short programs and code-golfing, so he made an abstract analysis of his problem.

iBug's magic bar is represented as a string (or an array or a sequence of characters if you prefer), like this:

aaabbccccccbbbaaacccccaabbbaaaaa


Each letter in the string represents one magic material. The bar always matches the RegEx ^\w*$, so there may be up to 63 materials in the bar. A "part" is a consecutive sequence of any characters that are not separated by spaces. iBug wants you to write a program that calculates the maximum parts that he could get, if zero or more character sets are fully removed (replaced by spaces), and tell iBug that number. Example 1: In: aaabbccccccbbbaaacccccaabbbaaaaa Out: 4  Description: If b is fully removed from the bar, iBug could get 4 parts. He can also get 4 parts by removing b and c, as is shown below aaabbccccccbbbaaacccccaabbbaaaaa # Original string aaa cccccc aaacccccaa aaaaa # Remove 'b' aaa aaa aa aaaaa # Remove 'b' and 'c'  And that's the maximum number of parts iBug can get from this bar Example 2: In: 111aa___9999____aaa99111__11_a_aa999 Result: 111aa 9999 aaa99111 11 a aa999 Out: 6  Description: By removing only the underscore, iBug can get 6 parts from the bar and that's the maximum. Example 3: In: __________ Out: 1  Description: What? You wanna cut this? It's only possible to get 1 part if you don't cut it at all. Example 4: In: Out: 0  Description: There's nothing to cut, so zero. There's also some rules that iBug want the programs to obey: 1. iBug dislikes standard loopholes and they are forbidden. 2. As long as it works, it need not be a full program. A function that takes input from a parameter and gives output via return value is also accepted. 3. Flexible input and output are allowed. Your program or function can take a string, or an array of characters, or whatever you find easiest to deal with. You can give the output by printing the number or returning it. ### Sample test cases (but not limited to these) aaabbbaaa = 2 123456789 = 5 AaAaAaAa = 4 aaabcccdedaaabefda = 6 ________ = 1 (empty) = 0  Since this is a , the shortest program (in bytes) in each language wins! ### Extra iBug highly appreciates if you can provide an explanation for your program, even though it does not affect your scoring (it's still length in bytes). • How does 123456789 yield 5? And how does aaabcccdedaaabefda yield 6? I get 2 and 4 respectively for these two test cases. – Mr. Xcoder Mar 3 '18 at 10:15 • @Mr.Xcoder for the first one, remove 2468, for the second, remove bd. – Martin Ender Mar 3 '18 at 10:28 • @MartinEnder Oh so any subsequence can be removed? if any of the characters are fully removed suggested otherwise. – Mr. Xcoder Mar 3 '18 at 10:29 • @Mr.Xcoder, if I've understood the challenge correctly, you remove 2,4,6,8 from the first and b,d,f from the second. – Shaggy Mar 3 '18 at 10:30 • @Mr.Xcoder it means removing all copies of any set of characters. I think the worked example shows it quite well. – Martin Ender Mar 3 '18 at 10:30 ## 8 Answers # Haskell, 73 71 70 bytes x#z|z==x=' '|1<2=z f x=maximum$length(words x):[f$(c#)<$>x|c<-x,c>' ']


Thanks to Laikoni for saving 1 byte!

Try it online!

• maximum$(length$words x): can be shortened to maximum$length(words x):. – Laikoni Mar 3 '18 at 12:05 ## JavaScript (ES6), 109 90 bytes f=s=>Math.max((s.match(/\s+/g)||[]).length,...[...s].map(c=>c> &&f(s.split(c).join ))) <input oninput=o.textContent=/\s/.test(this.value)?:f(this.value)><pre id=o>0 Somewhat slow on the 123456789 test case. Previous 109-byte answer wasn't limited to !/\s/: f= s=>(g=a=>Math.max(a.filter(s=>s).length,...[...a.join].map(c=>g([].concat(...a.map(s=>s.split(c)))))))([s]) <input oninput=o.textContent=f(this.value)><pre id=o>0 • – Asone Tuhid Mar 3 '18 at 16:53 • @AsoneTuhid Oh, I didn't see the restriction on the character set; my code works for any string at all. – Neil Mar 3 '18 at 20:38 • The only character it doesn't have to work for is space isn't it? – Asone Tuhid Mar 3 '18 at 20:50 • @AsoneTuhid Your port only works for exactly those characters that it needs to work for; your original seems to work for anything except spaces. – Neil Mar 3 '18 at 23:40 • What characters does your original answer work for that the new one doesn't? – Asone Tuhid Mar 3 '18 at 23:44 # Python 2, 11193 72 bytes -21 bytes thanks Kirill L. f=lambda s:max([len(s.split())]+[f(s.replace(c,' '))for c in s if'/'<c])  Try it online! • It looks like the approach currently used by JS and Ruby works quite well for Python too: 73 bytes – Kirill L. Mar 4 '18 at 16:14 • @KirillL. thanks for the recommendation – ovs Mar 4 '18 at 17:52 # Jelly, 13 11 bytes Too many 2-byte instructions -2 thanks to Zgarb (use the outer product quick þ >.<) eþŒPŒr¬S€ṀḢ  A monadic link accepting a list of characters and returning a non-negative integer. Try it online! ### How? For each subsequence of the input (the sets we may remove, plus redundant equivalents) gets an existence list to identify which are removed then effectively finds how many runs of zeros remain and yields the maximum. The last part works in a slightly odd way since I found it golfier than more naive alternatives - it finds the runs as [element, count] pairs, negates to identify zeros as ones, sums finds the maximum then takes the head (the sum of elements rather than of counts). eþŒPŒr¬S€ṀḢ - Link: list of characters e.g. "aabcde" ŒP - power-set - gets all subsequences ["","a","a","b",...,"bd",...,"aabcde"] þ - outer-product with: e - exists in? [[0,0,0,0,0,0],[1,1,0,0,0,0],[1,1,0,0,0,0],[0,0,1,0,0,0],..,[0,0,1,0,1,0]...,[1,1,1,1,1,1]] Œr - run-length encode [[[0,6]],[[1,2],[0,4]],[[1,2],[0,4]],[[0,2],[1,1],[0,3]],...,[[0,2],[1,1],[0,1],[1,1],[0,1]],...,[[1,6]]] ¬ - NOT [[[1,0]],[[0,0],[1,0]],[[0,0],[1,0]],[[1,0],[0,0],[1,0]],...,[[1,0],[0,0],[1,0],[0,0],[1,0]],...,[[0,0]]] € - for €ach: S - sum [[1,0],[1,0],[1,0],[2,0],...,[3,0],...,[0,0]] Ṁ - maximum [3,0] Ḣ - head 3  • I think €Đ€ can be þ. – Zgarb Mar 3 '18 at 16:02 # Ruby, 98 89 75 64 61 bytes f=->s{[s.split.size,*s.scan(/\w/).map{|c|f[s.tr c,' ']}].max}  Try it online! smaller and slower than before! Basically a port of @Neil's Javascript answer ### Ungolfed and annotated def f(input_string) # splits by / +/ by default size0 = input_string.split.size # an array of all non-space characters in input_string characters = input_string.scan(/\w/) size1 = characters.map {|i| # all letters and digits and _ are "bigger" than /, space isn't if i > '/' # tr replaces every occurrence of i in input_string with space next_string = input_string.tr(i, ' ') f(next_string) # recursive call else 0 end } # max value between size0 and any element in size1 return [size0, *size1].max end  Try it online! # Husk, 12 11 bytes ▲mȯ#€0gM€¹Ṗ  Try it online! This works by brute force and is quite slow. Add u to the right end to make it run faster, without changing the semantics. ## Explanation ▲mȯ#€0gM€¹Ṗ Implicit input, say S = "abddccbdcaab" Ṗ Powerset of S: P = ["","a","b","ab","d","ad"...,"abddccbdcaab"] m Map this function over P: Argument is a subsequence, say R = "acc" M ¹ Map over S € index of first occurrence in R: [1,0,0,0,2,2,0,0,2,1,1,0] g Group equal elements: [[1],[0,0,0],[2,2],[0,0],[2],[1,1],[0]] ȯ# Count the number of groups €0 that contain 0: 3 ▲ Take maximum of the results: 4  # Perl 5, (older versions), -p -I., 5249 43 bytes Old style counting: +3 for -p: 46 bytes (because it must be in a program, it can't be run using -e) barsplit.pl: #!/usr/bin/perl -pI.$G[split]+=s%\S%do$0for s/$&/ /rg%eg;$_=$#G


Run with the string on STDIN:

echo aaabcccdedaaabefda | ./barsplit.pl; echo


Try it online!

The -I. option is there to make this also work on recent perls where by default . is no more in @INC. In older versions of perl that option is not needed. I tested that on an older machine that still had perl 5.20, so the score is based on that (otherwise I should also count the . argument to -I)

Fast version (49 bytes):

#!/usr/bin/perl -pI.
$G[split]+=s%.%$$_++||do$0for s/$&/ /rg%eg;$_=\$#G


# Wolfram Language (Mathematica), 77 bytes

Max@Table[Tr[1^StringSplit[#,(##|##)..&@@s]],{s,Subsets@Union@Characters@#}]&


Try it online!