First: other projects popped their heads in: setting up a friend’s Etsy store, an announcement from Apple that I had 30 days to update an app before it was pulled, and the holidays. So I really haven’t touched the challenge since the 16th, or about ten days ago, and finishing all 75 problems in a month was already quite the challenge.
The store is up and has had some orders already, and the app has been brought forward from Swift 3 to Swift 5, and updated to Xcode 15 (which ChatGPT cheerily insists doesn’t exist unless you pay money for its dubious advice at the ChatGPT 4 level). So let’s get back into the challenges.
Another tree problem; this one requires us to find the longest leaf-to-leaf path in the tree, not necessarily going through the root. I struggled with this one a while, but did not hit on the need to have the current largest diameter outside of crawl; I eventually gave up and Googled a solution, which passed a pointer to the diameter into the crawler, so we always were looking at the absolute maximum across the whole tree.
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func diameterOfBinaryTree(root *TreeNode) int {
diameter := 0;
_ = crawl(root, &diameter);
return diameter;
};
func crawl(root *TreeNode, diameter *int) int {
if root == nil {
return 0
}
leftSubtreeDepth := crawl(root.Left, diameter)
rightSubtreeDepth := crawl(root.Right, diameter)
*diameter = max(*diameter, leftSubtreeDepth + rightSubtreeDepth)
return max(leftSubtreeDepth, rightSubtreeDepth) + 1
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
This was 100% on speed, and 20% on memory.
I was close; I had the nil root case, and I’d figured out I needed the depths of the trees, but I didn’t put together that I’d need to cache the diameter completely outside the crawler to accurately find the maximum – if you just pass it back recursively, a larger value can end up discarded.
This is a tougher one, and honestly, you would have needed to have solved this yourself before to have gotten to a reasonable algorithm in the usual 1/2 hour time. It’s generally a significant sign if the problem description has to refer to Wikipedia for an accurate description of the problem.
This is one that is very simple to do by inspection, but difficult to do simply by algorithm, let alone an efficient one.
My first idea was that I’d need to know the paths to the nodes, and that I’d *handwave* figure out the common ancestor by using those. The good algorithm for this kind of uses the idea of paths to the nodes, but instead it does an in-order trace of the paths through the tree – an Euler tour, dude comes in everywhere – and that allows us to transform the problem into a range-minimum query (e.g., when I have node P and node q, and the path I needed to get from one to the other, at some point in there I’ll have a minimum-depth node, which will either be one of the two, or a third higher node).
The Wikipedia example shows this as an illustration:
To spell this out more explicitly: you can see we did the in-order tour, transforming the tree into a linear walk through it: A, down to B, down to C, back up to B, down to D, down to E, up to D, and so on. We record the node value and the depth at each step. To get the range query, we want the first appearance of each of two nodes we’re searching for (and we can record that as we’re crawling), and then to look for the highest node in the range of nodes including both of them. For the example in the diagram, step 6 is where we find the first node, E, and step 9 is where we find the second node, F. Iterating from step 6 to step 9, the node with the lowest depth in that range is B, and we can see from inspecting the tree that this is correct.
So.
At this point I’ve explained the solution, but have not written any code for it at all yet. Better go get that done.
Note: I’ve gotten the Euler crawl to mostly work, but I’m having trouble with the returned data from the crawl. Debugging…and yes, I am too cheap to pay for leetcode’s debugger. fmt.Println FTW.
The crawler crawls, but the output is wrong. I’ve tracked this down to a fundamental error on my part: Go arrays are not built for this kind of thing. I am switching the crawler over to building a linked list, which I think I only have to traverse one direction anyway, so it’s just as good.
This definitely was a failure to time-block. I will keep plugging on this until I actually finish solving it, but this would have been a DQ in an interview.
I’ve now discarded two different Euler crawls, and have a working one…but the range-minimum isn’t working as I expect it to. Will have to come back to it again. I begin to wonder if trying to track the start node is, in fact, a bad idea, and if I should simply convert the linked list I’m generating in the crawl to an array for the range minimum once it’s returned.
The crawl now returns the head and tail of a list that contains the visit order for the Euler crawl: node, left subtree in order, node again, right subtree in order, node again. This breaks down like this:
If the current head is nil, return [nil, nil].
Generate a crawl node for just this node at the current level
Set head and tail to this node
If the current head points to a leaf node:
Return head and tail.
Otherwise:
Crawl the left side at level+1, getting a leftside head and tail.
Crawl the right side at level+1, getting a rightside head and tail.
If the leftside crawl is non-null:
Set tail.next to leftside head.
Create a new crawl node for the current node at the current level.
Set leftside tail node's next to this new node.
Set tail to this middle node.
If the rightside crawl is non-null:
Set tail.next to the rightside head.
Create a new crawl node for the current node at the current level.
Set rightside tail node's next to this new node.
Set tail to this new node.
Return head and tail.
This returns a singly-linked list with an in-order traversal, recording every node visited and the tree level at which it was seen. We should now be able to find the start and end nodes, and scan the list between the two inclusive, looking for the highest node, and that should find the LCA.
The scan is a bit of a bastard as well. The nodes may appear in any order, and we have to find the start and end no matter which order they show up in. I initially tried swapping them if they were out of order, but this didn’t work as I expected – that may have been other bugs, but I coded around it in the final scan code.
The final scan first says “I don’t have either node” and skips nodes until it finds one of them. Once it does, it starts looking for the node with the highest level. The tricky bit is that we need to detect that we’ve found the first node, then start checking, and only stop checking after we find the end node (as it may be the highest, since nodes are considered their own roots).
Here’s the final code. It did not do well in the rankings: bottom 5% in speed, and bottom 25% in memory usage. I suspect I could improve it by merging the “find the local high node” code into the Euler crawl, and by not actually recording the nodes in the linked list at all but passing the state around in the recursion.
Lessons learned:
Do not try to do complicated array machinations in Go. Better to record the data in a linked list if you’re doing something that needs to recursively append sublists.
Think more clearly about recursion. What is the null case? What is the one-element case? What is the more-than-once case? What is the termination criterion for the more-than-one case?
Don’t be afraid to discard an old try and do something different. Comment out the failed code (and note to the interviewer that you’d check the broken one in on a local branch in case you wanted to go back to it).
Continuing to practice with Go pointer code is necessary. I’m a bit weak with pointers.
This took way too long to do, and way too many shots at getting to something that would work at all. I grade myself a fail on this one. I might come back at a later date and try to make it faster and smaller.
Addendum: removed the debugging and the dump of the crawl output. Even without doing anything else, that bumped my stats to the top 73% in runtime and top 99% in memory usage, and that is a pass with flying colors!
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type eulerNode struct {
node *TreeNode
depth int
next *eulerNode
}
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// Use the transformation of this problem into a range-minimum one.
// Crawl the tree in-order, creating an Euler path. Each step records
// the node value and the depth.
head, tail := eulerCrawl2(root, p, q, 0)
// dump crawl output - note that removing this should make the code
// significantly faster
scan := head
for {
if scan == nil {
break
}
fmt.Println(scan.node.Val, "depth", scan.depth)
scan = scan.next
}
fmt.Println("crawl complete", head, tail)
// Start is the beginning of the range, and the end of the path is the end.
// Find the path minimum in the range (the lowest depth value).
var ancestor *TreeNode
minDepth := 9999999999
fmt.Println("Start at", head.node.Val, head.depth)
foundP := false
foundQ := false
for scan := head; scan != nil; scan = scan.next {
fmt.Println("node", scan.node.Val, scan.depth)
if scan.node.Val == p.Val {
fmt.Println("found p")
foundP = true
}
if scan.node.Val == q.Val {
fmt.Println("found q")
foundQ = true
}
if !foundP && !foundQ {
fmt.Println("skip", scan.node.Val)
continue
}
fmt.Println("check", scan.node.Val, scan.depth)
if scan.depth < minDepth {
// New range minimum
minDepth = scan.depth
ancestor = scan.node
fmt.Println("new candidate min at", scan.node.Val, scan.depth)
}
if foundP && foundQ {
fmt.Println("found and processed complete range")
break
}
}
fmt.Println("ancestor is", ancestor.Val)
return ancestor
}
func eulerCrawl2(root, p, q *TreeNode, depth int) (*eulerNode, *eulerNode) {
// Nil tree returns nil pointer
if root == nil {
fmt.Println("skipping nil pointer")
return nil, nil
}
// Non-nil next node. Generate a crawl node for this tree node.
fmt.Println("adding crawl node for", root.Val)
head := &eulerNode{
node: root,
next: nil,
depth: depth,
}
tail := head
// If this is a leaf, the crawl of
// this node is just this node. Head and tal point to the same node.
if root.Left == nil && root.Right == nil {
fmt.Println("returning at leaf")
return head, tail
}
// Non-leaf. Crawl will be this node, the left subtree at depth+1,
// another copy of this node at this depth, the right subtree at depth+1,
// and one more copy of this node.
fmt.Println("crawling down")
leftSubtreeHead, leftSubtreeTail :=
eulerCrawl2(root.Left, p, q, depth+1)
rightSubtreeHead, rightSubtreeTail :=
eulerCrawl2(root.Right, p, q, depth+1)
// Chain the results together:
// - this tree node
// - the left crawl below it
// - another copy of this node
// - the right crawl below it
// - a final copy of this node
// Link this node to the start of the list from the left crawl
if leftSubtreeHead != nil {
// If there is a crawl below, link it in, and add another
// copy of the current node for coming back up
tail.next = leftSubtreeHead
leftSubtreeTail.next = &eulerNode{
node: root,
next: nil,
depth: depth,
}
tail = leftSubtreeTail.next
}
if rightSubtreeHead != nil {
// right crawl exists. Add it at the current tail, reset tail.
tail.next = rightSubtreeHead
rightSubtreeTail.next = &eulerNode{
node: root,
next: nil,
depth: depth,
}
// reset tail to new last node
tail = rightSubtreeTail.next
}
// Return head and tail of the newly-generated list of crawled
// nodes.
fmt.Println("returning results at depth", depth)
return head, // Head of this new list
tail // Tail of this new list
}
A bit of a break working on a friend’s art business launch; still working on that, but made some time to come back to leetcode month today.
Today’s problem is flood fill; another easy-rated one. This is again a recursion problem, and the tricky bit is as usual preventing extra recursion that doesn’t need to happen.
Doing this one is made a lot easier by unifying the calling sequence with a helper function that adds an
Go-specific issues for me were properly extracting the dimensions of a two-D array and having to do that with a pointer. Since we want to alter the array we’re flood filling, we need to pass a pointer to it so that we can actually modify the source array.
I got tripped up by the termination condition. In addition to “are we outside the bounds of the array”, we also need to check if this cell needs filling at all (is it the fill color already? Is it the color we want to fill?).
I did need a couple runs with debug prints in to spot where my recursion was going wrong; the first cut didn’t have the “is this already the right color” test, and I was able to catch that one with the supplied test cases. It. failed on the submit because I wasn’t checking for “is the fill already done” case.
How did I do relative to other cases? Pretty good! Runtime in the top 92%, memory usage a quarter of a percent short of the 100th percentile. Should be a pass in an interview. (I did get this one at Thumbtack, and came out with a solution similar to this one, except I used an 8-cell neighborhood when a 4-cell will work. Too many Game-of-Life programs.)
Should have been an easy one, but I haven’t written one by hand in years. Ended up Googling.
Some interesting notes on the code:
for with a conditional break inside is considerably slower than for condition.
The version of this that I learned back when used a step division, and that actually is much harder to get right. The upper/lower/mid version is much easier to get right.
I decided to not do a recursive solution this time on purpose. The expressivity that recursion gives you is not to be denied.
Final version scored well: 90% on speed, 97% on memory. Acceptable, but the amount of dicking around was not. Note: study up more of these common but not commonly coded algorithms.
func search(nums []int, target int) int {
// Find midpoint, check element; equal, less, or greater.
// if the step size goes to 0 we did not find.
low := 0
high := len(nums) -1
for low <= high {
mid := (high + low )/ 2
if nums[mid] < target {
low = mid + 1
} else if nums[mid] > target {
high = mid -1
} else {
return mid
}
}
return -1
}
Problem: two strings. Are they anagrams of each other?
Software engineer hat again: if these are arbitrary Unicode strings, then the right solution is count the characters in the first string, binning the counts by character, and then subtract the counts of the characters in the second string. If the characters are ASCII, then you can be clever and use the character value as an index into an array and do the same add/subtract algorithm…but someone will use a non-ASCII character, sooner or later. And the failure mode of clever is…well.
Score: bottom 15% in time and space, but I’ll take that for the vastly reduced need to worry about weird input. If we remove the conversion to string and use bytes, then it improves to 30%. The real win doesn’t happen until the conversion to arrays. I initially had a delete to remove counts that went to 0 and a check for counts that went negative (chars in t not in s) but there wasn’t a significant speedup.
func isAnagram(s string, t string) bool {
// easiest way is to map the character counts into a hash.
// if the two strings match, there should be no odd counts.
if len(s) != len(t) {
return false
}
charCounts := make(map[byte]int)
for i := range(s) {
charCounts[s[i]]++
}
for i := range(t) {
x := string(t[i])
charCounts[x]--
}
for _, count := range(charCounts) {
if count != 0 {
return false
}
}
return true
}
Giving up and using an array of 256 ints, indexed by the int value of the bytes, it’s much faster: 93% on time, 98% on space. Good enough. I suppose you could use this on Unicode input, since it’s just looking at raw bytes. Depends on whether you have a character that can be represented in more than one way in Unicode.
The syntax for creating arrays continues to be a problem. I’m going to standardize on assigning the type followed by {} to the variable.
Today’s challenge is Valid parens. And it reminded me of several of the things that I don’t particularly like in Go.
Problem statement boils down to “here’s a string of brackets: parens, square brackets, braces. Tell us if they match properly (true) or don’t (false)”. Algorthmically this is dead simple:
Start with an empty stack.
for each character in the string:
if it's an open bracket, push it.
if its a close bracket:
if the stack is empty, return false.
if the top of the stack isn't the matching open, return false.
pop the stack.
When we're done, return true if the stack is empty, false otherwise.
In Perl or Python, I’d have a stack pointer, and move it up and down an array as I pushed and popped characters by altering the stack pointer and assigning to the appropriate point in the array. If the stack pointer went below 0, I’ve gotten too many close parens, and I return false.
This approach doesn’t work well at all with Go, because Go arrays and slices Do Not Work Like That.
To push onto an existing array, we need to use a := append(a, new). Just assigning to an index outside of the slice’s current boundaries will panic.
We could still use the stack pointer to move backward, but then we’d have to have more complex code to decide if we need to append or just move the pointer. (Side note: doing it that way would probably use less memory — the working version of my solution used more memory than 90% of the other solutions). Instead, we just use the slice notation to pop the stack instead, with a := a[:len(a)-1].
My original iterations with a real stack pointer failed miserably because I wasn’t properly tracking the length of the array, and was perpetually getting the stack pointer position wrong, causing the code to panic. It was only after completely discarding the stack pointer that I got it to finally work.
Items of note:
I remembered I’d need to use range() to iterate over the string, but forgot that I would have to string() the characters I was getting so they were strings instead of runes. I wasted a good chunk of time trying to mess with runes before I realized that I needed string() instead. Runes are considerably more second-class citizens.
Still running afoul of using make() properly. Finally figured out the syntax to create an empty string array, but it took some Googling to get it.
I decided to make the code less complex by creating a pairs map that mapped left brackets to right ones. This meant I could check pairs[left] == right for whether I’d matched the left and right brackets. It also meant that if we ever added more bracket pairs in the future, it’d be be easier to implement them.
I got fenceposted by a[len(a)-1] accessing the last element, and a[:len([a)-1]dropping the last element. I naively expected that since a[len(a)-1] accessed the last element, I’d want a[:len(a)-2] to drop that last element, but that takes one too many, running me into another fencepost. Yes, it’s good that it’s symmetric, and now I’ll remember, but I definitely had to look it up to figure out both of them.
Forgot the check for “did we close all the opens”. I probably would not have missed it if I was making my own test cases, but it wasn’t in the tests. Note to self: watch out for poor initial test cases. There is an opportunity to add more, I think?
So how’d I do overall? We saw I was in the bottom 10% in memory usage, boo, but runtime? “Beats 100.00% of users with Go”.
I’ll definitely take that as a win, but it’s definitely obvious I need to keep practicing and getting these idioms back under my belt.
func isValid(s string) bool {
// We'll run through the string, doing the following:
// - if we see an open bracket, we stack it.
// - if we see a close bracket, we pop the stack. If the
// brackets match, we continue, otherwise we fail.
// - when we run out of brackets, the stack must be empty or we fail.
stack := make([]string,0)
pairs := map[string]string{
"(": ")",
"[": "]",
"{": "}",
}
for i := range s {
char := string(s[i])
_, ok := pairs[char]
if ok {
// left, push it
stack = append(stack, char)
} else {
// right, stack empty?
if (len(stack) == 0) {
fmt.Println("pop of empty stack")
return false
}
// Not empty. match?
if (pairs[stack[len(stack)-1]] != char) {
fmt.Println ("mismatch")
// mismatched bracket, fail
return false
}
// Match. Pop stack.
stack = stack[:len(stack)-1]
}
}
// Check for "did we close all the open brackets".
return len(stack) == 0
}
That’s one for today, and I need to clean the house, so I’ll call it a day.
Well, these were fun, and definitely showed me I’m not ready to walk into an interview at the moment!
Twosum
Twosum is an easy challenge: you are given an array of numbers and a target value; your job is to find the only two numbers at different indexes in the array that sum to the target value and return those two indexes.
The brute-force strategy just repeatedly walks through the array, trying to find the right pair of numbers. This ends up being O(n^2) because we essentially run over the upper triangle of a square of the elements of the array> If in the example below were looking for numbers that sum to 9, we’d run over the numbers four times finally finding it on the fourth pass, and doing 4+3+2+1 = 10 checks. (We can save operations by precomputing the second term in the sum: subtract the first search value from the target sum, and just compare that against the value in the array at that index instead of summing the two.)
>1 2 3 4 5
1 >2 3 4 5
1 2 >3 4 5
1 2 3 >4 5
But the old Perl adage “when someone says search, consider a hash” comes in handy here. We can precompute exactly the number we want, so if we can make the values the keys of a hash (and we can, as we know that there is only one pair that sums to the target value), then we can make the indexes the values.
We walk through the array twice:
The first iteration builds the hash by taking each value and inserting it as the key with the index as its value. And since we’re doing one iteration over the whole array anyway at this point, we can check each item as we insert it to see if it hits the target with the first item!
If we don’t luck out during the insert, then we iterate over items 2 to N, calculating the value we’d need to hit the target, and then doing a hash lookup to see if it’s there The hash lookup is O(1), and the pass over the array (including the load) is also O(1), so we’ve made a pretty good reduction in overall runtime.
Things I’d forgotten in the last year of pretty much nothing but Scala:
The only loop structure in Go is the for loop.
var, not val. val is Scala, and as one tries for as much immutable data as possible in Scala, my fingers are trained to type val at every turn.
Go array initializer syntax. Square brackets, then the type, then the values in curly braces.
I remembered I needed to make() a map, but used Scala syntax instead of Go syntax trying to specify the types.
Go does not consider [2]int to be the same as []int. Fair.
Gotta have the parens for every function. Perl and Scala made me sloppy about that.
Things discovered:
Adding the “try to catch it in the load pass” made a significant speed difference when the first term was at index 0.
Putting the first index in the array initializer for the result array instead of assigning it vastly increased the speed of the search loop — I went from the top 75% to the top 95% with that one change.
The hash solution uses more memory; I was at the 15th percentile on memory, but I’ll definitely take being faster than 95% of the other solutions as better.
I missed the “must be different indexes” restriction on my first pass; fortunately the second test case was for 6 with [3, 4, 2], and I got a test fail for [0,0].
Here’s the final version. I do comment even when writing these because I can line out the code with comments and put the actual code itself in later. Writing down the assumptions helps clarify them as well (thanks loads, ADHD).
func twoSum(nums []int, target int) []int {
// Given that
// - there is only one solution, then all entries must be unique
// - therefore they can be used as keys to a hash
// - this means we can iterate O(1) over the array for term 1
// and lookup term 2 in the hash, getting its index. No need
// for a linear search for it.
// Fill the hash...and see if we can catch the solution
// during this pass, since we have to do it anyway.
locations := make(map[int]int)
prematch := target - nums[0]
for i := 0; i < len(nums); i++ {
if i > 0 && nums[i] == prematch {
return []int{0, i}
}
locations[nums[i]] = i
}
// scan the nums, looking for a match.
// first match wins.
for i := 0; i < len(nums); i++ {
result := []int{i, -1}
term2 := target - nums[i]
j, ok := locations[term2]
if ok {
// Disqualify same-entry match. Missed this first time,
// thank you test cases.
if i == j {
continue
}
// Found
result[1] = j
return result
}
}
// This is a "should not get here"; meant to show me if I've totally
// blown the loop.
panic("did not find a solution")
}
Add two numbers
This one was recommended by leetcode as a “hot” problem, and it looked like fun, so I did it. It’s not in the Grind 75 list, but it’s a nice pointer manipulation problem, and I was a bit stale on pointers.
The function is passed two linked lists; each list has an integer from 0-9 and a pointer to the next digit. The digits are presented in right-to-left order. The function is to take these two lists, and return a new list that represents the sum of the two numbers. Of course, the lists can be different lengths; if they are, then the list that runs out first is treated as if it were returning zeroes for the purposes of the sum.
It was instantly clear that the challenge here would be maintaining the scan pointers for the two numbers and the result, and that trying to do bookkeeping for all of it in the loop would suck. So my approach was to construct a function to return a closure that would follow the rules for reading the numbers off the list:
If the scan pointer is null, return 0 and false
If the scan pointer is not null, return the node’s value and true, advancing the pointer to the next node.
This meant that the list management was dead simple:
first := iterator(L1)
second := iterator(L2)
fVal, fState := first()
sVal, sState := second()
Each call to the first and second closures returns the next value to use in the sum; when both are false, the sum is complete.
So all I had to manage in the loop was the scan pointer for the sum, and the carry from the addition operation: adding it in, clearing it, and recalculating it after the current operation.
Things learned/relearned:
Had to remember when I needed * and when I didn’t for variable types.
The first run segfaulted. I realized that I’d mismanaged the scan pointer; I needed to save the root node, and then scan forward while doing the operations.
Once I fixed that, I found out I wasn’t clearing the carry. Whoops. Easy to fix.
The closures worked perfectly.
The “end the loop” and “restart the loop” keywords are break and continue. Trivial, but I had to go look it up.
I did make one major mistake: I missed that the output was supposed to be another list, and started calculating the sum as an integer. This wasn’t too terribly off from the desired solution; I had figured out that I’d need the carry tracking, and I had a power variable that I was multiplying by 10 to switch columns in the output variable, but that probably wasted 5 or 10 minutes and might have made the difference between a pass and a fail in an interview.
It was pretty easy to switch to the list building, but lesson hammered home again: be sure you read the problem statement correctly and know what the output is. Confirming with the interviewer that I got the details right is probably a good idea in a timed problem.
**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
// The tricky bit with this one is going to be watching out
// for the end of the list.
// the dumbest and easiest way is to have a bool for each
// list; when one list has no more entries, we set its bool
// to false and return a zero value for it.
// when both lists return a false value, we're done.
first := iterator(l1)
second := iterator(l2)
var currentDigit *ListNode
var root *ListNode
carry := 0
for {
fVal, fState := first()
sVal, sState := second()
if (!fState && !sState) {
// run off the end of both. Stop loop, finalize sum.
fmt.Println("Done")
break
}
// At least one still returning a value. (The other returns 0
// if there's no value.)
// Sum the digits and the curent carry; if > 9,
// take mod 10 and set the carry to 1. (no two
// digits can sum to > 18).
digitSum := fVal + sVal + carry
carry = 0
if digitSum > 9 {
carry = 1
digitSum = digitSum - 10
}
// Add space for a new digit, append it, continue.
if currentDigit != nil {
currentDigit.Next = &ListNode{digitSum, nil}
currentDigit = currentDigit.Next
} else {
// Create and save root digit
currentDigit = &ListNode{digitSum, nil}
root = currentDigit
}
}
if (carry != 0) {
// last addition had a carry we need to keep
currentDigit.Next = &ListNode{carry, nil}
}
return root
}
func iterator(l *ListNode) func()(int, bool) {
// Close over the pointer.
p := l
return func()(int, bool) {
if p == nil {
// Reached end. Keep returning 0 and false.
return 0, false
} else {
// Capture next digit, advance pointer,
// return next digit and true. If new pointer
// is nil, we'll just return 0 and end-of-list signal
// forever.
v := p.Val
p = p.Next
return v, true
}
}
}
So how’d I do overall in comparison? Pretty fuckin’ good. I was in the top 95% on speed, and the top 91% in memory use. I suspect that managing all the bookkeeping in the loop might make it a tad faster (no call overhead for the closures), but at the cost of significantly more complexity. This solution is fast and small, and I’ll take it.
Conclusions
My Go is pretty good. I didn’t spend a huge amount of time chasing bugs, and had it in a couple tries. I have a good grasp of the concepts and know mostly how to do things.
My Go is fairly stale. I don’t remember how to say things!
I had to look up a lot of things that I should have just remembered, like len() for array length (not.len, that’s Scala!). I need this practice!
Most people do a novel for NaNoWriMo, and that’s a great thing.
I am not a great fiction writer; maybe I’d be better if I practiced, but right now, writing code makes more money, so I’m going to spend the month of November working through the Grind 75 leetcode practice set.
I would very much prefer a Perl job, but there just aren’t that many places now that really want someone whose primary is Perl. Python’s fine, but it’s mostly tied up in LLMs and AI at the moment, neither of which I actually find very interesting. (They seem to be more “build a model and hope it does the work you wanted” as opposed to “write the code to do the job you want done”, which I find much more satisfying.)
I haven’t done much with Rust yet, and I think it’d be a fun language to work in, but I don’t see a lot of demand for it yet. Scala is fun to write but I’d rather jump out a window than use the JVM toolchain again. (This also crosses off Java, Dart, and Flutter for me as well.) I have not in general found C++ to be that much fun, and Javascript is what it is. I can write it, I just don’t enjoy it.
So it comes down to two languages, really: Go and Swift. I enjoy coding in both (for different reasons), but at the moment I’m seeing more Go jobs than Swift ones, though that may just be my settings. Certainly when you need a Mac/iOS programmer, you need someone who at least understands Swift.
So I’ll probably end up trying it with both, and seeing how it goes. Onward!
If you haven’t heard of “Swedish Death Cleaning”, the idea is that when you finally do drop dead, it’d be polite to not saddle whoever is taking care of your stuff with a big job of “is this important? should I keep it? should I just give all this away, or throw it away, because it’s just too much?”. Also, living with just the stuff that actually means something to you on a daily basis, as opposed to “I may want this someday, so I’ll keep it in my live gathering dust and generating clutter.”
I definitely need to do more of that in my physical life, but this weekend I embarked on it in my digital one. Like most people, when I finally had iTunes and no longer had an actually “how full are my shelves?” physical limit, I started hoarding music. I had a lot of stuff from my old CD collection, music I’d bought from iTunes, the StillStream library from when I was maintaining the music library for that station’s ambient robot, music from friends who’d lent me CDs, stuff I’d borrowed from the library and timeshifted into iTunes to listen to “later”, free releases from Amazon…basically a huge pile of stuff. Worse, I’d put all this in iTunes Match, so even if I cleaned out my library, turning iTunes Match on again would just put all the crud back.
In addition, my partner didn’t have a music library at all because her internal disk on her laptop was too small to keep all of her work and optional stuff as well. There was an offline copy of her old music library, and it too had also grown over the years from music lent to her, music I thought she might like, etc. She wanted to be able to pack up her CD collection and put it into storage, and maybe get rid of some of it as well. So we needed to take our old libraries and clean out anything that we didn’t want, and then see what each other might have that the other person might want afterward.
I spent a couple evenings last week ripping the CDs she didn’t have online yet into a separate library, so they wouldn’t be part of the existing mess, and then went through and did the following in a brand new library:
Anything she actually owned got copied in. iPhoto’s ability to let me photograph the discs on the shelf and copy the text off of them came in very handy to make sure i got them all.
Anything I didn’t find in the library on that pass got ripped into this new library.
The not-previously ripped CDs in the secondary library were copied in.
At this point, she had a clean “definitely mine” library. Now it was time to clean mine up. I had done one pass already to strip it down, but I wanted to make sure that I both cleaned out my iTunes Match library and made a conscious decision, “keep or not” for anything in there that I didn’t already have in the stripped-down library.
The easiest way to do this was to to create a brand new, empty library, and connect that to iTunes Match, after turning on the “I want lossless copies” option — this is apparently new in Ventura, and is very welcome. Once this synced up, I could download and copy in only things I knew I wanted to keep. This meant I would actually have to look at the music and say, “do I really want to listen to this again?”, but not having to pull it out of an existing library would help.
In addition, my partner had asked me to give her a copy of music of mine that I know she likes; we share a liking for world music, and several different other artists. After a little thought, I came up with the following:
There’s probably music in iTunes Match that we both want, and there’s definitely music I want. So let’s do this:
Create a new folder on a scratch disk that will contain music to add to her library.
Do the same for music I want to add to mine.
Drag those into the favorites in the finder.
Drag the Media folder from my target library to the sidebar as well. This will let me quickly check to see if a given release is already in my library , and if it is I can skip downloading it altogether, unless I want to give my partner a copy.
As I process each release in the Match library, I do the following:
If my partner would like it, download it.
If I want to keep it myself, open a Finder window using the Media folder shortcut and check if I have it.
If I do, simply delete it from the iTunes Match library (which also takes it out of iTunes Match).
If I don’t, download it.
If I downloaded it, right-click on one track in the iTunes list, and “Show in Finder”. This pops up a new Finder window with all the tracks for the release in it.
Command-Click on the folder name in the top bar of the window and go up one level to see the release in its enclosing folder.
Drag the release folder to the sidebar aliases for the “music to add” folders as appropriate.
Delete the tracks in iTunes. This removes them from the iTunes Match library, and iTunes Match as well.
This took the better part of two days to finish, but I now have two cleaned-up music libraries, and an empty iTunes Match. I am considering whether to retain iTunes Match, mostly because it’s not a “backup” — it’s just a convenient way to share music across my devices, and doesn’t guarantee I’ll get the original file back.
I’ve probably lost fidelity on some of the tracks I added to Match, and it’s possible some of them now have DRM. I will do another pass at some point and see; I’m not sure if it really makes a lot of difference to me right now, but I can always play them through Audio Hijack and re-record them to remove the DRM if I decide I want to.
We also wanted a list of “what you have that I don’t” for both the final libraries; I was able to do that with Google Sheets, but I’ll post that as a separate article.
I recent wrote a blog post on the Zip tech blog about Go concurrency; it’s mostly an intro to how channels and select both work, and how to use them effectively.
