Faits:
A.
Le 23 janvier 2012, le Tribunal correctionnel de la Broye et du Nord vaudois a acquitté X._ des infractions de lésions corporelles simples, lésions corporelles simples qualifiées, tentative de remise de substances nocives à des enfants, vol commis au préjudice d'un proche, dommages à la propriété, injure, menaces, tentative de viol, tentative de contrainte sexuelle et infraction à l'art. 19 bis LStup et l'a condamné pour vol, tentative de vol, utilisation frauduleuse d'un ordinateur, infraction et contravention à la LStup à une peine privative de liberté de 120 jours, sous déduction de 120 jours de détention avant jugement. Il a mis des frais arrêtés à 17'261 fr. 30 à la charge de X._, ainsi qu'un cinquième de l'indemnité due à son défenseur d'office, à condition que sa situation financière s'améliore. Le tribunal a alloué à X._, à la charge de l'Etat, une indemnité pour tort moral de 72'000 fr. avec intérêt à 5% l'an dès le 16 janvier 2012.
B.
Par jugement du 27 septembre 2012, la Cour d'appel pénale du Tribunal cantonal vaudois a partiellement admis les appels du Ministère public et de X._. Elle a fixé l'indemnité due par l'Etat de Vaud au recourant à 40'740 fr. et ordonné la compensation de ce montant avec les frais mis à la charge du recourant par 17'261 fr. 30, le solde finalement dû au recourant s'élevant à 23'478 fr. 70.
En bref, il ressort les éléments suivants de ce jugement.
Le 24 janvier 2011, à 11h54, un voisin de la mère de X._ a appelé la police en raison de cris de femme provenant du logement de celle-ci. A l'arrivée des policiers, la mère de X._ a signalé des agissements violents de ce dernier qui a été emmené au poste de police. Il a été fouillé à 12h30. Le rapport de police mentionne qu'il a été soupçonné d'être l'auteur d'un vol de sac à main commis quelques jours auparavant et qu'il a été relâché à 15h45.
X._ a commis des infractions contre le patrimoine et contre la LStup, pour lesquelles il a exécuté 61 jours de détention avant jugement (du 30 octobre 2010 au 29 décembre 2010) et pour lesquelles il a été condamné dans le cadre de la présente affaire. Il a en outre été soupçonné d'actes de violence à l'égard de ses proches à la suite des allégations de ces derniers qu'ils ont toutefois retirées devant le tribunal de première instance. Pour ces faits, il a été détenu avant jugement pendant 347 jours (du 4 février 2011 au 16 janvier 2012).
X._ a été soumis à une expertise psychiatrique qui fait état d'un trouble de la personnalité à traits immatures et dyssociaux lié à une forte dépendance aux drogues, aux opiacés et aux sédatifs. L'expert a conclu à un risque élevé de récidive et à une diminution moyenne de responsabilité.
Au début de son incarcération, X._ s'est automutilé. Il a par ailleurs été placé en cellule forte pour injures et menaces proférées à l'encontre d'une agente de détention.
Le casier judiciaire de X._ fait état de deux condamnations en 2010 notamment pour vol, tentative de vol et contravention à la LStup et une en 2011 pour violation de domicile.
X._ a fait l'objet de deux ordonnances de condamnation des 8 mars 2012 et 27 avril 2012 définitives et exécutoires. La première l'a condamné à 30 jours de peine privative de liberté dont à déduire 27 jours de détention avant jugement effectués dans le cadre de la présente affaire et à la révocation d'un sursis portant sur 20 jours-amende sous déduction de 20 jours de détention également effectués dans la présente affaire. La seconde l'a condamné à 45 jours de peine privative de liberté sous déduction de 45 jours de détention avant jugement effectués dans le cadre de la présente affaire.
C.
X._ forme un recours en matière pénale au Tribunal fédéral contre ce jugement. Il conclut, sous suite de frais et dépens, à la réforme du jugement entrepris en ce sens que les frais de justice mis à sa charge s'élèvent à 2'852 fr. 25 et que l'indemnité qui lui est due par l'Etat s'élève à un total de 52'770 fr., avec intérêt à 5% l'an dès le 16 janvier 2012, la compensation de ces montants n'étant pas prononcée. Il requiert par ailleurs l'assistance judiciaire.
Invités à déposer des observations sur le recours, la cour cantonale y a renoncé en se référant aux considérants de son arrêt, alors que le ministère public a conclu à son rejet. X._ a renoncé à se déterminer sur ces écritures.

