User m90 | chat.stackexchange.com

m90

Mar 19 10:25

@Simd I think it's for d in l: combined_dict.update(d); d.clear()

m90

Jan 28 08:54

@RubenVerg U+2571 and U+2572 could work (appearance depends on the font, of course).

m90

Jan 20 15:50

Yes.
Emulate an arbitrary [tag system](https://en.wikipedia.org/wiki/Tag_system).
The symbols are represented by binary strings all of the same length that begin with 1, end with 0, and contain exactly one other 1.
Then the main loop can be [[option0][option1][option2]... [][][]...] -- the outer loop consumes the first 1 of a symbol, then the rest of the symbol is used to select an option, and then the empty loops discard some constant number of symbols.
The halting symbol is represented by 0.
There's some uncertainty about edge cases -- you haven't specified what happens when popping from …

m90

Nov 20, 2024 10:33

However, it relies on PEXT and PDEP to carry information from the top to the bottom of a run of 1s, which might be a problem for SIMDifying it.

m90

Nov 20, 2024 10:33

@DanielT I have this solution: tio.run/…

m90

Oct 2, 2024 11:05

Yes. ([Try it online!](https://tio.run/##bVC7asMwFN39FQe6yGCKQ7dCyNwhHbJ0EKKo8XUtk1wJWU7ar3clJ360VNxF53kl9x0ay0/DUFGNWuzz5ww4YAuv@ZPEiThiecScp4uxfRcpKRVq6/EOwzgoPOCtMcdmkXh77dDoC2EDHRAa00VpRV@7GJScZnSmKuCsw7GhMffVMv1JfmFc/w3voGP6BxFHR89VlJGn2EU49t4Th6SEPnV2Uu/GvpTfrvoBU2MvjZKtmpCbyiXV1PuLHT33xaVTiO9jG5D2X4sAT6H3DCFcAZMXEIupQDt@7HRWcVu0M7Hqf9TOEVfC5IPzhoOohcxkWSDO5jaqyORmuiXmDpTTjIpyphdgzihVpvJ8@AE "Python 3 – Try It Online"))
`def f(M):`
` R = range(len(M))`
` previous = [[] for _ in R] # Which previous rows have 1 at this index?`

m90

May 15, 2024 10:14

@l4m2 Yes: (19, 0) and (10, 9) both produce 19190 (found by a quick brute-force search).

m90

Mar 26, 2024 15:08

@Simd It looks like that code is actually doing almost the same thing as the Fenwick tree! (The differences are that the tree is irregular and the midpoints are handled specially.)

m90

Mar 26, 2024 12:03

@Simd I don't see how that would work. If you have a method in mind, could you elaborate?

m90

Mar 25, 2024 19:55

@Simd I did some of those back in secondary school, but less often after that (and now even less, now that Google ended theirs).

m90

Mar 25, 2024 19:45

@Simd First, replace the floating point coordinates with consecutive integers by sorting and renumbering. Then, go through the points in order of increasing x, and increasing y for equal x. Maintain a Fenwick tree holding, for each value of y, the total weight of points processed so far with that y value; then each point's answer is obtained with one query to the Fenwick tree. The time complexity is n log(n).

m90

Mar 13, 2024 20:28

@Simd No: for example, (7, 1) and (5, 5) have the same sum of squares.

m90

Feb 24, 2024 16:10

@RubenVerg There are 7! ways to assign pairs of numbers to pairs of opposite faces, then 2⁷ ways to split up all the pairs. This shape has the same group of rotational symmetries as the cube, which is S₄, which has order 24. Thus the number of rotationally-distinct assignments is 7!*2⁷/24 = 26880. (The second question has the same answer, because all seven opposite sums must add up to the sum of all the numbers, thus if they are equal, they can only be 15.)

m90

Feb 24, 2024 15:25

Unfortunately not. (Did you have something in mind?)

m90

Feb 24, 2024 14:41

@Simd x+7>>3

m90

Jan 28, 2024 10:03

@vakvakvak The default numpy arrays already do that. ato.pxeger.com/…

m90

Jan 17, 2024 19:21

(I also modified the history mechanism to not get inefficient as the number increases further.)

m90

Jan 17, 2024 19:21

@Simd Yes, with just a few changes: tio.run/##dVHtbsIwDPydPIWl/…

m90

Jan 14, 2024 17:20

@Simd I think that's probably just because it's hard to figure out how to solve it efficiently.

m90

Jan 14, 2024 17:17

@Simd I don't see any obvious problems. Is there any part in particular that you were concerned about?

m90

Jan 14, 2024 16:40

Yes.
Think of it as placing four boundaries, each of which toggles whether or not numbers are being added.
This gives a DP over (position, no. of boundaries placed).
Here's a program that does it:
https://tio.run/##XZHdbsMgDIWvk6ewtJtkNVN@m2hbnwRxkTV0ReqgAjq1T5/ZpOukiUTEPt/BB@V8i0dn22WZ9QGCO33rYipf8@xDhwg7kLJCoFc9WwUH58GCseAn@6mLvlR59gRF2DuvEY4mROdv5RsRs76S2boXcAf4cBc7T97oAOfTtNdznvFJBuHKh2l7@dJ@ivfB2WOKrBFaxa2URlolKwWbHVz/Uw2BCN3KGpr4h7/fC1FzmYAsUFiK9xBS8@7hOyd9A9JsakWi1/Hi7Yp3Ks95dKRiPwWdEuSyRV5iTFurMJeixRFFjRUt0WOPzfrZUMV6jUSIAUXHVJeEAeuHJdk7HJgdyc5tsWWmIbpijp4t@3occCSOb3f2xsZi/Y@/GctyWX4A

m90

Oct 21, 2023 07:44

@l4m2 Well, then you're depending on the implementation of that rand function, and I believe those typically do have unbounded worst-case time (here's one example: github.com/python/cpython/blob/main/Lib/random.py#L252])

m90

Oct 21, 2023 07:37

I think that's technically impossible, because even generating a single uniformly-distributed random number in a range of arbitrary size has unbounded worst-case time.

If you can accept a small difference from the correct probabilities, then it becomes possible.

Start with all the numbers, then repeatedly: take a random one, remove it, and move the last one into its place (so that they remain contiguous).

To avoid the O(n) initialization, there are several options (the best option depends on how you'll be using this):

m90

Oct 14, 2023 15:01

@Simd Yes, since C++20: std::bit_width (found from the duplicate question from your link)

m90

Sep 6, 2023 06:14

@RydwolfPrograms (x + 1) | 1 (I have used this before)

m90

Mar 8, 2023 09:37

@mousetail ...except when a=-1, where it becomes a closed square path.

m90

Feb 22, 2023 18:08

@Simd It can actually be done using bisect in version 3.10 or greater (for the key parameter), with some tricks: ato.pxeger.com/…

m90

Feb 22, 2023 17:59

@mathcat Starting from (a²+b²)-(c²+d²), rearrange to (a²-c²)+(b²-d²). Then notice that setting a=c+1 can produce all odd values for a²-c², and find two suitable choices for b and d to cover everything.

m90

Feb 22, 2023 17:43

All of them!
(n+1)²+1²-n²-4² = 2n-14 (valid for n≥5) gives the evens.
(n+1)²+1²-n²-5² = 2n-23 (valid for n≥6) gives the odds.

m90

Feb 11, 2023 07:46

@l4m2 It cannot be used as the base register (in the SIB byte) with no displacement (because that was repurposed to specify disp32 without base). Also, there are some instructions that use it specifically (I'm not sure whether this counts as a special property).

m90

Jan 20, 2023 12:13

@lyxal Spelling error: "simplier"

m90

Jan 14, 2023 10:42

@mousetail Yes, that would make it O(n log n).

m90

Jan 14, 2023 10:39

@mousetail Then, reaching a given position takes time linear to the distance moved, and the overall time complexity is still quadratic.

m90

Jan 14, 2023 10:37

@mousetail No, because moving the already-placed elements to open up a space for the new one takes up to linear time, and is done n times.

m90

Nov 12, 2022 10:37

@mousetail JavaScript, 40 bytes: b=>((l=~-b)**3n+b*b)*b**~-l/l/l-(b/l|1n) (takes a BigInt) -- Try it online!

m90

Oct 10, 2022 16:05

The outer parentheses can also be removed.

m90

Sep 21, 2022 11:54

Hi.

m90

Sep 9, 2022 07:22

@Neil Python 3, 76 bytes: lambda n,h,w:(f'|{"":{w}}|\n'*h).join(['+'+w*'-'+'+\n']*2).join(['|\n'*n]*2) -- Try it online!

m90

Aug 22, 2022 12:37

@null Indeed; simultaneously rotate two parallel lines around the two sets: i.sstatic.net/bRMjr.png

m90

Aug 13, 2022 17:58

@NoHaxJustRadvylf I think so.

m90

Jul 31, 2022 08:11

@graffe heapq.nlargest can do exactly that.

m90

Jul 27, 2022 14:35

@thejonymyster If the parentheses aren't nested: to find xyz outside parentheses, use ^([^(]|\([^)]*\))*xyz.

m90

Jul 26, 2022 17:14

Indeed, it has already been asked: codegolf.stackexchange.com/questions/95035/natural-construction

m90

Jul 21, 2022 14:48

@Seggan How about replacing the semicolon with the comma operator?

m90

Jul 20, 2022 16:59

A 1-short-of-optimal triplet of the second form using less-obscure words: allele, sills, excesses

m90

Jul 20, 2022 16:59

An optimal triplet of the second form (each pair using a different letter): lessees, stats, tetter

m90

Jul 20, 2022 15:55

I think it is indeed optimal. Proof:
If two pairs use the same letter, that's at least 7 of that letter, 5 of the letter for the remaining pair, then all 3 words need 2 more letters, for 18.
If all three pairs use different letters, that's 5*3, and then each word needs 1 more letter, for a total of 18 again.

m90

Jul 20, 2022 15:47

3 satisfying "exactly twice": levee, presses, sensed

m90

Jul 20, 2022 15:44

@thejonymyster levee, emcee, tree

m90

The Nineteenth Byte

The Tarpit