Hvv's recent activity
-
Comment on A quick post on Chen’s algorithm in ~comp
-
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'; } -
Comment on Day 11: Cosmic Expansion in ~comp.advent_of_code
Hvv (edited )LinkThis feels like one of those problems that quality-checks how well thought out your initial implementation was, because I only narrowly dodged having to rewrite the whole thing for Part 2. Part 1...This feels like one of those problems that quality-checks how well thought out your initial implementation was, because I only narrowly dodged having to rewrite the whole thing for Part 2.
Part 1 Solution
We can start this one with the most obvious implementation, which is:
Going through all the rows & columns, mark off all the columns and rows that have a galaxy (or, equivalently, all the columns/rows that don't).
Create a new map doubling all those rows/columns and place all the galaxies appropriately in the new map.
Run a BFS from each galaxy to each other galaxy.This is probably good enough to get you through this part, though it might already be chugging a bit. We'll start by noting that a BFS actually isn't necessary. If you play around a bit, you might be able to see that the shortest path between 2 galaxies is to start at one galaxy and then go vertically until you're on the same plane as the other one, and then just go horizontally until you're at the other galaxy.
To capture this with an algorithm, if we took the X and Y positions of the two galaxies then the distance between those two galaxies is just the absolute differences between the X and Y coordinates (in math terms this is how distance works in the Taxicab Geometry).
We could go further here because the mere mention of "X" and "Y" positions might already be telling you things about how to optimize this, but if we do too much then there's nothing to write for Part 2! So we'll leave it here for now.
Part 2 Solution
This is where the solution above gets quality-checked out of existence. Even if you can check each galaxy in constant time, building a map that's millions by millions doesn't quite work.
But this is where some extra insight into what we're actually doing with our algorithm hints at a way to compress this map. Namely, we don't care about most of the map, we only care about the galaxies!
If we built compressed map that only contains the X and Y positions of the galaxies, then we can just use taxicab distance for all the pairs and solve everything right then and there.
The problem is getting those positions. But let's look more carefully how we're building that map. Namely, if on the un-expanded map a galaxy is at row R and column C, every empty row before R contributes a million* expanded empty rows to R in the expanded map, and every empty column before C independently contributes a million* expanded empty rows to C in the expanded map.
*Alright it's a million minus one, because the empty row itself is already counted in R (this is easier to see in Part 1 where it's just two rows).
That is, in the expanded map,
(expanded-R, expanded-C) = (R + (1000000-1)*(# of empty rows before R), C + (1000000-1)*(# of empty columns before C))Which we can figure out just by counting the number of empty rows before each R and each C.
Now once we've collected the galaxies, we can mark off which rows/columns are empty and collect a record of all the rows/columns that are empty, and build the expanded map using the above algorithm to get the answer.
Bonus Solution Discussion
We found a solution that is O(n^2) in terms of number of galaxies, which is definitely good enough for this problem. But what if I told you it isn't asymptotically optimal? Alright this one isn't nearly as ridiculous as the other bonus that involved polynomial interpolation, but it's still pretty cool.
The first thing to note is that the taxicab algorithm calculates the X and Y differences independently, and then just adds them together. So what if we uncoupled those and also calculated the X and Y parts of the taxicab distance independently as well?
That would look like:
Galaxies: (1,2), (5,3), (2,5), (3,7) X coords: 1,2,3,5 Total X distance: (5-1)+(3-1)+(2-1) + (5-2)+(3-2) + (5-3) = (5+3+2)-(3*1) + (5+3)-(2*2) + (5)-(1*3) = 13 Y coords: 2,3,5,7 Total Y distance: (7-2)+(5-2)+(3-2) + (7-3)+(5-3) + (7-5) = (7+5+3)-(3*2) + (7+3)-(2*3) + (7)-(1*5) = 15 Total distance: 28If you precompute those sums in the last equation, the whole thing can be done in O(n).
Now in this case you could argue that it's O(n log n) because you need to sort to get the X/Y coords in order, but because of the way our input is formatted there's actually a hidden second factor to the complexity, which is just reading the input at all.
If we scan left to right then top to bottom (like usual) then we get all the Y coordinates in order for free.
Similarly, if we scan top to bottom first and then left to right then we can also get the X coordinates in order, since we don't need to associate these coordinates to any particular galaxy.
Part 1/2 Code
#include <bits/stdc++.h> using namespace std; int main() { string s; vector<pair<int,int>> galaxies; vector<int> row_is_empty,col_is_empty; while(cin >> s) { col_is_empty.resize(s.size()); row_is_empty.push_back(0); for(int i=0;i<s.size();i++) { if(s[i] != '.') { col_is_empty[i] = 1; row_is_empty.back() = 1; galaxies.emplace_back(row_is_empty.size()-1,i); } } } for(int i=0;i<row_is_empty.size();i++) { row_is_empty[i] ^= 1; } for(int i=0;i<col_is_empty.size();i++) { col_is_empty[i] ^= 1; } for(int i=1;i<row_is_empty.size();i++) { row_is_empty[i] += row_is_empty[i-1]; } for(int i=1;i<col_is_empty.size();i++) { col_is_empty[i] += col_is_empty[i-1]; } for(const int EMPTY_FACTOR: {2,1000000}) { long long ans = 0; for(int i=0;i<galaxies.size();i++) { int r = galaxies[i].first; int c = galaxies[i].second; r += row_is_empty[r]*(EMPTY_FACTOR-1); c += col_is_empty[c]*(EMPTY_FACTOR-1); for(int j=0;j<i;j++) { int u = galaxies[j].first; int v = galaxies[j].second; u += row_is_empty[u]*(EMPTY_FACTOR-1); v += col_is_empty[v]*(EMPTY_FACTOR-1); ans += abs(r-u)+abs(c-v); } } cout << ans << '\n'; } } -
Comment on Day 10: Pipe Maze in ~comp.advent_of_code
Hvv LinkAlright we're getting to those Advent of code problems that go "yeah it's intuitive but now make a computer understand it" which are the best/worst type of problems. Part 1 Solution So the...Alright we're getting to those Advent of code problems that go "yeah it's intuitive but now make a computer understand it" which are the best/worst type of problems.
Part 1 Solution
So the algorithmic part of this problem is easy "just breadth/depth first search" but the real problem is figuring out what we're actually searching.
In order to not drown in switch statements, we're going to need to establish some sort of systematic way of saying "Can the animal go from this location to this other location?"
My thought for this was to describe each pipe by its openings. For example, the
|pipe is open at the north and south, and the7pipe is open at the west and south.This then gives us a strategy for DFS/BFS: For each node, try every opening in that pipe, and if the pipe next in that direction has an opening in the opposite direction, then the animal can move to that pipe. There's a bit of jank with the starting location
Swhich could theoretically be open at any location, but if you keep everything as a bitset (or, in my implementation, abusedintas a bitset) then you can just setSto be open everywhere.We now have a clear path forward for BFS, but DFS also offers a simple solution: Upon finding the loop, divide the distance by 2 (adding 1 if necessary).
Note for part 2: It turns out that depth first search makes part 2 way easier by making it much faster to figure out what's in the loop, but that's an implementation story for another time.
Part 2 Solution
This is even more "intuitive but computers don't get it".
Fortunately for us one relatively computer-friendly way to determine whether a point is on a curve is to count the number of times it crosses that curve (better known as the Ray casting algorithm).
Ray casting algorithm bonus
Of course someone had to prove that this method works, and the proof is one of the ultimate "intuitive but mathematically hairy" theorems out there. Enter the Jordan Curve Theorem, which states that closed loops in 2D space have an inside and an outside. Very simple, as long as you have absolutely no followup questions.
So this at least gives us a strategy to figure out which points are in the curve. Going from left to right, count how many times we cross the loop and only count points that have crossed an odd number of times. You've probably already spotted an issue with this strategy, though, which is "what if we're literally exactly on the loop, like if we enter a horizontal section?"
The answer is, naturally, to stretch our 2D analogy just enough to avoid having to actually answer the question. In particular, imagine that all the loops make their turns at exactly the midpoint of each section. Then, we imagine that our ray in the ray casting algorithm goes just beneath the midpoint, so that we can not-answer the question by saying that horizontal sections don't count as crossings (because the ray is always hovering just below the horizontal pipe and never touches/crosses it). This also gives us neat solution to the turns in pipes.
JandLpipes don't count as crossings (they stay above the ray the whole time) but7andFpipes do (the downwards going part does cross the ray). Problem successfully dodged!Well we're not quite out of the woods yet. One funny thing is determining which pipes are in the loop. With DFS this is easy, since you can just detect the last pipe in the search and go backwards to get the entire loop. With BFS, you have the fun problem of storing the pipes leading to the most distant loop and then inferring the loop in two (almost equal) halves, which is not nearly as nice.
One other problem is that we need to know what the starting pipe
Sactually is. This is a very tiny edge case but you have to look at the adjacent pipes fitting it and in the loop rather than just adjacent pipes fitting it.Once we have that sorted out, we can use the ray casting algorithm on all the points not on the loop to figure out whether they're inside or outside.
Part 1/2 Code
Cleaning this code up fully will take forever, so feel free to gaze upon the janky implementation details and weird hacks used to make this solution barely work. But as a bonus it outputs the loop and the inside/outside points!
#include <bits/stdc++.h> using namespace std; // E N W S const int dr[4] = {0,-1,0,1}; const int dc[4] = {1,0,-1,0}; int main() { vector<vector<int>> g; vector<vector<int>> dist; string s; vector<string> string_grid; pair<int,int> start_node; while(cin >> s) { string_grid.push_back(s); g.emplace_back(); auto& w = g.back(); for(const auto& c: s) { int nx = 0; if(c == 'J') { nx = (2|4); } else if(c == 'L') { nx = (1|2); } else if(c == 'F') { nx = (1|8); } else if(c == '7') { nx = (4|8); } else if(c == '|') { nx = (8|2); } else if(c == '-') { nx = (4|1); } else if(c == 'S') { start_node = pair<int,int>(g.size(),w.size()); nx = 1|2|4|8; } w.push_back(nx); } } start_node.first--; dist.assign(g.size(),vector<int>(g[0].size(),-1)); queue<pair<int,int>> q; q.push(start_node); dist[start_node.first][start_node.second] = 0; int max_dist = 0; vector<vector<pair<int,int>>> pa(g.size(),vector<pair<int,int>>(g.back().size())); pair<int,int> max_dist_node; while(!q.empty()) { pair<int,int> co = q.front();q.pop(); int r = co.first; int c = co.second; if(dist[r][c] > max_dist) { max_dist_node = co; } max_dist = max(max_dist,dist[r][c]); for(int i=0;i<4;i++) { if(!(g[r][c]&(1<<i))) {continue;} int u = r+dr[i]; int v = c+dc[i]; if(u < 0 || u >= g.size()) {continue;} if(v < 0 || v >= g[u].size()) {continue;} if(g[u][v]&(1<<(i^2))) { if(dist[u][v] == -1) { dist[u][v] = dist[r][c]+1; q.emplace(u,v); pa[u][v] = co; } } } } vector<vector<int>> in_loop(g.size(),vector<int>(g.back().size())); { int r = max_dist_node.first; int c = max_dist_node.second; int mad = -1; vector<pair<int,int>> oks; for(int i=0;i<4;i++) { int u = r+dr[i]; int v = c+dc[i]; if(u < 0 || u >= g.size()) {continue;} if(v < 0 || v >= g[u].size()) {continue;} if(dist[u][v] > mad) { oks.clear(); mad = dist[u][v]; } if(dist[u][v] == mad) { oks.emplace_back(u,v); } } oks.push_back(max_dist_node); for(const auto& co: oks) { pair<int,int> ok = co; in_loop[ok.first][ok.second] = 1; while(ok != start_node) { ok = pa[ok.first][ok.second]; in_loop[ok.first][ok.second] = 1; } } } { int r = start_node.first; int c = start_node.second; g[r][c] = 0; for(int i=0;i<4;i++) { int u = r+dr[i]; int v = c+dc[i]; if(u < 0 || u >= g.size()) {continue;} if(v < 0 || v >= g[u].size()) {continue;} if((g[u][v]&(1<<(i^2))) && in_loop[u][v]) { g[r][c] |= 1<<i; } } if(g[r][c]&8) { string_grid[r][c] = '|'; } } int count_in_loop = 0; for(int i=0;i<g.size();i++) { int inside = 0; for(int j=0;j<g[i].size();j++) { if(in_loop[i][j] == 1) { if(string_grid[i][j] == '|' || string_grid[i][j] == '7' || string_grid[i][j] == 'F') { inside ^= 1; } cout << string_grid[i][j]; } else { count_in_loop += inside; cout << (inside?'I':'O'); } } cout << '\n'; } cout << count_in_loop << '\n'; cout << max_dist << '\n'; } -
Comment on Day 9: Mirage Maintenance in ~comp.advent_of_code
Hvv LinkC++ A surprisingly conventional problem here, but I'm always down for a bit of math. Part 1 Solution This one is a pretty straightforward problem, and one that you might have seen before in math...C++
A surprisingly conventional problem here, but I'm always down for a bit of math.
Part 1 Solution
This one is a pretty straightforward problem, and one that you might have seen before in math somewhere.In this case, rather than stopping once we see all zeros it's easier to just go all the way to when it's just a single digit (which will certainly be zero if a previous row is zero, and if not then the next row will contain no digits and be "all zeros" anyway).
After that, we can just take the last element of each array to build the next column in the consecutive differences.
Part 2 Solution
Funnily enough, the simplest solution (code-wise) for this is just to reverse the input array. Proving that this solution works is pretty interesting in my opinion, but the most obvious proof probably involves a lot of algebra which doesn't seem all that fun.Even if you don't go through the effort of proving that, if you kept all those consecutive difference arrays you can always just go back and extract the first values to go backwards one step.
Part 1/2 Code
#include <bits/stdc++.h> using namespace std; vector<long long> consecutive_diff(const vector<long long>& p) { vector<long long> ans; for(int i=1;i<p.size();i++) { ans.push_back(p[i]-p[i-1]); } return ans; } int main() { ios::sync_with_stdio(0);cout.precision(20);cout.tie(0);cin.tie(0); string line; long long next_ans = 0; long long prev_ans = 0; while(1) { getline(cin,line); if(line.empty()) {break;} stringstream ss(line); vector<vector<long long>> diffs; diffs.emplace_back(); long long t; while(ss >> t) { diffs.back().push_back(t); } while(diffs.back().size() > 1) { diffs.push_back(consecutive_diff(diffs.back())); } vector<long long> next(diffs.size()),prev(diffs.size()); for(int i=diffs.size()-2;i>=0;i--) { prev[i] = diffs[i][0]-prev[i+1]; next[i] = diffs[i].back()+next[i+1]; } next_ans += next[0]; prev_ans += prev[0]; } cout << next_ans << '\n'; cout << prev_ans << '\n'; }Bonus Observations
The most obvious way to achieve what the problem is asking is just to reimplement the algorithm being described, and it's most likely the simplest. But what if I told you it's not asymptotically optimal?We might hope that this algorithm terminates quickly for all inputs, but in fact you can find inputs that force it to run in O(n^2). Examples include
1,2,4,8,16,...,2^nor0,1,0,-1,0,...,sin(pi*n/2).The question is then:
Given a list of N elements, can you find the next value with this consecutive-differences algorithm in faster than quadratic time?
I already gave away that the answer is yes, but people smarter than me have shown connections to much cooler math in order to get there.
The big leap here is to realize that this problem is equivalent to Polynomial Interpolation which might feel crazy if you haven't seen it before.
The basic idea is this: Look at the consecutive differences for polynomials:
n:
0 1 2 3 4 1 1 1 1 0 0 0n^2:
0 1 4 9 16 1 3 5 7 2 2 2 0 0n^3:
0 1 8 27 64 1 7 19 37 6 12 18 6 6 0And you'll notice that n takes 1 step to reach fixed consecutive differences, n^2 takes two, and n^3 takes 3. We might wonder whether this pattern continues, and it does! Starting from first principles takes forever, but just as a next step you should consider how consecutive differences looks when expressed with polynomials.
From this fact with polynomals we can work backwards, i.e. looking at the consecutive differences from bottom to top and re-adding polynomials to get the original list of numbers.
That would look something like
1 2 4 7 11 16 1 2 3 4 5 1 1 1 1 -(1/2)n^2 = 1 1.5 2 2.5 3 3.5 .5 .5 .5 .5 .5 0 0 0 0 -(1/2)n = 0 0 0 0 0 0And working from the bottom means that this polynomial will have minimal degree (i.e. you can't magic a simpler polynomial using some other method).
Then, going back to our original problem, this is essentially transforming our list of numbers
a_0,a_1,a_2,a_3,...,a_ninto a set of coordinates(0,a_0),...,(n,a_n)and finding the least degree polynomialPwhereP(x) = a_xfor0 <= x <= nand this gives us our solutions for Part 1 and Part 2: The part 1 answer isP(n+1)and the Part 2 answer isP(-1).Okay this all loops back around to that faster than quadratic solution because we have a much faster way to calculate a polynomial from its points: Lagrange Interpolation which is certified math by its math person name. Unfortunately the documentation on this is a little sketchy, but thanks to the ever cursed Fast Fourier Transform you can actually do this in O(n log^2(n)). The best source I found in my 1 minute of searching is here. I know that this algorithm works because I've used it before, but it's just really bad to describe without drowning in math.
As a bonus bonus, this also gives us a radically different way to prove that reversing the list works for Part 2:
Reinterpreting our list again as coordinates, we already know that there is some least degree polynomial
Pthat will match every coordinate on the list, and that the next and previous values areP(n+1)andP(-1), respectively.If we reverse our list, this list must also have a least degree polynomial (which we could call
Q) that matches every coordinate on that list. But wait,Q(x) = P(n-x)works, doesn't it?PandQshould have the same degree soP(n-x)should work just as well to fit the description of such aQ. Furthermore,Q(n+1) = P(n-(n+1)) = P(-1)so the next element for the reversed array is indeed the previous element of the regular array.There's even more bonus by the way: something missing from this is whether the least degree polynomial was unique. We secretly assumed this fact during the reversal proof, but you can get sucked into even more different math (in this case matrices) because there's always more math.
-
Comment on Day 8: Haunted Wasteland in ~comp.advent_of_code
Hvv (edited )Link ParentFor part 1, I'll admit now that part of my hideous string parsing is what happens when some part of my brain goes "but you must think of the general case" but only for things like input string...For part 1,
I'll admit now that part of my hideous string parsing is what happens when some part of my brain goes "but you must think of the general case" but only for things like input string length, leading to parsing ideas like "remove the last element which we know to be ")" but only reference the possibly non-fixed (even though we know it's fixed) string size when doing so".
I was already doing some fiddling with stringstream but I didn't know about split_view, so I'll look into that. At first glance it looks like it only accepts one delimiter, but that might still be useful in the future if I have to deal with commas or some related non-whitespace thing.
Part 2 discussion, with spoilers
You're right that Advent of Code often simplifies the problem implicitly in order to allow for simpler solutions.
To be more specific, my problem with Part 2 is that the simplified input is artificial to the point of absurdity.
For contrast, in Day 5 the maps given in the input were bijective (I think) even though there was no indication that this would be true in the problem (and indeed it was easy to create a non-bijective map). However, this idea that those maps will be one-to-one is very intuitive and is clearly shown by the example input, so it felt like a reasonable assumption to make.
In addition, there is a nice general solution that covers non-bijective maps. It's not as simple as the specialized solution, but it's still reasonable and thinking about it makes the problem more interesting.
However, the simplest type of graphs I can think of where the intended solution works is...
"Graphs in which the first node is not in a cycle, but immediately enters a cycle where, looking at the state graph, only the last element in the cycle (before looping) has Z as a suffix"
Or (closely related but not quite the same):
"Graphs in which the first step from the first node enters a cycle whose length is a multiple of the instruction length and only the last element in the cycle has Z as a suffix"
(There are other graphs for which this works but I think they're even more complicated to describe)
This is plainly ridiculous. To steal your chess analogy, it's like seeing a move and thinking "oh, this tactic would work if only they took with the queen, but obviously they won't because they can just block the threat with another piece". Except the tactic maker does intend have them take with the queen, because only then could the tactic feature a Windmillwe're really stretching the analogy here you get the point.
I was going to say that upon writing this I realized that the example input follows that description, but it doesn't! The 22A cycle has period 3 (the instructions are LR, length 2), clearly only doing so because all the L/R choices are the same.
Note on the example input
The example input doesn't present a simpler class of graphs, because the state after 1 move is 22B to move Right but the state after 4 moves is 22B to move Left. It's entirely possible for you to arrive at the same node but take a different path because you're at a different point in the instruction set. It only happens to be true here because L/R are the same everywhere, and we would need to add even more conditions to the graph if we wanted to quantify that.
In addition, there are several very similar classes of graphs with different solutions.
For example, removing the requirement of "the node with Z is at the end of the loop" adds in the need for the Chinese Remainder Theorem. Removing "only one node with Z in the cycle" adds a ton of complexity. Even changing the janky "the first node is not in a cycle but its first move enters the cycle" to "the first node is the first node of the cycle" will at least require the solution to subtract one, but they didn't even do that.
Advent of code does often simplify its problem sets, and most of the time it does so pretty well. But this one feels like it used "simplify the input" to paper over bad problem design.
-
Comment on Day 8: Haunted Wasteland in ~comp.advent_of_code
Hvv LinkC++ I really disliked Part 2. Part 2 Gripes So the ultimate solution here is pretty simple, since it's just taking all the loop lengths and getting their LCM. However, there are so many edge cases...C++
I really disliked Part 2.
Part 2 Gripes
So the ultimate solution here is pretty simple, since it's just taking all the loop lengths and getting their LCM.
However, there are so many edge cases that are possible here that you couldn't logically arrive at a quick solution from the problem description and must analyze the input to see what's going on.
For example, from what I can tell the following input is entirely valid:
L 11A = (11B, XXX) 11B = (11Z, XXX) 11Z = (11B, XXX) 22A = (11A, 22Z) XXX = (XXX, XXX)You can check to see that in this case you never escape!
There are more complex cases than that, though:
L 11A = (11B,XXX) 11B = (11Z,XXX) 11Z = (11A,XXX) 22A = (22Z,XXX) 22Z = (22B,XXX) 22B = (22C,XXX) 22C = (22A,XXX) XXX = (XXX,XXX)where the solution requires the Chinese Remainder Theorem to solve programmatically.
And there are cases even worse than that...
To make matters worse, they used the same LCM idea in 2019 and had the problem worded in such a way that you could arrive at the LCM solution logically and prove that it worked, rather than guessing at it from the specific input you're given. They got it right already! Was this really the best way to bring out this idea again?
I get that sometimes hacking the input is its own type of cleverness, but this was a significant break from the convention of the other problems and there was no indication this would the right way to go.
Part 1 Solution
The problem here is straightforward, which is to just follow the path from AAA until it reaches ZZZ. Of course, that leaves the full implementation to you.Implementation notes:
Aside from the almost comedically bad string parsing (even after cleaning up),
there are a couple of dumb implementation details that I love,
like converting a string to an int by just sticking the whole thing in a map or by dynamically resizing the array whenever we need extra elements.
After parsing all the strings, it's relatively easy to get the answer out.If anyone has a better way to parse strings (that doesn't involve a library) I would be happy to hear it.
Somehow I suspect this might not exist, because C++ tends to be the sort of language that makes you do that yourself.Part 1 Code
#include <bits/stdc++.h> using namespace std; map<string,int> string_to_node; int get_node(const string& s) { if(string_to_node.count(s)) { return string_to_node[s]; } else { int ans = string_to_node.size(); string_to_node[s] = ans; return ans; } } int main() { string path_choices; getline(cin,path_choices); string input_line; getline(cin,input_line); vector<array<int,2>> left_right_paths; getline(cin,input_line); while(input_line.size() > 0) { // Ah yes, bespoke string parsing in C++ stringstream ss(input_line); string start,left_string,right_string,_; ss >> start; ss >> _; ss >> left_string; ss >> right_string; // Take out the first character '(' and the last character ',' from the left // Take out the last character ')' from the right left_string = left_string.substr(1,left_string.size()-2); right_string = right_string.substr(0,right_string.size()-1); int node = get_node(start); int left_node = get_node(left_string); int right_node = get_node(right_string); left_right_paths.resize(string_to_node.size()); left_right_paths[node][0] = left_node; left_right_paths[node][1] = right_node; getline(cin,input_line); } int node = get_node("AAA"); int end_node = get_node("ZZZ"); int len = 0; while(node != end_node) { int path = path_choices[len%path_choices.size()] == 'L'?0:1; node = left_right_paths[node][path]; len++; } cout << len << '\n'; }Part 2 Code
#include <bits/stdc++.h> using namespace std; map<string,int> string_to_node; long long gcd(long long a, long long b) { if(a == 0) {return b;} if(b == 0) {return a;} return gcd(b,a%b); } long long lcm(long long a, long long b) { return b/gcd(a,b)*a; } int get_node(const string& s) { if(string_to_node.count(s)) { return string_to_node[s]; } else { int ans = string_to_node.size(); string_to_node[s] = ans; return ans; } } int main() { string path_choices; getline(cin,path_choices); string input_line; getline(cin,input_line); vector<array<int,2>> left_right_paths; getline(cin,input_line); while(input_line.size() > 0) { stringstream ss(input_line); string start,left_string,right_string,_; ss >> start; ss >> _; ss >> left_string; ss >> right_string; left_string = left_string.substr(1,left_string.size()-2); right_string = right_string.substr(0,right_string.size()-1); int node = get_node(start); int left_node = get_node(left_string); int right_node = get_node(right_string); left_right_paths.resize(string_to_node.size()); left_right_paths[node][0] = left_node; left_right_paths[node][1] = right_node; getline(cin,input_line); } set<int> z_suffix; vector<int> a_suffix; for(const auto& it: string_to_node) { if(it.first.back() == 'Z') { z_suffix.insert(it.second); } if(it.first.back() == 'A') { a_suffix.push_back(it.second); } } long long total = 1; for(const auto& node: a_suffix) { int len = 0; int current_node = node; while(!z_suffix.count(current_node)) { int path = path_choices[len%path_choices.size()] == 'L'?0:1; current_node = left_right_paths[current_node][path]; len++; } total = lcm(total,len); } cout << total << '\n'; } -
Comment on Day 7: Camel Cards in ~comp.advent_of_code
Hvv (edited )LinkC++ I've been doing these with another group of folks, but since we're here I might as well try to share the stuff I write until it becomes too time consuming or I forget. Going back and cleaning...C++
I've been doing these with another group of folks, but since we're here I might as well try to share the stuff I write until it becomes too time consuming or I forget.
Going back and cleaning up the code takes quite a bit of effort (if you program fast enough your code becomes hieroglyphics), but I think it's now legible enough to stick here.
Part 1 Explanation
I saw the hand descriptions and started worrying that I'd have to write Poker rules, but luckily these rules aren't that bad.The first important thing we see is that you can distinguish almost all the hands using the most frequent card in that hand (5 of a kind > 4 of a kind > (full house/3 of a kind) > (two-pair/pair) > high card).
Then, (full house/3 of a kind) and (two-pair/pair) can be distinguished using a variety of methods (e.g. second most frequent card). I used "number of distinct card ranks in hand" which sounds ridiculous but is surprisingly simple when expressed in code.Then, the tiebreaker is just comparing the hands in lexicographic order according to card strength (but without initially sorting by card strength, since I think poker does do that).
Once we have a way of getting hand strength, the rest of the problem is just sorting the list of hands according to (hand strength, the actual cards in the hand) and then multiplying each hand's bet by the index of that hand (+1 if your arrays start at 0, or reversed if you sorted by descending rank). In this case I just used a C++ custom comparator (wrapped in a custom struct) since the standard sort function will happily take your < function if you provide one.
Part 1 Code
#include <bits/stdc++.h> using namespace std; unordered_map<char,int> ranks = { {'A',0}, {'K',1}, {'Q',2}, {'J',3}, {'T',4}, {'9',5}, {'8',6}, {'7',7}, {'6',8}, {'5',9}, {'4',10}, {'3',11}, {'2',12}, }; // Assigns a numeric value to each hand, where lower = better // This does NOT account for tiebreakers. int evaluate_hand(const vector<int>& hand) { map<int,int> card_count; for(const auto& c: hand) { card_count[c]++; } vector<int> rank_freqs; for(const auto& it: card_count) { rank_freqs.push_back(it.second); } sort(rank_freqs.begin(),rank_freqs.end()); if(rank_freqs.back() == 5) { return 0; } else if(rank_freqs.back() == 4) { return 1; } else if(rank_freqs.back() == 3) { // There are only 2 partitions of 2: // 1+1, 2 // so we only need to look at the size to determine if // the hand is a full house (3+2) or a three-of-a-kind (3+1+1) if(rank_freqs.size() == 2) { return 2; } else { return 3; } } else if(rank_freqs.back() == 2) { // Similarly there are only 3 partitions of 3: // 1+1+1, 1+2, 3 // The last one is "impossible" by our construction so again we // only need size to distinguish between two-pair (1+2+2) and // pair (1+1+1+2) if(rank_freqs.size() == 3) { return 4; } else { return 5; } } else { return 6; } } // A Camel hand, annotated with its value. struct CamelHand { int quality,val; string hand; CamelHand(const vector<int>& ranked_hand, int val): quality(evaluate_hand(ranked_hand)), val(val) { for(const auto& card: ranked_hand) { hand.push_back(card); } } bool operator<(const CamelHand& ot) const { if(quality != ot.quality) {return quality < ot.quality;} // Why write a comparator for arrays in lexicographic order when // you can convert it to a string and get that for free? return hand < ot.hand; } }; int main() { vector<CamelHand> hands; string string_hand; int hand_value; while(cin >> string_hand >> hand_value) { vector<int> ranked_hand; for(const auto& c: string_hand) { ranked_hand.push_back(ranks[c]); } hands.emplace_back(ranked_hand,hand_value); } sort(hands.begin(),hands.end()); long long ans = 0; for(int i=0;i<hands.size();i++) { ans += hands[i].val*(hands.size()-i); } cout << ans << '\n'; }Part 2 Explanation
Aside from changing the strength order a bit, the main question here is how to deal with the Jokers, which will change in a way to give the strongest hand.Funnily enough, you can brute force the transformation of the Jokers into every possible card (despite how awful that sounds, assuming each hand is distinct you can prove that you'll only have to evaluate at most 245 = 7962624 hands, which is merely kind of bad and runs in <1 second on my machine).
But we can be smarter than that. Stealing our observation of distinguishing hands by their most frequent cards from before, we realize that a Joker always does best by converting to the most frequent card in the hand. Since my implementation already converts a hand into a list of card frequencies, this is almost* as simple as adding the number of jokers to the most frequent hand.
*almost, of course, because the problem writers knew you would think of this and likely threw a hand of all Jokers at you.
Part 2 Code
#include <bits/stdc++.h> using namespace std; unordered_map<char,int> ranks = { {'A',0}, {'K',1}, {'Q',2}, {'T',3}, {'9',4}, {'8',5}, {'7',6}, {'6',7}, {'5',8}, {'4',9}, {'3',10}, {'2',11}, {'J',12} }; const int JOKER = 12; int evaluate_hand(const vector<int>& hand) { map<int,int> card_count; int joker_count = 0; for(const auto& c: hand) { if(c == JOKER) { joker_count++; } else { card_count[c]++; } } vector<int> rank_freqs; for(const auto& it: card_count) { rank_freqs.push_back(it.second); } sort(rank_freqs.begin(),rank_freqs.end()); // We love those all-joker hands! if(rank_freqs.empty()) { rank_freqs.push_back(joker_count); } else { rank_freqs.back() += joker_count; } if(rank_freqs.back() == 5) { return 0; } else if(rank_freqs.back() == 4) { return 1; } else if(rank_freqs.back() == 3) { if(rank_freqs.size() == 2) { return 2; } else { return 3; } } else if(rank_freqs.back() == 2) { if(rank_freqs.size() == 3) { return 4; } else { return 5; } } else { return 6; } } struct CamelHand { int quality,val; string hand; CamelHand(const vector<int>& ranked_hand, int val): quality(evaluate_hand(ranked_hand)), val(val) { for(const auto& card: ranked_hand) { hand.push_back(card); } } bool operator<(const CamelHand& ot) const { if(quality != ot.quality) {return quality < ot.quality;} return hand < ot.hand; } }; int main() { vector<CamelHand> hands; string string_hand; int hand_value; while(cin >> string_hand >> hand_value) { vector<int> ranked_hand; for(const auto& c: string_hand) { ranked_hand.push_back(ranks[c]); } hands.emplace_back(ranked_hand,hand_value); } sort(hands.begin(),hands.end()); long long ans = 0; for(int i=0;i<hands.size();i++) { ans += hands[i].val*(hands.size()-i); } cout << ans << '\n'; } -
Comment on Please help me find a post/article posted here on tildes in ~tildes
Hvv LinkWas it this post? I remember there was a lot of discussion around June about how a community should respond to a user influx so it might be hard to pin down otherwise, but I distinctly remember...- Exemplary
I remember there was a lot of discussion around June about how a community should respond to a user influx so it might be hard to pin down otherwise, but I distinctly remember the linked article here for some reason and although there were a lot of comments with a similar sentiment my rudimentary searching doesn't turn up this specific topic all that much.
-
Comment on Timasomo 2023: Week 1 Updates in ~creative.timasomo
Hvv LinkThis week I upgraded my Phutball web interface from "Bad UI, nearly unusable UX" to "Bad UI, passable UX" which to me is already a very big improvement. It's still definitely that the level of...This week I upgraded my Phutball web interface from "Bad UI, nearly unusable UX" to "Bad UI, passable UX" which to me is already a very big improvement. It's still definitely that the level of "you need to know what Phutball is or have someone demonstrate it to you for it to make sense", but as a tiny webthing to show the point I think it's getting somewhere.
The UI is still essentially interactive ASCII art, but the game interaction can be done entirely on the board with the mouse, which is leagues better than the developer-only coordinates-based control panel that I hacked together previously to make sure it worked.
I think this week I'll try to dedicate more time to making the UI more presentable with the hopes of having an actual graphical board and "pieces", though this may be a several-weeks endeavor.
Beyond the "upgrading the UI past ASCII art" I'm hoping to also add a move highlighting system and with the option to partially undo moves (instead of just a full move revert). Actual web interaction is floating around somewhere in the back of my head, but I still suspect it won't happen this month.
-
Comment on We played a 72 hour game of tag across Europe (again) | Jet Lag: The Game in ~hobbies
Hvv Link ParentEpisode 5 Spoilers I'm in awe at the closeness of the circumstances at the end there. Ben gets unlucky with a curse challenge and has to double back and erase his lead on the chasers, except He...Episode 5 Spoilers
I'm in awe at the closeness of the circumstances at the end there.Ben gets unlucky with a curse challenge and has to double back and erase his lead on the chasers, except
He has a shot at deceiving the chasers by stopping off at Howald and using a plausible route back to Luxembourg as a cover to hide and get on a train to Metz, except
The chasers also stop at Howald to try to prevent him from continuing on that plausible route, except
They miss him getting off the train and are stuck on the route back to Luxembourg, meaning that Ben's plan ended up working!
My analytic brain says his lead is probably still smaller if Luxembourg/Metz is a reasonably big transit hub, but all he has to do is run out the clock and it's getting pretty close.
-
Comment on Timasomo 2023: Roll Call in ~creative.timasomo
Hvv LinkI'm trying to figure out web development at the moment, so I'll probably fold my existing project of making a Phutball web interface/site into this. In terms of getting something out, the main...I'm trying to figure out web development at the moment, so I'll probably fold my existing project of making a Phutball web interface/site into this.
In terms of getting something out, the main goal will likely be "Can I play Phutball more or less intuitively on this interface" (I have an existing "functional" interface, but I will definitely need to rework it) and all the bells and whistles will follow from that.
I was last thinking about working on the back end in preparation of potentially making it a real online thing, but that will likely be a stretch goal that I probably won't have time to achieve, given the 0 progress I have made in the last week.
-
Comment on What programming/technical projects have you been working on? in ~comp
Hvv LinkI've continued with my project to make a Phutball webpage It's "functional" though the UI is truly obnoxious (think ASCII display with no CSS and buttons to control everything) It was roughly at...I've continued with my project to make a Phutball webpage
It's "functional" though the UI is truly obnoxious (think ASCII display with no CSS and buttons to control everything)
It was roughly at this point that I realized nearly all the projects I really bothered to complete were CLI or back end stuff, and that it was more interesting to me to look at was server-side, so that's what I'm going to try until the UI bugs me enough to go rewrite it.I also spun up a Veilid node on a VPS, which has proven to be extremely simple (just follow 5 or 2 steps and get weird logs for free) which I wasn't expecting because I saw some people reporting issues in the associated chats. It's somewhat interesting to just play with the CLI interface but I don't understand most of it, so next thing is to think of a way to use it and try to understand what's going on by building something.
-
Comment on Veilid — a peer-to-peer network and application framework by Cult of the Dead Cow in ~comp
Hvv LinkOh I'm looking at this! The website itself is still pretty WIP, so if you have the time the DEFCON presentation (and slides) probably gives a better high level architecture/vision statement. There...The website itself is still pretty WIP, so if you have the time the DEFCON presentation (and slides) probably gives a better high level architecture/vision statement.
There are a few high level technical bits that stand out to me:
- No special assigned node roles (unlike Guard/Exit nodes in Tor and Relay/Bootstrap/Delegate routing)
- Trying to achieve all three of privacy/security/performance
- Light nodes (like a torrent peer rather than a Tor relay node)
- Works with both storage and routing (I'm unsure on the storage portion of this, but the idea is floating around in several sources)
There are a few other nitpicks I have about some of the details, like the mention about the ideas about changing route length, given that in Tor doing so can actually hurt your anonymity, but since I'm not a security researcher I'm not going to pretend that this is proof of any big flaw in the plans laid out.
If you're looking for a demo of the functionality on offer, I think there are only raw CLI nodes right now though there is a chat app somewhere in the works. Obviously the protocol isn't going to get much practical adoption for a while (especially with yet another secure messenger) but it is probably something I will occasionally think about for a while.
-
Comment on What programming/technical projects have you been working on? in ~comp
Hvv LinkTrying to learn the web framework svelte(kit) by building a web implementation of the game Phutball. My goal is to at least have some sort of usable web interface so I can show weird abstract...Trying to learn the web framework svelte(kit) by building a web implementation of the game Phutball. My goal is to at least have some sort of usable web interface so I can show weird abstract strategy games to my friends. The main roadblock right now is that I have no idea what I am doing.
Also somewhere in my brain's orbit is the thought of diving deeper into Veilid which seems to be a pretty interesting communication protocol with an oddly forgettable name (I heard of it some time in July and then forgot its name and had to wait until DEFCON to learn more about it. My mnemonic is Veil-ID which hooks into its whole privacy-oriented theme even if it's not the true etymology). Right now if I have the motivation the most obvious first step is just spinning up a node, though I haven't found the time to figure it out yet.
-
Comment on Nebula reopens lifetime subscriptions for $300 USD in ~tech
Hvv Link ParentChannels on Nebula can offer a discounted/sponsored subscription for $30/year (e.g. with Wendover Productions) so it could be up to 10 years' equivalent for some.Channels on Nebula can offer a discounted/sponsored subscription for $30/year (e.g. with Wendover Productions) so it could be up to 10 years' equivalent for some.
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.