If I had read the novel first, I would have said it was impossible to adapt into a movie. But what the screenwriters did was take the protagonists of the novel and construct a completely new plot in which those characters could play the same basic roles. The resulting movie is faithful to the spirit of the novel even though it’s radically unfaithful to the text. That’s an approach that would never have occurred to me; I think I’d be too reverent of the original to adapt anything to film.
I think the challenges of adapting Story of Your Life to film were different, but it was certainly something I was thinking about when I walked into the theater. I personally think they did a pretty good job, but I suppose that depends on what you thought the essential part of Story of Your Life was.
Now that I think about it, the movie Ender's Game was pretty faithful to the source novel, but probably fell down as a movie because of it. It's interesting to think about how that movie might have been better if it had tried to be (as Chiang says of L.A. Confidential) "faithful to the spirit of the novel" while playing faster and looser with the actual source material.