3 ms·
Their code was horrific. My algorithm: import itertools import collections candidates = [s for s in itertools.product(range(100), range(100)) if s[0]<=s
by blagie 4y ago
Their code was horrific. My algorithm:
import itertools
import collections
candidates = [s for s in itertools.product(range(100), range(100)) if s[0]<=s[1]]
def solutions_filter(sols, agg, flip=False):
aggregates = [agg(s) for s in sols]
d = collections.defaultdict(lambda:0)
for s in aggregates:
d[s] = d[s]+1
if not flip:
return [s for s in sols if d[agg(s)] != 1]
else:
return [s for s in sols if d[agg(s)] == 1]
ns = candidates
for i in range(7):
ns = solutions_filter(ns, lambda x:x[0]*x[1])
ns = solutions_filter(ns, lambda x:x[0]+x[1])
print(solutions_filter(ns, lambda x:x[0]*x[1], flip=True))
(Usually, next step is variable names, comments, etc.)
- jcheng 4y agoMy logic was similar, in R: library(dplyr) combos <- expand.grid(x = 1:99, y = 1:99) |> filter(x <= y) |> # Remove dupes mutate(sum = x + y, prod = x * y) find_singletons <- function(col = c("sum", "prod")) { singletons <- combos %>% group_by(!!sym(col)) %>% tally() %>% filter(n == 1) which(combos[[col]] %in% singletons[[col]]) } for (i in 1:7) { # Peter: I don't know the numbers. combos <- combos[-find_singletons("prod"),] # Sandy: I don't know the numbers. combos <- combos[-find_singletons("sum"),] } # Peter: I know the numbers. combos[find_singletons("prod"),]
- blagie 4y agoTo people who either know: - both R and Python; or - neither R nor Python: Which of the solutions do you find more readable? (I have my own opinion, but I'm biased)
- otras 4y agoHorrific is a new one! Thanks for posting your solution :)
- blagie 4y agoIt's worth looking at the other solutions in-thread. Key points: - Use of higher-order operations, like filters and aggregations, to avoid loops. - Passing around functions (the * and + side are the same, except for one operation) to avoid repeated code This results in: - Less code. Defects per KLOC tends to be pretty constant, so shorter / higher-level programs are typically less buggy. - In particular, less repeated code. Cut-and-paste introduces a whole slew of potential defects. - Less dependence on order-of-operations, which eliminates whole classes of errors, from off-by-ones to data structures in intermediate inconsistent states. The relevant book here is still SICP.
- deleted 4y ago[deleted]
- xisukar 4y agoI am still trying to wrap my head around the problem. Here's my attempt at your implementation in Raku: sub solutions-filter(@sols, &agg, Bool:D :$flip = False) { my @aggregates = @sols.map({ agg($_) }); my %d; %d{$_} += %d{$_} ?? %d{$_} !! 1 for @aggregates; return @sols.grep({ %d{ agg($_) } == 1 }) if $flip; return @sols.grep({ %d{ agg($_) } != 1 }); } my @candidates = ((1..99) X (1..99)).grep({ $_[0] ≤ $_[1] }); my @ns = @candidates; for 1..7 { @ns = solutions-filter @ns, { $_[0] * $_[1] }; @ns = solutions-filter @ns, { $_[0] + $_[1] }; } say solutions-filter(@ns, { $_[0] * $_[1] }, :flip);
- yen223 4y agoNever thought I'd see anything more concise than Python, but here's the Kotlin version: data class Candidate(val x: Int, val y: Int) fun List<Candidate>.filterCandidates(knows: Boolean, aggBy: (Candidate) -> Int) = groupBy(aggBy) .values .filter {value -> if (knows) {value.count() == 1} else {value.count() > 1} } .flatten() fun main() { var cs = (1..99).flatMap { x -> (x..99).map { y -> Candidate(x, y) } } repeat(7) { cs = cs.filterCandidates(knows = false) { (x, y) -> x * y } cs = cs.filterCandidates(knows = false) { (x, y) -> x + y } } cs = cs.filterCandidates(knows = true) { (x, y) -> x * y } println(cs) }