Considérant en droit:
1.
Les prétentions en indemnisation prévues à l'<ref-law>, non seulement celles pour les frais de défense (let. a) mais aussi celles relatives au dommage économique (let. b) et au tort moral (let. c) entrent dans le cadre des décisions rendues en matière pénale au sens de l'<ref-law>. Il en découle que le recours en matière pénale est ouvert à leur égard (arrêt 6B_668/2012 du 16 avril 2013 consid. 1 destiné à la publication). Dirigé contre un jugement final (<ref-law>) rendu par une autorité cantonale de dernière instance (<ref-law>), le recours est en principe recevable.
2.
Le recourant prétend que la cour cantonale aurait dû, dans son calcul des jours de détention, ajouter un jour relatif à la détention du 24 janvier 2011, celle-ci ayant duré 3h51 et l'indemniser pour ce jour supplémentaire. Il invoque notamment les art. 31, 32 Cst., 5 CEDH, 30 al. 5 Cst./VD.
2.1. Le recourant ne dit pas en quoi les garanties constitutionnelles et conventionnelles qu'il invoque auraient une portée plus étendue que l'art. 429 al. 1 let. c CPP. Le grief sera examiné à l'aune de cette disposition.
2.2. L'art. 429 al. 1 let. c CPP prévoit que si le prévenu est acquitté totalement ou en partie, il a droit à une réparation du tort moral subi en raison d'une atteinte particulièrement grave à sa personnalité, notamment en cas de privation de liberté.
La notion de privation de liberté au sens de l'art. 429 al. 1 let. c CPP doit s'interpréter à la lumière des art. 51 et 110 al. 7 CP. Selon cette dernière disposition, est considérée comme détention avant jugement, toute détention ordonnée au cours d'un procès pénal pour les besoins de l'instruction, pour des motifs de sûreté ou en vue de l'extradition.
Selon la jurisprudence rendue avant l'entrée en vigueur du CPP, qui n'examinait toutefois cette question que sous l'angle du droit constitutionnel et conventionnel, le fait de retenir une personne pendant une durée de quatre à six heures ne constituait pas une violation de la liberté personnelle (<ref-ruling> consid. 3 p. 152; <ref-ruling> consid. 4a p. 140; <ref-ruling> consid. 1 p. 180). Dans un arrêt publié aux <ref-ruling> (consid. 4 p. 273), le Tribunal fédéral a précisé que la détention préventive devait être imputée de la peine indépendamment de savoir quelle autorité (policier ou magistrat) l'avait ordonnée.
La doctrine, quant à elle, considère comme une détention avant jugement au sens de l'<ref-law> toute privation de liberté d'une durée supérieure à trois heures ( YVAN JEANNERET, in Commentaire romand, Code pénal I, 2009, n o 1 ad <ref-law> et les références citées; CHRISTOPH METTLER, in Basler Kommentar, Strafrecht I, 2 ème éd. 2007, n o 13 et 17 ad <ref-law> et n o 3 ad <ref-law> et les références citées). Elle fonde notamment cette limite sur le système mis en place par les <ref-law> (cf. YVAN JEANNERET, op. cit., n o 3 ad. <ref-law>).
Selon le message du Conseil fédéral, l'appréhension policière prévue à l'<ref-law> permet à la police de conduire une personne appréhendée au poste. Elle se distingue de l'arrestation des <ref-law> en ce sens que l'arrestation présuppose que la personne visée soit soupçonnée de manière concrète d'avoir commis une infraction, alors que l'appréhension doit permettre de définir le cercle des personnes soupçonnées. Le séjour au poste d'une personne appréhendée doit (précisément parce qu'il n'existe contre elle aucun soupçon concret) durer nettement moins de trois heures au total (Message du 21 décembre 2005 relatif à l'unification du droit de la procédure, FF 2005 1057, p. 1206; ci-après : Message CPP). L'appréhension ne doit pas être considérée comme une détention avant jugement et ne donne en principe pas droit à une indemnisation au sens de l'<ref-law> ( ULRICH WEDER, in Kommentar zur Schweizerischen Strafprozessordnung, Donatsch/Hansjakob/Lieber [éd.], 2010, n o 30 ad <ref-law>; NIKLAUS SCHMID, Schweizerische Strafprozessordnung, Praxiskommentar, 2009, n o 12 ad <ref-law>). L'arrestation quant à elle est une mesure privative de liberté (Message CPP, p. 1207). En application de l'<ref-law>, la prolongation de l'arrestation doit être ordonnée par un membre du corps de police habilité par la Confédération ou le canton si la personne arrêtée n'est prévenue que d'une contravention et si l'arrestation dure plus de trois heures. Le législateur a ainsi considéré qu'une durée de trois heures constituait une limite au-delà de laquelle l'atteinte à la liberté était plus grave. Au vu de ce qui précède, il faut considérer qu'une arrestation de plus de trois heures constitue une détention avant jugement qui peut donner lieu à indemnisation. Il convient toutefois de ne pas tenir compte de la durée d'un éventuel interrogatoire formel dans le décompte des heures, seule étant déterminante la période pendant laquelle la personne est retenue à disposition des autorités (cf. ATF <ref-ruling> consid. 1 p. 179).
2.3. Selon les constatations cantonales, le recourant a été interpellé quelques minutes après l'appel du voisin de sa mère à la police qui a été passé à 11h54, puis il a été emmené au poste de police. Il a été relâché à 15h45. Au vu des faits retenus, le séjour au poste du recourant a duré au plus 3h51. Toutefois, il ressort du rapport de police que, durant ces 3h51, il a été remis à deux inspecteurs dès lors qu'il était soupçonné d'un vol de sac à main dans le train. On ignore si le recourant a été formellement entendu par les inspecteurs et, le cas échéant, quelle a été la durée de cet interrogatoire. Les faits établis par la cour cantonale ne permettent pas de vérifier la bonne application du droit fédéral. La cause sera, par conséquent, renvoyée à la cour cantonale à qui il appartiendra d'établir si le recourant a été formellement entendu et la durée de son audition et, le cas échéant, de déduire cette durée de celle du séjour au poste. Si celle-ci reste supérieure à la limite des trois heures, il conviendra d'ajouter un jour au nombre de jours de détention avant jugement et, le cas échéant, d'adapter le montant de l'indemnité. A noter que le recourant ne formule aucun autre grief recevable quant au nombre de jours à indemniser et que la cour cantonale se fondera, sous réserve de la limite des trois heures précitée, sur le nombre de jours qu'elle avait par ailleurs retenu dans son jugement.
3.
Le recourant se plaint du montant de l'indemnité pour tort moral qui lui a été alloué en application de l'art. 429 al. 1 let. c CPP.
3.1. Les pièces produites par le recourant à cet égard sont des pièces nouvelles, partant irrecevables (<ref-law>).
3.2. En application de l'art. 429 al. 1 let. c CPP, si, du fait de la procédure, le prévenu a subi une atteinte particulièrement grave à ses intérêts personnels au sens des <ref-law> ou 49 CO, il aura droit à la réparation de son tort moral (Message CPP, p. 1313). Selon la jurisprudence rendue avant l'entrée en vigueur du CPP, le montant de l'indemnité en matière de détention injustifiée doit être fixé en fonction de la gravité de l'atteinte portée à la personnalité (<ref-law>; <ref-ruling> consid. 4.1 p. 47; <ref-ruling> consid. 3a p. 98). Il faut tenir compte de toutes les circonstances, notamment des effets négatifs de la détention sur l'intégrité physique, psychique ou encore sur la réputation (<ref-ruling> consid. 5b/aa p. 458). L'activité professionnelle du lésé doit également être prise en compte dans cette appréciation (ATF <ref-ruling> consid. 3a p. 98). Il appartient au demandeur d'invoquer et de prouver les atteintes subies (<ref-ruling> consid. 4.1 p. 47; <ref-ruling> consid. 4b p. 218). Le Tribunal fédéral considère en principe qu'un montant de 200 fr. par jour en cas de détention injustifiée de courte durée constitue une indemnité appropriée, dans la mesure où il n'existe pas de circonstances particulières qui pourraient fonder le versement d'un montant inférieur ou supérieur (arrêts 6B_745/2009 du 12 novembre 2009 consid. 7.1; 8G.12/2001 du 19 septembre 2001 consid. 6b/bb). Lorsque la détention injustifiée s'étend sur une longue période, la jurisprudence a précisé qu'une augmentation linéaire du montant accordé dans les cas de détentions plus courtes n'est pas adaptée, car le fait de l'arrestation et de la détention pèse d'un poids en tout cas aussi important que l'élément de durée pour apprécier l'atteinte que subit la personne incarcérée (cf. <ref-ruling> consid. 3b p. 156). La fixation de l'indemnité pour tort moral est une question d'appréciation, de sorte que le Tribunal fédéral ne la revoit qu'avec retenue (cf. <ref-ruling> consid. 2.2.2 p. 309 s.; arrêt 6B_111/2012 du 15 mai 2012 consid. 4.2). Il n'y a pas lieu de s'écarter de ces principes qui peuvent être repris s'agissant de l'application de l'art. 429 al. 1 let. c CPP (arrêt 6B_111/2012 du 15 mai 2012 consid. 4.2).
3.3. En substance, la cour cantonale a retenu que la détention était, en soi, source d'angoisse, d'autant plus pour une personne innocente qui avait l'impression de ne pas être entendue. Il fallait aussi admettre que, dans le cas du recourant, le type d'accusations formulées pouvait générer une crainte d'agression ou d'autres comportements hostiles, non susceptible de diminuer au fil du temps. Au vu des conclusions de l'expertise, il y avait lieu de retenir que le recourant, qui était encore très jeune (20 ans en 2012) et qui souffrait de troubles mentaux et de certaines carences éducatives, était vraisemblablement plus fragile qu'un autre détenu. Son acte d'automutilation attestait de ses souffrances et de son sentiment d'impuissance. Son mal-être était toutefois pour partie antérieur à la détention puisqu'il était toxicomane. Au vu de l'ensemble de ces éléments, il convenait de retenir que le recourant, célibataire et sans activité lucrative, n'avait pas été affecté dans sa vie familiale ou professionnelle par sa détention injustifiée. Une personne célibataire et sans enfant ne souffrait cependant pas moins, n'ayant personne pour la soutenir. Partant, le recourant avait certainement vécu cette période de détention comme une période très difficile. La détention injustifiée de longue durée et les circonstances personnelles du recourant entraînaient la fixation de l'indemnité au montant habituel de 200 fr. par jour, soit un total de 39'200 fr. pour 196 jours de détention injustifiée.
3.4. Le recourant fait grief à la cour cantonale d'avoir fixé le montant de l'indemnité journalière à 200 fr., alors que l'autorité de première instance l'avait fixé à 250 francs.
3.5. Afin de satisfaire à l'obligation de motivation posée par l'<ref-law>, le recourant devait discuter les motifs de la décision entreprise et indiquer précisément en quoi il estimait que l'autorité précédente avait méconnu le droit (cf. <ref-ruling> consid. 3.3 p. 60). En tant qu'il reprend les critiques présentées devant l'autorité précédente, sans indiquer, même succinctement, en quoi les motifs de la décision entreprise méconnaitraient le droit, son argumentation n'est pas conforme aux exigences minimales fixées à l'<ref-law> et est dès lors irrecevable.
Par ailleurs, le recourant soutient que la cour cantonale aurait considéré que la seule distribution d'anxiolytique en prison permettait de contenir les angoisses et dès lors de ne plus en tenir compte. Elle aurait ainsi oublié que, malgré la médication, son mal-être aurait atteint un stade paroxysmique lorsqu'il s'était ouvert les veines des avant-bras. Enfin, son statut en Suisse limiterait son accès aux soins, dès lors qu'il ne vivrait que de l'aide d'urgence.
La cour cantonale n'a pas ignoré le mal-être du recourant dont elle a toutefois relevé qu'il était pour partie antérieur à son incarcération, ni son acte d'automutilation, éléments dont elle a tenu compte dans son appréciation. S'agissant de l'accès limité aux soins, le recourant ne prétend ni ne démontre la nécessité d'un suivi médical. A cet égard, c'est à bon droit que la cour cantonale a relevé que le recourant avait un devoir de collaboration, notamment s'agissant de l'établissement de l'atteinte subie. Il lui appartenait donc d'établir la nécessité d'un éventuel suivi médical.
Au demeurant, l'indemnité fixée à 200 fr. par jour apparaît conforme au droit fédéral et à la jurisprudence compte tenu du pouvoir d'appréciation dont jouit l'autorité précédente (cf. supra consid. 3.2). La cour cantonale a pris en considération l'ensemble des circonstances pertinentes. Elle a renoncé à diminuer le montant de base de 200 fr. par jour malgré la longue période de détention (six mois et demi) et a ainsi tenu compte des circonstances particulières du cas d'espèce (notamment nature et gravité des accusations, crainte de leur découverte par les codétenus, fragilité psychologique du recourant, automutilation). Mal fondé, le grief doit être rejeté dans la mesure où il est recevable.
4.
Le recourant conteste la mise à sa charge de l'entier des frais relatifs à l'expertise psychiatrique, dont il soutient qu'il ne devrait supporter qu'un cinquième.
4.1. La mise à la charge des frais se juge à l'aune du principe selon lequel celui qui a causé les frais doit les supporter. Le devoir du prévenu de supporter les frais en cas de condamnation (<ref-law>) se fonde sur l'idée que ce dernier a occasionné, par son comportement, l'ouverture et la mise en oeuvre de l'enquête pénale et qu'il doit par conséquent en supporter les frais (<ref-ruling> consid. 4.4.1 p. 254; arrêt 6B_428/2012 du 19 novembre 2012 consid. 3.1). Un lien de causalité adéquate est nécessaire entre le comportement menant à la condamnation pénale et les coûts relatifs à l'enquête permettant de l'établir (arrêt 6B_428/2012 du 19 novembre 2012 consid. 3.1 et les références citées; sur la notion de causalité adéquate v. <ref-ruling> consid. 4.1.3 p. 61).
4.2. Contrairement à ce que soutient le recourant, l'expertise psychiatrique n'a pas été ordonnée uniquement en raison des infractions pour lesquelles il a bénéficié d'un acquittement. Il ressort du jugement entrepris que l'expertise a certes été ordonnée principalement en raison de ces infractions, mais également en raison de la consommation régulière de produits stupéfiants du recourant (jugement entrepris p. 14).
Le recourant a été condamné pour divers vols, utilisations frauduleuses d'un ordinateur et infractions et contraventions à la LStup. Les comportements à la base de cette condamnation, ajoutés aux antécédents du recourant, sont de nature, selon le cours ordinaire des choses et l'expérience de la vie, à causer l'ouverture d'une enquête pénale et, dans le cadre de celle-ci, à soumettre le prévenu à une expertise psychiatrique; plus particulièrement, la consommation de stupéfiants peut être de nature à mettre en doute la responsabilité de l'auteur et engendrer la mise en oeuvre d'une expertise psychiatrique. Les frais relatifs à dite expertise sont donc en lien de causalité adéquate avec le comportement ayant conduit à la condamnation du recourant. La cour cantonale pouvait, sans violer le droit fédéral, faire supporter au recourant l'entier des frais relatifs à l'expertise psychiatrique. Mal fondé, le grief doit être rejeté.
5.
Le recourant conteste la compensation des indemnités dues par l'Etat en sa faveur avec les frais de justice mis à sa charge.
5.1. Aux termes de l'<ref-law>, les autorités pénales peuvent compenser les créances portant sur des frais de procédure avec les indemnités accordées à la partie débitrice dans la même procédure pénale et avec des valeurs séquestrées. Conformément au Message, repris par une grande partie de la doctrine, la créance de la collectivité portant sur les frais de procédure ne peut être compensée qu'avec l'indemnité accordée à la partie débitrice, mais non avec la réparation du tort moral allouée à celle-ci (Message CPP, p. 1318; cf. aussi BENJAMIN F. BRÄGGER, in Basler Kommentar Schweizerische Strafprozessordnung, 2011, n o 2 ad <ref-law>; MICHEL PERRIN, in Commentaire romand, Code de procédure pénale suisse, 2011, n o 10 i.f. ad <ref-law>; NIKLAUS SCHMID, Schweizerische Strafprozessordnung, Praxiskommentar, 2009, n o 7 ad <ref-law>; ANGELA CAVALLO, in Kommentar zur Schweizerischen Strafprozessordnung, Donatsch/Hansjakob/Lieber [éd.], 2010, n o 15 ad <ref-law>). Cette interprétation est par ailleurs confirmée par le texte même de la disposition qui indique que les « indemnités » peuvent faire l'objet d'une compensation. Cette notion renvoie aux let. a et b de l'<ref-law> (indemnité pour les dépenses occasionnées et indemnité pour le dommage économique) mais non à la let. c (réparation du tort moral). Cette même différence est opérée dans le texte italien (art. 429 al. 1 let a et b CPP :« indennità »; let. c : « riparazione del torto morale »; et 442 al. 4 CPP : « pretese d'indennizzo ») et de manière encore plus claire dans le texte allemand (art. 429 al. 1 let. a et b CPP:« Entschädigung »; let c : « Genugtuung »; <ref-law> : « Entschädigungsansprüchen »). Elle est en outre conforme à la nature plutôt personnelle que patrimoniale de l'indemnité pour tort moral et à son but visant à compenser le préjudice que représente une atteinte au bien-être moral (cf. ANGELA CAVALLO, op. cit., n o 15 ad <ref-law>). Au demeurant, elle ne viole pas le principe de la compensation prévu à l'<ref-law> qui est une institution reconnue pour être générale, mais qui peut être exclue par le législateur (cf. MOOR/POLTIER, Droit administratif, Vol II, 3 e éd. 2011, p. 105 et les références citées).
5.2. Contrairement à ce qu'affirme la cour cantonale, l'interdiction de compenser les frais avec une indemnité pour tort moral ne s'adresse pas uniquement aux autorités de recouvrement, mais également aux autorités pénales. Elle a donc violé l'<ref-law> en ordonnant la compensation du montant des frais mis à la charge du recourant avec l'indemnité pour tort moral. En revanche, l'<ref-law> permet la compensation des frais mis à la charge du recourant avec l'indemnité pour les dépenses occasionnées par l'exercice raisonnable des droits de procédure (<ref-law>). La cour cantonale peut ainsi compenser les frais mis à la charge du recourant avec l'indemnité pour les dépenses occasionnées par l'exercice raisonnable des droits de procédure, plus particulièrement celle allouée en remboursement des frais de décision relative à sa détention avant jugement (cf. infra consid. 6), mais non avec l'indemnité pour tort moral. Il convient de renvoyer la cause à la cour cantonale pour qu'elle corrige ses calculs au sens de ce qui précède.
6.
Le recourant fait grief à la cour cantonale de ne lui avoir alloué que partiellement ses prétentions en indemnisation de ses dépenses occasionnées par l'exercice raisonnable de ses droits de procédure. Durant sa détention, il a requis sa mise en liberté à deux reprises et demandé l'exécution anticipée d'un traitement des addictions à trois reprises, ces cinq demandes ayant été refusées. Il a, à chaque fois, recouru devant la Chambre des recours pénale qui a systématiquement rejeté son recours mettant les frais de décision à sa charge. Le recourant a requis devant la cour cantonale l'allocation d'un montant équivalent à la somme des frais mis à sa charge par les cinq décisions, soit 3520 francs.
La cour cantonale a retenu qu'il était compréhensible qu'un innocent essaie de toutes les manières possibles d'obtenir sa libération. Elle a alloué au recourant un montant de 1540 fr. équivalent aux frais des deux décisions rendues à la suite de ses demandes de mise en liberté. Elle a toutefois refusé de lui allouer le montant des frais des décisions relatives à ses demandes d'exécution anticipée d'un traitement des addictions.
Le remboursement invoqué par le recourant s'inscrit dans le cadre de l'<ref-law>. La cour cantonale n'a exposé aucun motif permettant d'expliquer la différence de traitement entre l'acceptation et le refus d'indemnisation suivant le type de procédure initiée par le recourant. Le défaut de motivation du jugement entrepris ne permet pas de vérifier comment la cour cantonale a appliqué l'<ref-law>. Par conséquent, dans le cadre du renvoi, il lui incombera également de reprendre la question du remboursement des frais des décisions relatives aux demandes d'exécution anticipée d'un traitement des addictions.
7.
Le recours doit être partiellement admis et la cause renvoyée à la cour cantonale pour nouvelle instruction et nouvelle décision au sens des considérants. Pour le surplus, il est rejeté dans la mesure où il est recevable. Le recourant a requis l'assistance judiciaire. Cette requête est sans objet dans la mesure où il obtient gain de cause et peut, à ce titre, prétendre à des dépens réduits de la part du canton (art. 64 al. 2 et 68 al. 1 LTF). Le recours était, pour le surplus, dénué de chance de succès, si bien que l'assistance judiciaire doit être refusée dans cette mesure (<ref-law>). Une partie des frais sera ainsi supportée par le recourant (<ref-law>), dont le montant sera toutefois fixé en tenant compte de sa situation financière.

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est partiellement admis, le jugement attaqué annulé et la cause renvoyée à l'autorité cantonale pour nouvelle décision. Pour le surplus, le recours est rejeté dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge du recourant.
3.
La demande d'assistance judiciaire est rejetée dans la mesure où elle n'est pas sans objet.
4.
Le canton de Vaud versera à l'avocat du recourant une indemnité de 2000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
5.
Le présent arrêt est communiqué aux parties et à la Cour d'appel pénale du Tribunal cantonal du canton de Vaud.
Lausanne, le 8 juillet 2013
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Livet