15
\$\begingroup\$

I recently solved a coding challenge in one of the challenge papers that my IT teacher gave to us. It was a seemingly simple, but fun challenge, so I thought it will make fun golfing.

The task

Given an input of a 2x2 matrix that contains 4 strictly positive integers (i.e. non-negative and non-zero), like this:

$$\begin{pmatrix}a&b\\c&d\end{pmatrix}$$

We call the value of the matrix given is \$\left\lfloor\dfrac{a}{c}\right\rfloor - \left\lfloor\dfrac{b}{d}\right\rfloor\$.

Your task is to calculate the amount of rotation needed to get the maximum value of the matrix.

A rotation rotates the matrix 90 degrees clockwise.

Input and Output

The input can be a 2x2 matrix (as shown above), a flattened list [a b c d], or any other reasonable input.

Note that with the case of flattened lists, the numbers can be in any order you preferred. (e.g. [a b d c]).

The output must show a number that is the amount of rotation required.

Clarifications

  • In case of a tie, we will choose the one with the least amount of rotation needed.

  • In case where no rotation is required, we simply output 0 or 4 (the maximal rotation).

  • The division used here is integer division (i.e. the result of the division will always be an integer).

Examples

[a b c d] -> output
[1 2 3 4] -> 3
[5 7 9 2] -> 1
[5 6 7 8] -> 0 or 4
[1 9 2 3] -> 3
[2 5 6 8] -> 3

These examples are hand-calculated and written, so correct me if I'm wrong!

As always, standard loopholes are forbidden.

\$\endgroup\$
12
  • 2
    \$\begingroup\$ How should we handle 0 in the denominator? \$\endgroup\$ Oct 21, 2022 at 2:25
  • 1
    \$\begingroup\$ Will the values be positive integers? For ties, can we output any of the tied rotations? \$\endgroup\$
    – xnor
    Oct 21, 2022 at 4:35
  • 3
    \$\begingroup\$ Shouldn't [5 6 7 8] be 3? \$\endgroup\$ Oct 21, 2022 at 9:25
  • 3
    \$\begingroup\$ Is it integer division? \$\endgroup\$
    – AZTECCO
    Oct 21, 2022 at 10:20
  • 3
    \$\begingroup\$ @AZTECCO Good catch! I have clarified this in the Clarifications section \$\endgroup\$
    – oeuf
    Oct 21, 2022 at 12:56

16 Answers 16

6
\$\begingroup\$

Jelly, 12 bytes

ZU$Ƭ:/€INM’Ḣ

Try it online!

How it works

ZU$Ƭ:/€INM’Ḣ - Main link. Takes a matrix M on the left
  $Ƭ         - Do the following until a repeat is found:
Z            -   Transpose
 U           -   Reverse rows. This rotates clockwise 90°
      €      - To each rotation:
    :/       -   Reduce each column by integer division
       I     - Get the (negative) differences
        N    - Negate
         M   - Get the index of the maximal element
          ’  - Decrement
           Ḣ - Get the first (minimal) element
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Not quite right. You need to use integer division (:) e.g. [[7,5],[6,5]] should give 2, but with plain division you will find 0 instead. Also, "In case of a tie, we will choose the one with the least amount of rotation needed.", so you need to add after M e.g. [[5,7],[5,6]] should give 0 (or 4 since that's allowed) but we'll get [0,1,3] once we're using :. \$\endgroup\$ Oct 21, 2022 at 16:33
  • 4
    \$\begingroup\$ @JonathanAllan Yep, recently noticed the changes to the challenge. I'll update once I'm back at my laptop, thanks for the suggested changes :) \$\endgroup\$ Oct 21, 2022 at 16:34
4
\$\begingroup\$

Excel (ms365), 153, 148 bytes

-5 bytes by @jdt

=LET(a,INT(A1/C1)-INT(B1/D1),b,INT(C1/D1)-INT(A1/B1),c,INT(D1/B1)-INT(C1/A1),d,INT(B1/A1)-INT(D1/C1),m,MAX(a,b,c,d),IF(m=a,0,IF(m=b,1,IF(m=c,2,3))))

Original 153 bytes answer:

=XMATCH(9,BYROW(REDUCE(A1:D1,ROW(1:3),LAMBDA(a,b,VSTACK(a,SORTBY(TAKE(a,-1),{2,4,1,3})))),LAMBDA(c,SUM(INT(INDEX(c,{1,2})/INDEX(c,{3,4}))*{1,-1}))),-1)-1

