Sachverhalt:
A.
Am 3. August 2012 reichte Y._ ein Baugesuch für den Abbruch der bestehenden Baute (Scheune/Speicher) und die Erstellung eines Einfamilienhauses auf Parzelle 405 in der Gemeinde Andiast ein. Dagegen erhob X._ am 22. August 2012 Einsprache. Mit Entscheid vom 30. August 2012 wies der Gemeindevorstand Andiast die Einsprache ab, soweit er darauf eintrat, und erteilte die Baubewilligung.
B.
Dagegen erhob X._ am 6. Dezember 2012 Beschwerde beim Verwaltungsgericht des Kantons Graubünden. Er erhob verschiedene formelle Rügen und machte geltend, dass das Bauvorhaben die maximal zulässige Bruttogeschossfläche (BGF) überschreite; hierfür habe die Gemeinde zu Unrecht eine Ausnahmebewilligung erteilt. Am 30. April 2013 wies das Verwaltungsgericht die Beschwerde ab.
C.
Dagegen hat X._ am 16. August 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Er beantragt, der Entscheid des Verwaltungsgerichts, der Einspracheentscheid des Gemeindevorstands Andiast vom 30. August 2012 und die Baubewilligung vom gleichen Tag seien aufzuheben bzw. für nichtig zu erklären und die Baubewilligung für das Bauvorhaben von Y._ sei zu verweigern. Überdies beantragt er die Gewährung der aufschiebenden Wirkung.
D.
Y._ (im Folgenden: der Beschwerdegegner) beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Eventualiter sei die Sache an die Vorinstanz oder die Gemeinde Andiast zur Neubeurteilung zurückzuweisen.
Die Gemeinde Andiast hält fest, dass die vom angefochtenen Bauprojekt betroffene Scheune in keinem Inventar schützenswerter Bauten verzeichnet sei und ihr auch keineswegs eine spezielle Bedeutung für das Ortsbild von Andiast zukomme.

