I spy with my little eye a number beginning with n++

7

1

If you have ever travelled with kids more than about 20 minutes, you will have no doubt heard cries of "Are we there yet?" and "How much further?"

So we play games like "I Spy" to help pass the time as the miles go by.

There is a variation on "I Spy" whereby instead of spotting arbitrary named things, you must spot integers in strictly ascending order. Numbers are everywhere - licence plates, street names and numbers, street signs, adverts and so on - the list goes on; so this would appear to be a trivial game, so there are some restrictions to make this more challenging*:

  • Each number must be spied in isolation - if the next number you need to spy is 7 and you see house number 17 then this does not count. However license plate 7ABC123 would be OK.
  • In general, numbers may be considered "in isolation" if they are separated by any non digit separator, though there are some exceptions
  • Fractions cannot be used. For example if you see a road sign saying "Albuquerque ¾ mile" (or even "Albuquerque 3/4 mile") you would not be able to spy either the "3" or the "4"
  • Conversely if you see a date written as "3/4/2015" you may spy any of the "3", "4" or "2015"
  • Decimals are a bit tricky. If you see "Ford Escort 1.3 litre", the 1.3 here counts a non-integer and the "1" and "3" parts cannot be used in isolation. However if you see "Ford Mustang 5.0 liter", you may spy this as a 5, because even though 5.0 is written as a decimal it is in fact a whole number.
  • You may only spy numbers seen outside of the vehicle - so the ascending seconds of a your car's digital clock may not be spied. If you are lucky enough to see such a clock outside of the vehicle, then you may spy those ascending seconds until you can no longer see them (or they wrap to the next minute)
  • You may see descending countdown seconds at a pedestrian crossing. Because numbers must be spied in ascending order, you will only be able to spy at most one number per pedestrian crossing.
  • Numbers with leading zeros can be spied - for example the "020" in a London phone number would be acceptable as 20.

Challenge

The kids have already got bored of this game, so they want a program to play it for them. This program must do the following:

  • Read input from an unbounded stream. This will most likely be STDIN or equivalent pipe, though (theoretically at least) something like a TCP session could be used. Function parameters or command-line options generally won't work as there will be limits to how much data is passed. However some kind of pointer or reference to an unbounded stream would be OK.
  • The input stream will consist of random printable ASCII characters, as generated by tr -dc '[:print:]' < /dev/urandom on Linux. The input will generally not have newlines (these are control characters and not printable), so the input will effectively be one unbounded-length line.
  • Spy ascending integers appearing in the stream starting at 0. This spying is subject the rules of the game above. In particular:
    • Numbers may only be spied if they are isolated, i.e. separated by non-digits
    • Numbers with leading zeros must be spied
    • No numbers may be spied from a substring <sep>n/m<sep>, where <sep> is any legal separator other than /
    • Decimals of the form <sep>n.0*<sep> (where 0* indicates 0 or more zeros) should be spied, but decimals with non-zero fractional parts should not be spied. Numbers in dotted decimals such as IP addresses where there is more than one . should be spied.
  • For output, we need to keep track of what we have spied to so far. Every spied number should be output when it is spied. However we don't want to see a long stream of ascending numbers, so each number output must overwrite the previous one in some way. This may be achieved using escape characters, backspaces, output to some kind of textbox or any other method appropriate to your language.
  • The program will continue spying until either the input stream ends, or until interrupted by the user (e.g. CTRL-c or button click)
  • Your counter must be able to count up to at least 2^31-1. Above that, behavior may be undefined.

Examples

0 1 2 3 4 5 6 7 8 9 10   will spy up to 10
0a1b2c3d4e5f6g7h8i9j10   will spy up to 10
10 9 8 7 6 5 4 3 2 1 0   will spy up to 0
0 1 1 1 1 1 2 2 2 2 2    will spy up to 2
00 01 023 4 5            will spy up to 1
0 1 2 3/4 5              will spy up to 2
0 1 2 3/4/2015 5 6       will spy up to 6
0 1 2 3.1415 4 5 6       will spy up to 2
0 1 2 3.000 4 5 6        will spy up to 6
0 1 2 192.168.0.3 4      will spy up to 4
Output from `tr -dc '[:print:]' < /dev/urandom` or equivalent will spy up forever (or until interrupted)

*This game is harder than you might think - I tried it yesterday driving through the Bay Area for 2 hours and only got as far as 14.

Digital Trauma

Posted 2015-12-30T18:35:53.417

Reputation: 64 644

1What if [my language of choice]'s STDIN is buffered on newline? Can each character be separated by a newline? – Doorknob – 2015-12-30T18:37:05.197

