Regex (.NET), (削除) 106 (削除ここまで) 90 bytes
(?=(x*)(1円x?))(x*).*$(?<=(?=(?<-5>x)*1円(?<=3円))^2円((?<=(?=6円?(3円)*(?<=(?=3円$)(x*))).*)x)*)
Takes its input in unary, as a sequence of x characters whose length represents the number. Returns its output in group 3円.
By the very nature of this solution, its best-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), (削除) 166 (削除ここまで) 104 bytes
(?=(x*)(1円x?))(x*).*$(?<=(?=(?<-5>x)*(?<-6>x)*(?<=3円))^1円(x(?<=(?=(7円)?(3円)*(?<=(?=3円$)(x*)))(.+2円)?))*)
Takes its input in unary, as a sequence of x characters whose length represents the number. Returns its output in group 3円.
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), 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.
Regex (PCRE+(?^=)), 81 bytes
(?=(x*)(1円x?))(x*)(?^1=(x(?^=8円?(3円(?^=(6円?x)))*(x*)(?^3=7円(x*))))*)(?^3!6円?+1円x)
This is a port of the 90 byte .NET regex that rounds arbitrarily. It uses features available in PCRE, in addition to lookinto, a feature just added to RegexMathEngine. The fact that even after converting the use of .NET balancing groups to group-building, this regex is still 9 bytes smaller than the .NET version, demonstrates just how much expressibility is available with lookinto. The regex is also much easier understand in this form. (Lookinto is equal in power to variable-length lookbehind, i.e. there's nothing one can do that the other can't.)
# tail = N = input number
(?=
(x*) # 1円 = floor(N / 2)
(1円x?) # 2円 = ceil(N / 2)
)
(x*) # 3円 = guess for round(sqrt(N*N/2)) - may be rounded up or down
(?^1= # Lookinto: tail = 1円
(
x # tail -= 1
(?^= # Atomic lookinto: tail = N
8円? # tail -= 8,円 if 8円 is set
# X = floor(tail / 3円); tail -= 3円*X; 6円 += X;
# Note that in practice, 0 ≤ X ≤ 1
(
3円 # Assert tail ≥ 3円; tail -= 3円
(?^=
( # 6円 = sum of the following:
6円? # previous value of 6円 if set, 0 otherwise
x # 1
)
)
)* # Match the above as many times as possible, minimum 0
(x*) # 7円 = tail = remainder = dividend % 3円
(?^3= # Atomic lookinto: tail = 3円
7円 # tail -= 7円
(x*) # 8円 = tail == 3円 - 7円
)
)
)* # Iterate as many times as possible, which will be exactly 1円
)
(?^3! # Negative lookinto: tail = 3円
# Assert tail ≤ 6円 + 1円 (outside the negative lookinto), by asserting here
# that tail ≥ 6円 + 1円 + 1.
6円?+ # Take advantage of the fact that it is guaranteed 6円 ≤ 3,円
# meaning we don't have to use "(?(6)6円)".
1円x
# Note that 6円 + 1円 is 1 more than the actual number of times 8円 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 8円 from the last half-chunk, which is not covered in the loop
# we did. Note that depending on the final value of 8,円 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円.
)
Regex (PCRE+(?^=)), (削除) 123 (削除ここまで) 114 bytes
(?=(x*)(1円x?))(x*)(?^=((?=(2円$)|)x(?^=5円?((?=(7円?x))11円)?((?=(9円?x))3円)*(x*)(?^3=10円(x*))))*1円)(?^3!7円?+(?(9)9円)x)
This is a port of the 104 byte .NET regex that rounds down. Here, with the need to keep two running tallies instead of just one, it loses again over the .NET version, coming out 10 bytes longer. But there's probably at least one more lookinto-using golf optimization that can be done.
# tail = N = input number
(?=
(x*) # 1円 = floor(N / 2)
(1円x?) # 2円 = ceil(N / 2)
)
(x*) # 3円 = guess for round(sqrt(N*N/2)) - may be rounded up or down
(?^= # Atomic lookinto: tail = N
(
(?=(2円$)|) # 5円 = 2円 if tail == 2,円 unset otherwise
x # tail -= 1
(?^= # Atomic lookinto: tail = N
5円? # if N is odd and this is the last iteration: tail = 1円
# if 11円 is set: tail -= 11円; 7円 += 1
(
(?=
( # 7円 = sum of the following:
7円? # previous value of 7円 if set, 0 otherwise
x # 1
)
)
11円
)?
# X = floor(tail / 3円); tail -= 3円*X; 9円 += X;
# Note that in practice, 0 ≤ X ≤ 1
(
(?=
( # 9円 = sum of the following:
9円? # previous value of 9円 if set, 0 otherwise
x # 1
)
)
3円 # Assert tail ≥ 3円; tail -= 3円
)* # Match the above as many times as possible, minimum 0
(x*) # 10円 = tail = remainder = dividend % 3円
(?^3= # Atomic lookinto: tail = 3円
10円 # tail -= 10円
(x*) # 11円 = tail == 3円 - 10円
)
)
)*
1円 # Assert tail >= 1,円 forcing the loop above to iterate 2円 times
)
(?^3! # Negative lookinto: tail = 3円
# Assert tail ≤ 7円 + 9円 (outside the negative lookinto), by asserting here
# that tail ≥ 7円 + 9円 + 1.
7円?+ # Take advantage of the fact that it is guaranteed 7円 ≤ 3,円
# meaning we don't have to use "(?(7)7円)".
(?(9)9円)x
)
- 12.9k
- 2
- 71
- 55