17
\$\begingroup\$

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

Testcases

AB
BA
=> 3

A
B
C
D
E
=> 5

AAA
AAA
AAA
=> 3

ABCAB
DEACB
=> 7

POTATOS
DOBEYUM
=> 12
\$\endgroup\$
6
  • \$\begingroup\$ Sandboxed \$\endgroup\$
    – emanresu A
    Jun 20, 2021 at 10:16
  • \$\begingroup\$ Your challenges are always so hard man... \$\endgroup\$
    – Wasif
    Jun 20, 2021 at 11:51
  • 2
    \$\begingroup\$ @Wasif "challenges" That's why ;) \$\endgroup\$
    – user100690
    Jun 20, 2021 at 11:55
  • \$\begingroup\$ @Wasif Turns out there isn't a vanilla set difference challenge yet ;) \$\endgroup\$
    – emanresu A
    Jun 20, 2021 at 19:53
  • \$\begingroup\$ 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). \$\endgroup\$
    – xnor
    Jun 20, 2021 at 19:55

7 Answers 7

9
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I don't think the extra zip and [::-1] are necessary. \$\endgroup\$ Jun 20, 2021 at 13:52
  • 1
    \$\begingroup\$ I like the -{()} \$\endgroup\$
    – pxeger
    Jun 20, 2021 at 14:02
  • \$\begingroup\$ @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 \$\endgroup\$
    – ovs
    Jun 20, 2021 at 15:02
8
\$\begingroup\$

Charcoal, 57 bytes

WS⊞υι≔⟦Eθ⮌⭆υ§λκ⟧η≔⁰ζW⌊η«≦⊕ζ≔ηθ≔⟦⟧ηFθFκ⊞ηΦEκΦμ∨π¬⁼ξ§λ⁰μ»Iζ

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

WS⊞υι

Input the pile.

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

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

≔⁰ζ

Start counting the number of steps.

W⌊η«

Repeat until there is at least one empty pile.

≦⊕ζ

Increment the number of steps.

≔ηθ≔⟦⟧ηFθ

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

Fκ

Loop over each column of the pile.

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

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.

»Iζ

Print the number of steps needed.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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)

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.