I would prefer removing the "overwirte previous output" requirement entirely. Instead, why not just have the program output the index of first occurrence of each number? – quintopia – 2015-12-30T18:40:39.577

3I don't think there's a good reason to require an "unbounded" input stream, because for most languages it's just impossible or impractical. for instance, in python, i believe i would have to override sys.stdin and sys.stdout. this requirement seems shockingly arbitrary. – cat – 2015-12-30T19:01:11.780

@Doorknob冰 No - sorry - this is a hard requirement. In fact the I/O requirements are what interested me most about this challenge. The rest is just (likely) regex and counting, for which there are plenty of other challenges. – Digital Trauma – 2015-12-30T19:23:09.783

@quintopia Nope, sorry, I would prefer to keep this requirement ;-) – Digital Trauma – 2015-12-30T19:23:44.363

4@DigitalTrauma Hmm... what seems far more complex about this challenge to me is the rules for when to count numbers. – Doorknob – 2015-12-30T19:24:18.673

@cat The "good reason" to me is that there are few, if any challenges that have this kind of stipulation. I'm most interested in how different languages can handle this – Digital Trauma – 2015-12-30T19:26:10.303

@Doorknob冰 the counting rules certainly add some spice, but I'm pretty sure you regex wizards will handle them without too much difficulty (previous comment deleted and vulgar typo fixed in this version ;-)) – Digital Trauma – 2015-12-30T19:40:42.370

I went on a 12 hour trip from CA to Oregon and found the whole alphabet and up to 171. :P – Rɪᴋᴇʀ – 2015-12-30T19:50:23.483

@RikerW I didn't know anyone else actually plays this game ;-) Do you enforce any same or similar restrictions? I probably missed a lot while negotiating traffic :-/ – Digital Trauma – 2015-12-30T19:54:10.963

Some, I do dates are illegal too, and bonus points if you find a 5 zeros in a row. :P That one almost never gets found, and is like an instant win. – Rɪᴋᴇʀ – 2015-12-30T20:01:50.167

I also do 1 point per number, and the highest points at the end wins.

You still have to count up, but there are different bonuses for long numbers, specific number sequences, and a couple others. Like 10 extra points for a 3+ digit totient number. :P – Rɪᴋᴇʀ – 2015-12-30T20:03:22.177

Is 2 in 1.2/3/1015 part of a decimal and can't be spied, or part of a date and can? – nimi – 2015-12-30T21:18:18.250

Really easy way to do this: Wait until you get to Exit 1 on a highway, and count up until you get off of it. :P – ev3commander – 2015-12-30T22:14:16.800

@BlockCoder1392 - depends how your exits are numbered - in the US, most seem to be numbered as per the closest mile marker, so there are plenty of missed numbers – Digital Trauma – 2015-12-30T22:15:57.270

Not where I live... Anyway, what if a date is there without a year (e.g. 12/30 meaning december 30th?) – ev3commander – 2015-12-30T22:19:43.753

@BlockCoder1392 In that case, we just have to assume its a rational and ignore it – Digital Trauma – 2015-12-30T22:22:46.727

@nimi Part of a decimal, and thus can't be spied – Digital Trauma – 2015-12-30T22:24:35.207

What about times (eg.12:24 PM or 7:09 AM or 23:15) – ev3commander – 2015-12-31T00:12:37.520

@BlockCoder1392 Here the colons are like any other non-digit separator. 12, 24, 7, 09, 23 and 15 may all be treated as numbers in isolation – Digital Trauma – 2015-12-31T00:22:20.563

Thanks for lazy evaluation, in Haskell, we can call function with infinite length string. So I think the question should be restricted for full program, but allow functions. And in other language we can use generator as argument. – Akangka – 2015-12-31T06:23:47.230

Answers

2

sh, 170

tr -cs 0-9/. '\n'|
grep -vxEe"[0-9]+/[0-9]+" -e"[0-9]*\.0*[1-9][0-9]*"|
sed -r 's/^([0-9]*)\.0+$/0\1/'|
tr -s /. '\n'|
awk -vORS="\r" '$1==l{l=$1+1;print l-1}END{print "\n"}'

Rainer P.

Posted 2015-12-30T18:35:53.417

Reputation: 2 457

Doesn't quite work on my Ubuntu 14.04 - seems to be a problem with the awk - I am getting output from the last tr, but nothing from the awk – Digital Trauma – 2015-12-31T03:35:41.133

Fixed. Does not delete last output when working on bounded streams now. – Rainer P. – 2015-12-31T10:12:42.767