[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)