3 ms·

This is a sort I use all the time. Especially in coding challenges (AoC) because I'm usually lazy. It's nice to see it formally evaluated, it feels very intuiti

• ColinWright 2y ago
  This intrigues me. Would you be willing ... without looking at this article ... to provide exactly the code you "use all the time"? I'd like to compare what you write with the code in the article, because code that I write as a quick and dirty sort is definitely not this. In particular, this seems to take items that are already the right way round, and swaps them. I definitely don't do that. To be specific, I just knocked this out: #!/usr/bin/python a = [ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9 ] N = len(a) for i in range(0,N-2): for j in range(i+1,N-1): if a[i]>a[j]: a[i],a[j] = a[j],a[i] print a Specifically, note that I ask if a[i] is bigger than a[j] and if so then I swap them. The code in the article appears to do exactly the wrong thing, and I'd be surprised if your "go to" code does it the same way as the code in the article.
  • reedf1 2y ago
    Sure I have a "live" example in my 2024 AoC code. I'll add it here when I get home.
    • ColinWright 2y ago
      Fabulous ... thanks. I've bookmarked this bit of the thread so I can come back and check it. Cheers!
      • reedf1 2y ago
        Hi - for https://adventofcode.com/2024/day/5 https://adventofcode.com/2024/day/5 (Part 2): instructions = [] updates = [] with open("input.txt") as file: for line in file: line = line.rstrip() if line == "": break x, y = line.split('|') instructions.append((int(x), int(y))) for line in file: line = line.rstrip() pages = [int(i) for i in line.split(',')] updates.append(pages) def is_valid_update(update, instructions): pos = {num: idx for idx, num in enumerate(update)} for x, y in instructions: if x in pos and y in pos and pos[x] > pos[y]: return False return True valid_updates = [upd for upd in updates if is_valid_update(upd, instructions)] accum_valid = sum(upd[len(upd) // 2] for upd in valid_updates) print("Sum from valid updates:", accum_valid) def domain_sort(update, instructions): n = len(update) for i in range(n): for j in range(n): if (update[j], update[i]) in instructions: update[i], update[j] = update[j], update[i] return update invalid_updates = [upd for upd in updates if not is_valid_update(upd, instructions)] sorted_updates = [domain_sort(upd.copy(), instructions) for upd in invalid_updates] print("Sorted invalid updates:") for upd in sorted_updates: print(upd) accum_sorted = sum(upd[len(upd) // 2] for upd in sorted_updates) print("Sum from sorted invalid updates:", accum_sorted)
        • ColinWright 2y ago
          Gosh, I never thought I'd see this "in the wild"! I would have a hard time understanding why this finishes with the "updates" in the order expected instead of the opposite order, and I'm intrigued. In the paper it just seems to counter-intuitive to me that if the comparison is that way round then the items get swapped ... if I found this in code I was auditing then I'd spent a long time trying to work out what was going on. Thank you.
          • reedf1 2y ago
            Yes, not something I would write in production code. But very easy for me to think about in a stream of consciousness. Usually I complete the above challenges in about 5-10mins.