It's painstaking in Excel, but my thought process here was:

  • REDUCE(A1:D1,ROW(1:3),LAMBDA(a,b,VSTACK(a,SORTBY(TAKE(a,-1),{2,4,1,3})))) - Create a vertical array where we keep stacking a 90° tilted array to our previous array;
  • BYROW(~,LAMBDA(c,SUM(INT(INDEX(c,{1,2})/INDEX(c,{3,4}))*{1,-1}))) - Loop over each row from said array and do the math as per question: Devide the 1st and 3rd integer by the 2nd and 4th, discard the fractional part and do a negative summation of the resulting integers;
  • XMATCH(9,~,-1)-1 - Find a nine (the largest possible outcome) or the next lower value. Deduct one from the given index.

enter image description here

\$\endgroup\$
4
  • 1
    \$\begingroup\$ @jdt, if it works it works! I'll edit in the option but will leave the original too. \$\endgroup\$
    – JvdV
    Oct 23, 2022 at 12:25
  • \$\begingroup\$ @jdt yes with stuff like TOCOL() you can. Where is your mind going? I'm intriqued =) \$\endgroup\$
    – JvdV
    Oct 23, 2022 at 12:37
  • \$\begingroup\$ Using a HLOOKUP or something instead of the nested IF statements but i think it will be longer. \$\endgroup\$
    – jdt
    Oct 23, 2022 at 12:41
  • \$\begingroup\$ There might be some potential in doing something like this: =LET(s,{0,2,1,3;2,3,0,1;3,1,2,0;1,0,3,2},a,MAKEARRAY(2,4,LAMBDA(x,y,IF(x=1,INT(OFFSET(A1,0,INDEX(s,y,1))/OFFSET(A1,0,INDEX(s,y,2)))-INT(OFFSET(A1,0,INDEX(s,y,3))/OFFSET(A1,0,INDEX(s,y,4))),-y))),-VLOOKUP(MAX(a),a, 1)) \$\endgroup\$
    – jdt
    Oct 23, 2022 at 13:41
3
\$\begingroup\$

JavaScript (ES6), 72 bytes

Expects four BigInts as [a,b,c,d].

A=>A.map(m=(_,i)=>(([a,b,c,d]=A,v=a/c-b/d)<=m||(j=i,m=v),A=[c,a,d,b]))|j

Try it online!

Commented

A =>                    // A[] = input list
A.map(                  // repeat 4 times,
  m =                   //   with m initialized to a non-numeric value
  (_, i) => (           //   and i as the rotation index:
    (                   //
      [a, b, c, d] = A, //     split A into [a, b, c, d]
      v = a / c - b / d //     compute the value v for this rotation
    ) <= m              //     do nothing if it's less than or equal to m
    || (j = i, m = v),  //     otherwise update m and the best index j
    A = [c, a, d, b]    //     rotate the flattened view of the matrix
  )                     //     (see below)
) | j                   // end of map(); return j

Rotation

Below are the details of the 90° clockwise rotation of the flattened matrix:

$$[a,b,c,d]\rightarrow\begin{pmatrix}\color{blue}a&\color{blue}b\\\color{green}c&\color{green}d\end{pmatrix}\rightarrow\begin{pmatrix}\color{green}c&\color{blue}a\\\color{green}d&\color{blue}b\end{pmatrix}\rightarrow[c,a,d,b]$$

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 14 bytes

4FDøí})ε`÷Æ}Zk

Input as a matrix. Outputs 0 if no rotation is necessary.

Try it online or verify all test cases.

Explanation:

4F       # Loop 4 times:
  D      #  Duplicate the current matrix
         #  (which will be the implicit input-matrix in the first iteration)
   øí    #  Rotate it once clockwise:
   ø     #   Zip/transpose; swapping rows/columns
    í    #   Reverse each inner row
 })      # After the loop: wrap the stack of five matrices into a list
   ε     # Map over each matrix:
    `    #  Pop and push both pairs/rows separated to the stack
     ÷   #  Integer-divide the items at the same positions in the pairs
      Æ  #  Reduce the pair by subtracting
   }Z    # After the map: push the maximum (without popping the list)
     k   # Get the (first 0-based) index of this maximum in the list
         # (which is output implicitly as result)
\$\endgroup\$
3
\$\begingroup\$

Factor, 81 bytes

Thanks to @chunes for -22

[ 3 [ dup reverse flip ] times 4array [ first2 v/ vfloor first2 - ] map arg-max ]

Attempt This Online!

Explanation

code explanation
3 [ dup reverse flip ] times 4array Generate a 4-item array of all rotations, by sequential reverse and flips
[ first2 v/ vfloor first2 - ] map Calculate the value of each matrix, according to the scheme. (First does vectorized floor division, then outputs difference of first 2 items.)
arg-max Index of the largest item
\$\endgroup\$
2
  • \$\begingroup\$ [ floor ] map -> vfloor and [ supremum ] keep index -> arg-max. \$\endgroup\$
    – chunes
    Oct 21, 2022 at 13:12
  • \$\begingroup\$ Welcome to the site, btw, and nice answer. It's great to see a Factor answer! \$\endgroup\$
    – chunes
    Oct 21, 2022 at 13:19
