whs's recent activity
-
Comment on Riot’s Vanguard comes to League in ~games
-
Comment on Backdoor in upstream libxz targeting sshd in ~comp
whs LinkWith the current mistrust against liblzma and its complex code, I wonder if one could write a simple drop-in replacement for it. Perhaps a focus on simple code over performance might also result...With the current mistrust against liblzma and its complex code, I wonder if one could write a simple drop-in replacement for it. Perhaps a focus on simple code over performance might also result in somewhat usable performance too, like Serenity's Ladybird Browser.
-
Comment on Introducing Steam Families in ~games
whs Link ParentFor comparison, Google Family also have similar one year cooldown when used to share paid services like YouTube Premium or paid storage.For comparison, Google Family also have similar one year cooldown when used to share paid services like YouTube Premium or paid storage.
-
Comment on Steam Spring Sale suggestions in ~games
whs Link ParentAh. I like those genre and have played Factorio & Satisfactory. I like the automation part and that require too much thinking and it's not podcast-able for me. Adding to that list I find Oxygen...Ah. I like those genre and have played Factorio & Satisfactory. I like the automation part and that require too much thinking and it's not podcast-able for me.
Adding to that list I find Oxygen Not Included fun in easy mode. The early game is brutal with somewhat fixed opening moves, but the game open up in mid game. Since things take time to build it can be played with other things in the background. Unfortunately I quit to play Trails into Reverie and now I can't continue the save because they nerfed starvation fish ranching in the last patch (For under $10 and a game released in 2019 it is still updated like a live service game! They're planning to focus on a paid DLC this year though).
If anyone is buying, the Spaced Out expansion is a different experience (like StarCraft and Brood Wars has the same base unit with different balance). With so much mechanics to learn in vanilla game I'd not recommend it for the first time player.
-
Comment on Steam Spring Sale suggestions in ~games
whs Link ParentI played through all small-medium maps in VCD with friends. Got motion sickness but I push through. The annoying part is when your friend knock over your filthy bucket and you have to start over....I played through all small-medium maps in VCD with friends. Got motion sickness but I push through. The annoying part is when your friend knock over your filthy bucket and you have to start over. Or when your friends put footprints over your completed section. The multiplayer is also super laggy, adding to the motion sickness, if there's too much decals but setting low decals limit feel like cheating.
I think PowerWash Simulator got it that the game doesn't have any penalty, like it could've simulated hose tangling, max hose distance, breakable items, filthy water, PvP injury but it choose not to. Another example is Lawn Mowing Simulator where they could've made the lawnmover drive like a car in GTA, but it choose a more realistic driving. They also penalize when you mow over flowerbeds making it's not totally mindless.
-
Comment on Steam Spring Sale suggestions in ~games
whs (edited )LinkI need a recommendation for a new podcast game (or games that you play while watching other media) that can be played for a long time. Here's what I've been playing in this genre: Diablo IV - It's...I need a recommendation for a new podcast game (or games that you play while watching other media) that can be played for a long time. Here's what I've been playing in this genre:
- Diablo IV - It's fun to help people power level, but the game is almost dead in season 3. The annoying part is itemization which either you go through them quickly and miss something, or you spend 30 mins reading through two entire junk tab you accumulate while your party keep telling you to hurry up as they complete another dungeon. They say they'll improve this in the next season
- Euro Truck Simulator 2 (and the MMO mod ETS2MP) - It's almost perfect for podcast, but it get repetitive (and sleepy). If you're playing the MMO mod you can't pause to tab out of the game - you have to pull over which may take half a minute.
- Death Stranding - I love this game. The standard edition was on Game Pass but already left. The game open up around chapter 6 iirc, where you get cars and road building. Most people quit before that point as the first map is mostly exercise in walking than the second one. The problem is the game has a long list of repeatable delivery that I believe don't have a tracker whether you have completed them or not. And some of them goes through enemy controlled area (human or ghost) which may require audio clue to pinpoint attacks.
- Tetris Effect - I'm not good at Tetris so I have to focus. It doesn't work as a podcast game for me. I think it also already left Game Pass.
- PowerWash Simulator - I love this game. I think I completed the whole game twice and I bought all the (overpriced?) DLC day one. Unfortunately I'm bored to replay it for the third time
- (edited) Old School RuneScape - I grinded both RS3 and OSRS like two years ago. It even playable when I do my day job. Unfortunately I max WC on both games and there's no WC2 for OSRS. As for RS3 I tried getting back into it, but Player Owned Ports FOMO make me stay away from it since I'm like half way to Completionist Cape.
-
Comment on Steam Winter Sale 2023: Hidden gems in ~games
whs Link ParentWhat I didn't like about Obra Dinn is that the graphics style trigger my motion sickness so badly, but the story keep me very intrigued that I have to force myself to finish it in session of 1-2...What I didn't like about Obra Dinn is that the graphics style trigger my motion sickness so badly, but the story keep me very intrigued that I have to force myself to finish it in session of 1-2 hrs. The game has a "native resolution" option which is even smaller than 640x480 and that help with the motion sickness. It's weird playing a modern 3D games in resolution smaller than a GBA game...
-
Comment on Steam Winter Sale 2023: Hidden gems in ~games
whs Link ParentI'd like to add that there's also a small story, and even an ending once you have found all the combos.I'd like to add that there's also a small story, and even an ending once you have found all the combos.
-
Comment on Does Linux From Scratch actually teach you anything? in ~comp
whs LinkI did LFS over 10 years ago. Here's a few things I learned LFS list what each packages you're compiling provides - I learned that many "Linux tools" is actually part of the coreutils software The...I did LFS over 10 years ago. Here's a few things I learned
- LFS list what each packages you're compiling provides - I learned that many "Linux tools" is actually part of the coreutils software
- The GCC section talk about cross compiling and stuff. I think a question that many people will ask is how is a compiler was first created. You'll realize the "from scratch" part is false when you use gcc in the LFS CD to build your gcc so that's how the chicken and egg problem is solved in this case.
- Side note: I recently blogged about that question, and I referenced that LFS section that it actually answer the question of how compiler in a new platform was first created - by cross compiling, and how exactly does that process work.
- It demystified Linux "distribution" that a Linux system is not developed by Canonical (the Ubuntu company) or the Debian project, but in fact it was developed piece by piece by several projects, then the "distribution" is a compilation of required projects
- Although LFS didn't teach me this, but it was a stepping stone for me to understand the inner working of a Linux system. Even today Windows feel like a blackbox to me - I don't know how its booted, which software provide the GUI, who start the service manager service, where on the disk is the OS configuration (registry) is stored. While you could read about all those questions in Linux, LFS provide a hands-on approach and for my learning style I don't feel like I can apply those knowledge without a hands on experience.
It's probably like that "Kubernetes the Hard Way" guide, but I haven't read that one yet.
-
Comment on Day 16: The Floor Will Be Lava in ~comp.advent_of_code
whs LinkI thought it would be easy enough to use C++, but I already uninstalled CLion so I just use VSCode. That wasn't pleasant to debug, and the complex dict key make it unpleasant to write compared to...I thought it would be easy enough to use C++, but I already uninstalled CLion so I just use VSCode. That wasn't pleasant to debug, and the complex dict key make it unpleasant to write compared to higher level languages.
Part 2 runtime is 3.36s on my machine with brute force solving.
#include <iostream> #include <string> #include <vector> #include <set> #include <utility> using namespace std; enum Dir { DIR_UP, DIR_LEFT, DIR_DOWN, DIR_RIGHT }; typedef pair<int, int> Coord; const Coord advanceInDir(const Coord position, const Dir direction){ switch(direction){ case DIR_UP: return make_pair(position.first - 1, position.second); case DIR_LEFT: return make_pair(position.first, position.second - 1); case DIR_DOWN: return make_pair(position.first + 1, position.second); case DIR_RIGHT: return make_pair(position.first, position.second + 1); } __builtin_unreachable(); } typedef pair<Coord, Dir> WalkedDir; int solve1(const vector<string> &problem, Coord position, Dir direction, set<WalkedDir> &walked){ WalkedDir walkedDir = make_pair(position, direction); if (walked.contains(walkedDir)) { return 0; } if (position.first < 0 || position.first >= problem.size() || position.second < 0 || position.second >= problem[0].size()) { return 0; } walked.insert(walkedDir); // cout << "at position " << position.first << " " << position.second << endl; const char curChar = problem[position.first][position.second]; if (curChar == '.') { return solve1(problem, advanceInDir(position, direction), direction, walked); } else if (curChar == '\\') { switch(direction){ case DIR_UP: // \ // | return solve1(problem, advanceInDir(position, DIR_LEFT), DIR_LEFT, walked); case DIR_LEFT: // \-- return solve1(problem, advanceInDir(position, DIR_UP), DIR_UP, walked); case DIR_DOWN: // | // \ .. return solve1(problem, advanceInDir(position, DIR_RIGHT), DIR_RIGHT, walked); case DIR_RIGHT: // --\ .. return solve1(problem, advanceInDir(position, DIR_DOWN), DIR_DOWN, walked); } } else if (curChar == '/') { switch(direction){ case DIR_UP: // / // | return solve1(problem, advanceInDir(position, DIR_RIGHT), DIR_RIGHT, walked); case DIR_LEFT: // /-- return solve1(problem, advanceInDir(position, DIR_DOWN), DIR_DOWN, walked); case DIR_DOWN: // | // / return solve1(problem, advanceInDir(position, DIR_LEFT), DIR_LEFT, walked); case DIR_RIGHT: // --/ return solve1(problem, advanceInDir(position, DIR_UP), DIR_UP, walked); } } else if (curChar == '|') { switch(direction){ case DIR_UP: case DIR_DOWN: // pointy end return solve1(problem, advanceInDir(position, direction), direction, walked); case DIR_LEFT: case DIR_RIGHT: // flat end solve1(problem, advanceInDir(position, DIR_UP), DIR_UP, walked); solve1(problem, advanceInDir(position, DIR_DOWN), DIR_DOWN, walked); return 1; } } else if (curChar == '-') { switch(direction){ case DIR_UP: case DIR_DOWN: // flat end solve1(problem, advanceInDir(position, DIR_LEFT), DIR_LEFT, walked); solve1(problem, advanceInDir(position, DIR_RIGHT), DIR_RIGHT, walked); return 1; case DIR_LEFT: case DIR_RIGHT: // pointy end return solve1(problem, advanceInDir(position, direction), direction, walked); } } else { cout << "wtf is " << curChar << "??" << endl; throw new runtime_error("wtf"); } return walked.size(); } set<Coord> toCoordSet(const set<WalkedDir> walked) { set<Coord> out; for(WalkedDir d : walked) { out.insert(d.first); } return out; } void printWalkDiagram(int w, int h, const set<Coord> &walked) { for(int hi = 0; hi < h; hi++){ for(int wi = 0; wi < w; wi++){ if (walked.contains(make_pair(hi, wi))) { cout << "#"; }else{ cout << "."; } } cout << endl; } } int main() { vector<string> problem; for(;;) { string input; getline(cin, input); if(input.empty()){ break; } problem.push_back(input); } /*/ // part1 set<WalkedDir> walked; solve1(problem, make_pair(0, 0), DIR_RIGHT, walked); set<Coord> coords = toCoordSet(walked); printWalkDiagram(problem[0].size(), problem.size(), coords); cout << coords.size() << endl; /**/ /**/ // part 2 int maxTiles = 0; // top row for(int i = 0; i < problem[0].size(); i++) { set<WalkedDir> walked; solve1(problem, make_pair(0, i), DIR_DOWN, walked); set<Coord> coords = toCoordSet(walked); maxTiles = max(static_cast<int>(coords.size()), maxTiles); } // bottom row for(int i = 0; i < problem[0].size(); i++) { set<WalkedDir> walked; solve1(problem, make_pair(problem.size() - 1, i), DIR_UP, walked); set<Coord> coords = toCoordSet(walked); maxTiles = max(static_cast<int>(coords.size()), maxTiles); } // left row for(int i = 0; i < problem.size(); i++) { set<WalkedDir> walked; solve1(problem, make_pair(i, 0), DIR_RIGHT, walked); set<Coord> coords = toCoordSet(walked); maxTiles = max(static_cast<int>(coords.size()), maxTiles); } // right row int rightRow = problem[0].size() - 1; for(int i = 0; i < problem.size(); i++) { set<WalkedDir> walked; solve1(problem, make_pair(rightRow, 1), DIR_LEFT, walked); set<Coord> coords = toCoordSet(walked); maxTiles = max(static_cast<int>(coords.size()), maxTiles); } cout << maxTiles << endl; /**/ return 0; } -
Comment on Day 15: Lens Library in ~comp.advent_of_code
whs Link ParentThanks for the suggestion. I'm only familiar with for..empty in Django template so initially I thought that is what for..else is for.Thanks for the suggestion. I'm only familiar with for..empty in Django template so initially I thought that is what for..else is for.
-
Comment on Day 15: Lens Library in ~comp.advent_of_code
whs (edited )LinkRank 674! Wow, that was easier than expected. I saved Python for last as I thought the problem would get progressively harder. If I know it was this easy I might have used C. Python was my third...Rank 674! Wow, that was easier than expected. I saved Python for last as I thought the problem would get progressively harder. If I know it was this easy I might have used C.
Python was my third language, after Visual Basic (that I didn't know how to use if or loops) and PHP. My code quality was getting very bad that I wrote my blog in a single PHP file, and with a lot of one line ifs. So, I thought I should learn a language that forcibly make you write readable code. The choice was either Python, or Ruby. And I picked Python as I thought Ruby's
endmake it inferior to Python. A decade and a half later, I think I made the right choice as Python is a lot more popular. Although I only see employers here asking for Ruby backend engineers and not Python where it get more used in data-related fields.And with that I've wrote & reminiscence all 15 languages I've written in all my life in AoC. Thanks for the trip down memory lane. After this, I don't know. Maybe I'll quit, maybe I'll write more Rust, C or C++ to get some practice in.
Part 1
def hash(v: str): out = 0 for ch in v: out += ord(ch) out = out * 17 out = out % 256 return out assert hash("HASH") == 52 if __name__ == "__main__": problems = input().split(",") out = [hash(p) for p in problems] print(sum(out))Part 2
import re from aoc import hash boxes = [list() for x in range(256)] problems = input().split(",") for problem in problems: parts = re.split('([=-])', problem) box_index = hash(parts[0]) mutating_box = boxes[box_index] if parts[1] == '-': for item in mutating_box: if item[0] == parts[0]: mutating_box.remove(item) break elif parts[1] == '=': existing = False for item in mutating_box: if item[0] == parts[0]: item[1] = parts[2] existing = True break if not existing: mutating_box.append([parts[0], parts[2]]) print(boxes) out = 0 for index, content in enumerate(boxes): for lensIndex, lens in enumerate(content): out += (1 + index) * (lensIndex + 1) * int(lens[1]) print(out) -
Comment on Day 14: Reflector Dish in ~comp.advent_of_code
whs LinkTwo more languages to go. And of course it has to be Go today. I learned Go on the job during my first year. My first large open source contribution was written in Go (dnscontrol), and the...Two more languages to go. And of course it has to be Go today. I learned Go on the job during my first year. My first large open source contribution was written in Go (dnscontrol), and the maintainer even blogged that he have seen many new contributor mention that it was their first Go code.
I thought about pattern detection, but I thought the problem probably can be designed to create very long patterns that is not feasibly storeable, or the pattern might lies in the individual rotations in a cycle. After seeing visualizations on Reddit, I decided to give the simplest solution a Go
package main import ( "bytes" "fmt" "io" "os" "slices" "strings" ) func main() { input, err := io.ReadAll(os.Stdin) if err != nil { panic(err) } fmt.Println("start") problem := parse(input) // part 1 //for shiftUp(problem) { //} // part 2 steps := make([]string, 0, 10000) steps = append(steps, problemToString(problem)) var repeatingIndex int iterationLeft := 0 iterationCount := 1000000000 for i := 0; i < iterationCount; i++ { spinCycle(problem) if i%1_000_000 == 0 { fmt.Printf("cycle %d\n", i) } problemString := problemToString(problem) repeatingIndex = slices.Index(steps, problemString) if repeatingIndex != -1 { fmt.Printf("found cycle at %d - %d\n", repeatingIndex, i) iterationLeft = iterationCount - i - 1 break } steps = append(steps, problemString) } // at the break, problem == steps[repeatingIndex] patternLength := len(steps) - repeatingIndex problem = parse([]byte(steps[repeatingIndex+(iterationLeft%patternLength)])) fmt.Println(problemToString(problem)) fmt.Println(countLoad(problem)) } func problemToString(p [][]byte) string { var out strings.Builder for _, l := range p { out.Write(l) out.WriteRune('\n') } return out.String() } func parse(input []byte) [][]byte { return bytes.Split(bytes.TrimSpace(input), []byte{'\n'}) } func spinCycle(p [][]byte) { for shiftUp(p) { } for shiftLeft(p) { } for shiftDown(p) { } for shiftRight(p) { } } func shiftUp(p [][]byte) bool { mutated := false for row, rowCh := range p { if row == 0 { continue } for col, colCh := range rowCh { if colCh != byte('O') { continue } if p[row-1][col] == byte('.') { p[row-1][col] = 'O' p[row][col] = '.' mutated = true } } } return mutated } func shiftLeft(p [][]byte) bool { mutated := false for row, rowCh := range p { for col, colCh := range rowCh { if col == 0 { continue } if colCh != byte('O') { continue } if p[row][col-1] == byte('.') { p[row][col-1] = 'O' p[row][col] = '.' mutated = true } } } return mutated } func shiftDown(p [][]byte) bool { mutated := false for row, rowCh := range p { if row == len(p)-1 { continue } for col, colCh := range rowCh { if colCh != byte('O') { continue } if p[row+1][col] == byte('.') { p[row+1][col] = 'O' p[row][col] = '.' mutated = true } } } return mutated } func shiftRight(p [][]byte) bool { mutated := false for row, rowCh := range p { for col, colCh := range rowCh { if col == len(rowCh)-1 { continue } if colCh != byte('O') { continue } if p[row][col+1] == byte('.') { p[row][col+1] = 'O' p[row][col] = '.' mutated = true } } } return mutated } func countLoad(p [][]byte) int64 { out := int64(0) for row, rowCh := range p { rowWeight := int64(len(p) - row) for _, c := range rowCh { if c == byte('O') { out += rowWeight } } } return out } -
Comment on Day 12: Hot Spring in ~comp.advent_of_code
whs (edited )Link ParentMy code is probably dynamic programming. If I have the input .###..# 3,1 the algorithm works by Look at the leftmost character. It should be #, . or ? If it is ., then it is not relevant. The...My code is probably dynamic programming. If I have the input
.###..# 3,1the algorithm works by- Look at the leftmost character. It should be
#,.or? - If it is
., then it is not relevant. The result of.###..# 3,1is the same as###..# 3,1. So, we recurse with new input###..# 3,1 - If it is
#, then count all continuous#or?next to it. - If it is less than 3 (the first number) then this is not a valid solution (eg.
#.#?.or premature end of string) - Now we're sure that the first 3 characters must be
###. The fourth must be either end of string,.or?(which can only be resolved as.). Check that it is so. - Now that we know the first four characters, and used the first block we can strip them from the input. We now know that the result is the same as input
.# 1. - Recurse with the new input until end of string
- At the end there should be zero map left and zero blocks. This is one valid solution.
So with that you can now validate whether a solution is valid or not, but that is only a single solution. Now the
?comes into play. Let's say the input is?##?.? 3,1- The first character is
?. It can be either#or. - Assume that it is
#, then, similar to step 3-5 previously we check that the first 3 characters are###. And the 4th character is either end of string,.or?(which can only be.).- If the check holds, then similar to step 6 we strip the known part
?##?=###.. The input is now.? 1. Recurse and count the number of solutions
- If the check holds, then similar to step 6 we strip the known part
- Assume that it is
., then as mentioned in step 2.can be removed. The input is now##?.? 3,1. Recurse and count the number of solutions. - Sum the number of solution from step 2+3
As for the caching part, if you have the same inputs (map & blocks) then there's only one correct answer. So you can use both of them as cache key and lookup the cache first before actually recursing.
I found that for part 1, actually building out the solutions help in debugging. It is not scalable enough for part 2, however. Bugs may cause your algorithm to run wild (like I added an extra
?at the end of part 2 input), so good luck. - Look at the leftmost character. It should be
-
Comment on Day 13: Point of Incidence in ~comp.advent_of_code
whs (edited )LinkPHP! Ah, I haven't wrote anything in PHP probably since 6 years ago. I believe one of my largest (almost) solo project was in PHP in last year of high school. Next year my work is sending me to...PHP! Ah, I haven't wrote anything in PHP probably since 6 years ago. I believe one of my largest (almost) solo project was in PHP in last year of high school. Next year my work is sending me to oversee a PHP shop, so I probably have to exercise it at some point.
Good thing this problem doesn't require array juggling so much, as I never wrote map/reduce in PHP. MY transpose algorithm allocate 2D array members out of nowhere, I'm surprised that it works. However, the resulting data type is not
array<char>or evenarray<array<char>>. It gave memap<int, string>and iteration is done in insertion order, not by key. Luckilyksortallow me to iterate by key order easily without fixing the data type.For part 2, change `$foundSmudge` to `false`<?php $input = trim(file_get_contents($argv[1])); $input = explode("\n\n", $input); function solve1H(array $problem): int { for($i = 0; $i < count($problem) - 1; $i++){ if (!isReflection($problem, $i)) { continue; } return $i; } return -1; } function isReflection(array $problem, int $point): bool { $upDistance = $point; $downDistance = count($problem) - 1 - 1 - $point; $maxDistance = min($upDistance, $downDistance); echo "start up $upDistance down $downDistance\n"; $foundSmudge = true; // true for part 1 for($i = 0; $i <= $maxDistance; $i++){ $diff = lineDiff($problem[$point - $i], $problem[$point + 1 + $i]); echo "\trow " . ((string) $point-$i) . " vs row " . ((string) $point+1+$i) . " diff $diff smudge $foundSmudge\n"; if (!$foundSmudge && $diff == 1) { $foundSmudge = true; }else if ($diff != 0) { return false; } } return $foundSmudge; } function lineDiff(string $a, string $b): int { $out = 0; for($i = 0; $i < strlen($a); $i++) { if($a[$i] != $b[$i]) { $out++; } } return $out; } function rotateCW(array $problem): array { $out = []; $height = count($problem) - 1; for($i = 0; $i < count($problem); $i++){ for($j = 0; $j < strlen($problem[$i]); $j++){ $out[$j][$height - $i] = $problem[$i][$j]; } } for($i = 0; $i < count($out); $i++){ // the array is still keyed, need to sort first... ksort($out[$i], SORT_NUMERIC); $out[$i] = implode("", $out[$i]); } return $out; } function printProblem(array $problem) { foreach($problem as $line){ echo $line."\n"; } } $accum = 0 ; foreach($input as $i => $problem) { echo "problem $i\n"; $lines = explode("\n", $problem); $reflection = solve1H($lines); if($reflection == -1){ echo "\tchecking V\n"; $rotated = rotateCW($lines); // printProblem($rotated); // it is a vertical line $reflection = solve1H($rotated); if ($reflection == -1) { throw new Error("no solution for problem $i"); } echo "\treflection V $reflection\n"; $accum += $reflection + 1; }else{ echo "\treflection H $reflection\n"; // it is a horizontal line $accum += ($reflection + 1) * 100; } } echo $accum . "\n"; -
Comment on Day 12: Hot Spring in ~comp.advent_of_code
whs LinkToday's language is JavaScript. I wanted to use TypeScript, but I'm lazy to setup the compiler. A trailing separator in my join implementation make me rewrote part 2 into recursiveless, before...Today's language is JavaScript. I wanted to use TypeScript, but I'm lazy to setup the compiler. A trailing separator in my join implementation make me rewrote part 2 into recursiveless, before realizing it would be very complicated. I spotted the error during the rewrite.
Part 1
My actual part 1 implementation use exception to signify "invalid solution". Later on the the catch block catches the recursion depth limit error and make it return the wrong results. So during part 2 rewrite I had to change it to returning empty list.// @ts-check import * as fs from 'fs' let input = fs.readFileSync(process.argv[2]).toString().trimEnd() let problems = input.split("\n").map((line) => { let [map, unknowns] = line.split(" ") return { map, unknowns: unknowns.split(",").map((i) => parseInt(i, 10)) } }) function getBlock(map) { let out = 0 for(let i = 0; i < map.length; i++){ if(map[i] === '#' || map[i] === '?') { out++ }else{ break } } return out } /** * @param {string} map * @param {number[]} unknowns * @returns string[] */ function solve1(map, unknowns){ if(map.length === 0){ if(unknowns.length > 0){ // throw new Error(`invalid solution - empty map but ${unknowns.length} unknowns items left`) return [] } console.log(`End of the line - empty map`) return [""] } if (map[0] === "?") { let solns = [] // Try to fill right side let continuousUnknownOrDamaged = getBlock(map) let wantedSize = unknowns[0] if(continuousUnknownOrDamaged >= wantedSize){ // we can fill, but only if the right side is EOL or . or ? if(wantedSize === map.length || map[wantedSize] !== '#'){ console.log(`We can fill left side ${map} with length ${wantedSize}`) let subsoln = cachedSolve1(map.slice(wantedSize + 1), unknowns.slice(1)) solns.push(...subsoln.map(v => "#".repeat(wantedSize) + "." + v)) } } // Or fill the current tile with . and go on let subsoln = cachedSolve1(map.slice(1), unknowns) solns.push(...subsoln.map(v => `.${v}`)) return solns }else if(map[0] === "#") { let block = getBlock(map) if(block < unknowns[0]) { // throw new Error(`invalid solution - # block of ${block} but we want at least ${unknowns[0]}`) return [] } // fill the block with broken ones let prefix = "#".repeat(unknowns[0]) let newMap = map.slice(unknowns[0]) let newUnknown = unknowns.slice(1) if (newMap.length === 0){ if(newUnknown.length > 0){ // throw new Error(`invalid solution - end of line but ${newUnknown.length} unknowns items left`) return [] } // we reach the end, hooray! console.log("End of line after block fill") return [prefix] }else if (newMap[0] === "?") { // make that operational newMap = newMap.slice(1) prefix += "." }else if (newMap[0] === "#") { // throw new Error(`invalid solution - block filled but the next item is #`) return [] } console.log(`In ${map} we got block of ${block}. After we filled ${unknowns[0]} we got ${newMap} and unknown ${JSON.stringify(newUnknown)}`) return cachedSolve1(newMap, newUnknown).map(v => prefix + v) }else if(map[0] === ".") { return cachedSolve1(map.slice(1), unknowns).map(v => `.${v}`) }else{ throw new Error("unknown char") } } const cache = {} function cachedSolve1(map, unknowns) { let key = map + JSON.stringify(unknowns) if(cache[key] !== undefined){ return cache[key] } let out = solve1(map, unknowns) cache[key] = out return out } let out1 = problems.map((p) => { let out = cachedSolve1(p.map, p.unknowns) console.log("Problem:") console.log(p) console.log(`Solutions ${out.length}`) console.log(out) return out.length }).reduce((a, b) => a+b, 0) console.log(out1)Part 2
The part 2 version do not visually build the output (it was useful in part 1 to debug any mistakes). Otherwise it is mostly the same as part 1. Adding cache also help improve large running time.34c34 < return [] --- > return 0 37c37 < return [""] --- > return 1 41c41 < let solns = [] --- > let solns = 0 51c51 < solns.push(...subsoln.map(v => "#".repeat(wantedSize) + "." + v)) --- > solns += subsoln 57c57 < solns.push(...subsoln.map(v => `.${v}`)) --- > solns += subsoln 64c64 < return [] --- > return 0 73c73 < return [] --- > return 0 77c77 < return [prefix] --- > return 1 84c84 < return [] --- > return 0 87c87 < return cachedSolve1(newMap, newUnknown).map(v => prefix + v) --- > return cachedSolve1(newMap, newUnknown) 89c89 < return cachedSolve1(map.slice(1), unknowns).map(v => `.${v}`) --- > return cachedSolve1(map.slice(1), unknowns) 107,112c107,116 < let out = cachedSolve1(p.map, p.unknowns) < console.log("Problem:") < console.log(p) < console.log(`Solutions ${out.length}`) < console.log(out) < return out.length --- > let map = "" > let unknowns = [] > for(let i = 0; i < 5; i++){ > map += p.map + "?" > unknowns.push(...p.unknowns) > } > map = map.slice(0, map.length-1) > let out = cachedSolve1(map, unknowns) > console.log(`${p.map}: ${out}`) > return out -
Comment on Day 11: Cosmic Expansion in ~comp.advent_of_code
whs LinkI've been writing Kotlin this long weekend. It's nice, but it can be janky if something is missing. Now to use Kotlin on AoC... I realize in the first part that the distance is simply...I've been writing Kotlin this long weekend. It's nice, but it can be janky if something is missing. Now to use Kotlin on AoC...
I realize in the first part that the distance is simply |x1-x2|+|y1-y2|. Also, I realize the tricky part would be that the expanding step is mutating the list mid-loop, so I took extra precaution.For second part I tried adding the factor variable in, but that only cause OOM. So, I added
virtualExpandthat recompute star positions based on the rows. While doing that, I totally forgot about the mutating mid-loop thing...import kotlin.math.abs fun main() { // val factor = 2 val factor = 1_000_000 val input = mutableListOf<MutableList<Char>>() while (true) { input.add(readLine()?.toCharArray()?.toMutableList() ?: break) } val colsToExpand = findExpandingCol(input) val rowsToExpand = findExpandingRow(input) // Part 1 // expandRows(input, rowsToExpand, factor) // expandCols(input, colsToExpand, factor) // printMap(input) // val stars = findStars(input) // Part 2 var stars = findStars(input) stars = virtualExpand(stars, rowsToExpand, colsToExpand, factor) println(stars) val starPairs = combination(stars) val sumDistance = starPairs.map { distanceBetween(it.first, it.second) }.sum() println(sumDistance) } fun virtualExpand(stars: List<Pair<Int, Int>>, rowsToExpand: List<Int>, colsToExpand: List<Int>, factor: Int): List<Pair<Int, Int>> { return stars.map { // println("expanding $it") var row = it.first for(expandingRow in rowsToExpand) { if (expandingRow < it.first){ row += factor-1 } } var col = it.second for(expandingCol in colsToExpand) { if (expandingCol < it.second){ // println("expanding col $expandingCol") col += factor-1 } } // println("end result ($row, $col)") row to col } } fun printMap(l: List<List<Char>>) { for(row in l) { for (col in row) { print(col) } println() } } fun findExpandingCol(l: List<List<Char>>): List<Int> { return l[0].indices.filter { col -> l.all { it[col] == '.' } } } fun findExpandingRow(l: List<List<Char>>): List<Int> { return l.indices.filter { row -> l[row].all { it == '.' } } } fun findStars(l: List<List<Char>>): List<Pair<Int, Int>> { val out = mutableListOf<Pair<Int, Int>>() l.mapIndexed { rowId, row -> row.mapIndexed { colId, col -> if (col == '#') { out.add(rowId to colId) } } } return out } fun expandRows(input: MutableList<MutableList<Char>>, rowsToExpand: List<Int>, factor: Int = 1) { var expanded = 0 for (row in rowsToExpand) { val pattern = (0..<input[0].size).map { '.' }.toMutableList() val injectedRows = (0..<(factor-1)).map { pattern.toMutableList() } val realRow = row + expanded input.addAll(realRow, injectedRows) expanded += factor } } fun expandCols(input: MutableList<MutableList<Char>>, colsToExpand: List<Int>, factor: Int = 1) { val injectedCols = (0..<(factor-1)).map { '.' } for (row in input) { var expanded = 0 for (col in colsToExpand) { val realCol = col + expanded row.addAll(realCol, injectedCols) expanded += factor } } } fun <T> combination(list: List<T>) = sequence { list.indices.forEach { a-> ((a+1)..<list.size).forEach { b-> yield(list[a] to list[b]) } } } fun distanceBetween(first: Pair<Int, Int>, second: Pair<Int, Int>): Long { return abs(first.first - second.first).toLong() + abs(first.second - second.second).toLong() } -
Comment on Day 10: Pipe Maze in ~comp.advent_of_code
whs LinkInitially I didn't have C# on the "language I've written" list, but I realize I wrote a Unity game back in first year university. I remember that C# now has top level statement. Oh well, this is...Initially I didn't have C# on the "language I've written" list, but I realize I wrote a Unity game back in first year university. I remember that C# now has top level statement. Oh well, this is easily the messiest code I've wrote so far. I couldn't even split part 2 into a new file because only one file can have top level statements.
Finally today's problem is now proper programming problem and not math problem. Part 2 took a while to figure out. I thought of increasing grid resolution but I didn't think it would work until I saw some redditors does it. With increased grid resolution, I run into C# recursion limit that is solved by building in release mode.
using System.Diagnostics; var _grid = new List<char[]>(); using (var input = new StreamReader(args[0])) { while (!input.EndOfStream) { _grid.Add(input.ReadLine()!.ToCharArray()); } } var grid = new char[_grid.Count, _grid[0].Length]; for (int row = 0; row < _grid.Count; row++) { for (int col = 0; col < _grid[row].Length; col++) { grid[row, col] = _grid[row][col]; } } // row, col (int, int) GetStartingPos() { for (int row = 0; row < grid.GetLength(0); row++) { for (int col = 0; col < grid.GetLength(1); col++) { if (grid[row, col] == 'S') { return (row, col); } } } throw new UnreachableException("no starting point found"); } var startingPos = GetStartingPos(); var distanceGrid = MakeDistanceGrid(); int[,] MakeDistanceGrid() { int[,] dg = new int[grid.GetLength(0), grid.GetLength(1)]; for (int i = 0; i < dg.GetLength(0); i++) { for (int j = 0; j < dg.GetLength(1); j++) { dg[i,j] = Int32.MaxValue; } } // XXX: Starting position value is 1 NOT 0 as indicated in problem statement dg[startingPos.Item1, startingPos.Item2] = 1; return dg; } void PrintGrid(char[,] g) { for (int i = 0; i < g.GetLength(0); i++) { for (int j = 0; j < g.GetLength(1); j++) { Console.Write(g[i, j]); } Console.WriteLine(); } } void PrintDistanceGrid(int[,] g) { for (int i = 0; i < g.GetLength(0); i++) { for (int j = 0; j < g.GetLength(1); j++) { var val = g[i, j]; if (val == int.MaxValue) { Console.Write(" " + grid[i, j]); } else { Console.Write(string.Format("{0:00}", g[i,j]-1)); } Console.Write(" "); } Console.WriteLine(); } } int GridMax(int[,] grid) { int max = 0; for (int i = 0; i < grid.GetLength(0); i++) { for (int j = 0; j < grid.GetLength(1); j++) { var val = grid[i, j]; if (val == int.MaxValue) { continue; } max = Math.Max(max, val); } } return max; } void BFS((int, int) position) { var fillValue = distanceGrid[position.Item1, position.Item2] + 1; var currentCell = grid[position.Item1, position.Item2]; var queue = new List<(int, int)>(); // Pipes: |-LJ7FS // Check north if (position.Item1 - 1 >= 0) { var cell = (position.Item1 - 1, position.Item2); if (distanceGrid[cell.Item1, cell.Item2] > fillValue && "|7F".Contains(grid[cell.Item1, cell.Item2]) && "S|LJ".Contains(currentCell)) { distanceGrid[cell.Item1, cell.Item2] = fillValue; queue.Add(cell); } } // Check west if (position.Item2 - 1 >= 0) { var cell = (position.Item1, position.Item2 - 1); if (distanceGrid[cell.Item1, cell.Item2] > fillValue && "-LF".Contains(grid[cell.Item1, cell.Item2]) && "S-J7".Contains(currentCell)) { distanceGrid[cell.Item1, cell.Item2] = fillValue; queue.Add(cell); } } // Check south if (position.Item1 + 1 < grid.GetLength(0)) { var cell = (position.Item1 + 1, position.Item2); if (distanceGrid[cell.Item1, cell.Item2] > fillValue && "|LJ".Contains(grid[cell.Item1, cell.Item2]) && "S|7F".Contains(currentCell)) { distanceGrid[cell.Item1, cell.Item2] = fillValue; queue.Add(cell); } } // Check east if (position.Item2 + 1 < grid.GetLength(1)) { var cell = (position.Item1, position.Item2 + 1); if (distanceGrid[cell.Item1, cell.Item2] > fillValue && "-J7".Contains(grid[cell.Item1, cell.Item2]) && "S-LF".Contains(currentCell)) { distanceGrid[cell.Item1, cell.Item2] = fillValue; queue.Add(cell); } } // BFS foreach(var q in queue) { BFS(q); } } // Part 1 // BFS(startingPos); // PrintDistanceGrid(distanceGrid); // Console.WriteLine(gridMax(distanceGrid) - 1); char[,] DoubleGrid() { // Double the grid resolution var newGrid = new char[grid.GetLength(0) * 2, grid.GetLength(1) * 2]; for (int row = 0; row < grid.GetLength(0); row++) { for (int col = 0; col < grid.GetLength(1); col++) { var mappedRow = row * 2; var mappedCol = col * 2; newGrid[mappedRow, mappedCol] = grid[row, col]; newGrid[mappedRow+1, mappedCol+1] = '.'; switch (grid[row, col]) { case '|': // |. // |. newGrid[mappedRow, mappedCol+1] = '.'; newGrid[mappedRow+1, mappedCol] = '|'; break; case '-': // -- // .. newGrid[mappedRow, mappedCol+1] = '-'; newGrid[mappedRow+1, mappedCol] = '.'; break; case 'L': // L- // .. newGrid[mappedRow, mappedCol+1] = '-'; newGrid[mappedRow+1, mappedCol] = '.'; break; case 'J': // J. // .. newGrid[mappedRow, mappedCol+1] = '.'; newGrid[mappedRow+1, mappedCol] = '.'; break; case '7': // 7. // |. newGrid[mappedRow, mappedCol+1] = '.'; newGrid[mappedRow+1, mappedCol] = '|'; break; case 'F': // F- // |. newGrid[mappedRow, mappedCol+1] = '-'; newGrid[mappedRow+1, mappedCol] = '|'; break; case '.': // .. // .. newGrid[mappedRow, mappedCol+1] = '.'; newGrid[mappedRow+1, mappedCol] = '.'; break; case 'S': // S- // |. newGrid[mappedRow, mappedCol+1] = '-'; newGrid[mappedRow+1, mappedCol] = '|'; break; } } } return newGrid; } grid = DoubleGrid(); startingPos = GetStartingPos(); distanceGrid = MakeDistanceGrid(); BFS(startingPos); // Remove irrelevant grid positions for (int row = 0; row < distanceGrid.GetLength(0); row++) { for (int col = 0; col < distanceGrid.GetLength(1); col++) { if (distanceGrid[row, col] == int.MaxValue) { grid[row, col] = '.'; } } } PrintDistanceGrid(distanceGrid); void FloodFill((int, int) position) { if (grid[position.Item1, position.Item2] != '.') { return; } grid[position.Item1, position.Item2] = 'O'; // top if (position.Item1 - 1 >= 0) { FloodFill((position.Item1-1, position.Item2)); } // left if (position.Item2 - 1 >= 0) { FloodFill((position.Item1, position.Item2-1)); } // south if (position.Item1 + 1 < grid.GetLength(0)) { FloodFill((position.Item1+1, position.Item2)); } // right if (position.Item2 + 1 < grid.GetLength(1)) { FloodFill((position.Item1, position.Item2+1)); } } // Flood fill the edges with O for (int i = 0; i < grid.GetLength(0); i++) { // Fill left edge FloodFill((i, 0)); // Fill right edge FloodFill((i, grid.GetLength(1) - 1)); } for (int i = 0; i < grid.GetLength(1); i++) { // Fill top edge FloodFill((0, i)); // Fill bottom edge FloodFill((grid.GetLength(0)-1, i)); } PrintGrid(grid); int CountHalfDots() { int accum = 0; for (int row = 0; row < grid.GetLength(0); row += 2) { for (int col = 0; col < grid.GetLength(1); col += 2) { if (grid[row, col] == '.') { accum++; } } } return accum; } Console.WriteLine(CountHalfDots()); -
Comment on Day 9: Mirage Maintenance in ~comp.advent_of_code
whs LinkWow, this is easy. I kinda like this one. Today's language is Java, and I hate the multiple ways to store things in a sequential order with different API surfaces. Two days ago I wrote C++23 and...Wow, this is easy. I kinda like this one.
Today's language is Java, and I hate the multiple ways to store things in a sequential order with different API surfaces. Two days ago I wrote C++23 and it didn't feel this confusing to use vector, array, span in the same code.
Nonetheless, good thing we now have stream and it felt modern. I was writing some Kotlin code right before the start, and it felt much, much more pleasant to use.
import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Aoc9 { public static void main(String[] args){ Scanner scan = new Scanner(System.in).useDelimiter("\n"); int accum = 0; while (scan.hasNext()) { String history = scan.next(); accum += solve2(history); } System.out.println(accum); } private static int solve1(String history) { int[] input = Arrays.stream(history.split(" ")) .mapToInt(Integer::parseInt) .toArray(); ArrayList<int[]> historyTiers = new ArrayList<>(); historyTiers.add(input); int[] current = input; while(!isAllZero(current)){ System.out.println(Arrays.toString(current)); current = diff(current); historyTiers.add(current); } int nextValue = 0; for (int i = historyTiers.size() - 2; i >= 0; i--) { int[] currentTier = historyTiers.get(i); int lastValue = currentTier[currentTier.length - 1]; nextValue = lastValue + nextValue; } return nextValue; } private static int solve2(String history) { int[] input = Arrays.stream(history.split(" ")) .mapToInt(Integer::parseInt) .toArray(); ArrayList<int[]> historyTiers = new ArrayList<>(); historyTiers.add(input); int[] current = input; while(!isAllZero(current)){ current = diff(current); historyTiers.add(current); } int nextValue = 0; for (int i = historyTiers.size() - 2; i >= 0; i--) { int[] currentTier = historyTiers.get(i); int firstValue = currentTier[0]; // lastNextValue = firstValue - nextValue // -nextValue = lastNextValue - firstValue // nextValue = firstValue - lastNextValue System.out.printf("Tier %d, %d - %d\n", i, firstValue, nextValue); nextValue = firstValue - nextValue; } System.out.printf("Input: %s, out = %d\n", Arrays.toString(input), nextValue); return nextValue; } private static int[] diff(int[] input) { int[] out = new int[input.length - 1]; for(int i = 1; i < input.length; i++){ out[i-1] = input[i] - input[i-1]; } return out; } private static boolean isAllZero(int[] input) { return Arrays.stream(input).allMatch(i -> i == 0); } } -
Comment on Day 8: Haunted Wasteland in ~comp.advent_of_code
whs LinkI tried to learn Ruby over half a decade ago, but I found that it mostly overlap Python in use cases so I didn't get to use Ruby much and forgot almost everything about it. Looking at the problem...I tried to learn Ruby over half a decade ago, but I found that it mostly overlap Python in use cases so I didn't get to use Ruby much and forgot almost everything about it. Looking at the problem it seems doable in Ruby even though I don't know how to write anything in Ruby now. Surprisingly, I think this is one of the fastest day I've completed so far.
Part 1
instruction = gets.chomp gets nodes = {} while l = gets do parsed = l.match(/^([A-Z]+) = \(([A-Z]+), ([A-Z]+)\)/) nodes[parsed[1]] = { "L" => parsed[2], "R" => parsed[3], } end current = "AAA" step = 0 while current != "ZZZ" do cmd = instruction[step % instruction.length] current = nodes[current][cmd] step += 1 end puts stepPart 2
instruction = gets.chomp gets $nodes = {} while l = gets do parsed = l.match(/^([0-9A-Z]+) = \(([0-9A-Z]+), ([0-9A-Z]+)\)/) $nodes[parsed[1]] = { "L" => parsed[2], "R" => parsed[3], } end current = $nodes.keys.filter { |k| k.end_with?("A") } current_z_every = current.map { |v| step = 0 cur = v while !cur.end_with?("Z") do cmd = instruction[step % instruction.length] cur = $nodes[cur][cmd] step += 1 end step } puts current_z_every.reduce(1, :lcm)I don't like math problem posing as programming problem...
My concerns on these kernel space anticheat is security. The driver could have vulnerabilities that allow elevated system control without UAC prompt. Especially that the anticheat is often used to avoid implement the basic security principle of don't trust the client inputs - speedhacks, fly, highscore cheats, or unlocking achievements for other players are cheats that should be detected as invalid inputs.
If the anticheat only runs when the player enter online mode (and offer offline modes if applicable) and unload itself after the play session completes then it should be acceptable to me.