Skip to content

Sunday Times Teaser 3059 – Nine Blocks to the Diner

by BRG on May 8, 2021

by Colin Vout

Published Sunday May 09 2021 (link)

“Sure, I can help. From this hotel it’s nine blocks to the diner; from there it’s five blocks to the library, and then six blocks back here. I guess instead you could come back from the diner to the museum — that’s four blocks — and then seven blocks back here. Or three blocks to the gallery and then eight blocks back here.”

“So the diner’s straight along here?”

“No sir, it’s not straight along one road for any of these trips; I just meant so many edges of blocks. The city’s on a square grid, and all these places are on corners, but, fact is, none of them is on the same street or avenue as any other one.”

How many blocks between the library and the museum, museum and gallery, and gallery and library?

From → Uncategorized

11 Comments Leave one →
  1. Brian Gladman permalink

  2. John Z permalink

  3. John Z permalink

    Here is a solution using a recursive function to replace a large chunk of inline code in my previous solution in the hope of reducing the number of lines of code. In the event, there was no improvement. In this problem, the order in which the solution is found is indifferent which would indicate that a recursive function is not necessarily the best fit.

  4. Brian Gladman permalink

    Hi John,

    As you say, it was longer and no different in speed.

    The easiest way of increasing speed is to avoid looking in all four quadrants of the grid which would make it around five times faster.

    In terms of length, it rather depends on what count as lines since it would be a pity to loose all comments in pursuit of a ‘fewest lines’ objective. And in my experience reducing the number of code lines in Python can easily end up reducing the clarity of the code involved.

    Nevertheless, I do think that using a dictionary in place of a list, avoiding some list indexing and compressing some of the comments can shorten your code without impacting on its clarity:

  5. John Z permalink

    Hi Brian,
    Thanks for doing a rework of my second post. I’ll study your version with interest, in particular your use of a dictionary as opposed to a list. I had gotten the impression that dictionary access must be slower than list access. My lines 12,13 could have made CC into a tuple instead of a list but having to use ‘tuple(‘ twice instead of the single opening square brace character puts me off. CC as a tuple would I think be slightly faster.

    I did at one point limit the ‘Diner’ coordinate search to the NE quadrant but felt this was a bit of a fudge. I wasn’t trying for speed with this teaser.

    When counting lines of code, I don’t count comments and count continuation lines of a statement as additional lines of code.

    I agree: too much compaction can make code harder to comprehend.

    • Brian Gladman permalink

      HI John,

      Dictionaries are fundamental in Python since every aspect of the language uses them. For example, every time you define a variable it becomes a key in a dictionary that points to the variables current value. And because they are so fundamental a lot of effort goes into making them fast. Dictionary access will only be slower than list access only in rare circumstances and if a list is of any significant length, dictionary access will on average be a great deal faster. On average for 100 items a dictionary is typically six times faster, for 1000 items about 15 times faster and for 10 million items, 500,000 times faster. So it generally pays to use dictionaries if you can. The downside of dictionaries is that they use a lot more memory than lists.

      I understand the tuple inside a tuple issue and I, too, also often use lists to avoid this. There is also another subtle issue in that tuples inside tuples built using two left brackets in sequence ‘((‘ can mean that the inner tuple is not a tuple at all but a generator instead. So to be sure of getting a tuple inside a tuple it might be necessary to use the tuple(tuple( …)) construction.

  6. John Z permalink

    Here is an even more pared down version with savings based on the fact that the variables ‘st’ and ‘av’ contain the same information as ‘res’ but in a transposed form. This allows ‘res’ to be removed from the ‘fp’ argument list if ‘st’ and ‘av’ are kept in order as a list or tuple.

  7. Erling Torkildsen permalink

    I post a very basic approach. I whish I could have got my pos()-function just a little more compact not to speak of the cumbersome way the program checks that no institution is in the same street or avenue. But in the end of the day, it gets the answer based on all the eight possible locations..

    I shall try to figure out how Brian make use of the ‘class-object’ above. That will be a fundamental concept to learn.

    • Brian Gladman permalink

      Hi Erling,

      Its nice to see a different approach based on set intersection. You could use the following to reduce the length of the code:

      and

      • Erling Torkildsen permalink

        Thanks, Brian,

        I made some efforts to find something like your line 3, yet your simple suggestion escaped me!

      • Erling Torkildsen permalink

        After the suggested improvements:

        (With so much space gained, I added one line to allow for reporting the number of different locations involved.)

Leave a comment to Erling Torkildsen Cancel reply

Note: HTML is allowed. Your email address will not be published.

Subscribe to this comment feed via RSS