Gen install shenzhen fails 50% of the time

We install shenzhen in our circle.yml script and our builds fail 50% of the time on that command with the following error:

current directory: /Users/distiller/.gem/ruby/2.3.4/gems/nokogiri-1.8.0/ext/nokogiri
make "DESTDIR=" install
compiling html_document.c
In file included from html_document.c:1:
In file included from ./html_document.h:4:
./nokogiri.h:19:10: fatal error: 'libxml/parser.h' file not found
#include <libxml/parser.h>
1 error generated.
make: *** [html_document.o] Error 1

make install failed, exit code 2

You can see the failure here:
Same build (just a simple rebuild of the previous) succeeded here: