Minimum rotation to get the maximum value

Question

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.

• dingledooper: How should we handle 0 in the denominator?
• xnor: Will the values be positive integers? For ties, can we output any of the tied rotations?
• Kevin Cruijssen: Shouldn't [5 6 7 8] be 3?
• AZTECCO: Is it integer division?
• oeuf: @AZTECCO Good catch! I have clarified this in the Clarifications section

Answer 1

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

• Jonathan Allan: 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 :.
• caird coinheringaahing: @JonathanAllan Yep, recently noticed the changes to the challenge. I'll update once I'm back at my laptop, thanks for the suggested changes :)

Answer 2

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

• JvdV: @jdt, if it works it works! I'll edit in the option but will leave the original too.
• JvdV: @jdt yes with stuff like TOCOL() you can. Where is your mind going? I'm intriqued =)
• jdt: Using a HLOOKUP or something instead of the nested IF statements but i think it will be longer.
• jdt: 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))

Answer 3

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]$$

Answer 4

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)

Answer 5

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

• chunes: [ floor ] map -> vfloor and [ supremum ] keep index -> arg-max.
• chunes: Welcome to the site, btw, and nice answer. It's great to see a Factor answer!

Answer 6

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!

Answer 7

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.

Answer 8

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}

Answer 9

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!

Answer 10

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`

• Neil: 99 bytes
• Kevin Cruijssen: @Neil Ah, of course! Thanks. :)

Answer 11

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.

• jdt: 85 bytes
• AZTECCO: @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

Answer 12

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!

Answer 13

Charcoal, 41 bytes

NθNηNζNεF4«⊞υ−÷θζ÷ηε≔θδ≔ζθ≔εζ≔ηε≔δη»I⌕υ⌈υ

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

NθNηNζNε

Input a, b, c and d.

F4«

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:

≔E4NθF4«⊞υθ≔E1302§θIκθ»UMυ−÷⊟ι⊟ι÷⊟ι⊟ιI⌕υ⌈υ

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

≔E4Nθ

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

F4«

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.

Answer 14

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!

Answer 15

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)

Answer 16

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