We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.

Return to Revisions

Regex (.NET), 90 bytes

(?=(x*)(1円x?))(x*).*$(?<=(?=(?<-5>x)*1円(?<=3円))^2円((?<=(?=6円?(3円)*(?<=(?=3円$)(x*))).*)x)*)

Try it online!

By the very nature of this solution, its most-golfed form rounds arbitrarily, sometimes up, sometimes down. As such, it's more complicated to explain why it works, so I suggest reading the explanation of the 104 byte always-round-down solution below first. (This is oddly appropriate, given the order of operations in regexes that use right-to-left evaluated variable-length lookbehind.)

Compared to the always-round-down solution, this regex takes a shortcut. Instead of counting the number of times the anti-remainder was subtracted, it uses \$\lfloor{N\over 2}\rfloor\$ in place of that count. For even values of \$N\$ this is \1ドル\$ greater than the actual number of times the anti-remainder was subtracted (since it's never subtracted on the first iteration, and always subtracted on each subsequent iteration). As such, sometimes it doesn't change the resulting returned value \$M\$, but sometimes it results in finding an \$M\$ that is \1ドル\$ greater than the value it would otherwise have, i.e. \$\lceil{N\over\sqrt 2}\rceil\$ instead of \$\lfloor{N\over\sqrt 2}\rfloor\$.

For odd values of \$N\$, adding \1ドル\$ to that count effectively simulates the extra loop iteration done on \$\lfloor{N\over 2}\rfloor\$ in the always-round-down regex. The thing is, without actually doing that, we don't know whether the final value of the anti-remainder was greater than \$\lfloor{N\over 2}\rfloor\$ or not. Iff it was greater, then the anti-remainder subtraction count wouldn't have been incremented by \1ドル\$. Thus, by unconditionally effectively adding that \1ドル\$, we're doing the same thing for odd \$N\$ as we are for even \$N\$ – giving a return value of \$M\$ that is arbitrarily rounded up or down.

 # tail = N = input number
(?=
 (x*) # 1円 = floor(N / 2)
 (1円x?) # 2円 = ceil(N / 2)
)
(x*) # 3円 = guessed value of round(sqrt(N*N/2)) - may be rounded up or down
.*$ # tail = 0; head = N
(?<=
 # head = 0
 (?=
 (?<-5>x)* # head += 5円.capture_count
 1円 # head += 1円; this is 1 more than the actual number of times
 # 6円 was subtracted, which will change the 3円 result for some
 # even values of N from rounded-down to rounded-up. But for
 # odd values of N, it simulates subtracting 6円 from the last
 # half-chunk, which is not covered in the loop we did. Note
 # that depending on the final value of 6,円 it may be <= 1,円
 # in which case we'll get a rounded-down 3,円 or > 1,円 in which
 # case we'll get a rounded-up 3円.
 (?<=3円) # assert head >= 3円
 )
 ^2円 # force the loop below to iterate 1円 times; head = 0
 (
 (?<=
 # tail = N
 (?=
 6円? # tail -= 6,円 if 6円 is set
 (3円)* # X = floor(tail / 3円); tail -= 3円*X; 5円.capture_count += X;
 # note that in practice, 0 <= X <= 1;
 # Y = tail = remainder
 (?<=
 (?=3円$) # assert tail == 3円
 (x*) # 6円 = 3円 - Y
 )
 )
 .* # tail = N
 )
 x # head -= 1; tail += 1
 )*
)

Regex (.NET), 104 bytes

(?=(x*)(1円x?))(x*).*$(?<=(?=(?<-5>x)*(?<-6>x)*(?<=3円))^1円(x(?<=(?=(7円)?(3円)*(?<=(?=3円$)(x*)))(.+2円)?))*)

Try it online!

This solution always rounds down, returning \$M=\lfloor{N\over\sqrt 2}\rfloor\$. It accomplishes this by calculating \$M=\lfloor\sqrt{N^2\over 2}\rfloor\$, which is done by searching for the largest value of \$M\$ for which \$\lfloor{{N^2\over 2}/M}\rfloor\ge M\$. A regex can't directly operate on values larger than the input, so this must be done by looping multiple times over \$N\$ instead of directly operating on \$N^2\$.

For even values of \$N\$ this is straightforward enough; we just loop over \$N/2\$ copies of \$N\$, subtracting \$M\$ from it as many times as will fit (which will be \0ドル\$ or \1ドル\$), taking note of the remainder, and then subtracting the corresponding "anti-remainder" (the remainder's difference from \$M\$) at the beginning of the next loop iteration. Then the value of \$\lfloor{{N^2\over 2}/M}\rfloor\$ is the sum of the number of times \$M\$ was subtracted and the number of times the anti-remainder was subtracted. This works because for even \$N\$, we have \$\lfloor{N^2\over 2}\rfloor = \lfloor{N\over 2}\rfloor N\$.

For odd values of \$N\$, we do the above, but then do \1ドル\$ extra loop iteration, subtracting from \$\lfloor{N\over 2}\rfloor\$ instead of \$N\$. This works because for odd \$N\$, we have \$\lfloor{N^2\over 2}\rfloor = \lfloor{N\over 2}\rfloor N + \lfloor{N\over 2}\rfloor\$.

The number of times \$M\$ and the anti-remainder were subtracted are counted using the .NET feature of balanced groups; these are the (?<-6>x)* and (?<-5>x)* below.

This algorithm would not work on a regex flavor lacking variable-length lookbehind (and lookinto, which no regex engines have yet), because to loop more than once with a count that scales with \$N\$, the regex needs to subtract at least \1ドル\$ from \$tail\$ on each iteration (a zero-width loop iteration would result in terminating the loop). Without lookbehind/lookinto, it would be impossible to operate directly on \$N\$ after the first iteration. And once the current value of \$tail\$ went below the currently tested value of \$M\$, it would no longer be possible to operate on the value of \$M\$ in any way. Thus forward-declared backreferences, while required by this algorithm, aren't enough on their own.

So at this point, I think that a regex flavor with forward-declared backreferences but no variable-length lookbehind (or lookinto) would still not be availed of any shorter algorithm than my ECMAScript solution.

 # tail = N = input number
(?=
 (x*) # 1円 = floor(N / 2)
 (1円x?) # 2円 = ceil(N / 2)
)
(x*) # 3円 = guessed value of floor(sqrt(N*N/2))
.*$ # tail = 0; head = N
(?<=
 # head = 0
 (?=
 (?<-5>x)* # head += 5円.capture_count
 (?<-6>x)* # head += 6円.capture_count
 (?<=3円) # assert head >= 3円
 )
 ^1円 # force the loop below to iterate 2円 times; head = 0
 (
 x # head -= 1; tail += 1
 (?<=
 # tail = 1円 if N is odd and this is the last iteration, or N otherwise
 (?=
 (7円)? # if 7円 is set: tail -= 7円; 5円.capture_count += 1
 (3円)* # X = floor(tail / 3円); tail -= 3円*X; 6円.capture_count += X;
 # note that in practice, 0 <= X <= 1;
 # Y = tail = remainder
 (?<=
 (?=3円$) # assert tail == 3円
 (x*) # 7円 = 3円 - Y
 )
 )
 (.+2円)? # unless N is odd and this is the last iteration: head = 0; tail = N;
 # else: head = 2円; tail = 1円
 )
 )*
)