Regex (.NET), 90 bytes
(?=(x*)(1円x?))(x*).*$(?<=(?=(?<-5>x)*1円(?<=3円))^2円((?<=(?=6円?(3円)*(?<=(?=3円$)(x*))).*)x)*)
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円)?))*)
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円
)
)*
)
- 12.9k
- 2
- 71
- 55