[HN Gopher] Bubble sort in pure CSS ___________________________________________________________________ Bubble sort in pure CSS Author : andai Score : 174 points Date : 2023-11-04 22:01 UTC (1 days ago) (HTM) web link (dev.to) (TXT) w3m dump (dev.to) | op00to wrote: | > Editor's Note: This article ends on a cliffhanger. The next | part goes out in a week | | I stopped reading there. | | Let us know when the second part is out. Why write half an | article? | EForEndeavour wrote: | Where does that text appear in the article? | | I learned from the article and found the subject interesting, | but the breathlessly excited tone and forced cuteness were | offputting. | Hamuko wrote: | I think he clicked on the wrong article since https://one- | from-nippon.ghost.io/worlds-first-app-store/ ("The First App | Store") on the front page starts with that. | topato wrote: | I'm glad to know other people are annoyed by this rather | perverse style of writing. I associate it with "web business | guru" / "side-hustle tutorial" / "how I made X amount of | dollars in Y months", and it reeks of ultra thirdh::) xx For | a while, I | op00to wrote: | Oops! Sorry all! | codesnik wrote: | I can't wait for "tone it down" AI button in the next chrome | version. | broken-kebab wrote: | I guess you're on mobile, and your finger landed on a | neighboring article. | globalise83 wrote: | Why release half a product? We should only release when 100% of | the features are completed. | autoexec wrote: | > . Why write half an article? | | Twice the page views? To "drive engagement"? | Jaxan wrote: | It seems to only work for a fixed size. Wouldn't that be called a | sorting network? | pzmarzly wrote: | It is a sorting network corresponding to bubble sort on | 5-element input. | | It is actually pretty good - the code uses 10 comparisons, | while the optimal sorting network for 5 elements uses 9: | https://bertdobbelaere.github.io/sorting_networks.html#N5L9D... | Jaxan wrote: | That's a cool page! Thanks! | pzmarzly wrote: | > (oneIsGreater * origArray[0]) + (twoIsGreater * origArray[1]) | | There is a reason why conjunction (AND) is also called logical | multiplication, and disjunction (OR) logical addition. There is | not much difference between this and: | (oneIsGreater ? origArray[0] : 0) | (twoIsGreater ? origArray[1] | : 0) | | This is often useful to think about when working on bitset or | SIMD algorithms. | thaumasiotes wrote: | > There is a reason why conjunction (AND) is also called | logical multiplication, and disjunction (OR) logical addition. | | Really? The connection between AND and multiplication is | obvious, but disjunction doesn't behave like addition. (For one | thing, just like AND, it destroys information, which | multiplication does do and addition doesn't.) Addition would | usually be XOR. | | In fact, AND and XOR are what you get when you apply | multiplication and addition to the integers (mod 2). | dvt wrote: | It's called _logical addition_ which is different than | arithmetic addition, so it 's best to not conflate the two. | It's called "addition" because you "add" another propostion, | creating a disjunction. And by the rules of logic, as long as | the original proposition was true, the truth value is | preserved no matter how many propositions you introduce (or | "add"). A [?] ((A [?] B) [?] C) ... [?] n | thaumasiotes wrote: | > It's called "addition" because you "add" another | propostion, creating a disjunction. | | By that argument, conjunction is also called "addition". | Perhaps there's a different reason? | | The choice of terminology, contrasting "logical addition" | with "logical multiplication", obviously indicates that | logical addition is supposed to be analogous to addition. | What is the analogy? | andai wrote: | I don't know if this relates to formal logic, but in C a | true value is defined as not zero, so all nonzero values | are treated as the same value. So the only way to get a | false is to OR (or add) two zeroes, making the two | operations equivalent as far as boolean logic goes. | | Actually, you can add 1 and -1 to get 0, which breaks the | model... Hmm... Guess it only works on natural numbers / | unsigned. | EGreg wrote: | The analogy is deep. But actually the relationship is as | follows: | | P(A u B) = P(A) + P(B) - P(A^B) | | P(A ^ B) = P(A u B) - P(A) - P(B) | | And to the guy who said xor is addition -- no it's not: | | P(A xor B) = P(A) + P(B) - 2 * P(A^B) | | In Probability, when you have a space of outcomes, doing | a Union on two disjoint events (sets of outcomes) the | probabilities add. Whereas doing an Intersection on two | non-disjoint events those probabilities multiply. If two | events have no outcomes in common, for instance, the | probability of them both occurring is zero. | | When you "condition" probability on an event X happening, | you restrict the space of all outcomes to that set X, and | intersect every event with it. | | When you condiition B[n] = A[n] given that (A[n-1] AND | ... A[1]) having already happened, you have a sales | funnel and each step is independent of the previous, so | the probabilities multiply. | | It is also called a Markov Chain if you have a discrete | set of possibilities at each step so you can form a | matrix. | cubefox wrote: | Interesting, I never saw the arithmetic probability | formula for xor. | | Though the original topic was truth values, not | probabilities. To make it short, conjunctions in | probability are multiplicative when they are independent, | and disjunctions in probability are additive when they | are mutually exclusive. | EGreg wrote: | Well I actually came up with it on the spot. Just think | of the venn diagram, and add the areas of A and B, which | counts A^B twice, and then just remove it twice. :) | dvt wrote: | > By that argument, conjunction is also called | "addition". Perhaps there's a different reason? | | A chain of (arbitrary) conjunctions is not necessarily | implied by the first proposition, so we have the much | less interesting: A [?] ((A [?] B) [?] | C) ... [?] n | cubefox wrote: | > By that argument, conjunction is also called | "addition". | | Yeah, I just noticed: | | a and b = a + b - (a or b) | | Or with probability | | P(a and b) = P(a) + P(b) - P(a or b) | moritzwarhier wrote: | Is there a way to express OR (not XOR) using integer | arithmetic without case distinction or special functions in | the natural numbers mod 2? | | Meaning, using only elementary arithmetic and modulo? | | Seems like there should be either an obvious answer or an | interesting one :) | 201p wrote: | The maximum function. | moritzwarhier wrote: | Yeah that makes sense of course. Should have specified | "special function", was aiming at "algebraic" or | "polynomial" I guess. | | Then the answer seems to be no, right? | | Edit: The abs() function seems to be enough, awesome: | | https://math.stackexchange.com/a/1641271 | adrian_b wrote: | The abs function works because it is equal to the maximum | of x and -x. | | The logical "and" and logical "or" functions are | precisely particular cases of the minimum and maximum | functions. | | The so-called "exclusive or" function is simultaneously a | particular case of addition and of subtraction, i.e. | addition modulo 2 and subtraction modulo 2 are the same | function. Therefore applying the 4 functions minimum, | maximum, addition and subtraction to 1-bit numbers | produces only 3 functions, AND, OR and XOR. | | It makes no sense to search other functions for | expressing logical "and" and logical "or" except for | minimum and maximum, because this is what they are. The | search could only find alternative more complicated ways | to express minimum and maximum. | | The minimum and maximum functions also work in logic | systems with more than 2 values of truth. Also in | hardware, analog circuits for minimum and maximum are one | of the 2 ways of implementing the logical "and" and "or" | functions, the other way being with series and parallel | connections. | | The main mistake of George Boole was his unsuccessful | attempt to find an equivalence between logical "and" and | "or" and integer multiplication and addition, because he | was not habituated to use minimum and maximum, so he did | not see the correct relationships. | | The functions maximum and minimum are arithmetic | functions as important as addition and subtraction. The | only reason for which they have not been counted among | the basic arithmetic functions is because when computed | by a human they required much less effort than even | addition, so there was no need for a long training of how | to do computations with them, like for the more complex | arithmetic functions. | | Most modern instruction-set architectures now include | maximum and minimum instructions, together with the | addition and subtraction instructions. | moritzwarhier wrote: | That makes sense, thank you for your great reply. | | As someone without much mathematical ropes, this might | also be related to non-integer algebra and the | distinction of "smooth" (edit: or differentiable) and | discontinuous functions, no? | | > The functions maximum and minimum are arithmetic | functions as important as addition and subtraction. The | only reason for which they have not been counted among | the basic arithmetic functions is because when computed | by a human they required much less effort than even | addition | adrian_b wrote: | As I have mentioned, in the logic systems with 3 or more | discrete values of truth (e.g. false, unknown and true, | or false, unlikely, unknown, likely and true) and also in | the logic systems with a continuous range of truth values | (e.g. those based on probabilities), to the base logic | functions AND, OR and NOT, correspond the base logic | functions minimum, maximum and inversion a.k.a. | reflection functions (the last may be e.g. integer | negation when the truth values are symmetric around zero, | or it may be e.g. 1-x when the truth values are between 0 | and 1). | | A set with minimum and maximum operations has a special | algebraic structure named distributive lattice, which is | a structure as useful and frequently encountered as | structures like the algebraic groups and rings that | characterize addition-like and multiplication-like | operations. | cubefox wrote: | It's interesting that maximum/minimum for | disjunction/conjunction doesn't apply for probabilities, | except when the probabilities "overlap as much as | possible" (when at least one implies the other). | | And when the probabilities overlap as little as possible, | then the formulas are: | | P(a or b) = min(1, P(A)+P(B)) | | P(a and b) = max(0, P(a)+P(b)-1) | | I guess there is some lesson about logic and truth here, | but I can't quite see it... | skrebbel wrote: | I really enjoyed reading this comment, thanks. I love the | reason why min/max aren't thought of as basic arithmetic | building blocks (they're too easy), it makes so much | sense now you put it that way. | thaumasiotes wrote: | The maximum function isn't elementary arithmetic or | modulo. You can define it as a limit, but people are | unlikely to be convinced that that's a simple, elementary | function. | adrian_b wrote: | By the sense of the word "elementary", the maximum and | minimum functions are exactly as elementary as addition | and subtraction. | | Most textbooks define a set of elementary functions which | does not include maximum and minimum only because they | use "elementary" as an abbreviation for "elementary and | differentiable", and they do not bother to explain this | to the students. | xigoi wrote: | a + b + a * b | moritzwarhier wrote: | This is the obvious solution I was looking for. Thanks! | (and I rightfully feel stupid now) | cubefox wrote: | The formula is slightly wrong though. This is the right | one: | | a or b = a + b - (a * b) | | The last term is equivalent to a conjunction. Which also | makes sense when you think of probability: | | P(a or b) = P(a) + P(b) - P(a and b) | moritzwarhier wrote: | Awesome, thanks! | | For the mod 2 addition, the sign makes no difference I | guess, but this cross-link makes the negative sign much | more convincing | xigoi wrote: | True, but in modulo 2, + and - are the same. I chose the | + to keep the formula simple. | layer8 wrote: | OR still forms a semiring with AND, and that semiring | operation is still called addition. OR is also like addition | in saturation arithmetics. In those senses, it's an additive | operation, and it is indeed called logical addition: | | https://en.wikipedia.org/wiki/Logical_disjunction | | https://mathworld.wolfram.com/deMorgansDualityLaw.html | pzmarzly wrote: | Posting update since it's too late to edit: I confused | multiplication with maximum. It's been too long since I took a | course in formal logic. Though for binary values, | multiplication works as well. | tutfbhuf wrote: | That's cool, but it's expected since CSS is Turing complete as | long as you consider an appropriate accompanying HTML file and | user interactions to be part of the execution. | ourmandave wrote: | _As I said, not a tutorial. But I did want to introduce some | interesting CSS "switches" and "booleans" that may become useful | in some strange scenario in the future for you!_ | JaDogg wrote: | This is scary good. Well done. If your product have any frontend | and you have the power to decide ensure at least one of your | hires can write CSS at this level. | karaterobot wrote: | This is a fun proof of concept, but it isn't what CSS is used | for. There's no conceivable reason you'd do this in practice. | JaDogg wrote: | Those you know it well can abuse it in a fun way. Probably | not useful in practice. Nevertheless this proves talent of | the one who wrote it. | karaterobot wrote: | A better test for someone using CSS would be activities | that CSS is typically used for. Have them make a complex | layout that is responsive at multiple display sizes, or | have them architect a set of reusable classes for a design | library or something. You may think that this sort of | cleverness is generalizable: that someone who would come up | with this solution would also be good at laying out web | components. But there is no relationship between this (very | neat) trick and CSS skills, so it would be a terrible test | to give people. | JaDogg wrote: | Fair enough. | micromacrofoot wrote: | If someone asked me to write CSS at this level for an interview | I'd probably question the job, because if you have to write CSS | at this level for work something is horribly wrong. | schemescape wrote: | Despite the pressure to constantly hustle, it's still ok to | take a job just because it sounds fun*. | | *Obviously, abusing CSS isn't everyone's idea of fun. | JaDogg wrote: | Fair enough, however it is better to hire few frontend | specalists rather than depending on fullstack/backend people | to do the frontend. | vore wrote: | I think it would be a waste of time if they could because it is | both extremely inefficient and has nothing to do with actual | frontend skills. | yedava wrote: | When you get an idea like "I'm going to X with Y, where Y is | not designed to do X", it probably takes several hours or a | couple of days to implement it. Are you going to let your hire | take that much time? And more importantly, are you going to pay | the hire for that time, regardless of whether they succeed in | doing it? | EMM_386 wrote: | > This is scary good. Well done. If your product have any | frontend and you have the power to decide ensure at least one | of your hires can write CSS at this level. | | I'm having trouble determening as written if this is a joke or | not. | | If anyone looked at this and thought something along the lines | of "wow, think of the possibilities", I would would ask only | that they don't put more thought into it. Other thoughts could | bring pain ... to the browser that has to run it, the user | staring at the page as the fans spin up, and the developer who | has the pleasure to work with it next. | | This was clearly one of those interesting-yet-useless things | that was worth a read. | stylepoints wrote: | Could've used flex weights instead of hardcoding the heights. | andai wrote: | See also the sequel: pure CSS neural network! | | https://news.ycombinator.com/item?id=38151018 | hoosieree wrote: | 2026: npm in pure css | adrianmonk wrote: | > _and add visualisations to it_ | | Might I suggest a different animation. The current one swaps two | elements (bars) by vertically shrinking the taller bar and | growing the shorter one. Instead, the bars should stay the same | height but move horizontally. I would rather see values move than | slots in the array morph to the new value they should hold. The | current animation feels like you are pumping water from one tank | to another. | SonOfLilit wrote: | The visualization you're suggesting would be orders of | magnitude harder to create, since this one visualizes what | actually happens in his algorithm and the better one would | require an algorithm that tracks more things. | appplication wrote: | The current one also broke in my case (mobile safari). The | three smallest bars just sort of disappeared right before the | last swap. | sentientslug wrote: | It's noted on the page right above the visualization that it | doesn't work on mobile | omneity wrote: | Since the steps are hardcoded in the CSS, this would better be | named "Bubble sort _visualization_ in pure CSS ". I don't know | what I was expecting honestly, but seeing all the sorting steps | in the stylesheet wasn't it. | | Pretty cool trick nevertheless, well done to the author! | The_Colonel wrote: | Tangential, but this brought me to | https://en.wikipedia.org/wiki/Bogosort, and I love a sorting | algorithm "Miraclesort": | | > A sorting algorithm that checks if the array is sorted until a | miracle occurs. It continually checks the array until it is | sorted, never changing the order of the array. | | It basically waits for god intervention / single event upset. It | is guaranteed to be optimal in at least one quantum universe, | though. ___________________________________________________________________ (page generated 2023-11-05 23:00 UTC)