18
\$\begingroup\$

Context :

Suppose you have a sheet of paper measuring 8 x 10. You want to cut it exactly in half while maintaining its rectangular shape. You can do this in two ways.

  • You can cut it in half preserving its long dimension of 10 (for our purpose we will refer to this as long cut from now on).

Example : $$ [8, 10] \rightarrow {long cut} \rightarrow [4, 10] $$ Or you can cut it in half preserving its short dimension (we will refer to it as short cut).

Example :

$$ [8,10]→short cut→[5,8] $$

For a square, the short and long cut are same. i.e : $$ [12,12]→long cut→[6,12] $$ $$ [12,12]→short cut→[6,12] $$

Task :

For this challenge you are given two arguments.

  • The first is a string containing the cuts to be made to a sheet of paper in sequence from first to last. A long cut is designated by "L" and a short cut by "S".
  • The second is dimension of paper after said cuts were made (an array)

Given that devise a function that will find the all the possible original dimensions of the sheet of paper before any cuts were made.

The dimensions of a sheet are given as an array [x,y] (\$y\geq x\$)

Return all possible orignial paper measures : [x, y] for (\$y\geq x\$)

If input make it so that an output is not possible return a falsey value (be it empty array , false, 0, empty string, nil/null/Null). You may not give an error though

Examples :

cuttingPaper("S", [3, 7])      --> [[3, 14]]
cuttingPaper("L", [5, 7])      --> []
cuttingPaper("", [3, 7])       --> [[3, 7]]
cuttingPaper("S", [5, 7])      --> [[5, 14], [7, 10]]
cuttingPaper("LSSSSS", [1, 2]) --> [[2, 64], [4, 32], [8, 16]]

Explanation :

For example 2 :

L for [5, 7] gives empty array since if it started [5, 14] then the long cut would result in [2.5, 14] and if it started with [10, 7] then the long cut would result in [10, 3.5]. so in this case the cut is simply not possible

For example 4 :

[5, 7] for S cut gives 2 solutions since it could start as [5, 14] and then short cut would yield [5, 7] which is possible solution 1.

Alternately you can start with [7, 10] and then cut and you would end up with [5, 7] which is possible solution 2. B

ecause of that you get 2 possible solutions. (you output both)

In such a case you will return an array of array / list of list / etc...

I/O :

You take 2 inputs :

  • A String containing the cuts made.
  • The array after said cuts were made

You can take it as the following :

  • an array/set (or equivalents) containing 3 inputs (in following order [cuts, x, y] or [x, y, cut]
  • Three inputs cut, x, y or x, y, cut
  • 2 input cut, [x, y] or [x, y], cut
  • A string consisting of all 3 cuts x y (space seperated, you may choose your separator)

Notes :

  • The string will either be empty or contain some combination of S and/or L.
  • The array will always contain two Positive integers.
  • This is code-golf so shortest answer in bytes will win (note : I won't be selecting any answer as accepted).
  • Standard loopholes apply.

For those that solve it kindly if you can give a small explanation so others (mainly me) can learn/understand your code (if you have the time and patience)

\$\endgroup\$
6
  • \$\begingroup\$ Will it be okay to output the same solution more than once like (7,10) (7,10)? \$\endgroup\$
    – jdt
    Sep 18, 2021 at 21:43
  • \$\begingroup\$ @JohanduToit L unique array \$\endgroup\$ Sep 19, 2021 at 4:02
  • \$\begingroup\$ example id don't match? \$\endgroup\$
    – l4m2
    Sep 19, 2021 at 20:34
  • \$\begingroup\$ @l4m2: huh ? what is example id ? \$\endgroup\$ Sep 20, 2021 at 5:45
  • \$\begingroup\$ I think @l4m2 means that your reference to the 3rd example is actually a reference to the 4th one. \$\endgroup\$
    – Arnauld
    Sep 20, 2021 at 6:31

4 Answers 4

6
\$\begingroup\$

Python 3.8, 115 110 bytes

f=lambda s,d:{k for a,b in[d,d[::-1]]if(x:=(2*a,b)[::s[-1]<'S'or-1])[0]<=x[1]for k in f(s[:-1],x)}if s else{d}

Try it online!


Python 3.8, 104 bytes

Takes some inspiration from Arnauld's answer.

f=lambda s,d:s==''!=print(d)or[f(s[:-1],x)for a,b in{d,d[::-1]}if(x:=(2*a,b)[::s[-1]<'S'or-1])[0]<=x[1]]

Try it online!

\$\endgroup\$
6
\$\begingroup\$

JavaScript (V8),  94  91 bytes

Expects (list, width, height), where list is either a string or an array of characters. Prints the solutions.

f=([...c],w,h)=>c+c?c.pop(W=w*2)>"L"?f(c,w,h*2,W<h|w==h||f(c,h,W)):W>h||f(c,W,h):print(w,h)

Try it online!

How?

Given an operation and the resulting dimensions \$(w,h)\$ (with \$w\le h\$), we look for the possible solutions for the original dimensions.

If the operation was a long cut:

  • If \$2w\le h\$, the only possible solution is \$(2w,h)\$. Otherwise, this is invalid.

If the operation was a short cut:

  • \$(w,2h)\$ is always a solution.
  • If \$2w\ge h\$, \$(h,2w)\$ is another solution.
  • If \$w=h\$, both solutions are identical so we make sure to try only one of them to avoid duplicate results.

We attempt to apply these rules, starting with the last operation and going backwards. Whenever we successfully process the entire chain, we print the final result.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ dayum. +1 man :) \$\endgroup\$ Sep 18, 2021 at 19:34
4
\$\begingroup\$

05AB1E, 19 bytes

Takes [x, y] on the first and the (unquoted) cut sequence on the second line.

¸sRv€ÂÙ€ƶyCÉií}ʒD{Q

Try it online!

¸                    # wrap the pair into a list [[x,y]]
 sR                  # swap to the string and reverse it
   v                 # for each character y in the reversed string:
    €Â               #   extend the list by all pairs reversed
      Ù              #   remove duplicate pairs
       €ƶ            #   "Lift" each pair; multiply first element by 1, second by 2
         yCÉ         #   is y equal to 'L'?
            ií}      #   if so, reverse each pair
               ʒ     #   only keep resulting pairs, that are ...
                D{Q  #     equal when sorted
\$\endgroup\$
1
  • \$\begingroup\$ -1 byte by changing Éi to F. (And usually you're allowed to take a pair wrapped in a list by default, so the leading ¸ isn't really necessary in that case, but maybe ask OP if he allows it first.) \$\endgroup\$ Sep 19, 2021 at 21:12
0
\$\begingroup\$

Charcoal, 73 43 bytes

⊞υE²NF⮌S≔ΦE⁺υEυ⮌κEκ×μ⊕⁼ν⁼ιS¬›⁰↨κ±¹υIΦυ⁼κ⌕υι

Try it online! Link is to verbose version of code. Takes x, y, cuts on separate lines and outputs pairs of x, y on separate lines with double-spacing between each pair. Explanation: Now inspired by @ovs's answer.

⊞υE²N

Push the target pair to the predefined empty list.

F⮌S

Loop over the cuts in reverse order.

≔ΦE⁺υEυ⮌κEκ×μ⊕⁼ν⁼ιS¬›⁰↨κ±¹υ

Take the list of sizes and reverse each size. Take both lists and double either the width or length depending on the cut. Filter out those sizes where the width is larger than the length.

IΦυ⁼κ⌕υι

Deduplicate and output the final sizes.

\$\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.