Drop some boxes

Say I have a pile of boxes:

AAA
BBB


I can create it in two steps:

BBB
↓
(empty)
---
AAA
↓
BBB


But with this:

AB
BA


I need three steps:

 A
↓
(empty pile)
---
BB
↓
A
---
A
↓
B
BA


Given a pile of boxes, output the minimum number of steps needed to create that pile.

A step consists of dropping a row of boxes of the same type onto the current pile.

For example, AAA can be dropped as a step, so can A A, but A B and

 A
AAA


can't.

Input can be as a matrix, text, whatever. The input will always be a solid block - nothing like

BB
AAA


Will ever be inputted, so you don't have to parse spaces / empty values.

Scoring

This is , shortest wins!

Testcases

AB
BA
=> 3

A
B
C
D
E
=> 5

AAA
AAA
AAA
=> 3

ABCAB
DEACB
=> 7

POTATOS
DOBEYUM
=> 12

• Sandboxed Jun 20 '21 at 10:16
• Your challenges are always so hard man... Jun 20 '21 at 11:51
• @Wasif "challenges" That's why ;)
– user100690
Jun 20 '21 at 11:55
• @Wasif Turns out there isn't a vanilla set difference challenge yet ;) Jun 20 '21 at 19:53
• I think this problem is equivalent to finding the shortest string that has all of the given strings as subsequences, a task that's NP-complete. So, we're not going to see any efficient solutions (which is fine for golfing, just pointing it out).
– xnor
Jun 20 '21 at 19:55

Pyth, 22 bytes

L&lbhSmhyfT>RqhkhdbbyC


This is basically ovs's Python solution translated verbatim to Pyth (it seems that their solution's exact algorithm is also shortest in Pyth), so I'm posting it as community wiki. Doesn't time out thanks to Pyth's memoization.

Python 2, 103 91 bytes

-12 bytes thanks to PurkkaKoodari!

lambda s:f(zip(*s))
f=lambda s:len(s)and-~min(f({r[r[0]==x[0]:]for r in s}-{()})for x in s)


Try it online! The last testcase times out.

The first function just transposes the input, if we can take input as a list of columns it can be omitted.

• I like the -{()} Jun 20 '21 at 14:02
• @PurkkaKoodari thanks a lot. I was thinking I need to remove items from the bottom, but since the input is always rectangular this doesn't seem to be the case
– ovs
Jun 20 '21 at 15:02

Charcoal, 57 bytes

ＷＳ⊞υι≔⟦Ｅθ⮌⭆υ§λκ⟧η≔⁰ζＷ⌊η«≦⊕ζ≔ηθ≔⟦⟧ηＦθＦκ⊞ηΦＥκΦμ∨π¬⁼ξ§λ⁰μ»Ｉζ


Try it online! Link is to verbose version of code. Uses brute force so too slow for the last test case on TIO. Explanation:

ＷＳ⊞υι


Input the pile.

≔⟦Ｅθ⮌⭆υ§λκ⟧η


Rotate the pile by 90° and put it into a list.

≔⁰ζ


Start counting the number of steps.

Ｗ⌊η«


Repeat until there is at least one empty pile.

≦⊕ζ


Increment the number of steps.

≔ηθ≔⟦⟧ηＦθ


Make a copy of the list of piles so that it can be looped over while starting a new list of piles.

Ｆκ


Loop over each column of the pile.

⊞ηΦＥκΦμ∨π¬⁼ξ§λ⁰μ


Remove the letter at the bottom of that column from all of the columns that have it as its bottom letter and push any remaining non-empty columns to the list.

»Ｉζ


Print the number of steps needed.

Brachylog, 31 bytes

∧≜.&z{{⟨k≡t⟩|;X}ᵐRtᵛ∧Rhᵐ}ⁱ↖.zĖ∧


Try it online!

It's a bit less efficient than even the other two answers so far (it does the classic recompute everything if it hasn't reached the end in as many steps as it's trying), so I might just delete this when I wake up if it still hasn't spit something out for the second-to-last test case.

Jelly, 24 bytes

ZWṖ€ṛ¦Ɱ0ịⱮĠƊ$€Ẏ$Ẹ€Ạ$Ð¿L’  Try it online! A monadic link taking a list of Jelly strings (a list of lists of characters) and returning an integer. Explanation Z | Transpose W | Wrap in a list$Ð¿   | While the following is true:
Ẹ€       | - Any list is non-empty for each list of lists
Ạ      | - All
$| Do the following, collecting up intermediate results$€           | - For each list:
Ṗ€ṛ¦Ɱ    Ɗ             |   - Remove the last character of the lists for each of the groups of indices determined by the following:
0ịⱮ               |     - Last character of each list
Ġ              |     - Group indices of identical characters
Ẏ         | - Tighten (join outermost lists together)
L  | Length
’ | Subtract 1


All cases (uses Q for 1 extra byte to make it more efficient, but would complete eventually without it)

J, 55 bytes

(1+[:<./\$:"1)@((]}.~1{.=)&.>"0/~' '-.~{.&>)0:@.(''-:;)


Try it online!

Brute force recursion taking away boxes until none are left, and returning the minimum number of steps.

Ruby, 73 bytes

->l{l.permutation.map{|x|x*=?_;1while x.sub!(/(.*)_\1/,'\1');x.size}.min}


Try it online!

Assuming I can accept a list of columns in input

Ruby, 108 bytes

->l{l.map(&:chars).transpose.map(&:join).permutation.map{|x|x*=?_;1while x.sub!(/(.*)_\1/,'\1');x.size}.min}
`

Try it online!

Otherwise