Sachverhalt:
A.
A._ wurde der Führerausweis im Jahr 2014 erstmals wegen Fahrens unter Drogeneinfluss auf unbestimmte Zeit entzogen. Aufgrund einer günstig verlaufenen Fahreignungsabklärung wurde er im August 2016 wieder zum motorisierten Strassenverkehr zugelassen, dies unter der Auflage, eine Drogenabstinenz einzuhalten und sich während der Dauer von zwölf Monaten in Abständen von sechs Monaten verkehrsmedizinischen Kontrolluntersuchungen zu unterziehen.
B.
Die erste Kontrolluntersuchung am Institut für Rechtsmedizin der Universität B._ (Institut C._) mittels Haaranalyse erfolgte am 17. Januar 2017. Sie ergab, dass A._ in den letzten vier bis acht Monaten Kokain konsumiert hatte. Daraufhin verfügte die Motorfahrzeugkontrolle des Kantons Solothurn (MFK) am 21. Februar 2017 einen vorsorglichen Führerausweisentzug. Da A._ den festgestellten Kokainkonsum bestritt und eine Verwechslung oder Kontaminierung der Haarprobe behauptete, holte die MFK beim Institut C._ eine Stellungnahme dazu ein. Dieses hielt an den Ergebnissen der Kontrolluntersuchung fest. Gestützt darauf bestätigte die MFK am 28. März 2017 ihre Verfügung. Eine von A._ dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Solothurn am 20. Juni 2017 ab.
C.
Am 31. August 2018 liess die MFK A._ erneut zum motorisierten Strassenverkehr zu, wobei er sich einer neuen, vollständigen Führerprüfung zu unterziehen hatte, um wieder in den Besitz des Führerausweises auf Probe zu gelangen. Die Zulassung wurde wiederum verbunden mit der Auflage der Drogenabstinenz; er wurde verpflichtet, sich während der Dauer von 18 Monaten in Abständen von sechs Monaten verkehrsmedizinischen Kontrolluntersuchungen mittels Haaranalyse zu unterziehen.
Die erste Kontrolluntersuchung erfolge am 12. November 2018 am Institut D._ in U._ und ergab, dass A._ im Zeitraum zwischen Ende April 2018 und Ende Oktober 2018 Kokain konsumiert hatte. Das Institut D._ kam zum Schluss, die Fahreignung von A._ könne nicht bejaht werden. In der Folge entzog ihm die MFK am 10. Dezember 2018 wegen der Missachtung von Auflagen vorsorglich den Lernfahrausweis.
D.
Da A._ den Kokainkonsum wiederum bestritt, holte die MFK auch diesmal eine Stellungnahme des begutachtenden Instituts ein. Das Institut D._ hielt in seinem Schreiben vom 16. Mai 2019 am Ergebnis seines Gutachtens fest und bestätigte, die Fahreignung von A._ könne nicht bejaht werden. Weil der festgestellte Kokainwert nicht hoch war, holte die MFK per Mail eine Stellungnahme von Dr. E._ vom Institut C._ ein. Diese gelangte zum Schluss, aus toxikologischer Sicht handle es sich um einen Grenzfall. Sie plädierte dafür, A._ eine Chance zu geben; seine Fahreignung könne unter Auflagen positiv beurteilt werden.
Gestützt auf diese Stellungnahme hob die MFK mit Verfügung vom 24. Mai 2019 den vorsorglichen Entzug des Lernfahrausweises wieder auf. Sie ordnete zugleich eine Drogentotalabstinenz an und verpflichtete A._ namentlich, sich während der Dauer eines Jahres in Abständen von sechs Monaten verkehrsmedizinischen Kontrolluntersuchungen inklusive Haarprobe zu unterziehen und während der Dauer der Auflage bei seinem Hausarzt zweiwöchentlich eine kurzfristig anberaumte Urinprobe abzugeben, die auf Drogen untersucht werde.
Das Verwaltungsgericht des Kantons Solothurn hat am 28. August 2019 eine Beschwerde A._s gegen diesen Entscheid abgewiesen.
E.
Mit Eingabe vom 30. September 2019 führt A._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen diesen Entscheid. Er beantragt im Wesentlichen dessen Aufhebung und die Rückweisung der Angelegenheit an die Vorinstanz und sucht um Gewährung der aufschiebenden Wirkung nach.
Das Verwaltungsgericht, die MFK sowie das ASTRA beantragen die Abweisung der Beschwerde.
Am 28. Oktober 2019 hat der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts das Gesuch um aufschiebende Wirkung abgewiesen.