Erwägungen:
1.
Gegen den kantonal letztinstanzlichen Endentscheid des Verwaltungsgerichts steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht offen (Art. 82 lit. a und 86 Abs. 1 lit. d BGG). Der Beschwerdeführer ist als Nachbar zur Beschwerde legitimiert (<ref-law>). Auf die rechtzeitig erhobene Beschwerde (<ref-law>) ist daher einzutreten.
2.
Der Beschwerdeführer macht erstmals vor Bundesgericht geltend, dass es sich beim Bauvorhaben um eine Zweitwohnung handle, die nach <ref-law> unzulässig sei, weil der Zweitwohnungsanteil der Gemeinde Andiast 20 % übersteige.
2.1. Die Gemeinde hält diese Rüge für verspätet. Der Beschwerdegegner macht geltend, der Beschwerdeführer weite unzulässigerweise das Prozessthema aus; zudem fehlten Sachverhaltsfeststellungen zur Zweitwohnungseigenschaft des Bauvorhabens.
2.2. Der Streitgegenstand bestimmt sich aufgrund des Anfechtungsobjekts (d.h. des Dispositivs des vorinstanzlichen Entscheids) und der gestellten Anträge (<ref-ruling> E. 3.4.3 S. 365; <ref-ruling> E. 2 S. 415 ff.; je mit Hinweisen). Vorliegend wurde die vom Beschwerdeführer vollumfänglich angefochtene Baubewilligung vom Verwaltungsgericht (durch Abweisung der Beschwerde) bestätigt; auch vor Bundesgericht beantragt der Beschwerdeführer die Aufhebung der Baubewilligung und die Abweisung des Baugesuchs. Im Streit steht somit die Bewilligungsfähigkeit des Bauvorhabens als Ganzes. Einzelne Teilaspekte davon stellen Begründungselemente dar, die für sich allein nicht in Rechtskraft erwachsen ( ULRICH MEYER/ISABEL VON ZWEHL, L'objet du litige en procédure de droit administratif fédéral, Mélanges Moor, 2005, S. 435 ff., S. 441 ff.). Insofern ist die Baubewilligung nicht - wie der Beschwerdegegner und die Gemeinde meinen - im Bezug auf die Zweitwohnungsproblematik in Rechtskraft erwachsen (vgl. auch Urteil 1C_113/2013 vom 4. Oktober 2013 E. 3).
Neue rechtliche Begründungen sind vor Bundesgericht grundsätzlich zulässig (<ref-ruling> E. 4.1 S. 366 mit Hinweisen). Ohnehin kann dieses die Vereinbarkeit der Baubewilligung mit Art. 75b i.V.m. <ref-law> von Amtes wegen prüfen (<ref-law>). Zwar legt es seinem Urteil grundsätzlich den vorinstanzlich festgestellten Sachverhalt zugrunde (<ref-law>); es kann aber ausnahmsweise auch selber eine Sachverhaltsfeststellung ergänzen (<ref-law>), namentlich dann, wenn ein Sachverhaltselement erst infolge einer anderen rechtlichen Betrachtung des Bundesgerichts rechtserheblich wird (<ref-ruling> E. 4.1 S. 366).
3.
Die angefochtene Baubewilligung wurde am 30. August 2012, d.h. nach dem Inkrafttreten von <ref-law> und <ref-law>, erteilt. Es ist unstreitig, dass der Zweitwohnungsanteil der Gemeinde Andiast über 20 % beträgt (vgl. Anhang zur Verordnung über Zweitwohnungen vom 22. August 2012 Gemeinde Nr. 3611 [SR 702]). Dagegen haben weder die Gemeinde noch das Verwaltungsgericht geprüft, ob es sich beim Bauvorhaben um eine Zweitwohnung handelt. Der Beschwerdeführer bejaht dies, weil der Beschwerdegegner seinen Wohnsitz in Zürich habe. Dieser macht dagegen geltend, er sei aus gesundheitlichen sowie aus finanziellen Gründen (infolge seiner bevorstehenden Pensionierung) gezwungen, von seinem derzeitigen Wohnort wegzuziehen.
Wie es sich damit verhält, braucht nicht näher geprüft zu werden. Entscheidend ist, dass die (in den Akten liegende) Baubewilligung die Zweitwohnungsnutzung der Neubaute nicht ausschliesst, d.h. keine nutzungsbeschränkende Auflage enthält. Diese aktenkundige Tatsache genügt für die Beurteilung des Falles, wie im Folgenden darzulegen sein wird.
4.
Das Bundesgericht hat in <ref-ruling> (E. 9-11 S. 249 ff.) entschieden, dass <ref-law> seit seinem Inkrafttreten am 11. März 2012 anwendbar ist. Zwar bedarf diese Bestimmung der Ausführung durch ein Bundesgesetz. Unmittelbar anwendbar ist sie jedoch insoweit, als sie (in Verbindung mit <ref-law>) ein Baubewilligungsverbot für Zweitwohnungen in allen Gemeinden anordnet, in denen der 20 %-Zweitwohnungsanteil bereits erreicht oder überschritten ist. Dieses vorläufige Bauverbot kommt im Ergebnis einer Planungszone gleich. Es ist weit auszulegen, um dem Gesetzgeber nicht vorzugreifen und eine Präjudizierung der künftigen Ausführungsgesetzgebung zu vermeiden (<ref-ruling> E. 10.5 S. 257). Insofern erfasst es nicht nur Bauten, die erklärterweise als Zweitwohnungen genutzt werden sollen, sondern auch Bauten, die - wie im vorliegenden Fall - als Zweitwohnungen genutzt werden könnten. Die dem Beschwerdegegner erteilte Baubewilligung enthält keine Nutzungsbeschränkung und lässt somit eine Zweitwohnungsnutzung zu (Urteil 1C_604/2013 vom 8. Oktober 2013 E. 3). Sie verstösst somit gegen <ref-law> i.V.m. <ref-law>. Dies ergibt sich unmittelbar aus der Verfassung, unabhängig von den Bestimmungen der (erst am 1. Januar 2013) in Kraft gesetzten Zweitwohnungsverordnung.
Da die Frage der Zweitwohnungsnutzung erstmals vor Bundesgericht thematisiert wurde, hatte der Beschwerdegegner bislang keine Gelegenheit, sich zur beabsichtigten Nutzung zu äussern und gegebenenfalls eine Nutzungsbeschränkung zu beantragen. Dies würde eine Änderung des Baugesuchs voraussetzen, zu der dem Beschwerdeführer im Einspracheverfahren das rechtliche Gehör gewährt werden müsste.
5.
Unter diesen Umständen rechtfertigt es sich, den verwaltungsgerichtlichen Entscheid, den Einspracheentscheid und die Baubewilligung aufzuheben, nicht aber, den Bauabschlag zu erteilen. Vielmehr ist die Sache an die Gemeinde zurückzuweisen. Der Beschwerdegegner hat die Möglichkeit, entweder ein modifiziertes Baugesuch einzureichen oder aber auf das Baugesuch zu verzichten.
Ist die Baubewilligung ohnehin aufzuheben, braucht auf die übrigen (ebenfalls neuen) Rügen des Beschwerdeführers zur Schutzwürdigkeit des Dorfkerns von Andiast und der abzubrechenden Scheune bzw. des Speichers nicht eingegangen zu werden. Es wird Sache der Gemeinde sein, dies zu prüfen, sofern das Bauvorhaben (mit Nutzungsbeschränkung) aufrechterhalten wird und auch der Beschwerdeführer an seiner Einsprache festhält.
6.
Bei diesem Ausgang des Verfahrens obsiegt der Beschwerdeführer im Wesentlichen (abgesehen vom Antrag auf Abweisung des Baugesuchs). Der Beschwerdegegner wird kostenpflichtig, und zwar grundsätzlich sowohl für das bundesgerichtliche Verfahren (Art. 66 und 68 BGG), als auch für das Verfahren vor Verwaltungsgericht (Art. 67 und 68 Abs. 5 BGG). Allerdings auferlegte das Verwaltungsgericht einen Viertel der Kosten der Gemeinde, weil diese mit ihrem unzutreffenden Einspracheentscheid Anlass zur Beschwerdeerhebung gegeben habe. Dieser Teil des Kostenentscheids wurde von keiner Seite beanstandet und ist daher aufrechtzuerhalten.
Mit dem vorliegenden Entscheid in der Hauptsache wird das Gesuch um aufschiebende Wirkung gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und der Entscheid des Verwaltungsgerichts des Kantons Graubünden, 5. Kammer, vom 30. April 2013 sowie der Einspracheentscheid und die Baubewilligung der Gemeinde Andiast, beide vom 30. August 2012, werden aufgehoben. Die Sache wird im Sinne der Erwägungen an die Gemeinde Andiast zurückgewiesen.
2.
Die Gerichtskosten von Fr. 1'000.-- für das bundesgerichtliche Verfahren werden dem Beschwerdegegner (Y._) auferlegt. Die Kosten des verwaltungsgerichtlichen Verfahrens von Fr. 2'352.-- werden zu einem Viertel (Fr. 588.--) der Gemeinde Andiast und zu drei Vierteln (Fr. 1'764.--) dem Beschwerdegegner auferlegt.
3.
Der Beschwerdegegner hat den Beschwerdeführer für das bundesgerichtliche und für das verwaltungsgerichtliche Verfahren mit insgesamt Fr. 3'000.-- zu entschädigen. Die Gemeinde Andiast hat den Beschwerdeführer für das verwaltungsgerichtliche Verfahren mit Fr. 800.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, der Gemeinde Andiast, dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 25. November 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Gerber