2
\$\begingroup\$

Ruby, 58 bytes

->a,b,c,d{(1..4).max_by{a,b,c,d=c,a,d,b
[a/c-b/d,-_1%-4]}}

Attempt This Online!

\$\endgroup\$
2
\$\begingroup\$

Factor, 62 bytes

[ 4 [ -rotd swap 4dup [ swap /i ] 2bi@ - ] replicate arg-max ]

Attempt This Online!

Takes 4 integers as input in the order a b c d.

  • 4 [ ... ] replicate Create a sequence of 4 elements where the elements are determined by the output of [ ... ].

Now let's take a look at what happens inside the replicate quotation:

                  ! 2 5 6 8          (example input)
-rotd             ! 6 2 5 8
swap              ! 6 2 8 5          (this is the next rotation of the matrix)
4dup              ! 6 2 8 5 6 2 8 5
[ swap /i ] 2bi@  ! 6 2 8 5 0 0      (apply [ swap /i ] to the top two pairs of items)
-                 ! 6 2 8 5 0        (so 0 is the first element of the sequence)
                  ! 6 2 8 5          (now the next element will be determined...)
  • arg-max Get the index of the largest element.
\$\endgroup\$
2
\$\begingroup\$

ARM Thumb-2 machine code, 34 bytes

03 24 e7 07 0f b4 08 bc 07 bc b0 fb f3 f5 b1 fb
f2 f6 ad 1b bd 42 a4 bf 2f 46 a4 46 01 3c f1 da
70 47

Assembler source:

    .syntax unified
    // doesn't work with clang?!
    // .arch armv7ve
    .arch armv7-a
    .arch_extension idiv
    .globl rotation
    .thumb
    .thumb_func
    // input: r0=A, r1=B, r2=D, r3=C
    // output: r12
    // Uses r0-r7, r12
rotation:
    // Register aliases since it is otherwise confusing
    A       .req r0
    B       .req r1
    D       .req r2
    C       .req r3
    rot     .req r4
    res     .req r12
    max     .req r7
    // Current rotation. This loops backwards, so we rotate backwards.
    movs    rot, #3
    // 3 << 31 = 0x80000000 = INT_MIN
    lsls    max, rot, #31
.Lloop:
    // Rotate COUNTER-CLOCKWISE by pushing/popping in a different order
    // Push and pop are the only things that make Thumb viable for this :)
    // A, B, D, C = B, D, C, A
    push    {A, B, D, C}
    pop     {C}
    pop     {A, B, D}
    // r5 = A / C
    udiv    r5, A, C
    // r6 = B / D
    udiv    r6, B, D
    // r5 = (A / C) - (B / D)
    subs    r5, r5, r6
    // Is this less than or equal to the max?
    cmp     r5, max
    // If so, save the new lowest rotation and the new max
    itt     ge
    movge   max, r5
    movge   res, rot
    // Loop while rot >= 0
    subs    rot, rot, #1
    bge    .Lloop
    // Return
    bx      lr

Uses the idiv extension.

Accepts arguments as r0=A, r1=B, r2=D, r3=C, and returns 0, 1, 2, or 3 in r12.

This cannot be called from C so I provide a wrapper which allows it to be called with this signature:

int rotation_c_wrapper(int A, int B, int D, int C);
    .syntax unified
    .arch armv7-a
    .thumb
    .thumb_func
    .globl rotation_c_wrapper
    // Wrapper to be called from C
    // int rotation_c_wrapper(int a, int b, int d, int c);
rotation_c_wrapper:
    // Save callee-saved registers
    push    {r4-r7, lr}
    // call the function
    bl      rotation
    // move result to r0
    mov     r0, r12
    // Restore callee-saved registers and return
    pop     {r4-r7, pc}
\$\endgroup\$
2
\$\begingroup\$

Python 3, 74 bytes

f=lambda a,b,c,d,*m:m.index(max(m))if 3<len(m)else f(c,a,d,b,*m,a//c-b//d)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Java 8, 116 99 bytes

a->{int r=0,i=-1,m=0,t;for(;++i<4;a=new int[]{a[2],a[0],a[3],a[1]})if((t=a[0]/a[2]-a[1]/a[3])>m){m=t;r=i;}return r;}

-17 bytes thanks to @Neil by taking four loose integer inputs instead of an integer-array

Try it online.

Explanation:

(a,b,c,d)->{ // Method with four integer parameters and integer return-type
 int r=0,    //  Result-index, starting at 0
     i=-1,   //  Index-integer, starting at -1
     m=0,    //  Max value, starting at 0
     t;      //  Temp-integer, uninitialized
     ++i<4   //  Loop `i` in the range (-1,4) (or [0,3]):
     ;       //    After every iteration:
      t=a,a=c,c=d,d=b,b=t)
             //     Rotate: change a,b,c,d to c,a,d,b
   if((t=a/c-b/d)
             //    Set `t` to a//c-b//d
      >m){   //    And if `t` is larger than `m`:
     m=t;    //     Set maximum `m` to this `t`
     r=i;}   //     And update the result with the current index `i`
  return r;} //  Finally, return the result-index `r`
