jzimbel's recent activity

  1. Comment on Server-Side Rendering is a Thiel Truth in ~comp

    jzimbel
    Link Parent
    If you're willing to pick up Elixir, the Phoenix framework has recently added a "LiveView" feature that allows developers to create purely server-side rendered interactive web applications. It...

    If you're willing to pick up Elixir, the Phoenix framework has recently added a "LiveView" feature that allows developers to create purely server-side rendered interactive web applications. It does look like it supports components.

    Full disclosure, I only recently started using Elixir at a new job, and while we do use Phoenix here, we haven't used LiveView for anything yet. I don't know a lot about this beyond the fact that it exists, so I can't say how user-friendly the component system is.

    5 votes
  2. Comment on This isn’t the flattened curve we were promised in ~health.coronavirus

    jzimbel
    Link
    I’d encourage people to check out the mathematical models on this, since pure math is harder to bullshit and relatively simple to understand. The SIR model for example has shown this asymmetrical,...

    I’d encourage people to check out the mathematical models on this, since pure math is harder to bullshit and relatively simple to understand. The SIR model for example has shown this asymmetrical, slow-falling infection curve since the beginning.

    Here are a few nice videos:

    5 votes
  3. Comment on Americans' opinions on the coronavirus are changing fast in ~health.coronavirus

    jzimbel
    Link Parent
    I feel the same way after seeing this video today of Trump laughing at my state's governor for complaining that he lost out to the fed on 3 bids for PPE and other essential equipment after...

    I feel the same way after seeing this video today of Trump laughing at my state's governor for complaining that he lost out to the fed on 3 bids for PPE and other essential equipment after following the instructions Trump himself gave. The fact that states are competing with the federal government for goods is terrifying. The fact that all Trump could say was "you should have bid more" is terrifying. People will die as a direct result of this. I have a lot less confidence that the goods will be used effectively in the fed's hands than in those of individual states.

    I think residents of even mid-sized US cities will be completely left to their own devices for surviving this disease within a week or two.

    6 votes
  4. Comment on How would you reduce speeding by car drivers? in ~talk

  5. Comment on How would you reduce speeding by car drivers? in ~talk

    jzimbel
    (edited )
    Link Parent
    This is called traffic calming, and I’d argue that it’s the “correct” answer to OP’s question. It is the main technique employed by countries like the Netherlands, and it has been extremely...

    This is called traffic calming, and I’d argue that it’s the “correct” answer to OP’s question. It is the main technique employed by countries like the Netherlands, and it has been extremely effective—they consistently hover around the least traffic fatalities per capita worldwide.

    The idea is simple and grounded in basic design principles: instead of telling people how to use a system, design the system such that users are implicitly guided to use it as intended and stay within acceptable limits.

    9 votes
  6. Comment on Day 10: Monitoring Station in ~comp

    jzimbel
    Link
    The amount of raw math involved in this one made it really difficult. I had an especially tough time getting the angle calculation right for the second part, due to a combination of factors: The...

    The amount of raw math involved in this one made it really difficult. I had an especially tough time getting the angle calculation right for the second part, due to a combination of factors:

    1. The angle 0 should start at "up", not "right". And to complicate the mental model more, "up" on our grid is -y, not +y.
    2. The angle should advance in a clockwise direction as it increases, not counterclockwise as is the norm in polar coordinate systems.
    3. Atan2 returns values in the range [-π,π] (in a disjoint way—if y ≥ 0, Atan2 returns a positive; if y < 0 it returns a negative) but we need to have the range [0,2π] in order for sorting the list of polar coordinates to work for this problem.

    This would have been a good candidate for test-driven development, but instead I was stubborn and went through a lot of trial and error, and graph paper.

    I also spent some extra time making my GCD (greatest common denominator) function memoized, and it turned out to only save maybe 20 nanoseconds overall, if anything, since Go is just that fast.

    Things I learned from this puzzle:

    • Floating-point arithmetic is tricky and not super well documented. Took me a while to track down the correct way to get an epsilon value for testing float equality in Go: epsilon = math.Nextafter(n1, n2) - n1.
    • Go is fast enough that sometimes it's not worth making certain optimizations in code—seems like the compiler either does them under the hood for you, or the runtime is just flat out really really fast.
    • Trig is hard, and trig in programming languages is harder.
    • Never assign a pointer to a map key on a variable while iterating through said map. It changes, so all of your pointers end up referring to the same key in the map at the end of the loop.
    • Go purposely randomizes the order that maps are iterated through (like, more than the usual coincidental "randomness" that happens because of how hash maps are implemented) so that developers have no chance of mistakenly assuming they can iterate through a map's keys in the order they were inserted.

    GitHub link with sane tab widths

    Parts 1 and 2, Go
    package d10
    
    import (
    	"math"
    	"sort"
    	"strings"
    
    	"github.com/jzimbel/adventofcode-go/solutions"
    )
    
    const (
    	// width and height of my puzzle input, used for some slight optimizations
    	width  = 24
    	height = 24
    )
    
    var epsilon float64
    
    type point struct {
    	x int
    	y int
    }
    
    type grid map[point]struct{}
    
    // stores memoized results
    var gcdCache map[[2]int]int
    
    // gcd returns the greatest common denominator of two ints.
    // Results are memoized for a slight performance bump.
    func gcd(a, b int) (n int) {
    	var key [2]int
    	if a < b {
    		key = [...]int{a, b}
    	} else {
    		key = [...]int{b, a}
    	}
    
    	var ok bool
    	if n, ok = gcdCache[key]; !ok {
    		if b != 0 {
    			n = gcd(b, a%b)
    		} else {
    			n = a
    		}
    		gcdCache[key] = n
    	}
    	return
    }
    
    // axisDistances returns (separately) the x and y distances between two points.
    func axisDistances(p1, p2 *point) (xDist int, yDist int) {
    	xDist, yDist = int(math.Abs(float64(p1.x-p2.x))), int(math.Abs(float64(p1.y-p2.y)))
    	return
    }
    
    func isBlocked(p1, p2 *point, g grid) (blocked bool) {
    	denom := gcd(axisDistances(p1, p2))
    	xStepSize, yStepSize := (p2.x-p1.x)/denom, (p2.y-p1.y)/denom
    	for i := 1; i < denom; i++ {
    		if _, ok := g[point{p1.x + i*xStepSize, p1.y + i*yStepSize}]; ok {
    			blocked = true
    			break
    		}
    	}
    	return
    }
    
    func part1(g grid) (maxVisibleCount int, optimalPoint point) {
    	for p1 := range g {
    		var visibleCount int
    		for p2 := range g {
    			if p1 == p2 {
    				continue
    			}
    			if !isBlocked(&p1, &p2, g) {
    				visibleCount++
    			}
    		}
    		if visibleCount > maxVisibleCount {
    			maxVisibleCount = visibleCount
    			optimalPoint = p1
    		}
    	}
    	return
    }
    
    type rPoint struct {
    	r    float64
    	θ    float64 // #codegolfing
    	orig point
    }
    
    // rPoints is an ordered list of radial (or polar) coordinates.
    // Polar axis (where θ = 0) is up.
    type rPoints []rPoint
    
    func (rg rPoints) Len() int {
    	return len(rg)
    }
    
    func (rg rPoints) Less(i, j int) bool {
    	if math.Abs(rg[i].θ-rg[j].θ) < epsilon {
    		return rg[i].r < rg[j].r
    	}
    	return rg[i].θ < rg[j].θ
    }
    
    func (rg rPoints) Swap(i, j int) {
    	rg[i], rg[j] = rg[j], rg[i]
    }
    
    // dist returns the Euclidean distance between two points. ( sqrt(a**2 + b**2) )
    func dist(p1, p2 *point) float64 {
    	return math.Sqrt(math.Pow(math.Abs(float64(p1.x-p2.x)), 2) + math.Pow(math.Abs(float64(p1.y-p2.y)), 2))
    }
    
    // clockwiseAngleFromUp calculates the angle from -y in radians of the ray from p1 to p2, moving clockwise.
    // Atan2 normally takes arguments as (y,x), but we reverse them and negate x in order to
    // have polar θ = 0 be Cartesian (0,-1) and increasing θ move in a clockwise direction.
    // Atan2 also produces values in range [-π, π], but we want them to be [0, 2π],
    // so when it would normally produce a negative, we use 2π + atan2Result.
    func clockwiseAngleFromUp(p1, p2 *point) (θ float64) {
    	newX, newY := -(p2.y - p1.y), p2.x-p1.x
    	θ = math.Atan2(float64(newY), float64(newX))
    	if θ < 0 {
    		θ = 2*math.Pi + θ
    	}
    	return
    }
    
    func part2(g grid, optimalPoint point) int {
    	// record angle and distance from center of each asteroid in a sorted slice of struct {rad float64; dist float64}
    	rp := make(rPoints, 0, len(g))
    	for p := range g {
    		if p == optimalPoint {
    			continue
    		}
    		rp = append(rp, rPoint{r: dist(&optimalPoint, &p), θ: clockwiseAngleFromUp(&optimalPoint, &p), orig: p})
    	}
    	sort.Sort(rp)
    
    	var vaporizedCount int
    	for len(rp) > 0 {
    		nextRp := make(rPoints, 0, len(rp))
    		remove := make([]*point, 0, len(rp))
    		for i := range rp {
    			if isBlocked(&optimalPoint, &rp[i].orig, g) {
    				nextRp = append(nextRp, rp[i])
    			} else {
    				vaporizedCount++
    				if vaporizedCount == 200 {
    					return rp[i].orig.x*100 + rp[i].orig.y
    				}
    				remove = append(remove, &rp[i].orig)
    			}
    		}
    
    		for i := range remove {
    			delete(g, *remove[i])
    		}
    		rp = nextRp
    	}
    	// unreachable as long as there are at least 200 asteroids on the grid
    	return 0
    }
    
    // Solve provides the day 10 puzzle solution.
    func Solve(input string) (*solutions.Solution, error) {
    	g := make(grid, width*height)
    	rows := strings.Split(input, "\n")
    	for y := range rows {
    		for x := range rows[y] {
    			if rows[y][x] == '#' {
    				g[point{x, y}] = struct{}{}
    			}
    		}
    	}
    	maxVisibleCount, optimalPoint := part1(g)
    
    	return &solutions.Solution{Part1: maxVisibleCount, Part2: part2(g, optimalPoint)}, nil
    }
    
    func init() {
    	epsilon = math.Nextafter(1, 2) - 1
    	gcdCache = make(map[[2]int]int, width*height)
    }
    
    1 vote
  7. Comment on Day 7: Amplification Circuit in ~comp

    jzimbel
    Link
    I'm pretty far behind, but I really enjoyed this one as it was ideally suited to Go's channel-based concurrency model. I got each amplifier series to run concurrently, and even within a single...

    I'm pretty far behind, but I really enjoyed this one as it was ideally suited to Go's channel-based concurrency model. I got each amplifier series to run concurrently, and even within a single series had the individual amplifiers running in their own goroutines, passing inputs and outputs around via channels.

    Some notes

    I'm not including my intcode interpreter implementation because it's unchanged from day 5. All you really need to know is that interpreter.New takes a program ([]int), an input device (func() int), and an output device (func(int)).
    I'm also omitting the code that loads the puzzle input from a file into a string as I keep that logic in a separate package that's used by all of my solutions.

    If you want to view the code in GitHub, it's here. Go code is kind of rough to view in-browser—it uses tabs for indentation, and most browsers have default tab width set to 8 spaces. In GitHub you can set the tab width using the ?ts query param. I set it to 2 in that link.

    Parts 1 and 2, Go
    package d07
    
    import (
    	"strconv"
    	"strings"
    	"sync"
    
    	"github.com/jzimbel/adventofcode-go/solutions"
    	"github.com/jzimbel/adventofcode-go/solutions/y2019/interpreter"
    	"modernc.org/mathutil"
    )
    
    const (
    	ampCount          = 5
    	initialInput      = 0
    	minPhase     uint = 0
    	maxPhase     uint = 4
    )
    
    // Implements sort.Interface to take advantage of mathutil Permutation functions
    type phaseSettings [ampCount]uint
    
    func (ps *phaseSettings) Len() int {
    	return len(ps)
    }
    
    func (ps *phaseSettings) Less(i, j int) bool {
    	return ps[i] < ps[j]
    }
    
    func (ps *phaseSettings) Swap(i, j int) {
    	ps[i], ps[j] = ps[j], ps[i]
    }
    
    // phaseSettingsGenerator returns a channel that receives all permutations of phase settings and then closes.
    // ch1 := phaseSettingsGenerator(0)
    // ch1 will receive [0 1 2 3 4], [0 1 2 4 3], ...
    // ch2 := phaseSettingsGenerator(5)
    // ch2 will receive [5 6 7 8 9], [5 6 7 9 8], ...
    func phaseSettingsGenerator(offset uint) <-chan *phaseSettings {
    	ch := make(chan *phaseSettings)
    
    	go func() {
    		defer close(ch)
    		ps := &phaseSettings{}
    		for i := uint(0); i < ampCount; i++ {
    			ps[i] = i + offset
    		}
    		mathutil.PermutationFirst(ps)
    
    		var done bool
    		for !done {
    			psCopy := *ps
    			ch <- &psCopy
    			done = !mathutil.PermutationNext(ps)
    		}
    	}()
    
    	return ch
    }
    
    // makeInputDevice returns an input function to be used by the amplifier intcode program.
    // The first time the input is called, it return the phase setting for the amplifier.
    // All future calls return values received from the given channel.
    func makeInputDevice(phaseSetting uint, ch <-chan int) func() int {
    	callCount := 0
    	return func() (n int) {
    		defer func() { callCount++ }()
    		switch callCount {
    		case 0:
    			n = int(phaseSetting)
    		default:
    			n = <-ch
    		}
    		return
    	}
    }
    
    // makeOutputDevice returns an output function to be used by the amplifier intcode program.
    // This function sends its argument to the given channel.
    func makeOutputDevice(ch chan<- int) func(int) {
    	return func(n int) {
    		ch <- n
    	}
    }
    
    // makeLoopingOutputDevice is like makeOutputDevice, but the function it produces sends values to
    // two given channels instead of one. This allows for signals to be passed in a loop but also received
    // by an outside function that's interested in the final output of the amplifiers.
    func makeLoopingOutputDevice(loop chan<- int, output chan<- int) func(int) {
    	return func(n int) {
    		loop <- n
    		output <- n
    	}
    }
    
    // runAmplifiers runs a series of amplifiers with the given phase settings and returns their output.
    func runAmplifiers(codes []int, settings *phaseSettings) (signal int) {
    	// 0 -> Amp A -> Amp B -> Amp C -> Amp D -> Amp E -> (to thrusters)
    	// 5 amps, 6 channels
    	chs := [ampCount + 1]chan int{}
    	for i := range chs {
    		chs[i] = make(chan int)
    	}
    
    	for i := 0; i < ampCount; i++ {
    		go func(icpy int) {
    			interpreter.New(codes, makeInputDevice(settings[icpy], chs[icpy]), makeOutputDevice(chs[icpy+1])).Run()
    		}(i)
    	}
    
    	chs[0] <- initialInput
    	return <-chs[ampCount]
    }
    
    // runAmplifierLoop runs a series of amplifiers in a loop with the given phase settings and returns their final output when they halt.
    func runAmplifierLoop(codes []int, settings *phaseSettings) (signal int) {
    	// 0 -> Amp A -> Amp B -> Amp C -> Amp D -> Amp E -> (to thrusters upon Amp E halt)
    	//    0        1        2        3        4        0
    	// 5 amps, 5 channels
    	chs := [ampCount]chan int{}
    	for i := range chs {
    		if i == 0 {
    			// use a buffered channel for the first channel so that it can receive
    			// one more value that won't be consumed during the final iteration of the loop
    			chs[i] = make(chan int, 1)
    		} else {
    			chs[i] = make(chan int)
    		}
    	}
    	// final amplifier also sends to this channel so that we can capture outputs
    	output := make(chan int)
    
    	for i := 0; i < ampCount; i++ {
    		go func(icpy int) {
    			var outDevice func(int)
    			if icpy == ampCount-1 {
    				// when this interpreter halts, the whole amplifier loop is done
    				defer close(output)
    				outDevice = makeLoopingOutputDevice(chs[(icpy+1)%ampCount], output)
    			} else {
    				outDevice = makeOutputDevice(chs[(icpy+1)%ampCount])
    			}
    			interpreter.New(codes, makeInputDevice(settings[icpy], chs[icpy]), outDevice).Run()
    		}(i)
    	}
    
    	chs[0] <- initialInput
    	var finalSignal int
    	for n := range output {
    		finalSignal = n
    	}
    	return finalSignal
    }
    
    func run(codes []int, phaseSettingOffset uint, runner func([]int, *phaseSettings) int) (maxSignal int) {
    	ch := make(chan int)
    	wg := sync.WaitGroup{}
    
    	for settings := range phaseSettingsGenerator(phaseSettingOffset) {
    		wg.Add(1)
    		go func(settings *phaseSettings) {
    			defer wg.Done()
    			ch <- runner(codes, settings)
    		}(settings)
    	}
    
    	go func() {
    		defer close(ch)
    		wg.Wait()
    	}()
    
    	for signal := range ch {
    		if signal > maxSignal {
    			maxSignal = signal
    		}
    	}
    	return
    }
    
    func part1(codes []int) int {
    	return run(codes, 0, runAmplifiers)
    }
    
    func part2(codes []int) int {
    	return run(codes, 5, runAmplifierLoop)
    }
    
    // Solve provides the day 7 puzzle solution.
    func Solve(input string) (*solutions.Solution, error) {
    	numbers := strings.Split(input, ",")
    	codes := make([]int, len(numbers))
    	for i, n := range numbers {
    		intn, err := strconv.Atoi(n)
    		if err != nil {
    			return nil, err
    		}
    		codes[i] = intn
    	}
    
    	return &solutions.Solution{Part1: part1(codes), Part2: part2(codes)}, nil
    }
    
  8. Comment on Day 6: Universal Orbit Map in ~comp

    jzimbel
    Link
    This puzzle was good practice with pointers, which I'm a little rusty on. I've started using Go at work, and it's the first language with explicit pointers that I've used since C and C++ in some...

    This puzzle was good practice with pointers, which I'm a little rusty on. I've started using Go at work, and it's the first language with explicit pointers that I've used since C and C++ in some college courses.

    My approach was to create a standard tree data structure for the orbits, but also simultaneously create a map that associates each celestial object name with a pointer to its node in the tree. This made for easy and quick access to any node in the tree, from which it could be traversed as needed.

    Loading the input from a file into a string isn't included in this code because I keep that logic in a separate package that's used by all of my solutions.

    Parts 1 and 2, Go
    package d06
    
    import (
    	"regexp"
    	"strings"
    
    	"github.com/jzimbel/adventofcode-go/solutions"
    )
    
    // intermediate data structure to make building the tree easier
    type orbitMap map[string][]string
    
    // standard tree structure with awareness of its parent and depth from the root
    type tree struct {
    	label    string
    	depth    uint
    	parent   *tree
    	children []*tree
    }
    
    // allows for fast access to any node in a tree by its label
    type flatTree map[string]*tree
    
    const (
    	centerOfMass string = "COM"
    	you          string = "YOU"
    	santa        string = "SAN"
    )
    
    var pattern = regexp.MustCompile(`(.+)\)(.+)`)
    
    // makeFlatTree creates a flatTree that points to nodes in an underlying tree.
    func makeFlatTree(om orbitMap) flatTree {
    	ft := make(flatTree, len(om))
    
    	var buildTree func(string, uint, *tree) *tree
    	buildTree = func(label string, depth uint, parent *tree) *tree {
    		t := tree{
    			label:    label,
    			children: make([]*tree, 0, len(om[label])),
    			depth:    depth,
    			parent:   parent,
    		}
    		for i := range om[label] {
    			t.children = append(t.children, buildTree(om[label][i], depth+1, &t))
    		}
    		ft[label] = &t
    		return &t
    	}
    
    	buildTree(centerOfMass, 0, nil)
    	return ft
    }
    
    func (ft flatTree) sumDepths() (count uint) {
    	for _, t := range ft {
    		count += t.depth
    	}
    	return
    }
    
    func (t *tree) getAncestors() []*tree {
    	ancestors := make([]*tree, t.depth)
    	current := t
    	for i := uint(0); i < t.depth; i++ {
    		current = current.parent
    		ancestors[i] = current
    	}
    	return ancestors
    }
    
    func getCommonAncestor(t1 *tree, t2 *tree) (common *tree) {
    	ancestors1 := t1.getAncestors()
    	ancestors2 := t2.getAncestors()
    
    	// put the second list of ancestors into a set for faster existence checking between the two lists
    	compareSet := make(map[*tree]struct{}, len(ancestors2))
    	for _, ancestor := range ancestors2 {
    		compareSet[ancestor] = struct{}{}
    	}
    	for _, ancestor := range ancestors1 {
    		if _, ok := compareSet[ancestor]; ok {
    			common = ancestor
    			break
    		}
    	}
    	return
    }
    
    func parseInput(input string) (om orbitMap) {
    	lines := strings.Split(input, "\n")
    	om = make(orbitMap, len(lines))
    	for _, line := range lines {
    		matches := pattern.FindStringSubmatch(line)
    		base, satellite := matches[1], matches[2]
    		if _, ok := om[base]; ok {
    			om[base] = append(om[base], satellite)
    		} else {
    			om[base] = []string{satellite}
    		}
    	}
    	return
    }
    
    func part1(ft flatTree) uint {
    	return ft.sumDepths()
    }
    
    func part2(ft flatTree) uint {
    	common := getCommonAncestor(ft[you].parent, ft[santa].parent)
    	return (ft[you].parent.depth - common.depth) + (ft[santa].parent.depth - common.depth)
    }
    
    // Solve provides the day 6 puzzle solution.
    func Solve(input string) (*solutions.Solution, error) {
    	ft := makeFlatTree(parseInput(input))
    	return &solutions.Solution{Part1: part1(ft), Part2: part2(ft)}, nil
    }
    
    2 votes
  9. Comment on Advent of Code 2019 in ~comp

    jzimbel
    Link
    If anyone's interested, I have projects in Python and Go that auto-download puzzle inputs for you and pass them to your solution function as a string. All you have to provide is your session ID...

    If anyone's interested, I have projects in Python and Go that auto-download puzzle inputs for you and pass them to your solution function as a string. All you have to provide is your session ID which is stored in a cookie on the site.

    Python
    Go

    Feel free to fork if they seem useful. :)

    3 votes
  10. Comment on What do you daydream about? in ~talk

    jzimbel
    Link
    My mind is a broken record lately. Like for the past three years. It’s not great. Climate change Climate change Climate change Climate change How to fix climate change before we’re all living...

    My mind is a broken record lately. Like for the past three years. It’s not great.

    • Climate change
    • Climate change
    • Climate change
    • Climate change
    • How to fix climate change before we’re all living something like this

    I’ve found myself using work and TV as an escape more and more lately.

    4 votes
  11. Comment on Remove Richard Stallman in ~tech

    jzimbel
    Link
    Also see the /r/programming comments on same, and discussions in other subreddits. Hacker News comments are a bit more level-headed as usual. I think a lot of the reactions to this are strong...

    Also see the /r/programming comments on same, and discussions in other subreddits. Hacker News comments are a bit more level-headed as usual.

    I think a lot of the reactions to this are strong examples of the "guys who love logic" phenomenon posted and discussed here on Tildes about two weeks ago.

    22 votes
  12. Comment on What are you playing this week? in ~games

    jzimbel
    Link Parent
    I just want to add another recommendation for Baba. It’s probably the best puzzle game I’ve ever played. I’m almost done with every level now, and the last few are really challenging. There’s even...

    I just want to add another recommendation for Baba. It’s probably the best puzzle game I’ve ever played.

    I’m almost done with every level now, and the last few are really challenging. There’s even a great Easter egg in one of the levels!

    I think the most astonishing thing about this game is that, if some of the puzzles are this hard to solve, it must have been at least doubly hard for the game creator to formulate them in the first place. How on earth did he do that?

    3 votes
  13. Comment on What have you been listening to this week? in ~music

    jzimbel
    Link
    The National recently released a single leading up to their new album releasing in May, which I thought was decent, but they simultaneously released a Spotify playlist containing their entire...

    The National recently released a single leading up to their new album releasing in May, which I thought was decent, but they simultaneously released a Spotify playlist containing their entire discography (over 8 hours long!). I’ve been listening through that and even found a few great tracks that I’ve somehow missed in the past, like Humiliation.

    I’m more of a fan of their older work without the electronic bits mixed into the sound, but am nonetheless very excited about the approaching album release.

  14. Comment on What have you been listening to this week? in ~music

    jzimbel
    Link Parent
    Here’s a nice Italian song for you: Senza Un Perché Full disclosure—I only know about this song because it’s on the soundtrack of The Young Pope. I don’t even know what the lyrics mean. 😅

    Here’s a nice Italian song for you: Senza Un Perché

    Full disclosure—I only know about this song because it’s on the soundtrack of The Young Pope. I don’t even know what the lyrics mean. 😅

    1 vote
  15. Comment on What have you been listening to this week? in ~music

    jzimbel
    Link
    I discovered D.D Dumbo this past week. Really enjoying the unique sound he’s got going on. My favorite tracks: Satan Brother (only the live version is available on YouTube; be sure to check out...

    I discovered D.D Dumbo this past week. Really enjoying the unique sound he’s got going on.

    My favorite tracks:

    1. Satan
    2. Brother (only the live version is available on YouTube; be sure to check out the album version as well)
    3. Tropical Oceans

    If anyone has similar artists to recommend, please don’t hold back.

    2 votes
  16. Comment on Programming Challenge: Shape detection. in ~comp

    jzimbel
    Link Parent
    I iterated on this a little too much and ended up with a thing that finds all the squares in the input grid and prints the grid back out with all of the squares bolded. from sys import stdin MARK...

    I iterated on this a little too much and ended up with a thing that finds all the squares in the input grid and prints the grid back out with all of the squares bolded.

    from sys import stdin
    
    MARK = '\033[1m'
    END_MARK = '\033[0m'
    
    def getGrid(str):
      '''
      Computes and returns a 2D list of booleans from the input string.
      Grid is surrounded in a "frame" of False values (representing the "unfilled"
      border) to make finding squares at the edge of the grid easier.
      '''
      grid = [
        [True if char == '1' else False for char in line]
        for line in str.split('\n')
      ]
      rowLength = len(grid[0])
      if any(len(row) != rowLength for row in grid):
        raise ValueError('Input grid must have equal-length rows.')
      boundaryRow = [False for x in grid[0]]
      grid.insert(0, boundaryRow)
      grid.append(boundaryRow)
      return [
        [False] + row + [False]
        for row in grid
      ]
    
    def getSquareStarts(row):
      '''
      Computes a list of 2-tuples, each giving the start and end indices of a contiguous filled segment in this row.
      End indices are exclusive: a tuple (2,5) means that there's a contiguous filled segment covering cells 2,3, and 4.
      '''
      contiguousSegments = []
      previousWasFilled = False
      inContiguousSegment = False
      for i, cell in enumerate(row):
        if previousWasFilled and cell:
          if inContiguousSegment:
            contiguousSegments[-1] = (contiguousSegments[-1][0], i + 1)
          else:
            contiguousSegments.append((i - 1, i + 1))
        inContiguousSegment = previousWasFilled and cell
        previousWasFilled = cell
      return contiguousSegments
    
    def findSquaresInGrid(grid):
      '''
      Returns a list containing (x, y, sidelength) tuples where x and y give the coordinates of the top left corner of a
      filled square in the given grid.
      '''
      squares = []
      for i, row in enumerate(grid):
        for startIndex, endIndex in getSquareStarts(row):
          # So far we've found a single contiguous horizontal line of filled cells that might be the start of a square.
          # Now we just need to check a bunch of things to see if it really is one.
          sidelength = endIndex - startIndex
          if (
            # are there enough rows left in the (non-bordered) grid to fit a square this tall?
            i + sidelength <= len(grid) - 1
            # do all segments from startIndex to endIndex in rows below this one have all filled spaces?
            and all(
              all(row[startIndex:endIndex])
              for row in grid[i:i + sidelength]
            )
            # does the previous row have all unfilled spaces adjacent to this segment?
            and not any(grid[i - 1][startIndex:endIndex])
            # does the row after the last expected row of the square have all unfilled spaces adjacent to this segment?
            and not any(grid[i + sidelength][startIndex:endIndex])
            # does the column to the left of the left side of the expected square have all unfilled spaces?
            and not any(row[startIndex - 1] for row in grid[i:i + sidelength])
            # does the column to the right of the right side of the expected square have all unfilled spaces?
            and not any(row[endIndex] for row in grid[i:i + sidelength])
          ):
            squares.append((startIndex - 1, i -1, sidelength))
      return squares
    
    def markSquares(inputString):
      '''
      Finds solid squares of "1"'s in the given input and returns a new string with each square marked in bold.
      '''
      squares = findSquaresInGrid(getGrid(inputString))
      output = inputString.split('\n')
      for i in range(len(squares)):
        cornerX, cornerY, sidelength = squares[i]
        for y in range(cornerY, cornerY + sidelength):
          output[y] = (
            output[y][:cornerX]
            + MARK
            + output[y][cornerX:cornerX + sidelength]
            + END_MARK
            + output[y][cornerX + sidelength:]
          )
        # adjust x indices that were affected by the insertion of the formatting characters
        squares = [
          (
            otherX + len(MARK) + len(END_MARK) if otherY in range(cornerY, cornerY + sidelength) and otherX >= cornerX else otherX,
            otherY,
            otherSidelength
          )
          for otherX, otherY, otherSidelength in squares
        ]
      return '\n'.join(output)
    
    def main():
      if stdin.isatty():
        print 'Enter a grid. Enter a blank line when done.'
      inputString = ''
      inputLine = None
      while inputLine != '':
        try:
          inputLine = raw_input()
        except EOFError:
          break
        inputString += inputLine + '\n'
      inputString = inputString.strip()
      print markSquares(inputString)
    
    if __name__ == '__main__':
      main()
    

    Fun thing: save a 2D 0's and 1's Menger sponge generated by this script and pass it to my python script to see it highlight everything nicely.

    python mark_squares.py < menger_sponge.txt
    
    2 votes
  17. Comment on Programming Challenge: Shape detection. in ~comp

    jzimbel
    (edited )
    Link
    Python 2.7: This operates by searching the grid from top to bottom for horizontal segments of 2 or more contiguous filled cells within a row, then starting a search anchored from each contiguous...

    Python 2.7:
    This operates by searching the grid from top to bottom for horizontal segments of 2 or more contiguous filled cells within a row, then starting a search anchored from each contiguous segment found for a shape like:

     000 
    01110               * the 111 in this row is the contiguous segment we start from
    01110
    01110
     000
    

    (arbitrarily scalable)
    If any such shape is found, then the grid contains a square.

    def contiguousReducer(acc, enumeratedCell):
      '''
      Based on state passed in the (acc)umulator and current cell's value, returns
      a new state for the next cell.
      State is a 3-tuple containing, in order:
      - a list of 2-tuples, each giving the start and end indices of a contiguous filled segment in this row found so far
      - a boolean indicating whether the previous visited cell was filled
      - a boolean indicating whether we're currently in a contiguous filled segment
      '''
      i, cell = enumeratedCell
      contiguousSegments, previousWasFilled, inContiguousSegment = acc
      if previousWasFilled and cell:
        if inContiguousSegment:
          contiguousSegments = contiguousSegments[:-1] + [(contiguousSegments[-1][0], i + 1)]
        else:
          contiguousSegments = contiguousSegments + [(i - 1, i + 1)]
      return (
        contiguousSegments,
        cell,
        previousWasFilled and cell
      )
    
    def getSquareStarts(row):
      '''
      Computes a list of 2-tuples, each giving the start and end indices of a contiguous filled segment in this row.
      End indices are exclusive: a tuple (2,5) means that there's a contiguous filled segment covering cells 2,3, and 4.
      '''
      return reduce(contiguousReducer, enumerate(row), ([], False, False))[0]
    
    def gridContainsSquare(grid):
      for i, row in enumerate(grid):
        for startIndex, endIndex in getSquareStarts(row):
          # So far we've found a single contiguous horizontal line of filled cells that might be the start of a square.
          # Now we just need to check a bunch of things to see if it really is one.
          sidelength = endIndex - startIndex
          if (
            # are there enough rows left in the (non-bordered) grid to fit a square this tall?
            i + sidelength <= len(grid) - 2
            # are there enough columns left in the (non-bordered) grid to fit a square this wide?
            and startIndex + sidelength <= len(row) - 2
            # do all segments from startIndex to endIndex in rows below this one have all filled spaces?
            and all(
              all(cell for cell in row[startIndex:endIndex])
              for row in grid[i:i + sidelength]
            )
            # does the previous row have all unfilled spaces adjacent to this segment?
            and not any(grid[i - 1][startIndex:endIndex])
            # does the row after the last expected row of the square have all unfilled spaces adjacent to this segment?
            and not any(grid[i + sidelength][startIndex:endIndex])
            # does the column to the left of the left side of the expected square have all unfilled spaces?
            and not any(row[startIndex - 1] for row in grid[i:i + sidelength])
            # does the column to the right of the right side of the expected square have all unfilled spaces?
            and not any(row[endIndex] for row in grid[i:i + sidelength])
          ):
            return True
      return False
    
    def getGrid(str):
      '''
      Computes and returns a 2D list of booleans from the input string.
      Grid is surrounded in a "frame" of False values (representing the "unfilled"
      border) to make finding squares at the edge of the grid easier.
      '''
      grid = [
        [True if char == '1' else False for char in line]
        for line in str.split('\n')
      ]
      boundaryRow = [False for x in grid[0]]
      grid.insert(0, boundaryRow)
      grid.append(boundaryRow)
      return [
        [False] + row + [False]
        for row in grid
      ]
    
    def inputContainsSquare(inputString):
      return gridContainsSquare(getGrid(inputString))
    
    inputA = '''
    000000
    011100
    011100
    011100
    000010
    '''.strip()
    inputB = '''
    000000
    011100
    011100
    011110
    000000
    '''.strip()
    inputC = '''
    000000
    011100
    010100
    011100
    000000
    '''.strip()
    
    print inputContainsSquare(inputA) # True
    print inputContainsSquare(inputB) # False
    print inputContainsSquare(inputC) # False
    
    3 votes
  18. Comment on <deleted topic> in ~life

    jzimbel
    Link
    Really interesting piece, thanks for sharing. The pragmatic approach is pretty refreshing compared to that of the "We have N years remaining to stop using fossil fuels entirely"-type articles that...

    Really interesting piece, thanks for sharing. The pragmatic approach is pretty refreshing compared to that of the "We have N years remaining to stop using fossil fuels entirely"-type articles that are more common. Still unfathomably alarming to think about, but at least it lays out the choices people have if we really are starting down a long global decline.

    6 votes
  19. Comment on Firefox Color V2 released in ~tech

    jzimbel
    Link
    I love the Windows 3.1 Hot Dog Stand throwback on the last page of preset themes.

    I love the Windows 3.1 Hot Dog Stand throwback on the last page of preset themes.

    4 votes