3 ms·

> Q: Can I make assumptions on the names of the weather stations showing up in the data set? > A: No, while only a fixed set of station names is used by the da

> Q: Can I make assumptions on the names of the weather stations showing up in the data set? > A: No, while only a fixed set of station names is used by the data set generator, any solution should work with arbitrary UTF-8 station names (for the sake of simplicity, names are guaranteed to contain no `;` character). I'm unsure if it's intentional or not, but this essentially means that the submission should be correct for all inputs, but can and probably should be tuned for the particular input regenerated by `create_measurements.sh`. I can imagine submissions with a perfect hash function tuned for given set of stations, for example.

Hugsun 3y ago
Given this requirement, they would be wise to have the test data be different from the example data. That would prevent overfitting optimizations.
- josephg 3y ago
  I'm not sure that it is overfitting to optimize your code for the test set. The requirement is just that you don't break compatibility for arbitrary names in the process. This sort of thing shows up all the time in the real world - where, for example, 90% of traffic will hit one endpoint. Or 90% of a database is one specific table. Discovering and microoptimizing for the common case is an important skill.
  - lifthrasiir 3y ago
    That's why I was so unsure. I think though, that it is generally better to have the input generator seeded and do not disclose the chosen seed in advance, which prevents overfitting to a single input and yet encourages overfitting to a much bigger class of inputs.
    - rocqua 3y ago
      That invites probing submissions to figure out a good hash for all names from that one seed. I think having the names for performance tests public is fine. But there should be correctness tests on sets with random names.
      - lifthrasiir 3y ago
        Of course, I assume names are also randomly generated. But it might be the case that they are all ASCII-only, which can be exploited.
  - gunnarmorling 3y ago
    Their should be no optimizations which rely on a-priori knowledge of the dataset. I.e. if you calculate a perfect hash function at runtime by inspecting the dataset, that's fine (not sure whether it's beneficial), but hard coding it, is not.
    - johndough 3y ago
      That is a tricky rule to enforce. For example, some solutions assume that the temperature values fit into an int, which could be interpreted as relying on a priori knowledge.
      - Hugsun 3y ago
        That's true. Some assumptions always have to be made. In this case, we can assume place names that can be arbitrary strings and temperatures that occur naturally on earth. Optimizing around those constraints should be fine. We could probably limit the string length to something like 100 characters or so. Bad assumptions would for example be to assume that all possible place names are found within the example data.
      - sfn42 3y ago
        Somehow I doubt any weather station would register temperatures above 2,14 billion degrees