\$\endgroup\$
2
  • \$\begingroup\$ 99 bytes \$\endgroup\$
    – Neil
    Oct 21, 2022 at 23:52
  • \$\begingroup\$ @Neil Ah, of course! Thanks. :) \$\endgroup\$ Oct 22, 2022 at 10:39
2
\$\begingroup\$

C (gcc), 92 bytes

y,r;g(a,b,c,d,i){y=i>3?0:g(c,a,d,b,i+1)<(a=a/c-b/d)?r=i,a:y;}f(a,b,c,d){g(a,b,c,d,r=0);r=r;}

Try it online!

  • function f initializes gobal r to 0 which is kinda default result. Then calls g which recursively sets r when a greater combination happens.

  • g sets global y to a greater value or itself or 0 if the recursion loop is completed(i>3), there cannot be greater value less than 0.

\$\endgroup\$
2
  • \$\begingroup\$ 85 bytes \$\endgroup\$
    – jdt
    Oct 22, 2022 at 15:19
  • \$\begingroup\$ @jdt I checked the IO rules again and it seems that your suggestion is fine, you are talking a reference and output to it, the internal use of it may seem a bit cheaty but it's clever, I think you can post it and also post a tip for golfing in C \$\endgroup\$
    – AZTECCO
    Oct 23, 2022 at 10:32
1
\$\begingroup\$

Perl 5, 99 bytes

sub f{($a,$b,$c,$d,$i,$m,$I)=@_;$v=$a/$c-$b/$d;$i-4?f($c,$a,$d,$b,$i+1,$v>$m?($v,$i):($m,$I)):$I|0}

Try it online!

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

Charcoal, 41 bytes

NθNηNζNεF⁴«⊞υ⁻÷θζ÷ηε≔θδ≔ζθ≔εζ≔ηε≔δη»I⌕υ⌈υ

Try it online! Link is to verbose version of code. Explanation:

NθNηNζNε

Input a, b, c and d.

F⁴«

Repeat four times.

⊞υ⁻÷θζ÷ηε

Push the value of the current rotation to the predefined empty list.

≔θδ≔ζθ≔εζ≔ηε≔δη

Rotate the matrix.

»I⌕υ⌈υ

Find the index of the maximum value.

I tried working with lists but the best I could do was 42 bytes:

≔E⁴NθF⁴«⊞υθ≔E1302§θIκθ»UMυ⁻÷⊟ι⊟ι÷⊟ι⊟ιI⌕υ⌈υ

Try it online! Link is to verbose version of code. Takes input in the order d b c a. Explanation:

≔E⁴Nθ

Input d, b, c and a into a list.

F⁴«

Repeat four times.

⊞υθ

Push the list to the predefined empty list.

≔E1302§θIκθ

"Rotate" the list.

»UMυ⁻÷⊟ι⊟ι÷⊟ι⊟ι

Replace each list with the value of the matrix it represents.

I⌕υ⌈υ

Find the index of the maximum value.

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

C (clang), 84 bytes

*t,m,v,i;f(*r,a,b,c,d){r?t=r,i=m=0:0;v=a/c-b/d;v<m||(m=v,*t=i);i++<4&&f(0,c,a,d,b);}

Try it online!

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

Vyxal, 18 bytes

 4(:⁽ḭÞC÷-$∩R)_WÞMh

Try it Online!

Unfortunately useful operator İ "collect while unique" currently works bad, so simple for-loop is used.

4(     # Open for-loop with 4 iterations
:      # Duplicate
⁽ḭÞC   # Reduce columns by integer division
÷-     # Calculate value
$      # Swap
∩R     # Transpose + Reverse = Rotate
)      # Close loop 
_      # Pop unnecessary
W      # Wrap stack into list
ÞM     # Find all indices of maximum
h      # Pick and print one (first)
\$\endgroup\$
0
\$\begingroup\$

Japt -h, 15 bytes

4o ñ@zX yÈrzÃr-

Try it

4o ñ@zX yÈrzÃr-     :Implicit input of 2D-array
4o                  :Range [0,4)
   ñ                :Sort by
    @               :Passing each X through the following function
     zX             :Rotate U clockwise X times
        y           :Transpose
         È          :Map
          r         :  Reduce by
           z        :  Integer division
            Ã       :End map
             r-     :Reduce by subtraction
                    :Implicit output of last element
\$\endgroup\$

Your Answer

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

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