DataWraith's recent activity
-
Comment on Megathread #7 for news/updates/discussion of AI chatbots and image generators in ~tech
-
Comment on What programming/technical projects have you been working on? in ~comp
DataWraith LinkI've moved all my computers to NixOS over the past two weeks. NixOS is a declaratively configured Linux distribution. In many cases you can just add a few lines of Nix language to your...I've moved all my computers to NixOS over the past two weeks.
NixOS is a declaratively configured Linux distribution. In many cases you can just add a few lines of Nix language to your configuration files to activate a pre-defined module, and with a single additional command, NixOS will install and configure the desired software for you. The ecosystem is fantastic; the only real problem is that the Nix language itself is kind of arcane and difficult to grok at first.
There are many upsides I see when using NixOS on all of my computers:
-
The configuration is stored in a single version-controlled repository. Making a change on all four machines is about as simple as making it on one computer only.
-
An add-on called Home-manager manages my dotfiles. There are a ton of pre-defined modules you can enable with a one-line config change. This obviates the need for most of the usual configuration files (e.g.
.bashrc), because those get automatically built from a high-level description of what you want. -
My Homeserver can be automatically deployed to with
deploy-rs; this is something that's unique to NixOS, and even Ansible can't match its power. It will build an updated system locally, transfer that to the server, activate it, and, should anything go wrong, has automatic rollback. -
I'm using devenv.sh for my programming projects now. It extends the idea of a lockfile from just language-specific dependencies to the entire project -- the compiler and all tools can be version-pinned through the power of Nix.
-
For things I don't need very often, the
commatool is pretty cool. It is basically 'command-not-found' on steroids. Instead of printing a string that tells you the name of the package for the program you intended to run, it'll just go ahead and install that package ephemerally and then run the program for you. You just have to prefix the invocation with a comma:, cowsay foo.
I made quite a few mistakes along the way, but now that everything is running smoothly, I'm very happy with the setup.
-
-
Comment on Another megathread for news/updates/discussion of ChatGPT and other AI chatbots in ~tech
DataWraith LinkA group from Stanford released Alpaca, an instruction-tuned version of Facebook's LLaMA 7B model: There's an online demo, but it is completely overloaded at the moment. First you have to wait 2-5...A group from Stanford released Alpaca, an instruction-tuned version of Facebook's LLaMA 7B model:
We introduce Alpaca 7B, a model fine-tuned from the LLaMA 7B model on 52K instruction-following demonstrations. Alpaca behaves similarly to OpenAI’s text-davinci-003, while being surprisingly small and easy/cheap to reproduce (<600$).
There's an online demo, but it is completely overloaded at the moment. First you have to wait 2-5 minutes after you agree to the terms, with no visible progress (unless you crack open the developer tools and look at the websocket messages), and then, after you get to input your prompt, you have to wait in a queue again. I gave up after 15 minutes; I think it bugged out after it started the actual processing.
Llama is interesting in so far that it is supposed to give near-GPT3 levels of performance, but appears to be capable of running on consumer-grade hardware when quantized down to 4 bit precision.
-
Comment on <deleted topic> in ~tech
DataWraith (edited )Link ParentBut that's exactly what creates the slippery slope. For example, from what I understand, Photoshop has a so-called brush engine that can randomly jitter the brush strokes to create various...Yes, because the artificial intelligence system is making decisions without human input. Yes, the generated work is overall created by an input given by a human (presumably), but there are individual steps in the generation process that are decided specifically by the system itself. In other words, the human is not the only artist of the work, and the other artist is not human.
But that's exactly what creates the slippery slope. For example, from what I understand, Photoshop has a so-called brush engine that can randomly jitter the brush strokes to create various artistic effects using random numbers. It would be preposterous to deny copyright for an image created using that feature; the question I was posing is: where does the human artist end and the machine artist begin (assuming there is a machine artist that is not just a tool)?
For example, I can't scribble this shitty rendition of a dog and then go claim it as a copyrighted work that I have sole permission to use. I could certainly try, but even if I was granted a copyright to that work, its extreme triviality would make enforcing my copyright on any works derived from it almost impossible.
Again, that's exactly what I meant with my slippery slope argument. Approximately anyone can scribble a shitty rendition of a dog, and I'd agree that it should probably not be protected. But what if the input is an actually artistical line drawing and the system colorizes or enhances it? Is there enough that is "directly controlled by a human" to invalidate the current claim of "it's just random noise" that resulted in the comic not being recognized?
-
Comment on <deleted topic> in ~tech
DataWraith LinkInteresting. I wonder what the copyright office would think of the recent ControlNet, which allows you to turn, among other things, crude sketches into pictures or photos. Would that still not...The USCO said that since Midjourney produces an image first by "randomly generating noise," the process wasn't something that could be directly controlled by humans. Text prompts fed into the software don't guarantee it will create a particular image – therefore it is not a tool like Photoshop or GIMP.
Interesting. I wonder what the copyright office would think of the recent ControlNet, which allows you to turn, among other things, crude sketches into pictures or photos. Would that still not count as "directly controlled by humans" because the details are filled in by the model? How detailed would an input sketch have to be to count? To me, it seems like they've taken themselves onto a quite slippery slope here.
-
Comment on YouTube as a form of hard drive in ~comp
DataWraith Link ParentSomeone made a FUSE filesystem to store data in GMail, back when a few gigabytes of storage was a lot. You could also abuse the free tier of many data storage services via a Redundant Array of...Any website that hosts user data opens itself up to being used as storage.
Someone made a FUSE filesystem to store data in GMail, back when a few gigabytes of storage was a lot.
You could also abuse the free tier of many data storage services via a Redundant Array of Independant Clouds, that's even simpler. I can't find the original blog post anymore, but someone signed up for Dropbox and just about every other free cloud storage service and made a RAID (or RAIC, I guess) out of all of them by striping data across the different sync folders...
There's not really a clear need for it for most. But a single file could be distributed across multiple sites being made up of reddit comments, youtube, comments, imgur pictures, and in this case youtube videos.
There's lots of creative ways to store data (see: Harder drives).
The encoding doesn't even need to be obvious if it's steganographically hidden. Which dramatically reduces the amount of data the medium could hold but likely wouldn't be noticed.
You could also apply some sort of forward error correction, such as Fountain codes, to guard against some of the posts/images getting removed.
That said, all of this is eminently impractical versus just uploading a file to Freenet or sharing it via .onion services...
-
Comment on The prompt box is a minefield in ~tech
DataWraith Link ParentAh. I guess this is where we differ in opinion. If we step back from language generation for a second and focus on chess, you can either say 'a chess engine is artificially intelligent', or you...This task obviously does not require intelligence, because we can instruct a non-sapient computer to do it.
Ah. I guess this is where we differ in opinion.
If we step back from language generation for a second and focus on chess, you can either say 'a chess engine is artificially intelligent', or you can say 'playing chess does not require intelligence at all'. Either could be true, depending on your definition of intelligence.
Coming back to language modelling, to me it seems distasteful to say that using language well does not require intelligence though, so I'd rather go with "this thing is artificially intelligent" rather than "using language requires no intelligence whatsoever" (because, as you say, we can construct a computer that does it).
-
Comment on The prompt box is a minefield in ~tech
DataWraith Link ParentI feel reminded of what Kasparov's advisor said about Deep Blue when the chess computer beat the world chess champion: In other words, as you scale up a simple process like auto-completion or...Noone thinks of their smartphone auto-complete program as intelligent, so why do they think these bigger auto-completers are intelligent?
I feel reminded of what Kasparov's advisor said about Deep Blue when the chess computer beat the world chess champion:
As it goes deeper and deeper, it displays elements of strategic understanding. Somewhere out there, mere tactics are translating into strategy. This is the closest thing I've seen to computer intelligence. It's a weird form of intelligence, the beginning of intelligence. But you can feel it. You can smell it."
In other words, as you scale up a simple process like auto-completion or principal variation search, it may start to give you results that exceed the sum of its parts (tactics turn into strategy), and compound into intelligent behavior.
I don't consider the small-scale auto-complete on my phone to be intelligent, but I consider the larger-scale ChatGPT to have the quality of intelligence, in the original sense of the term "Artificial Intelligence" -- i.e. that it can do things that would require intelligence if a human were to do them.
-
Comment on AI-powered Bing Chat loses its mind when fed Ars Technica article / "It is a hoax that has been created by someone who wants to harm me or my service." in ~tech
DataWraith Linktl;dr: Thesis: The smiley at the end of a Bing Chat paragraph denotes the personality that was used to generate the preceding paragraph. I wonder what exactly the smileys at the end of a paragraph...tl;dr: Thesis: The smiley at the end of a Bing Chat paragraph denotes the personality that was used to generate the preceding paragraph.
I wonder what exactly the smileys at the end of a paragraph mean. At first I just thought the AI was using them wrong, because a lot of the emoticons don't seem to fit where it uses them, and thus it gives off creepy vibes. But then I noticed that they tended to, almost exclusively, appear at the end of a paragraph.
Just now found From Bing to Sydney, which describes, among other things, a different, malicious personality called Venom that uses a devil-emoticon at the end of a paragraph. That was just a hypothetical "anti-Sydney" that came up during conversation, but what if the smileys actually mean something?
This is probably my own pattern recognition going haywire, but...
Maybe Sydney and Venom are just two personalities that Bing Chat can take on? I don't have access myself, but judging from the screenshots, if there is no smiley at all, the answer tends to be generic and boring -- machine- or assistant-like. The smileys usually accompany a paragraph that could have been written by a person -- I associate that with the Sydney persona. Then there's the sad smiley, of which I can't really draw any conclusion because there's only one screenshot I saw that has it, but the text was very repetitive and the sentences very short, which is different from the normal sentence lengths of the other 'personalities'.
I'm probably imagining things... but I thought it was an interesting enough thought that I wanted to share it and see what y'all think.
-
Comment on Toolformer: Language models can teach themselves to use tools in ~tech
DataWraith LinkIt is fascinating to me that you can use a Large Language Model to generate new training data for said language model, which then improves performance on the tasks you care about after...It is fascinating to me that you can use a Large Language Model to generate new training data for said language model, which then improves performance on the tasks you care about after re-training.
In this case they're teaching the model to use tools by
- Giving a demonstration of tool use to the LLM, which only requires a few hand-written examples
- Asking the model to come up with many more examples similar to the demonstrations
- Filling in the generated examples with the output of the requested tool/API
- If the output from the tool improves perplexity, the example is added to the training set. In other words, if "knowing" the answer from, say, a calculator API improves the probability of generating the correct output, the tool use is shown to be beneficial and the example is added to the training set.
The most impressive version of this bootstrapping procedure I've seen so far is probably Anthropic's Constitutional AI (PDF), which takes in a "Constitution" of rules ("don't be racist", etc.) and then critiques its own past outputs on whether they adhere to the constitutional rules. Following that, they ask the model itself to rewrite the response to remove any violations of the constitution and use the result of that as part of a new training set, completing one step of the bootstrapping procedure.
-
Comment on Browser Session vs JWT tokens for authentication system for an app? in ~comp
DataWraith LinkWriting a REST API seems to not be that hard, but the devil is in the details. It is easy to make an API too tightly coupled to your own frontend so that it becomes harder for others to use the...Writing a REST API seems to not be that hard, but the devil is in the details.
- It is easy to make an API too tightly coupled to your own frontend so that it becomes harder for others to use the API, so keep that in mind.
- Browser sessions usually require cookie storage, which is inconvenient to deal with when you're writing an API client or just want to test things with
curl. - Because of that, instead of browser sessions, APIs usually use Bearer Tokens given in the
Authorizationheader. - Bearer Tokens can be JWTs, but you can also use custom ones (e.g. just generate a random Base64 string per user and store it in your database)
- If the API is exposed to the public, you'll want some sort of rate limiting in place (per user and per IP)
- Think about how you want to paginate results if you don't want to serve everything in one request (e.g. cursor-based pagination)
- I personally haven't used it, but tools like PostgREST can make serving an API simpler if you know your way around Postgres
- JWTs are something of a double-edged sword. There were security vulnerabilities in several popular libraries, and the advantage of using a JWT over a random or HMAC-signed token really only comes into play when you have multiple servers or microservices: One server (e.g. a Login microservice or external provider like Auth0) can sign a request, and if you pass that to another server, it can verify that the first server authorized the request. The advantage is that the user password or API-Key is only stored in that one location and does not have to be distributed to all API servers, but that only comes into play if you have multiple servers.
-
Comment on Five days in class with ChatGPT in ~tech
DataWraith (edited )Link ParentThe future is already here, it is just not very evenly distributed. ;) Deepmind's Sparrow works this way. Instead of answering immediately using its internalized knowledge, it can decide to do a...I imagine future tech will just do this step for me and link to the proofs.
The future is already here, it is just not very evenly distributed. ;)
Deepmind's Sparrow works this way. Instead of answering immediately using its internalized knowledge, it can decide to do a Google search using a query it formulates on the fly. Then it will summarize the top result(s) and show you a snippet and a link to the source.
Though one still has to be careful with it. IIUC, the evidence it cites does not support the summary itself 20% of the time, so I imagine the overall error rate is at least that high.
Edit: The way I phrased that may imply that access to Sparrow is publicly available, which is not the case yet.
-
Comment on Day 19: Not Enough Minerals in ~comp.advent_of_code
DataWraith LinkThis one looked like it would be similar to Day 16, but I underestimated how long it would take again. I wasn't going to do any more of the puzzles because each takes at least an hour (this one...This one looked like it would be similar to Day 16, but I underestimated how long it would take again.
I wasn't going to do any more of the puzzles because each takes at least an hour (this one took me close to 3h), but I sensed an opportunity to use an algorithm I had never found practical use for so far, and I had some time to kill.
Algorithm
Iterated Width
Width-based Planning is a search method that was, among other things, used successfully to play ATARI games in almost-realtime. The idea is to use a Breadth-First Search with a novelty pruning rule.
Each state is associated with features or atoms that are true for that state (e.g. "geodes=7"). The algorithm is called with increasing widths starting from 1. New states are pruned if there is no n-tuple of features (of size width) that has not already been seen during the search.So if a state has the atoms 'A', 'B' and 'C', then IW(1) prunes the state if A, B and C have been seen before, and IW(2) prunes a state if (A, B), (A, C), and (B, C) have all been seen before. It is known that many problems have a low intrinsic width, so they are solvable using few calls to the IW search procedure, even if they have many different features.
I elected to use the complete search state of the problem (i.e. one atom for each robot and ore count, as well as the time remaining, and the current robot in production).
Apart from not knowing whether it would work at all, the main problem was that IW is an algorithm that is used for planning when you know the goal state, and here we didn't, so there was no way to know when to stop increasing the width parameter. This is probably highly unsound, but I stopped incrementing once the same result was returned twice in succession, and that worked.
The running time for both parts together is between 15 and 20 seconds, and that's with using multiple cores, so that could be better...
Part 1 & 2 (Rust)
use std::collections::{HashSet, VecDeque}; use std::hash::{Hash, Hasher}; use itertools::Itertools; use rayon::prelude::*; use wyhash::WyHash; // For hashing. Faster than rust's default SIPhash use parser::parse; mod parser; // Parses the puzzle input (omitted) #[derive(Clone, Debug)] pub struct Blueprint { number: usize, ore_robot_ore_cost: usize, clay_robot_ore_cost: usize, obsidian_robot_ore_cost: usize, obsidian_robot_clay_cost: usize, geode_robot_ore_cost: usize, geode_robot_obsidian_cost: usize, } #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] enum Atom { Time(usize), Ore(usize), Clay(usize), Obsidian(usize), Geodes(usize), OreRobot(usize), ClayRobot(usize), ObsidianRobot(usize), GeodeRobot(usize), } #[derive(Debug, Clone, PartialEq, Eq)] pub struct SearchState { time_remaining: usize, ore: usize, clay: usize, obsidian: usize, geodes: usize, ore_robots: usize, clay_robots: usize, obsidian_robots: usize, geode_robots: usize, currently_building: Option<Atom>, // This is a bit unclean, but eh. } impl SearchState { // Advance the simulation by one minute. // This is quite inelegant, but I'm out of time and won't refactor it now. pub fn tick(&self) -> Self { let time_remaining = self.time_remaining - 1; let ore = self.ore + self.ore_robots; let clay = self.clay + self.clay_robots; let obsidian = self.obsidian + self.obsidian_robots; let geodes = self.geodes + self.geode_robots; match self.currently_building { Some(Atom::OreRobot(_)) => Self { time_remaining, ore, clay, obsidian, geodes, ore_robots: self.ore_robots + 1, currently_building: None, ..*self }, Some(Atom::ClayRobot(_)) => Self { time_remaining, ore, clay, obsidian, geodes, clay_robots: self.clay_robots + 1, currently_building: None, ..*self }, Some(Atom::ObsidianRobot(_)) => Self { time_remaining, ore, clay, obsidian, geodes, obsidian_robots: self.obsidian_robots + 1, currently_building: None, ..*self }, Some(Atom::GeodeRobot(_)) => Self { time_remaining, ore, clay, obsidian, geodes, geode_robots: self.geode_robots + 1, currently_building: None, ..*self }, None => Self { time_remaining, ore, clay, obsidian, geodes, ..*self }, _ => unreachable!(), } } // The atoms of a search state pub fn atoms(&self) -> impl Iterator<Item = Atom> + '_ { let mut atoms = vec![ Atom::Time(self.time_remaining), Atom::Ore(self.ore), Atom::Clay(self.clay), Atom::Obsidian(self.obsidian), Atom::Geodes(self.geodes), Atom::OreRobot(self.ore_robots), Atom::ClayRobot(self.clay_robots), Atom::ObsidianRobot(self.obsidian_robots), Atom::GeodeRobot(self.geode_robots), ]; if self.currently_building.is_some() { atoms.push(self.currently_building.unwrap()); } atoms.into_iter() } // Buy the robots. // // Each function checks if the purchase is valid, and if so, returns a new // search state with the purchase made. // // There are minor pruning rules here. For example, we don't buy a // obsidian bot if we already have enough bots so we can afford to buy // a geode bot every turn (wrt obsidian cost). pub fn buy_geode_bot(&self, blueprint: &Blueprint) -> Option<Self> { if self.time_remaining > 1 && self.obsidian >= blueprint.geode_robot_obsidian_cost && self.ore >= blueprint.geode_robot_ore_cost { Some(Self { geode_robots: self.geode_robots, ore: self.ore - blueprint.geode_robot_ore_cost, obsidian: self.obsidian - blueprint.geode_robot_obsidian_cost, currently_building: Some(Atom::GeodeRobot(1)), ..*self }) } else { None } } pub fn buy_obsidian_bot(&self, blueprint: &Blueprint) -> Option<Self> { if self.time_remaining > 1 && self.clay >= blueprint.obsidian_robot_clay_cost && self.ore >= blueprint.obsidian_robot_ore_cost && self.obsidian_robots < blueprint.geode_robot_obsidian_cost { Some(Self { obsidian_robots: self.obsidian_robots, ore: self.ore - blueprint.obsidian_robot_ore_cost, clay: self.clay - blueprint.obsidian_robot_clay_cost, currently_building: Some(Atom::ObsidianRobot(1)), ..*self }) } else { None } } pub fn buy_clay_bot(&self, blueprint: &Blueprint) -> Option<Self> { if self.time_remaining > 1 && self.ore >= blueprint.clay_robot_ore_cost && self.clay_robots < blueprint.obsidian_robot_clay_cost { Some(Self { clay_robots: self.clay_robots, ore: self.ore - blueprint.clay_robot_ore_cost, currently_building: Some(Atom::ClayRobot(1)), ..*self }) } else { None } } pub fn buy_ore_bot(&self, blueprint: &Blueprint) -> Option<Self> { let max_cost = blueprint .ore_robot_ore_cost .max(blueprint.clay_robot_ore_cost) .max(blueprint.obsidian_robot_ore_cost) .max(blueprint.geode_robot_ore_cost); if self.time_remaining > blueprint.ore_robot_ore_cost + 1 && self.ore >= blueprint.ore_robot_ore_cost && self.ore_robots < max_cost { Some(Self { ore_robots: self.ore_robots, ore: self.ore - blueprint.ore_robot_ore_cost, currently_building: Some(Atom::OreRobot(1)), ..*self }) } else { None } } // Prune checks if the state should be pruned according to the IW(k) novelty // rule. If so, it returns None, otherwise it returns the state itself and a // Vec of the atoms that were newly seen. // // Again, this could probably done more elegantly. // pub fn prune(self, true_atoms: &HashSet<u64>, width: usize) -> Option<(Self, Vec<u64>)> { let mut prune = true; let mut new_atoms = Vec::new(); for atom in self.atoms().combinations(width) { let mut h = WyHash::default(); atom.hash(&mut h); let atom_hash = h.finish(); if true_atoms.contains(&atom_hash) { continue; } else { prune = false; new_atoms.push(atom_hash); } } if prune { return None; } Some((self, new_atoms)) } } // Given a blueprint, calculate how many geodes we can open in the given time fn calculate_openable_geodes(blueprint: Blueprint, time_remaining: usize, width: usize) -> usize { let mut q = VecDeque::new(); let mut true_atoms: HashSet<u64> = HashSet::new(); let mut best = 0; let initial_state = SearchState { time_remaining, ore: 0, clay: 0, obsidian: 0, geodes: 0, ore_robots: 1, clay_robots: 0, obsidian_robots: 0, geode_robots: 0, currently_building: None, }; q.push_back(initial_state); while let Some(state) = q.pop_front() { if state.time_remaining == 0 { best = best.max(state.geodes); continue; } let next_state = state.tick(); // Always try to buy a geode robot if possible, not doing so does not make sense if let Some(buy_geode_bot) = next_state.buy_geode_bot(&blueprint) { if let Some((novel, new_atoms)) = buy_geode_bot.prune(&true_atoms, width) { q.push_back(novel); true_atoms.extend(new_atoms); } } else { // If we can't buy a geode cracker, try the other options if let Some(buy_obsidian_bot) = next_state.buy_obsidian_bot(&blueprint) { if let Some((novel, new_atoms)) = buy_obsidian_bot.prune(&true_atoms, width) { q.push_back(novel); true_atoms.extend(new_atoms); } } if let Some(buy_clay_bot) = next_state.buy_clay_bot(&blueprint) { if let Some((novel, new_atoms)) = buy_clay_bot.prune(&true_atoms, width) { q.push_back(novel); true_atoms.extend(new_atoms); } } if let Some(buy_ore_bot) = next_state.buy_ore_bot(&blueprint) { if let Some((novel, new_atoms)) = buy_ore_bot.prune(&true_atoms, width) { q.push_back(novel); true_atoms.extend(new_atoms); } } // Do nothing if let Some((novel, new_atoms)) = next_state.prune(&true_atoms, width) { q.push_back(novel); true_atoms.extend(new_atoms); } } } best } // Repeatedly increase the IW width until we get the same result twice // or the width exceeds 4. fn evaluate_blueprint(blueprint: Blueprint, time: usize) -> usize { let mut width = 1; let mut prev_result = None; while width < 4 { let result = calculate_openable_geodes(blueprint.clone(), time, width); if Some(result) == prev_result { break; } prev_result = Some(result); width += 1; } prev_result.unwrap() } fn part1(blueprints: Vec<Blueprint>) -> usize { blueprints .into_par_iter() .map(|bp| bp.number * evaluate_blueprint(bp, 24)) .sum::<usize>() } fn part2(blueprints: Vec<Blueprint>) -> usize { blueprints .into_par_iter() .map(|bp| evaluate_blueprint(bp, 32)) .reduce(|| 1, |a, b| a * b) } fn input_text() -> &'static str { include_str!("../input.txt") } fn main() { dbg!(part1(parse(input_text()))); let p2_blueprints = parse(input_text()); dbg!(part2( p2_blueprints.iter().take(3).cloned().collect::<Vec<_>>() )); } -
Comment on Day 16: Proboscidea Volcanium in ~comp.advent_of_code
DataWraith LinkI haven't done any of the other puzzles this year, but the description looked fun, so I gave Part I a shot. Of course it ended up being way harder than I imagined; I'm not even going to attempt...I haven't done any of the other puzzles this year, but the description looked fun, so I gave Part I a shot.
Of course it ended up being way harder than I imagined; I'm not even going to attempt Part II.
Part 1 (Rust)
I've omitted the code for parsing and pathfinding -- the former is just standard
nomparsing and the latter is (a) ugly and (b) a direct translation from Python code on Wikipedia.use std::collections::{BTreeMap, VecDeque}; use ndarray::Array2; use parser::parse; mod parser; // Parses the puzzle input mod seidel; // Computes all-pairs shortest paths, used by parser module to complete the Puzzle struct (https://en.wikipedia.org/wiki/Seidel%27s_algorithm) #[derive(Debug)] pub struct Puzzle { indices: BTreeMap<String, usize>, flow_rate: Vec<usize>, adjacency: Array2<usize>, path_lengths: Array2<usize>, } #[derive(Debug, Clone, PartialEq, Eq)] pub struct SearchState { unopened: Vec<usize>, current_position: usize, remaining_time: usize, cumulative_flow: usize, pressure_released: usize, } /// A breadth-first search on the tree implied by the SearchState transitions. /// /// It prunes branches that cannot beat the current best (ala Branch & Bound). /// This improves the runtime on my puzzle input from 250ms to 12ms. It solves /// both the test input and my actual input, but I'm not entirely sure if it is /// actually sound, or if there are inputs for which it will fail. fn part1(puzzle: Puzzle) -> usize { let mut best = 0; let mut q = VecDeque::new(); let initial_state = SearchState { // Filter out valves with flow rate 0, no point in opening them unopened: puzzle .indices .values() .cloned() .filter(|idx| puzzle.flow_rate[*idx] > 0) .collect(), current_position: puzzle.indices["AA"], remaining_time: 30, cumulative_flow: 0, pressure_released: 0, }; q.push_back(initial_state); while let Some(state) = q.pop_front() { if state.unopened.is_empty() || state.remaining_time == 0 { // We've ran out of time or valves to open best = best.max(state.pressure_released + state.remaining_time * state.cumulative_flow); continue; } for unopened in state.unopened.iter() { let mut neighbor = state.clone(); let movement_time = puzzle.path_lengths[[state.current_position, *unopened]]; if movement_time >= neighbor.remaining_time { // Not enough time left, count out remaining flow neighbor.pressure_released += neighbor.remaining_time * neighbor.cumulative_flow; neighbor.remaining_time = 0; } else { // Go to valve, pressure is released while we are en route neighbor.remaining_time -= movement_time; neighbor.pressure_released += movement_time * neighbor.cumulative_flow; neighbor.current_position = *unopened; // Open valve, pressure is released while we do it neighbor.remaining_time -= 1; neighbor.pressure_released += neighbor.cumulative_flow; neighbor.unopened.retain(|idx| idx != unopened); neighbor.cumulative_flow += puzzle.flow_rate[*unopened]; } if neighbor.pressure_released + neighbor.remaining_time * neighbor.cumulative_flow > best { q.push_back(neighbor); } } } best } fn part1_input() -> &'static str { include_str!("../input.txt") } fn main() { dbg!(part1(parse(part1_input()))); } -
Comment on Developers/sysadmins: What marketing terminology do you find most enraging? in ~comp
DataWraith LinkNot sure if this qualifies as "marketing to techies" (it probably doesn't), but I always groan when someone advertises "military grade encryption". That usually means AES if you dig further, but...Not sure if this qualifies as "marketing to techies" (it probably doesn't), but I always groan when someone advertises "military grade encryption". That usually means AES if you dig further, but to me it also signals that you'd better give wide berth to whatever product they're selling...
Edit: Eh, looks like the reddit post already had that.
-
Comment on What programming/technical projects have you been working on? in ~comp
DataWraith LinkI've been developing a StarCraft II bot in Rust for the past few weeks. The bot beats the strongest non-cheating built-in AI more than 85% of the time using nothing but Marines. In order to...I've been developing a StarCraft II bot in Rust for the past few weeks.
The bot beats the strongest non-cheating built-in AI more than 85% of the time using nothing but Marines. In order to achieve this, it uses speed-mining, which exploits the practically limitless APM (actions per minute) of a bot to increase resource gathering rate by ~12% (so I guess it is cheating -- kind of).
Implementing speed-mining in particular was tricky and took several days of experimentation and much gnashing of teeth -- a lot of the example code I looked at for it was just plain wrong and/or ineffective, and I also ran into a bug or limitation in the SC2 interface that cost me a lot of time to figure out.
I also used the project as an excuse to finally test GitHub Copilot. In the beginning it was more annoying than helpful and it took me a few days to get the hang of it, but now that I know its limitations, I find it very useful, especially when prototyping: just write a comment (or even the start of a comment) and it will fill in the blanks, sometimes with an elegant approach I would not have thought of myself. I still wouldn't want to use it for work stuff though, because (a) it potentially could leak the source code to Microsoft and (b) it can (and does) introduce subtle problems into the code if you're not vigilant.
Despite its success against the built-in AI, the bot is still nowhere near good enough to be uploaded to the SC2AI ladder because it is lacking so many basic skills (e.g. making anything other than Marines...).
Working on this has been extremely addictive and exhausting, enough so that it could potentially lead to problems if I keep it up, so, unfortunately, I've decided to shelve the project for now and wrote this post as a conclusion of sorts.
-
Comment on Let's talk about ChatGPT in ~tech
DataWraith Link ParentGPT is a Transformer neural network (GPT stands for General Pre-trained Transformer). The Illustrated Transformer by Jay Alammar is a fantastic resource that explains how a Transformer works in...GPT is a Transformer neural network (GPT stands for General Pre-trained Transformer).
The Illustrated Transformer by Jay Alammar is a fantastic resource that explains how a Transformer works in detail. GPT does not use the encoder part of the network, but from what I understand, it is otherwise a vanilla transformer architecture scaled-up to a massive size.
ChatGPT appears to have been further evolved from GPT3 using reinforcement learning and a curated training set.
-
Comment on Day 3: Rucksack Reorganization in ~comp.advent_of_code
DataWraith Link ParentI thought this would be nicely doable using reduce, but it turns out that that solution is far from elegant. Reduce multiple HashSets use std::collections::HashSet; fn main() { let a =...I really wish rusts HashSet implentation allowed finding the intersection of more than one other hashset at a time...
I thought this would be nicely doable using reduce, but it turns out that that solution is far from elegant.
Reduce multiple HashSets
use std::collections::HashSet; fn main() { let a = HashSet::from([1, 2, 3]); let b = HashSet::from([1, 3, 4]); let c = HashSet::from([1, 4, 5]); let d = HashSet::from([1, 2, 7]); println!("{:?}", [a, b, c, d].into_iter().reduce(|a, b| a.intersection(&b).map(|x| *x).collect())); } -
Comment on Resources for learning more programming fundamentals in ~comp
DataWraith LinkThis is more of a meta-suggestion, but I'd suggest that you simply pick a project that is challenging and get programming -- if the problem you choose is complex enough, you'll eventually be...This is more of a meta-suggestion, but I'd suggest that you simply pick a project that is challenging and get programming -- if the problem you choose is complex enough, you'll eventually be needing specialized data structures to make it work (or at least to make it work fast). Learning about algorithms and data structures in a vacuum is much harder in my experience. Be sure to choose something you can be passionate about, that you actually want to work on.
One suggestion I've seen is that people should start writing a blog-backend. Yes, it is kind of pointless since there are so many different hosted solutions, but it is a problem that is easy to scale up in complexity. You can have something working in a couple of hours, but that doesn't stop you from adding more bells and whistles. A blog engine could, for example, lead into writing a spam filter for comment submissions, which means you could be learning about HMAC, Naive Bayes, Feature Hashing, the Count-Min Sketch, the basics of machine learning, etc., etc. Just follow whatever trail seems most interesting.
You can also drill down fairly easily with such a project by replacing things you would normally use a library or external application for, e.g. "how do I do this without using MySQL?", "How does the markdown parser work? " (Parsing is a whole rabbit hole on its own...)
In order to decide on appropriate algorithms and data structures, you should probably at least learn the basics of Big O-notation if you haven't yet.
Personally I like programming competitions like BattleSnake for programming practice. Writing a bot for these competitions can be as simple as glueing together a few if-statements, but if you want to climb in the leaderboard, it can become more complex than a chess engine. At the very least you'll likely learn about search algorithms (A*, Dijkstra, Depth-First, Breadth-First, Best-First) and the required data structures (stack, heap, queue, deque), as well as game tree search, how and when to cache stuff using transposition tables/hash maps, etc.
One last comment: math skills aren't necessarily required to begin with -- my math skills are still atrocious, but I understand a lot of the mathematical notation now, simply through having seen them often in different contexts.
-
Comment on Introducing Whisper (OpenAI speech recognition model) in ~comp
DataWraith (edited )Link ParentFrom what I understand, the model works on 30s snippets of audio in order to achieve the quality it gets, so it won't run interactively no matter what GPU you throw at it. Translation does not...Certainly not real time/interactive
From what I understand, the model works on 30s snippets of audio in order to achieve the quality it gets, so it won't run
in real-timeinteractively no matter what GPU you throw at it.Translation does not seem to be noticeably slower than transcription in my testing, though the quality of the translation seems to be worse than if you transcribe it first and then run the text through a separate translator.
I'm using GitHub Copilot for my personal projects, currently mainly written in Rust.
In the beginning I was not sure whether it would be worth the subscription price, but it seems to have improved a lot within the last few months, and now I no longer have doubts.
I type relatively fast, but even so, the completions save a ton of time when the tool can infer what I'm trying to do.
It's especially good for repetitive tasks, and if you're implementing a known algorithm (say, calculating the running variance of a stream of data) it will often suggest most of the necessary code.
You still have to check that code for correctness, but the number of instances in which Copilot was wrong feels like it has gone down over time.
It's also nice to get completions for my comments to see if the phrasing I had in mind was actually plausible English.
I also occasionally use ChatGPT when I am researching something complicated; not sure if that counts as day-to-day. For example, it recently taught me about the Hypergeometric distribution, which I would not have known to look for on Google in the context of my problem.