Hvv's recent activity
-
Comment on California lets residents opt-out of a ton of data collection on the web in ~tech
-
California lets residents opt-out of a ton of data collection on the web
22 votes -
Comment on Rupert's snub cube and other math holes in ~comp
Hvv LinkI'm slightly surprised that Tom would sink time into something as practical(?) as an open math problem, but as someone who has seen things like square packings and thought "hey I could probably...I'm slightly surprised that Tom would sink time into something as practical(?) as an open math problem, but as someone who has seen things like square packings and thought "hey I could probably write a crappy optimizer and improve some obscure case" I can attest to the black hole-like nature of problems like these.
Spoilers(? is there a plot to be spoiled here?)
Having independently learned about the Noperthedron before this video, once I realized this was about Rupert's property I was anticipating that Tom would reveal that he was somehow involved in the paper and even double-checked to see whether he was one of the authors. Nope, turns out the timing was because he was as surprised by this paper as I was.
-
Comment on pass: the standard u̴n̴i̴x̴ Bash password manager in ~comp
Hvv LinkHey I used to use this! There’s a whole technical critique out there on why this might not be the best password manager choice, but for me it boiled down to losing track of my entries after a...Hey I used to use this!
There’s a whole technical critique out there on why this might not be the best password manager choice, but for me it boiled down to losing track of my entries after a while because I was too stubborn/paranoid to name the password files descriptively (the passwords are encrypted but the names are plaintext) and because I sometimes forgot to record what account corresponded to what password. You can put multiline entries into the password field but I ultimately decided on another password manager with more metadata handling and search tooling.
-
Comment on Donation drive: Lambda Legal in ~lgbt
Hvv LinkThank you for letting me know about this. I’m in for $125 with a 100% employer match for a total of $250.Thank you for letting me know about this. I’m in for $125 with a 100% employer match for a total of $250.
-
Comment on What are you reading these days? in ~books
Hvv LinkI’m starting to read The Plague by Albert Camus (the English translation by Laura Morris). I was inspired to get the book after rewatching this YouTube video (just be aware that it has sad vibes)...I’m starting to read The Plague by Albert Camus (the English translation by Laura Morris). I was inspired to get the book after rewatching this YouTube video (just be aware that it has sad vibes) in November due to some things happening at the time that reminded me of those themes.
While at the bookstore I also got The Lathe of Heaven by Ursula K. LeGuin. I read the Left Hand of Darkness earlier and enjoyed it, though I'm basically going into this one blind.
-
Comment on Tildes Video Thread in ~misc
Hvv Linkhow many Super Mario games are there NOW? Quite a long video but also an entertaining exploration of the public perception of video games and particularly Super Mario games, all stemming from the...how many Super Mario games are there NOW?
Quite a long video but also an entertaining exploration of the public perception of video games and particularly Super Mario games, all stemming from the fact that “Super Mario game” is not actually well defined.
-
Comment on Carbon offsets and the Nebula show "Jet Lag" in ~enviro
Hvv Link ParentYou may be thinking about @tvl (per this comment, which I have just noticed is replying to you), though they haven’t been active here in a long time.You may be thinking about @tvl (per this comment, which I have just noticed is replying to you), though they haven’t been active here in a long time.
-
Comment on US DOJ sues Visa, alleges the card issuer monopolizes debit card markets in ~finance
Hvv LinkFollows up on https://tild.es/1j0r. US DOJ announcement here: https://www.justice.gov/opa/pr/justice-department-sues-visa-monopolizing-debit-markets I’m quite surprised it progressed so soon, but...Follows up on https://tild.es/1j0r.
US DOJ announcement here:
https://www.justice.gov/opa/pr/justice-department-sues-visa-monopolizing-debit-markets
I’m quite surprised it progressed so soon, but the DOJ was most certainly prepping for a while and likely let it slip just before it actually went through with things.
-
US DOJ sues Visa, alleges the card issuer monopolizes debit card markets
39 votes -
Comment on Are DAOs still a thing? in ~tech
Hvv LinkEh, not really? They're not all that structurally sound and generally boil down to "an organization with a computer". (Pre-script note: The points are my own, but the examples are sourced from...- Exemplary
Eh, not really?
They're not all that structurally sound and generally boil down to "an organization with a computer".
(Pre-script note: The points are my own, but the examples are sourced from Molly White and her resource https://www.web3isgoinggreat.com, which is dedicated to recording the outcomes of cryptocurrency projects and showing where they haven't lived up to the hype.)
Every organization needs to figure out how decisions are made. Member-created proposals and member voting is a quite obvious structure, and one that has been battle-tested by many organizations. However, DAOs must contend with a new issue due to their decentralized structure: Who is a member? What counts as a "vote"? You can't just count up people (or wallets), because making a wallet is free, and someone could just make 1000 wallets to 1000x their representation. To solve this, DAOs usually associate votes with a cryptocurrency token, so that to get voting power, one must purchase said token. This fixes both problems at once: A member is a token holder, and a token is a vote. Who cares how many wallets are involved? The money spent on the tokens is the same.
An immediate side effect of this is that more token ownership confers more voting power for a single person. Putting aside (strong) ideological objections, this lends itself to power concentration and the constant threat of hostile takeover from any party with great financial resources.
This has recently happened to the "Compound" protocol, whose DAO was ordered to move 24 million USD to a new protocol that just happened to be under the proposers' control:
https://decrypt.co/242095/compound-finance-proposal-passes-concerns-over-governance-attack
That hostile party can also be the devs, who may decide that the DAO's money simply belongs to them, as is what happened to the DAO governing the Sushiswap cryptocurrency exchange:
https://decrypt.co/225431/sushiswap-community-cries-foul-over-vote
But this is still dealing with the idea of governance. There's another, much simpler technical issue for DAOs:
If code is law, bugs and malware are also law.
A core principle of Web3 is that decisions are made by code. Following this principle, DAOs are made of code, and their laws must be written as code. However, any developer will tell you that all code has bugs, and most will also suggest that running an untrusted stranger's code on your computer is a very bad idea.
In the real world we have courts (and general human logical fuzziness) to help decide what the deal is when the law says something funny, so adding a clause saying "oh and also give me all the money in this institution" wouldn't pass anyone's smell test and get struck down as soon as somebody notices. However, an equivalent clause in a DAO governance proposal (or in the DAO itself) can be obfuscated in any number of ways, and a computer isn't going to tell you whether that code is bad.
A malicious proposal can get passed, as has happened to the Tornado Cash cryptocurrency tumbler which surreptitiously added functions to leak or steal deposited cryptocurrency:
Or the DAO could have a flaw that lets a hacker drain its funds without needing to interact with governance at all, as was the case for one of the original DAOs, aptly named "The DAO":
https://en.wikipedia.org/wiki/The_DAO
As an aside, this hack was so catastrophic that it literally split the Ethereum blockchain in two, but that's a story for another time.
I could continue, but all of this is just jargon to deal with computers. And that is the biggest issue with DAOs:
Code on its own can only flip bits. As soon as you need to enact the will of a DAO in the real world, you encounter all the same issues that a regular organization would.
A DAO runs a cryptocurrency exchange. What happens when it gets sued by the CFTC?
https://decrypt.co/110407/cftc-ooki-dao-bzx-lawsuit-legal-questions-defi
A DAO tries to crowdfund for Julian Assange. What happens when the money gets mismanaged?
A DAO pools people's money to buy a Dune artifact and start their own Dune-inspired animated series. What happens when it wins the auction... and realizes copyright doesn't work that way?
A DAO can decide how to react and how to move forward, but then what distinguishes it from any other decision making body? At that point, it's basically just an organization with a computer.
-
Comment on Inside the "three billion people" National Public Data breach in ~tech
Hvv Link ParentI know that every opt-out service comes packaged with discourse on whether it’s actually productive, but there’s a pretty substantive case to be wary of Onerep specifically, since its CEO is also...I know that every opt-out service comes packaged with discourse on whether it’s actually productive, but there’s a pretty substantive case to be wary of Onerep specifically, since its CEO is also the founder of several people search companies which expose personal information.
In terms of alternatives, the particularly privacy minded/paranoid tend to favor a DIY approach, which has the additional benefit of being free, though it is a MASSIVE time sink.
The “gold standard” for this approach is the Extreme Privacy opt-out workbook
though I’ve also seen shorter lists for the less paranoid such as here:
https://github.com/yaelwrites/Big-Ass-Data-Broker-Opt-Out-List?tab=readme-ov-file
Which also has a Consumer Reports on opt out services report on other opt out services if you didn’t want to go through that list yourself.
-
Comment on Twiddler: Configurability for me, but not for thee. (From the coiner of "enshittification") in ~tech
Hvv Link ParentJust taking this essay as an example, here is the link to it on his site. If you're curious, there's also an Indieweb wiki page (I think this is where the term originated?) that goes over the idea...Just taking this essay as an example, here is the link to it on his site.
If you're curious, there's also an Indieweb wiki page (I think this is where the term originated?) that goes over the idea in more detail.
-
Comment on On the XZ Utils backdoor (CVE-2024-3094): FOSS delivered on its pitfalls and strengths in ~comp
Hvv Link ParentJust a heads up, your link goes to localhost (did you mean this list?).Just a heads up, your link goes to localhost (did you mean this list?).
-
Comment on A quick post on Chen’s algorithm in ~comp
Hvv LinkLooks like the author has reported a bug in the presented algorithm that breaks the main result:(https://eprint.iacr.org/2024/555) As someone who has been loosely following post-quantum crypto...Looks like the author has reported a bug in the presented algorithm that breaks the main result:(https://eprint.iacr.org/2024/555)
As someone who has been loosely following post-quantum crypto developments I have to say that the idea of having the foundation for most of the NIST selected cryptosystems turn out to be quantum insecure is pretty funny in a cosmic sense, especially because a version of this scenario has already happened where one of the final candidates for standardization turned out to be crackable using classical computation alone.
-
Comment on Megathread: April Fools’ Day 2024 on the internet in ~talk
Hvv LinkToday's daily Squardle puzzle (a 2d wordle variant) has a particularly unique choice of words. Squardle without ridiculous words is already a pretty involved puzzle, but I actually didn't know any...Today's daily Squardle puzzle (a 2d wordle variant) has a particularly unique choice of words. Squardle without ridiculous words is already a pretty involved puzzle, but I actually didn't know any of the words in this one.
-
Comment on What programming/technical projects have you been working on? in ~comp
Hvv LinkI created the Library of Babel. Okay I jest, of course, but it turns out that making a "Library of Babel" is not obvious at all. If you haven't read the short story by Luis Borges, you probably...I created the Library of Babel.
Okay I jest, of course, but it turns out that making a "Library of Babel" is not obvious at all.
If you haven't read the short story by Luis Borges, you probably should (it's pretty short), but the basic premise is that there is an astronomically large, possibly infinite library out there containing nothing but shelves and shelves of books, seemingly containing every possible arrangement of letters and punctuation. Most of these books appear totally useless, but if the library is complete then it has somewhere a compendium of all scientific discovery, every novel that has ever been written, and a transcript of every conversation that all people will ever have.
Naturally, we can't build a physical version of this (to my knowledge), but we can simulate the idea by creating an index into this library of pure information, taking in some input and returning a virtual book sampled from range of all possible such books.
You may already be familiar with a website that already did this, but if you read the "About" section carefully, you'll find that this online creation doesn't actually cover the full breadth of the Library of Babel. Namely, it only offers every possible page, which are compiled together to form books but wouldn't cover (for example) if an identical page were found in two different books.
If your brain is scrambled in the same way as mine, you know that this shortcoming is unacceptable and demands a complete solution.
Referring back to the original material, a book is 410 pages, each of which contains 40 lines of 80 characters from a symbol set of 25 characters.
In order to exactly recreate the Library in a way that is at least kind of interesting, we need a way to index into this set of books in a way that is:
-
Complete (so you can access every book, i.e. not just using a random number generator to extend the input into book-length*)
-
Unpredictable (to simulate the "ocean of information" feel, since otherwise just outputting the input would indeed access every book, but obviously not in the way we want).
*
If you read even more carefully into the About section of the Library of Babel Website you'll realize that the website author literally does use a random number generator. However, this was a specially crafted generator that had enough state to actually generate the full range required to represent every possible page. Most random number generators will only generate 264 or 2256 or even 219937-1 different values, which while good enough for normal uses, isn't enough for us here.
These constraints will immediately give us a few caveats. For one, pesky Information Theory dictates that no matter what we use to index the Library of Babel, our input will contain at least enough information to encode a book in that library. That is, most indices to books in the Library will be essentially be books themselves.
This is a little annoying (funnily enough Borges also wrote a short story about this exact scenario), but it is a necessary cost if we want a complete library.
For another, just retrieving a book will likely be expensive in memory and/or time depending on the final algorithm. A "Complete Library of Babel" website with any meaningful server-side activity will have ridiculous DOSability potential, so we won't focus on any online experience for now.
With these constraints in mind we can reuse random number generator idea from before and just make an extremely long and unwieldy one, but as is often the case with mathy things we can instead find out that if we state the problem in math terms it's actually a well known problem.
We return to those two requirements from before, and restate our indexing system as a function from some input space that we can specify to the set of books (the set of strings of length 1312000 containing which characters from an set of size 25*).
*
You might notice that 25 is notably not a power of 2 and less than the English alphabet length of 26. Apparently this character set is alluded to in a previous essay and is the result of cutting some "unnecessary" letters out of the Spanish alphabet to arrive at 22 letters and 3 punctuation characters.
In fact, the Library of Babel website uses 29 letters (26 + 3 punctuation) and for the sake of convenience we'll be fudging this alphabet size as well.
The function needs to be:
-
Surjective
-
Indistinguishable from a Random Oracle for an adversary given a number of queries and time polynomial in the input size
That second requirement is a mouthful, but captures what we mean by "Unpredictable": nobody should be able to figure out any patterns in this function, so much so that they can't tell it apart from random noise, even if they test it with some sample inputs or think about it for a while. Of course, this is also (almost) the definition of a crypto object, namely the Pseudorandom Function.
We now come across something that will actually solve our problem, the Pseudorandom Permutation, which is like a Pseudorandom Function (actually it provably is one) but is bijective. What is a common way to think about Pseudorandom Permutations? As a block cipher, of course! That is, to simulate going from our index to some book in the Library of Babel, we just encrypt the input with the appropriate encryption algorithm, like AES.
Well that's not the whole story, because there is no block cipher that directly operates on blocks the size of books. AES itself only operates on blocks of 128 bits, which returns to our problem of being not big enough. Block ciphers generally get around this size limit by using chaining, i.e. by slightly changing the cipher between blocks so that the output remains unpredictable between blocks. This actually doesn't solve our problem, because part of the way these algorithms stay secure is using randomization, which we can't do (lest the shelves of the Library shift and shuffle from beneath our feet), and otherwise if you change a part of the input, only part of the output changes (all blocks before the part that changed stay the same) which violates our unpredictability requirement.
My solution to this is to create my own scheme, which is a cardinal sin for cryptography but is is fine for me since I don't hide my secrets in near-infinite libraries. It's practically the bare minimum to have a small change in the input potentially affect every bit of the output, but it's enough to be nontrivial to crack.
With that, we arrive at an index for the Library of Babel:
-
Fix 2 256-bit keys K1, K2 and 2 128-bit initialization vectors IV1, IV2. Note that these should stay fixed between runs to keep the index consistent. You should also pre-select some character set of 32 symbols to get a book out at the end.
-
Take a length 6560000 string as input. (I just filled the initial bits with ASCII input and then padded the reset with zeros).
-
Encrypt with AES-256 under the CBC mode with K1 and IV1 to get a ciphertext C1.
-
Reverse C1 bitwise and encrypt with AES-256 under the CBC mode with K2 and IV2 to get the bitwise C2.
-
Interpret the resulting bits in blocks of 5 using the predefined size-32 character set to retrieve some book of 410 pages with 40 lines of 80 characters from the Library of Babel.
And it works! I made a C++ script that did this which I probably won't publish (for now; it kind of sucks) but it is enough to demonstrate that it's possible, and this algorithm is invertible! You can "search" the Library of Babel for a certain text and find out "where" it is in the index (though this index will literally be book-length, so be warned).
I did return to the "restate this in mathy terms" and found out that "variable length block ciphers" are a thing that people have thought about, cf. this and this.
One day when I feel bothered enough by the possible cipher-insecurity of rolling my own crypto and/or interested in the idea again (website that's basically all client-side? non-awful source code?) I might come back to it.
-
-
Comment on Day 22: Sand Slabs in ~comp.advent_of_code
Hvv LinkOkay I did do some more of these but writing up solutions turned out to be very time consuming, so I didn't stopped a couple of weeks ago. Some of these do have some pretty crazy asymptotically...Okay I did do some more of these but writing up solutions turned out to be very time consuming, so I didn't stopped a couple of weeks ago. Some of these do have some pretty crazy asymptotically faster solutions though (have you ever done string matching with polynomial multiplication?) so if there's time/interest I might go back and fill in the details for some of those.
This is also definitely going to be my last one done live, though, since I'm going to be going to a place with a worse time zone and no easy access to a coding computer.
Part 1 Solution
Part 1 is basically already a two-part problem, where you first have to build a graph representation of the blocks and only after doing that do you get to tackle the problem of what to do with it.
We should first define what graph we're trying to build. Namely, from the problem it sounds like we should pay attention to what blocks support each other, so we'll build a graph where every node is a block and there is an edge directed block A -> block B if A is resting on top of B.
For the first sub-part, once we have a decent representation of the blocks we can just build it from the ground up in a simple way. Namely, we can keep a 2D representation of the top-down view, and build up from the ground what the tower looks like once each block falls down onto to that tower.
Before we start we do need to know what order to consider the blocks in, since this building-up approach assumes that we know what relative order blocks will show up in the tower. The simplest way to do this is to order the blocks by increasing Z-coordinate of the bottom part of the block, so we can just go with that (you might want to prove to yourself that this works, even if it seems obvious).
The next thing to note is that the blocks do, in fact, fall, so their Z-coordinates are not necessarily fixed. This means that in our top-down view we're going to use the max Z-coordinate of every block in the shadow of each new block in order to determine what height we end up at.
Finally, even if a block overlaps another block in the top-down view, that doesn't mean the obscured block will support the upper block. This is pretty easy to see but means that we have to be careful in code, since we'll need to check the height for each block underneath. You can do this in a variety of ways (by the way you might want to be careful about multi-edges! There surface where two blocks touch might be many squares) but it's important that it gets done.
Now that we actually built our graph, we can then move onto the second sub-part. How can we use
If we disintegrate some block B, then all blocks supported by B also need to be supported by another block. In our graph, this means that for all other blocks C such that C -> B, if C -> B is the only edge then we can't destroy block B. And inversely, if every block has another edge, then if we destroy B we can let all the other blocks depend on whatever other block is on the other side of that edge, so it is safe to destroy B.
Repeating this logic for every block gets us the full answer.
Part 2 Solution
Since we already built the graph in Part 1 it's nice that we can just reuse it for part 2.
The main thing here is that we need to the propagation of falling blocks. In particular, even if a block has more than one support, if all those supports fall then the block will still fall. This actually isn't that hard to track. Namely, for each block we track how many of its supports fell, and if we see that all of a block's supports fall then we have this block fall as well.
Luckily we can process the blocks falling in any order, since we will get to all of them eventually.
We can then simply repeat this process for every block and add it up to get the full answer.
Part 2 Bonus
The algorithm we described in part 2 runs in O(VE) since it could potentially check off every edge and vertex individually.
But what if I told you it's not asymptotically optimal?
This one starts with an interesting observation and leads into graph theory that people smarter than me did a couple decades ago.
Namely, let's try to answer a seemingly obvious question: Given two blocks A and B, if we remove block A, will block B fall?
We basically just answered this in our solution to Part 2, but we did that by looking at the blocks being removed. What if we looked at the block doing the falling? Namely, using our graph, is there a way for us to determine from block B which blocks beneath it will cause it to fall?
Starting our search from block B, we imagine that we're travelling down those edges to the ground. If there's a path that avoids path A, then block B is supported, since this path can remain standing even if A (or any block not in that path) is removed.
However, if every path from block B to the ground goes through A, then clearly it will fall when block A is removed.
This gives us a new way to answer our question:
For blocks A and B, then B will fall when A is removed only if every path from B to the ground goes through A.
And now for the connection with graph theory: this sounds a lot like the definition of a dominator node:
In computer science, a node d of a control-flow graph dominates a node n if every path from the entry node to n must go through d.
This is almost the relationship between the blocks A and B we had from before, but we can make it exactly the same relationship by reversing all the edges in the graph (so instead of B -> A when B rests on A with edges going towards the ground, edges go up from the ground).
Then, in this reversed graph, B will fall when A is removed only if A dominates B when entering from the ground (which we can represent as its own node).
With this connection established we can finally start doing the real weird logic leaps.
In particular, node dominators actually follow a strict ordering. Namely, if a node X has two dominators A and B, either A is a dominator of B or B is a dominator of A.
The basic proof idea is to start at the entry node and look at paths to X, which all must contain A and B in some order. If one path has A before B and another has B before A, then we can create a new path that takes the first path's route to A and then skips to the second path from A to X to avoid B entirely, which contradicts the definition of dominator nodes, so all nodes must have the same ordering of A and B.
This means that we can order dominators in a tree structure rooted at the entry node (if you play around with nodes under ordering rule above you'll see that every node must have at most one parent), where A -> B if A dominates B, and the full set of nodes dominated by A is the subtree rooted at A.
Now instead of directly calculating the dominators for each node, we can instead calculate the tree (uncreatively named the dominator tree) and use subtree sizes to calculate the full answer.
Finally, because of course people thought of this, dominator trees can be calculated very quickly (another analysis that's not literally 40 years old here), in the time complexity of O(E * α(V,E)) where α is the wonderfully slow growing and weird to describe Inverse Ackermann Function.
Part 1/2 Code
#include <bits/stdc++.h> using namespace std; vector<string> split(string s, string delim) { vector<string> ans; while(s.find(delim) != string::npos) { int idx = s.find(delim); ans.push_back(s.substr(0,idx)); s = s.substr(idx+delim.size()); } if(!s.empty()) { ans.push_back(s); } return ans; } int get_num_falling(int source, const vector<vector<int>>& graph, const vector<vector<int>>& graph_reverse) { int ans = 0; queue<int> q; q.push(source); vector<int> degree(graph.size()); while(!q.empty()) { int u = q.front();q.pop(); ans++; for(const auto& v: graph[u]) { degree[v]++; if(degree[v] == graph_reverse[v].size()) { q.push(v); } } } return ans-1; } int main() { string s; vector<vector<pair<int,int>>> block_coords; map<int,vector<int>> z_coord_blocks; while(cin >> s) { auto coords = split(s,"~"); auto coords_low_str = split(coords[0],","); auto coords_high_str = split(coords[1],","); vector<int> coords_low,coords_high; for(const auto& u: coords_low_str) { coords_low.push_back(stoi(u)); } for(const auto& u: coords_high_str) { coords_high.push_back(stoi(u)); } block_coords.emplace_back(); auto& row = block_coords.back(); for(int i=0;i<3;i++) { row.emplace_back(coords_low[i],coords_high[i]); } z_coord_blocks[coords_low[2]].emplace_back(block_coords.size()-1); } vector<vector<int>> graph(block_coords.size()); vector<vector<int>> graph_reverse(block_coords.size()); map<pair<int,int>,int> gob; set<pair<int,int>> sos; for(const auto& [_,block_ids]: z_coord_blocks) { for(const auto& idx: block_ids) { int max_z_coord = 0; set<int> mos; for(int i=block_coords[idx][0].first;i<=block_coords[idx][0].second;i++) { for(int j=block_coords[idx][1].first;j<=block_coords[idx][1].second;j++) { if(gob.count(pair<int,int>(i,j))) { int p = gob[pair<int,int>(i,j)]; max_z_coord = max(max_z_coord,block_coords[p][2].second); mos.insert(p); } } } int fall = block_coords[idx][2].first-(max_z_coord+1); block_coords[idx][2].first -= fall; block_coords[idx][2].second -= fall; for(int i=block_coords[idx][0].first;i<=block_coords[idx][0].second;i++) { for(int j=block_coords[idx][1].first;j<=block_coords[idx][1].second;j++) { gob[pair<int,int>(i,j)] = idx; } } for(const auto& p: mos) { if(block_coords[p][2].second+1 == block_coords[idx][2].first) { graph[p].push_back(idx); graph_reverse[idx].push_back(p); } } } } int ans = 0; for(int i=0;i<graph.size();i++) { int not_falling = 1; for(const auto& v: graph[i]) { if(graph_reverse[v].size() == 1) { not_falling = 0;break; } } ans += not_falling; } cout << ans << '\n'; ans = 0; for(int i=0;i<graph.size();i++) { ans += get_num_falling(i,graph,graph_reverse); } cout << ans << '\n'; } -
Comment on 2023 GCHQ Christmas Challenge in ~misc
Hvv Link ParentOh you got the bits I didn't! I also back solved some of them but luckily different ones. Challenge 3 Ignore the note pitches and look at the note lengths only. A quarter (filled) note is a 1 and...Oh you got the bits I didn't! I also back solved some of them but luckily different ones.
Challenge 3
Ignore the note pitches and look at the note lengths only.A quarter (filled) note is a 1 and a half (hollow) note is a 0, and then it's just reading the binary value with a=1, b=2, etc. like Bacon's cipher
Challenge 5
The one you're missing goes letter by letter, whereW = 23rd letter of the alphabet, U = 21 S = 19 Q = 17 O = 15 M = 13and K = 11, I = 9
Challenge 6
The connections are:Sirius Black, Penny Black, Pitch BlackScarborough, Beverley, Pudseyare all in YorkshireJasmine Rice, Sticky Rice, Delcan Rice(Delcan Rice is a footballer not a type of rice as far as I know)Black, Yorkshire, Riceare all types ofteapuddingAs a sidenote, this seems like a nod to Only Connect (example here) which has a similar structure and cultural references that I'm not British enough to get.
-
Comment on Day 12: Hot Spring in ~comp.advent_of_code
Hvv LinkThis problem isn't really quality-checking your initial implementation so much as it is daring you to do the straightforward solution so it can pull the rug out from under you. Part 1 Solution...This problem isn't really quality-checking your initial implementation so much as it is daring you to do the straightforward solution so it can pull the rug out from under you.
Part 1 Solution
Like yesterday if we go with the future-proof solution here we won't have anything to discuss for Part 2, so we'll spend a bit of time checking out the most obvious solution.
Namely, just try all the combinations and see what works!
I imagine you could have a hideous for loop do the manual checking since the array size is limited, but we can at least spare ourselves the dignity here of using recursion to deal with that instead. I would imagine such a solution could pass to itself the context of which part of the string you're building and where in the list you are, like something like:
COUNT_SOLUTIONS(string_candidate, array_position): if array_position is at the end of the array: if string_candidate matches against the reference string: return 1 else: return 0 answer = 0 # Try adding a '.' to the candidate answer += COUNT_SOLUTIONS(string_candidate+'.', array_position) # Try adding a block of '#' corresponding to the current array position. # Note that if we're not at the end of the array, we need to add another '.' answer += COUNT_SOLUTIONS( string_candidate+(array[array_position]*'#'+'.' if we're not at the end of the array, array_position+1)This solution is pretty crude and elides some detail, but the general idea should work for a real solution.
If you program it well (and you don't need to program it well to get this part), then your code will only make a few calls per valid assignment, assuming there aren't many assignments, it should be pretty fast.
My answer was on the order of thousands, so it really doesn't take that long.
Part 2 Solution
Now it's time for the rug pull, because this expanded version absolutely takes that long (my answer was on the order of 1012).
Let's go back to the original problem and our original solution.
Did you notice an optimization for our
COUNT_SOLUTIONSsearch routine? Namely, if thestring_candidateis known to not match the reference string prefix, then we can cut it off early. This sounds simple, but it means that we can actually haveCOUNT_SOLUTIONSbe in terms ofstring_indexandarray_position(i.e. we know that the string is correct up tostring_indexand we're trying to build the rest of the string afterwards).But now we realize something even more interesting: If we call
COUNT_SOLUTIONSwith the samestring_indexandarray_positionevery time, it will always return the same answer, but our current search algorithm calls itself billions of times to count every solution one by one. Why process all those calls forCOUNT_SOLUTIONSwhen we can just call eachstring_indexandarray_positiononce and cache the answer to return any time it gets called again?This insight represents a ridiculous speedup (and a complete rethinking of the solution's complexity which we'll get back to later), because it saves not only the immediate call to
COUNT_SOLUTIONSbut also every recursive call that it would have made, and every call that that call makes, etc.So, after rewriting the
COUNT_SOLUTIONSto be based off ofstring_indexandarray_positionwe can stick an map/dict/2d array somewhere that, if we encounter a call where we've already calculated the answer, just returns it immediately.Now back to the complexity. It's much faster, but how much faster?
Well we can answer that with how our function is called and what it does.
There are at most (string length) values of
string_indexand at most (array length) values ofarray_position, and most importantly every corresponding calculation withCOUNT_SOLUTIONSis done at most once (because every call after that is just a map/dict/array lookup).Then, for each call,
COUNT_SOLUTIONSdoes some string building/checking and makes 2 other calls toCOUNT_SOLUTIONS.This gives means that we do at most
(string length)*(array length)*(string comparison cost)operations, which is much faster than the(weird, could be really bad)complexity that it was before and definitely enough to solve the expanded version of the problem they're throwing at us now.Just to note, the strategy we used here is has the wonderfully undescriptive computer science name of Dynamic Programming, which can be used to find solutions to some very weird and hard problems, though with the distinct downside of the solutions themselves being strange looking and difficult to describe.
C++ Part 1/2 Code
I have to preface this with the fact that my solution doesn't actually do
COUNT_SOLUTIONSin the same way as above, but it uses the same dynamic programming idea of re-using existing counts.#include <bits/stdc++.h> using namespace std; vector<int> string_to_array(const string& s) { vector<int> ans; long long val = 0; for(int i=0;i<s.size();i++) { if(s[i] == ',') { ans.push_back(val); val = 0; } else { val *= 10; val += s[i]-'0'; } } ans.push_back(val); return ans; } long long solve(const string& s, const vector<int>& gear_list) { vector<vector<long long>> dp(s.size()+1,vector<long long>(gear_list.size()+1,0)); // prefix_good[i] = # of gears before index i in s that are known to be good // In the solution I described "cost of string comparison" but // here we can reduce that to a 2 array lookups to answer the question of // "Is ######. valid?" // With "does the string from [x,x+5) contain no '.' values and // one non-'#' at the end?" vector<int> prefix_good(1); for(int i=0;i<s.size();i++) { prefix_good.push_back(prefix_good.back()); if(s[i] == '.') { prefix_good.back()++; } } // dp[string_index][array_index] counts: // the number of string prefixes up to string_index (exclusive) // that are valid and account for the gear list up to // array_index (exclusive) // Our full answer is then dp[string size][array size] dp[0][0] = 1; int n = s.size(); for(int i=0;i<s.size();i++) { for(int j=0;j<=gear_list.size();j++) { if(s[i] != '#') { dp[i+1][j] += dp[i][j]; } if(j < gear_list.size()) { if(i+gear_list[j] <= n) { if(prefix_good[i+gear_list[j]]-prefix_good[i] == 0) { if(j+1 == gear_list.size()) { dp[i+gear_list[j]][j+1] += dp[i][j]; } else { if(i+gear_list[j] < n && s[i+gear_list[j]] != '#') { dp[i+gear_list[j]+1][j+1] += dp[i][j]; } } } } } } } return dp[n][gear_list.size()]; } int main() { string input_line; long long ans1 = 0; long long ans2 = 0; while(getline(cin,input_line)) { if(input_line.size() == 0) {break;} stringstream ss(input_line); string gears; ss >> gears; string gear_list_string; ss >> gear_list_string; vector<int> gear_list = string_to_array(gear_list_string); ans1 += solve(gears,gear_list); string extended_gears; vector<int> extended_gear_list; for(int i=0;i<5;i++) { if(i > 0) { extended_gears.push_back('?'); } extended_gears = extended_gears+gears; extended_gear_list.insert(extended_gear_list.end(),gear_list.begin(),gear_list.end()); } ans2 += solve(extended_gears,extended_gear_list); } cout << ans1 << '\n'; cout << ans2 << '\n'; }
Alternative Links:
Consumer Reports
California Governor's office
California Privacy Protection Agency
The laws themselves:
AB 566
SB 361
Kind of local and also reading the bills the changes aren't massive (basically just increasing the scope of data sharing disclosure and increasing access to existing privacy signals like the Global Privacy Control signal), but if you remember the GDPR-induced flood of privacy policy updates and/or opt out of every privacy consent toggle out of spite, then I think this will be welcome news (that being said I suspect someone who cares enough has already bent their browser choice around this.)
One interesting thing I'm waiting to see for AB 566 is whether this is going to affect browser design for everyone, because there's no way a change to a browser like that can be limited to just California without some really annoying geofencing, and that might really change the popularity of these opt-out signals given that they now have actual enforcement behind them.