Discussion:
Google Code Jam 2020: "Overrandomized" solution - where's my bug?
(too old to reply)
Simon Leinen
2020-05-03 15:13:59 UTC
Permalink
Google does an annual coding competition called "Code Jam"[0]. I like
their problems very much, and since I haven't been able to use Lisp
professionally much lately, I've been participating using Lisp (SBCL),
which they kindly support (again).

My participation this year ended yesterday in round 1C. I ran out of
time trying to debug a solution to problem 2 "Overrandomized"[1]. This
is vexing because I don't know why or where this would always cause a RE
(runtime error), despite working fine in all of my tests. Even after
the deadline I haven't been able to fix this. My current still-broken
code (commented version on GitHub[2]):

------------------------------ snip ------------------------------
(labels
((i2c (i) (code-char (+ i #.(char-code #\A))))
(c2i (c) (- (char-code c) #.(char-code #\A))))
(dotimes (caseno (read))
(format t "Case #~D: " (+ caseno 1))
(let ((u (read))
(seen 0)
(d1-counters (make-array (list 26) :initial-element 0)))
(declare (ignore u))
(dotimes (i 10000)
(let ((qi (read))
(ri (read-line)))
(declare (ignore qi))
(incf (aref d1-counters (c2i (char ri 0))))
(dotimes (k (length ri))
(setf seen (logior seen (ash 1 (c2i (char ri k))))))))
(let ((zero (dotimes (i 26 0)
(when (and (logbitp i seen) (zerop (aref d1-counters i)))
(return i)))))
(write-char (i2c zero))
(let ((sorted-counters (sort (copy-seq d1-counters) #'>)))
(dotimes (i 9)
(write-char (i2c (position (aref sorted-counters i) d1-counters)))))))
(terpri)))
------------------------------ snip ------------------------------

Any idea what the problem might be?

What's most frustrating is that when I re-implemented the method in
C++/C, it worked right away 8-(
--
Simon.
[0] https://codingcompetitions.withgoogle.com/codejam/
[1] https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4/00000000003179a1
[2] https://github.com/sleinen/gcj2020/blob/master/1c/2.lisp
Madhu
2020-05-04 06:28:17 UTC
Permalink
Post by Simon Leinen
My participation this year ended yesterday in round 1C. I ran out of
time trying to debug a solution to problem 2 "Overrandomized"[1]. This
is vexing because I don't know why or where this would always cause a RE
(runtime error), despite working fine in all of my tests. Even after
the deadline I haven't been able to fix this. My current still-broken
(labels
((i2c (i) (code-char (+ i #.(char-code #\A))))
(c2i (c) (- (char-code c) #.(char-code #\A))))
(dotimes (caseno (read))
(format t "Case #~D: " (+ caseno 1))
(let ((u (read))
(seen 0)
(d1-counters (make-array (list 26) :initial-element 0)))
(declare (ignore u))
(dotimes (i 10000)
(let ((qi (read))
(ri (read-line)))
(declare (ignore qi))
(incf (aref d1-counters (c2i (char ri 0))))
(dotimes (k (length ri))
(setf seen (logior seen (ash 1 (c2i (char ri k))))))))
(let ((zero (dotimes (i 26 0)
(when (and (logbitp i seen) (zerop (aref d1-counters i)))
(return i)))))
(write-char (i2c zero))
(let ((sorted-counters (sort (copy-seq d1-counters) #'>)))
(dotimes (i 9)
(write-char (i2c (position (aref sorted-counters i) d1-counters)))))))
(terpri)))
Any idea what the problem might be?
I think the only runtime error that is possible is the array out of
bounds error. The only way that can happen is because you are misreading
the input. (I doubt this is any type inference bug in the particular
version of lisp that the organizers were running.)

I turned on javascript (and the browser downloaded some 9MB google junk)
to look at the page.

:Then, exactly 10^4 lines follow. Each of these lines contains an
integer Q[i] (in base 10 using digits 0 through 9, as usual) and
a string R[i], representing the i-th query and response,
respectively. If Q[i] = -1, then the integer M[i] used for the
i-th query is unknown. Otherwise, Q[i] = M[i]."

I don't think you are handling this case where Q[i]=1 where you have to
skip the rest of the line. Instead your program read-line will read the
*next* line
Post by Simon Leinen
What's most frustrating is that when I re-implemented the method in
C++/C, it worked right away 8-(
No it would have the same problem. You say you have never gotten a
runtime error with lisp on your own (well-formed) data without -1 in the
first column. You wouldn't get an error for the same algorithm in C++
either.

If you did actually get an error when running the program you could just
have looked at the debugger and see what the runtime error was and fixed
it
Simon Leinen
2020-05-04 11:04:42 UTC
Permalink
Dear Madhu,

thanks for looking at this. You certainly brought me on the right track!
Post by Madhu
I think the only runtime error that is possible is the array out of
bounds error. The only way that can happen is because you are
misreading the input.
Right; it turns out my program had trouble reading the input correctly.
But I still don't quite understand why. The input for each case
consists of a line containing a single positive integer <U> followed by
10000 lines of the form "<Q[i]> <R[i]>", where

* Q[i] is either -1 (meaning "lost") or an integer between 1 and 10^U-1
* R[i] is a sequence of 1..U upper-case alphabetic characters.

My original code read these Q[i] / R[i] lines using the following idiom:

(1)
(dotimes (i 10000)
(let ((qi (read))
(ri (read-line)))
...

...and it crashes.

Now I rewrote this to

(2)
(dotimes (i 10000)
(let ((line (read-line)))
(let ((space-pos (position #\Space line)))
(let ((qi (parse-integer line :start 0 :end space-pos))
(ri (subseq line (1+ space-pos))))

...and it no longer crashes. In fact it now solves the problem by
giving the expected output for all input sets. Yay!

I can even add a bunch of ASSERTs - to make sure the input looks like I
think it should - and it still works fine without crashing:

(3)
(dotimes (i 10000)
(let ((line (read-line)))
(let ((space-pos (position #\Space line)))
(assert space-pos)
(assert (not (zerop space-pos)))
(let ((qi (parse-integer line :start 0 :end space-pos))
(ri (subseq line (1+ space-pos))))
(assert (or (= qi -1) (<= 1 qi (- (expt 10 u) 1))))
(assert (<= 1 (length ri) u))
(assert (every #'alpha-char-p ri))
(assert (every #'upper-case-p ri))

This leaves me wondering what a legal input line might look like that
isn't read correctly by my naive code (1), but that IS read correctly by
(2) and doesn't trigger any ASSERT in (3).

I could probably find this out experimentally, but I think it's a nice
Common Lisp puzzle, and maybe someone here has an idea.

Anyway, it bothers me that I have to think about these things. I'd
rather know that I can just use (READ) to read any decimal integer and
the single space following it, and that a subsequent (READ-LINE) will
read the rest of the line after the space.

Having to write code like (2) to parse such simple input adds mental
load. Yes, I know that in a "real" program I should not use (READ) to
read an integer... but for harmless puzzles it would seem appropriate.
Post by Madhu
(I doubt this is any type inference bug in the particular version of
lisp that the organizers were running.)
At one point I was wondering whether the SBCL version on the Code Jam
platform is buggy. In fact I don't know exactly which SBCL version is
installed there - the FAQ mentions exact versions for other languages,
but not for Lisp. Looks like Google forgot to extend the FAQ when they
added Lisp support in 2019. Locally I use 2.0.2.
Post by Madhu
I turned on javascript (and the browser downloaded some 9MB google junk)
to look at the page.
Sorry about that.
Post by Madhu
:Then, exactly 10^4 lines follow. Each of these lines contains an
integer Q[i] (in base 10 using digits 0 through 9, as usual) and
a string R[i], representing the i-th query and response,
respectively. If Q[i] = -1, then the integer M[i] used for the
i-th query is unknown. Otherwise, Q[i] = M[i]."
I don't think you are handling this case where Q[i]=1 where you have to
skip the rest of the line. Instead your program read-line will read the
*next* line
Even when Q[i]=-1 (I think you meant -1 rather than 1), the R[i] value
will be present in the input.
Post by Madhu
Post by Simon Leinen
What's most frustrating is that when I re-implemented the method in
C++/C, it worked right away 8-(
No it would have the same problem. You say you have never gotten a
runtime error with lisp on your own (well-formed) data without -1 in the
first column. You wouldn't get an error for the same algorithm in C++
either.
Sorry, I should have clarified that when I ran this against my own input
sets, I *did* generate some sets where (all) Q[i] were -1. But the R[i]
were also present, as that's how I understand the description. This is
plausible, because if Q[i] is -1 and R[i] were missing, then you
wouldn't have any information at all to go on. Also, the fact that (3)
works corroborates that R[i] is always there (and a non-empty string of
upper-case alphabetic characters).

And conversely, I actually submitted my C++ and C implementations to the
platform, and their results were accepted against the same input that
caused runtime errors with my initial Lisp code.
Post by Madhu
If you did actually get an error when running the program you could just
have looked at the debugger and see what the runtime error was and fixed
it
Yes, that's true. But the Code Jam environment doesn't permit this.
You submit your code, the platform runs it, and responds with either "✓"
(check mark/correct), or "WA" (wrong answer), or "RE" (runtime error)
for each input set (as soon as one input set results in anything other
than "correct", the larger input sets won't even be attempted).

So there's no real possibility to interact with the platform for
debugging, except trying to intentionally terminate with a "WA" in an
attempt to "bisect" where the "RE" might happen.

Again, thank you for your help!
--
Simon.
Madhu
2020-05-04 12:36:17 UTC
Permalink
Post by Simon Leinen
(1)
(dotimes (i 10000)
(let ((qi (read))
(ri (read-line)))
...
...and it crashes.
I can even add a bunch of ASSERTs - to make sure the input looks like I
(3)
(dotimes (i 10000)
(let ((line (read-line)))
(let ((space-pos (position #\Space line)))
(assert space-pos)
(assert (not (zerop space-pos)))
(let ((qi (parse-integer line :start 0 :end space-pos))
(ri (subseq line (1+ space-pos))))
(assert (or (= qi -1) (<= 1 qi (- (expt 10 u) 1))))
(assert (<= 1 (length ri) u))
(assert (every #'alpha-char-p ri))
(assert (every #'upper-case-p ri))
Yes this gives the lie to my theory that the code was bombing because
R[i] was empty,
Post by Simon Leinen
This leaves me wondering what a legal input line might look like that
isn't read correctly by my naive code (1), but that IS read correctly by
(2) and doesn't trigger any ASSERT in (3).
I could probably find this out experimentally, but I think it's a nice
Common Lisp puzzle, and maybe someone here has an idea.
I'm stumped.
Post by Simon Leinen
Anyway, it bothers me that I have to think about these things. I'd
rather know that I can just use (READ) to read any decimal integer and
the single space following it, and that a subsequent (READ-LINE) will
read the rest of the line after the space.
Having to write code like (2) to parse such simple input adds mental
load. Yes, I know that in a "real" program I should not use (READ) to
read an integer... but for harmless puzzles it would seem appropriate.
(Personally I would obsessive-compulsively put every READ call within a
(*read-eval* nil) scope and perhaps with-standard-io-syntax) I can't
imagine what input this is failing on.
Post by Simon Leinen
And conversely, I actually submitted my C++ and C implementations to the
platform, and their results were accepted against the same input that
caused runtime errors with my initial Lisp code.
Ah yes I should have guessed

Loading...