Drop some boxes

Question

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

Your challenge

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 code-golf, shortest wins!

Testcases

AB
BA
=> 3

A
B
C
D
E
=> 5

AAA
AAA
AAA
=> 3

ABCAB
DEACB
=> 7

POTATOS
DOBEYUM
=> 12

Answer 1

Pyth, 22 bytes

L&lbhSmhyfT>RqhkhdbbyC

Try it online! Or run all test cases at once.

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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)

Answer 6

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.

Answer 7

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