Erwägungen:
1.
1.1. Angefochten ist ein kantonal letztinstanzlicher Endentscheid über eine Auflage für die Belassung des Führerausweises. Dagegen steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht offen (vgl. Art. 82 lit. a und Art. 86 Abs. 1 lit. d und Abs. 2 BGG); eine Ausnahme nach <ref-law> liegt nicht vor. Der Beschwerdeführer hat am vorinstanzlichen Verfahren teilgenommen und verfügt über ein schutzwürdiges Interesse an der Aufhebung oder Änderung des ihn besonders berührenden Entscheids. Er ist somit gemäss <ref-law> zur Beschwerde befugt.
1.2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann insbesondere die Verletzung von Bundesrecht gerügt werden (<ref-law>). Das Bundesgericht wendet dieses von Amtes wegen an (<ref-law>). Es prüft die bei ihm angefochtenen Entscheide aber grundsätzlich nur auf Rechtsverletzungen hin, die der Beschwerdeführer vorbringt und begründet (vgl. <ref-law>). Erhöhte Anforderungen an die Begründung gelten, soweit die Verletzung von Grundrechten gerügt wird (<ref-law>).
1.3. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Es kann deren Sachverhaltsfeststellung nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig, das heisst willkürlich (<ref-law>) ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Die beschwerdeführende Person wiederum darf die vorinstanzliche Sachverhaltsfeststellung nur rügen, wenn sie mit einem solchen Mangel behaftet ist und dessen Behebung für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Eine entsprechende Rüge ist substanziiert vorzubringen (Art. 42 Abs. 2 i.V.m. <ref-law>).
2.
Der Beschwerdeführer wirft der Vorinstanz zunächst vor, den Sachverhalt offensichtlich unrichtig festgestellt zu haben. Zum einen habe sie das Schreiben seines Hausarztes Dr. F._ nicht erwähnt und die dortigen Feststellungen nicht beachtet. Aus dem Schreiben gehe hervor, dass er bei seinem Hausarzt fortlaufend unangekündigt und unter Aufsicht Urinproben abgegeben habe. Diese seien stets negativ ausgefallen, weshalb feststehe, dass er mindestens seit Januar 2019 kein Kokain konsumiere. Sodann ist der Beschwerdeführer der Auffassung, die Werte der Haarproben seien unzuverlässig. Er habe immer bestritten, Kokain genommen zu haben; dennoch sei ihm bereits zweimal der Führerausweis entzogen worden, ohne ihm aber einen Drogenkonsum nachzuweisen. Schliesslich erachtet der Beschwerdeführer die Verpflichtung, sich regelmässig Haarproben nehmen zu lassen, als unverhältnismässig und als Verletzung seiner persönlichen Freiheit.
3.
3.1. Der Beschwerdeführer ist der Auffassung, das Verwaltungsgericht habe das Schreiben seines Hausarztes Dr. F._ ignoriert und damit den rechtserheblichen Sachverhalt unvollständig festgestellt.
Im Verfahren vor der Vorinstanz hat er in seiner Replik vom 16. August 2019 eine Stellungnahme seines Hausarztes vom 11. August 2019 eingereicht. Dieser führt aus, sein Patient habe seit längerem auf unangekündigte Aufgebote hin unter Aufsicht Urinproben abgegeben. Diese würden seit Januar 2019 auch auf Kokain getestet und seien stets negativ ausgefallen. Aufgrund dieser Befunde und seines ärztlichen Ermessens sei klar davon auszugehen, dass der Beschwerdeführer seit mindestens Januar 2019 kein Kokain konsumiert habe.
Es trifft zu, dass sich die Vorinstanz im angefochtenen Entscheid nicht ausdrücklich mit diesem Arztbericht auseinandergesetzt hat. Zugleich macht sie nicht geltend, das Beweismittel sei aus Gründen des kantonalen Prozessrechts verspätet eingereicht worden. Aufgrund ihrer Erwägungen kann indes angenommen werden, sie habe die Stellungnahme des Hausarztes zur Kenntnis genommen, denn sie hat sich in ihrem Entscheid eingehend zur Tauglichkeit von Urinproben geäussert. Die Vorinstanz hat erwogen, die Haaranalytik sei ein geeignetes Verfahren zur Kontrolle des Konsums von Alkohol und Drogen, denn sie ermögliche einen Überblick über einen längeren Zeitraum. Die Überprüfung mittels Blut- oder Urinprobe sei dagegen weniger geeignet, weil sie nur sehr punktuelle Ergebnisse liefere; auch in kurzen Abständen wiederholte Tests stellten deshalb nur Stichprobenkontrollen dar. Nach der Vorinstanz wäre es "somit auch nicht aussergewöhnlich, wenn die zweiwöchentlichen Untersuchungen des Blutes und des Urins zu negativen Befunden trotz eines Kokainkonsums führten". Aufgrund dieser Erwägungen kann, wie erwähnt, davon ausgegangen werden, die Vorinstanz habe sich mit der Kontrollmethode, der sich der Beschwerdeführer zurzeit bei seinem Hausarzt unterzieht, auseinandergesetzt und diese für ungeeignet zum Nachweis der Drogenabstinenz erachtet. Eine unvollständige Feststellung des Sachverhalts liegt insofern nicht vor.
3.2. Das Bundesgericht hat sich im Urteil <ref-ruling> gestützt auf auf ein Arbeitspapier der Schweizerischen Gesellschaft für Rechtsmedizin (SGRM) eingehend mit der Haaranalyse als Mittel zur Kontrolle der Alkoholabstinenz auseinandergesetzt (SGRM, Arbeitsgruppe Haaranalytik, Die forensisch-toxikologische Haaranalytik, Version 12/ 2009, abrufbar unter <https://www.sgrm.ch/de/forensische-chemie-und-toxikologie/toxikologie/uebersicht/> [besucht am 2. April 2020]). Demnach findet die Haaranalyse zum Nachweis der Abstinenz regelmässig Anwendung; die Methode wird in <ref-law> auch ausdrücklich erwähnt. Anders als Blutanalysen gibt die Haaranalyse direkten Aufschluss über den Alkoholkonsum; nach dem Alkoholgenuss wird das Abbauprodukt EtG im Haar eingelagert und erlaubt über ein grösseres Zeitfenster als bei der Blutuntersuchung Aussagen über den erfolgten Konsum. Im zitierten Urteil wird festgehalten, dass die bundesgerichtliche Rechtsprechung die Haaranalyse als geeignetes Mittel sowohl zum Nachweis eines übermässigen Alkoholkonsums als auch der Einhaltung einer Abstinenzverpflichtung anerkennt (<ref-ruling> E. 3 S. 337 f.). Die im genannten Urteil mit Bezug auf die Kontrolle des Alkohokonsums angestellten Überlegungen zur Haaranalytik treffen gleichermassen für den Nachweis eines Drogenkonsums bzw. der Drogenabstinenz zu (vgl. etwa das Urteil 1C_243/2010 vom 10. Dezember 2010 E. 2; SGRM, Arbeitsgruppe Haaranalytik, Die forensisch-toxikologische Haaranalytik, Version 12/ 2009, Ziff. 2.2 und 2.4.1). Auch im jüngsten Papier der SGRM vom Februar 2020 (Bestimmung von Drogen und Medikamenten in Haarproben, abrufbar unter <https://www.sgrm.ch/de/forensische-chemie-und-toxikologie/toxikologie/uebersicht/> [besucht am 2. April 2020]) wird die Haaranalyse als geeignetes Instrument zur Überprüfung der Abstinenz resp. zum Monitoring des Substanzkonsums im Rahmen verkehrsmedizinischer Fahreignungsabklärungen beschrieben (a.a.O., Ziff. 3.1 und 3.2).
Vor diesem Hintergrund erweist sich die Kritik an der Anordnung der MFK, die von der Vorinstanz geschützt wurde, als unbegründet. Die Haaranalytik erlaubt eine Überprüfung des (Alkohol- bzw.) Drogenkonsums über einen längeren Zeitraum und erschwert oder verunmöglicht damit die Umgehung der Kontrollen. Der Nachweis psychotroper Substanzen im Urin ist in der Regel bloss wenige Tage nach dem letzten Konsum möglich, weshalb auch in kurzen Abständen wiederholte Tests nur eine Stichprobenkontrolle darstellen (MARKUS BAUMGARTNER, Nachweis des Konsums von psychotropen Substanzen und Alkohol mittels Haaranalytik, in: Therapeutische Umschau 2011, S. 269). Die vom Beschwerdeführer vorgeschlagene Beschränkung der Kontrollen auf Urinproben wäre daher nur geeignet, einen regelmässigen Kokainkonsum nachzuweisen. Die Einnahme von Drogen kurz nach erfolgtem Urintest liesse sich demgegenüber bereits einige Tage später im Urin nicht mehr nachweisen. Daher ist diese Massnahme nicht geeignet, die völlige Drogenabstinenz zu belegen.
3.3. Des Weiteren ist der Beschwerdeführer der Auffassung, ihm sei der Führerausweis zweimal entzogen worden, ohne dass ihm der Konsum von Drogen tatsächlich nachgewiesen worden sei.
Vorweg ist dem Beschwerdeführer entgegen zu halten, dass das Verwaltungsgericht in seinem ersten ihn betreffenden Urteil vom 20. Juni 2017 festgehalten hat, das positive Ergebnis des Tests auf Kokain durch das Institut C._ vom 17. Februar 2017 sei einzig durch vereinzelten, schwachen Kokainkonsum im Zeitraum, in dem er zur Abstinenz verpflichtet gewesen wäre, zu erklären; eine Verwechslung oder eine Kontamination, wie vom Beschwerdeführer behauptet, könne dagegen ausgeschlossen werden. Dieses Urteil ist rechtskräftig. Es kann daher keine Rede davon sein kann, dem Beschwerdeführer sei der Führerausweis in der Vergangenheit ohne den Nachweis des Konsums von Drogen entzogen worden.
Darüber hinaus verkennt er die ihm obliegende Beweislast, nachdem ihm der Führerausweis im Jahr 2017 auf unbestimmte Zeit entzogen worden ist: Nach <ref-law> wird der Lernfahrausweis erteilt, wenn der Bewerber nachweist, dass er über die erforderliche körperliche und psychische Leistungsfähigkeit zum sicheren Führen von Motorfahrzeugen verfügt. Der auf unbestimmte Zeit entzogene Lernfahr- oder Führerausweis kann gemäss <ref-law> bedingt und unter Auflagen wiedererteilt werden, wenn eine allfällige gesetzliche oder verfügte Sperrfrist abgelaufen ist und die betroffene Person die Behebung des Mangels nachweist, der die Fahreignung ausgeschlossen hat. Aus beiden Bestimmungen geht klar hervor, dass die Beweislast bei der Person liegt, die den Führerausweis erwerben möchte. Diese hat nachzuweisen, dass die Voraussetzungen für das sichere Führen von Motorfahrzeugen vorliegen bzw. der Mangel, der zum Entzug geführt hat, behoben ist. Vorliegend hat also der Beschwerdeführer seine Fahreignung nachzuweisen und vorbestehende Zweifel daran müssen sich zu seinen Ungunsten auswirken.
3.4. Das Vorgehen der Solothurner Behörden ist auch keineswegs unverhältnismässig. Da, wie erwähnt, der Beschwerdeführer zu beweisen hat, dass der Mangel behoben ist, der seine Fahreignung ausgeschlossen hat, wäre auch in Betracht gefallen, ihm die Fahrerlaubnis erst wieder zu erteilen, wenn er vorher während einer bestimmten Zeit seine Drogenabstinenz nachgewiesen hätte. Da es sich nach Angaben des Instituts C._ bei der nachgewiesenen Menge von Kokain um einen toxikologischen Grenzfall gehandelt hatte, hat die MFK eine mildere Massnahme ergriffen und - statt ihm die Fahrerlaubnis gänzlich zu verweigern - dem Beschwerdeführer den Führerausweis unter Auflagen wieder erteilt. Die Auflage, sich einer Kontrolluntersuchung mittels Haaranalyse zu unterziehen, ist geeignet und erforderlich, da die vom Beschwerdeführer vorgeschlagenen Urinproben wesentliche Schwächen aufweisen (vgl. oben E. 3.2). Die Solothurner Behörden sind ihm damit trotz der immer wieder aufgetretenen Drogenproblematik weit entgegengekommen. Dass er dabei gewisse Unannehmlichkeiten in Kauf nehmen muss, ist ihm ohne Weiteres zuzumuten. Somit kann weder von einer unverhältnismässigen Massnahme die Rede sein noch von einem unzulässigen Eingriff in die persönliche Freiheit des Beschwerdeführers.
4.
Demnach ist die Beschwerde abzuweisen.
Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kostenpflichtig (<ref-law>). Parteientschädigungen für das bundesgerichtliche Verfahren sind keine auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird dem Beschwerdeführer, dem Bau- und Justizdepartement des Kantons Solothurn, dem Verwaltungsgericht des Kantons Solothurn und dem Bundesamt für Strassen, Sekretariat Administrativmassnahmen, schriftlich mitgeteilt.
Lausanne, 28. Mai 2020
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Die Gerichtsschreiberin: Hänni