londons_explore 3y ago
UTF-8 makes this far harder... But if you stick to the letter but not spirit of the rules, you can simply fall back to a slow implementation if you ever detect any byte > 127 (indicating a multibyte UTF-8 character).
- jerf 3y ago
  Only if you validate the UTF-8 as being valid. If you just accept that it is you can treat it as just some bytes. Nothing in the spec I see requires processing UTF-8 as an actual Unicode string. The easiest way to handle Unicode is to not handle it at all, and just shove it down the line. This is often even correct, as long as you don't need to do any string operations on it. If the author wanted to play Unicode games, requiring normalization would be the way to go, but that would turn this into a very different challenge.
  - alkonaut 3y ago
    Since the tail of the line has a known format I guess we are rescued by the fact that the last 0x3B is the semicolon as the rest is just a decimal number. We can’t know the first 0x3B byte is the semicolon since the place names are only guaranteed to not contain 0x3B but can contain 0x013B. So a parser should start from the rear of the line and read the number up to the semicolon and then it can treat the place name as byte soup. Had two places shared line this challenge would have required real utf parsing and been much harder.
    - jerf 3y ago
      Yes, sorry, I'm so used to this sort of thing with the work I've been doing lately I forgot to lay it out like that. Thank you for filling it in for me.
    - marginalia_nu 3y ago
      I'm not sure scanning backwards this helps. Running in reverse you still need to look for a newline scanning over an UTF-8 string which might plausibly contain a newline byte. I'm no UTF-8 guru, but I think you might be possible to do this sort of a springboard for skipping over multi-byte codepoints, since as far as I understand the upper bits of the first byte encodes the length: byte utfByte1 = (byte) (val & 0xF0); if (utfByte1 == (byte) 0xF0) { // 4 byte codepoint // ignore 3 } else if (utfByte1 == (byte) 0xE0) { // 3 byte codepoint // ignore 2 } else if (utfByte1 == (byte) 0xC0) { // 2 byte codepoint // ignore 1 }

Hugsun 3y ago

Given this requirement, they would be wise to have the test data be different from the example data. That would prevent overfitting optimizations.

josephg 3y ago
I'm not sure that it is overfitting to optimize your code for the test set. The requirement is just that you don't break compatibility for arbitrary names in the process. This sort of thing shows up all the time in the real world - where, for example, 90% of traffic will hit one endpoint. Or 90% of a database is one specific table. Discovering and microoptimizing for the common case is an important skill.
- lifthrasiir 3y ago
  That's why I was so unsure. I think though, that it is generally better to have the input generator seeded and do not disclose the chosen seed in advance, which prevents overfitting to a single input and yet encourages overfitting to a much bigger class of inputs.
  - rocqua 3y ago
    That invites probing submissions to figure out a good hash for all names from that one seed. I think having the names for performance tests public is fine. But there should be correctness tests on sets with random names.
    - lifthrasiir 3y ago
      Of course, I assume names are also randomly generated. But it might be the case that they are all ASCII-only, which can be exploited.
- gunnarmorling 3y ago
  Their should be no optimizations which rely on a-priori knowledge of the dataset. I.e. if you calculate a perfect hash function at runtime by inspecting the dataset, that's fine (not sure whether it's beneficial), but hard coding it, is not.
  - johndough 3y ago
    That is a tricky rule to enforce. For example, some solutions assume that the temperature values fit into an int, which could be interpreted as relying on a priori knowledge.
    - Hugsun 3y ago
      That's true. Some assumptions always have to be made. In this case, we can assume place names that can be arbitrary strings and temperatures that occur naturally on earth. Optimizing around those constraints should be fine. We could probably limit the string length to something like 100 characters or so. Bad assumptions would for example be to assume that all possible place names are found within the example data.
    - sfn42 3y ago
      Somehow I doubt any weather station would register temperatures above 2,14 billion degrees

londons_explore 3y ago

UTF-8 makes this far harder... But if you stick to the letter but not spirit of the rules, you can simply fall back to a slow implementation if you ever detect any byte > 127 (indicating a multibyte UTF-8 character).

jerf 3y ago
Only if you validate the UTF-8 as being valid. If you just accept that it is you can treat it as just some bytes. Nothing in the spec I see requires processing UTF-8 as an actual Unicode string. The easiest way to handle Unicode is to not handle it at all, and just shove it down the line. This is often even correct, as long as you don't need to do any string operations on it. If the author wanted to play Unicode games, requiring normalization would be the way to go, but that would turn this into a very different challenge.
- alkonaut 3y ago
  Since the tail of the line has a known format I guess we are rescued by the fact that the last 0x3B is the semicolon as the rest is just a decimal number. We can’t know the first 0x3B byte is the semicolon since the place names are only guaranteed to not contain 0x3B but can contain 0x013B. So a parser should start from the rear of the line and read the number up to the semicolon and then it can treat the place name as byte soup. Had two places shared line this challenge would have required real utf parsing and been much harder.
  - jerf 3y ago
    Yes, sorry, I'm so used to this sort of thing with the work I've been doing lately I forgot to lay it out like that. Thank you for filling it in for me.
  - marginalia_nu 3y ago
    I'm not sure scanning backwards this helps. Running in reverse you still need to look for a newline scanning over an UTF-8 string which might plausibly contain a newline byte. I'm no UTF-8 guru, but I think you might be possible to do this sort of a springboard for skipping over multi-byte codepoints, since as far as I understand the upper bits of the first byte encodes the length: byte utfByte1 = (byte) (val & 0xF0); if (utfByte1 == (byte) 0xF0) { // 4 byte codepoint // ignore 3 } else if (utfByte1 == (byte) 0xE0) { // 3 byte codepoint // ignore 2 } else if (utfByte1 == (byte) 0xC0) { // 2 byte codepoint // ignore 1 }