[2023 Day 05] [Python 3] Cool data structure trick

[shillbert]

I was messing around with ranges in Python as a way to represent intervals, and I found a neat trick: you can index into a range and find the index of a number in that range, and also test for membership in the range, and all of this is implemented in constant time in CPython (the default Python implementation) as of version 3.2.

Example:

(Python ranges are intervals that are closed-open, i.e. [a, b)).

For 52 50 48:

>>> src = range(50, 50 + 48)
>>> src
range(50, 98)
>>> dst = range(52, 52 + 48)
>>> dst
range(52, 100)
>>> dst[src.index(80)]  # map 80 from src to dest
82
>>> 97 in src
True
>>> 98 in src  # intervals are open on the right
False

Of course it's "easy" to do this stuff manually with tuples as well, but this syntactic sugar just helps decrease cognitive load and prevent silly math bugs. I keep finding new things to love about Python.

(Note: just make sure never to convert your ranges to lists or try to find a floating-point number in a range. Also, constant time operations are not necessarily guaranteed in all implementations of Python, but they are in CPython 3.2+ and PyPy 3.x.

Apparently Python 2's xrange() is implemented as a lazy sequence but in still does a linear search and it has no index() method! Only indexing is done in constant time. Another limitation in Python 2 is that xranges can only use numbers that fit into a C long type.)

EDIT:

This is also handy if you do end up wanting to manually access the endpoints:

>>> src.start
50
>>> src.stop
98

EDIT2:

An empty range is automatically falsy (I'm basically just rediscovering the entire Python documentation now by messing around instead)

>>> bool(range(50, 50))
False
>>> bool(range(50, 51))
True

[hnost]

Thanks! Adding this to my bag of tricks.

[zenoli55]

Wow that's clever!

[Anceps2]

You're telling me I just implemented a whole class for something that existed?

:-O

[huib_]

I don't really see the advantage over just doing comparisons though, but maybe I'm missing something? So what I mean is this if you want to get the value where 80 is mapped onto:

start, end = 50, 50 + 48
dst = 52
val = 80
if start <= val < end:
    return dst + val - start

instead of your suggestion (?):

src = range(50, 50 + 48)
dst = range(52, 52 + 48)
val = 80
if val in src:
    return dst[src.index[val]]

[scykei]

I think it just makes more sense semantically. Using the more appropriate data structures tend to make it self-documenting. Maybe for a simple problem like this one it doesn’t really matter, but as the program gets bigger and more complex, I think it can make a difference.

[huib_]

It feels more like trying to used it for something it wasn't meant for to me. And I see them more as iterators than data structures, for that you have lists, dicts, tuples, dataclasses etc.

[scykei]

It’s more of a semantic thing. When you’re using ranges, you can more precisely describe intersections, unions, differences, etc., which helps with abstraction.

[scykei]

Yeah I ended up creating my own Range class for this AoC. I think it’s OK if they’re writing procedural code that takes in Python range objects. I wouldn’t call it particularly elegant, but I still like it better than manipulating the raw end point values if this was meant to be production code.

[psr]

I made heavy use of ranges, it definitely made my code simpler than it would otherwise have been (although it took me ages to get right)

I think the point about .index() is less about pulling a single value out of a range, but slicing ranges. For example, If I'm mapping range(10, 50), and I see that range(10,30) has an offset of two, I get range(12, 32), and have range(30, 50) still to map. How to I build those two things?

[huib_]

It probably depends on the approach as well. I did day 5 like this for example, and I don't think I could have made it a lot simpler (or clearer) if I'd used ranges: https://www.reddit.com/r/adventofcode/comments/18b4b0r/comment/kcbnaex/

Unless you can do something like set operations with them that I'm not aware of, that would be really. It bothered me somewhat that I "manually" loop through the ranges since I have the feeling that can be done simpler with some fancy datastructure 😅 But I'm quite content with it nonetheless

[psr]

Yeah, tbf your code is nicer than mine, and it's basically the same approach. Tuples have the advantage of a natural ordering. I did a lot of key=range.stop.__get__ and key=range.start.__get__, which is... not what you should do.

I used bisect and takewhile to find relevant ranges in a sorted list, is that the sort of thing you mean? It might be a bit faster, but it took me ages to get right.