Readit News logoReadit News
hwayne commented on When would you ever want bubblesort? (2023)   buttondown.com/hillelwayn... · Posted by u/atan2
addaon · 4 days ago
The article, and many of the responses, are hinting at the fact that bubblesort is an example of an anytime algorithm. This is a wide class of algorithms which provide a correct answer after some amount of time, but provide an increasingly good answer in increasing amounts of time short of the completion time. This is a super valuable property for real time systems (and many of the comments about games and animations discuss that). The paper that introduced me to the category is "Anytime Dynamic A*" [0], and I think it's both a good paper and a good algorithm to know.

[0] https://cdn.aaai.org/ICAPS/2005/ICAPS05-027.pdf

hwayne · 4 days ago
Thanks for sharing the general term! I didn't know about it.
hwayne commented on A Early History of Algebraic Data Types   hillelwayne.com/post/algd... · Posted by u/surprisetalk
Rochus · 2 months ago
hwayne · 2 months ago
Now you just gotta go to the first submission and post a link here. Complete the circle!
hwayne commented on A Early History of Algebraic Data Types   hillelwayne.com/post/algd... · Posted by u/surprisetalk
hwayne · 2 months ago
Since writing this I've been informed of some gaps (mostly through email and a lobsters [1] thread). Some of the main ones:

- McCarthy's "Direct Union" is probably conflating "disjoint union" and "direct sum".

- ML probably got the sum/product names from Dana Scott's work. It's unclear if Scott knew of McCarthy's paper or was inspired by it.

- I called ALGOL-68 a "curious dead end" but that's not true: Dennis Ritchie said that he was inspired by 68 when developing C. Also, 68 had exhaustive pattern matching earlier than ML.

- Hoare cites McCarthy in an earlier version of his record paper [2].

Also I kinda mixed up the words for "tagged unions" and "labeled unions". Hope that didn't confuse anybody!

[1] https://lobste.rs/s/ppm44i/very_early_history_algebraic_data...

[2] https://dl.acm.org/doi/10.5555/1061032.1061041

hwayne commented on A dumb introduction to z3   asibahi.github.io/thought... · Posted by u/kfl
joek1301 · 3 months ago
I also was inspired to play around with Z3 after reading a Hillel Wayne article.

I used it to solve the new NYT game, Pips: https://kerrigan.dev/blog/nyt-pips

hwayne · 3 months ago
I love how you create dataclasses to abstract over constraints!
hwayne commented on A dumb introduction to z3   asibahi.github.io/thought... · Posted by u/kfl
mohsen1 · 3 months ago
This was such a pleasure to read! Thank you for sharing!

My understanding is that solvers are like regexes. They can easily get out of hand in runtime complexity. At least this is what I have experienced from iOS's AutoLayout solver

hwayne · 3 months ago
Even worse than that, SMT can encode things like Goldbach's conjecture:

    from z3 import \*

    a, b, c = Ints('a b c')
    x, y = Ints('x y')
    s = Solver()

    s.add(a > 5)
    s.add(a % 2 == 0)
    theorem = Exists([b, c],
                     And(
                         a == b + c,
                         And(
                             Not(Exists([x, y], And(x > 1, y > 1, x \* y == b))),
                             Not(Exists([x, y], And(x > 1, y > 1, x \* y == c))),
                             )
                         )
                     )

    if s.check(Not(theorem)) == sat:
        print(f"Counterexample: {s.model()}")
    else:
        print("Theorem true")

hwayne commented on A dumb introduction to z3   asibahi.github.io/thought... · Posted by u/kfl
ebonnafoux · 3 months ago
Does someone, with some experience on this subject, has an opinion on the best solver with binding in Python for a begginer? The OP use Z3 but also mentionned MiniZinc and I heard about Google OR-Tools.
hwayne · 3 months ago
It really depends on the kind of solving you want to do. Mathematical optimization, as in finding the cheapest/smallest/whatever solution that fits a problem? OR-Tools. Satisfaction problems, like finding counterexamples in rulesets or reverse engineering code? Z3.
hwayne commented on Crimes with Python's Pattern Matching (2022)   hillelwayne.com/post/pyth... · Posted by u/agluszak
orbisvicis · 4 months ago
I've given up on matching as I'm tired of running into its limitations.

That said, I don't think OP's antics are a crime. That SyntaxError though, that might be a crime.

And a class-generating callable class would get around Python caching the results of __subclasshook__.

hwayne · 4 months ago
Now I'm mad I didn't remember the word "antics". It's so much more evocative than "crimes"!
hwayne commented on Motif-Index of Folk-Literature (1958) [pdf]   ia600301.us.archive.org/1... · Posted by u/hwayne
hwayne · 4 months ago
Entertaining collection of Folklore classifications. Some examples:

- T550.6. T550.6. Only half a son is born by queen who ate merely half of mango.

- A1066. A1066. Sun will lock moon in deep ditch in earth's bottom and will eat up stars at end of world.

- K87.1. K87.1. Laughing contest: dead horse winner.

hwayne commented on Fast   catherinejue.com/fast... · Posted by u/gaplong
pjmlp · 4 months ago
Appreciation isn't the same as market share, formal proofs in general are pretty much inexistent in enterprise, unless there are legal requirements to do otherwise.

I fail to see how you validate that TLA+ model is actually correctly mapped into the written Java code.

hwayne · 4 months ago
Main way we're validating that now is by using TLA+ models to generate test suites. Mongo came out with a new paper on this recently: https://will62794.github.io/assets/papers/mdb-txns-modular-v...

u/hwayne

KarmaCake day2872March 21, 2017View Original