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.

 # 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円
 )
 )*
)

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, a regex flavor with forward-declared backreferences but no variable-length lookbehind (or lookinto) could probably use an algorithm based on this one, but additional tricks would have to be used to emulate operating on larger numbers. I'm pretty sure it would not have to use the full-fledged algorithm of my ECMAScript solution, but I haven't worked out the details yet.