Faits :
A.
Le 19 août 2013, X._ a fait opposition à l'ordonnance pénale le reconnaissant coupable de lésions corporelles simples et d'injures commises à l'encontre de A._. L'ordonnance ayant été transmise par le Ministère public au Tribunal de police du Littoral et du Val-de-Travers (ci-après: le Tribunal de police), ce dernier a convoqué X._ et A._ à une première audience, le 28 octobre 2013, à laquelle X._ a comparu. X._ ne s'est cependant pas présenté à une seconde audience, le 20 janvier 2014, en dépit du mandat de comparution qui lui avait été adressé et qui indiquait les conséquences du défaut. Le 21 janvier 2014, le Tribunal de police a rendu un prononcé, intitulé " ordonnance de classement ", par lequel il a constaté le défaut de X._ à l'audience du 20 janvier 2014 et indiqué que l'article 356 al. 4 CPP était applicable, de sorte que l'opposition de X._ était considérée comme retirée. Les deux points du dispositif de l'ordonnance étaient libellés comme suit " 1. Ordonne le classement du dossier ouvert à l'encontre de X._. 2. Statue sans frais ni dépens ".
Par courrier daté du 20 janvier 2014 mais posté le lendemain et reçu au Tribunal de police le 22 janvier 2014, X._ s'est excusé de son absence à l'audience, dont il a expliqué les raisons. Le 23 janvier 2014, le Tribunal de police a demandé à X._ de lui indiquer si son courrier du 20 janvier 2014 devait être considéré comme un recours contre l'ordonnance de classement du 21 janvier 2014. Le 27 janvier 2014, X._ a répondu accepter, avec toute sa " gratitude ", l'ordonnance de classement du 21 janvier 2014.
Le 30 juin 2014, X._ a adressé une requête en interprétation de l'ordonnance de classement du 21 janvier 2014 au Tribunal de police par l'intermédiaire de son mandataire, étant précisé qu'il avait agi seul jusqu'alors. Dans cette requête, X._ affirmait avoir compris l'ordonnance de classement du 21 janvier 2014 comme un abandon des charges dirigées contre lui. Il n'avait eu de doutes quant à la signification de l'ordonnance qu'en juin 2014, dans le cadre d'une procédure civile l'opposant à A._. Le 8 septembre 2014, le Tribunal de police a rejeté la requête en interprétation de X._, pour autant qu'elle ait été recevable.
B.
Par arrêt du 23 mars 2015, l'Autorité de recours en matière pénale du Tribunal cantonal du canton de Neuchâtel (ci-après: la cour cantonale) a rejeté le recours de X._. Elle a considéré, en substance, que les conditions d'une requête en interprétation au sens de l'<ref-law> n'étaient pas remplies car le dispositif attaqué ne pouvait être qualifié de " peu clair, contradictoire, incomplet ou en contradiction avec l'exposé des motifs ".
C.
X._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt. Il conclut, avec suite de frais et dépens, à l'annulation de l'arrêt attaqué et, principalement, au renvoi de la cause au tribunal de police ou, subsidiairement, à la cour cantonale afin qu'elle procède à l'interprétation de la décision du 21 janvier 2014. Plus subsidiairement, il conclut à l'interprétation de l'ordonnance de classement en ce sens qu'il s'agit d'une ordonnance de classement au sens de l'<ref-law> avec l'<ref-law>, plus subsidiairement encore, à ce que le point 1 du dispositif soit rectifié en ces termes " constate le retrait de l'opposition formée à l'endroit de l'ordonnance pénale du 15 août 2013 et constate que celle-ci est entrée en force " et que l'ordonnance soit annulée et la cause renvoyée au tribunal de police pour qu'il entre en matière sur le fond de l'action pénale. Il sollicite par ailleurs l'assistance judiciaire.
D.
Invités à se déterminer sur le recours, la cour cantonale y a renoncé, tandis que le Ministère public et A._ ont conclu à son rejet.

Considérant en droit :
1.
A l'appui de son recours, le recourant produit l'arrêt ARMP. 2014.93 rendu le 23 mars 2015 par la cour cantonale. Cet arrêt déclare irrecevable le recours de l'intéressé du 22 septembre 2014 contre l'ordonnance du 21 janvier 2014 au motif du non-respect du délai de recours, qui ne pouvait être restitué, mais relève néanmoins, dans un obiter dictum, que le constat du retrait fictif de l'opposition par le tribunal de police était inadmissible. Dans la mesure où la décision attaquée mentionne que l'intéressé a également recouru en parallèle directement contre l'ordonnance du 21 janvier 2014, ce qui a conduit au prononcé de l'arrêt ARMP.2014.93, la pièce produite par le recourant résulte de la décision de l'autorité précédente au sens de l'<ref-law>, de sorte qu'elle est recevable.
2.
Le recourant invoque une violation de l'<ref-law>. Il soutient que le dispositif de l'ordonnance du 21 janvier 2014 qui prévoit que le tribunal " ordonne le classement du dossier ouvert à l'encontre de X._ " suggère un abandon des charges, si bien qu'il entrerait en contradiction avec les motifs de ladite ordonnance, lesquels constatent le retrait fictif de l'opposition à l'ordonnance pénale formée par le recourant. En outre, le dispositif serait incomplet dans la mesure où il ne dirait rien sur la validité de l'opposition et de l'ordonnance pénale.
2.1. L'autorité pénale qui a rendu un prononcé dont le dispositif est peu clair, contradictoire ou incomplet ou qui est en contradiction avec l'exposé des motifs, l'explique ou le rectifie à la demande d'une partie ou d'office (<ref-law>). Plus précisément, selon la jurisprudence relative aux <ref-law> et 145 aOJ dont la teneur est similaire, un dispositif est peu clair, et doit donc être interprété, lorsque les parties ou les autorités à qui la cause est renvoyée risquent subjectivement de comprendre la décision autrement que ce que voulait le tribunal lorsqu'il s'est prononcé (arrêts 5G_3/2015 du 2 novembre 2015 consid. 2.1; 2C_724/2010 du 27 juillet 2011 consid. 2.2, in RDAF 2012 II 37; 4C.86/2004 du 7 juillet 2004 consid. 1.4).
Les requêtes en interprétation et en rectification d'une décision ne sont soumises à aucun délai; elles ne peuvent avoir pour objet la modification de son contenu matériel, mais doivent être limitées à sa clarification, respectivement à la correction d'inadvertances manifestes (arrêt 6B_727/2012 du 11 mars 2013 consid. 4.2.1 et les références citées). En principe, l'interprétation a pour objet le dispositif de l'arrêt, qui seul jouit de l'autorité de la chose jugée, et non ses motifs (NIKLAUS SCHMID, Schweizerische Strafprozessordnung, Praxiskommentar, 2e éd., 2013 n° 1 ad <ref-law>). Les considérants ne peuvent faire l'objet d'une interprétation que si et dans la mesure où il n'est possible de déterminer le sens du dispositif de la décision qu'en ayant recours aux motifs (<ref-ruling> consid. 1 p. 222; arrêt 8G_1/2014 du 3 juin 2014 consid. 2.2).
Le prononcé rectifié ou expliqué est communiqué aux parties (<ref-law>). Cette communication fait en principe partir un nouveau délai de recours (<ref-ruling> p. 88 consid. 3; NIKLAUS SCHMID, op. cit., n° 5 ad <ref-law>; ALAIN MACALUSO, in Commentaire romand, Code de procédure pénale suisse, 2011, n° 13 ss ad <ref-law>).
2.2. La cour cantonale a considéré que les motifs de l'ordonnance attaquée mentionnaient clairement le fait que l'opposition " devra être considérée comme retirée ", que " la présente procédure est ainsi vidée de tout objet " et que, par conséquent, " la présente procédure doit être classée ". Ce dernier terme ne pouvait équivaloir à un abandon des charges sans que celles-ci n'aient été même examinées, la procédure se clôturant alors par un acquittement et non par un classement. Il n'y avait ainsi aucun doute possible sur le fait qu'en ordonnant le " classement du dossier ouvert à l'encontre de... ", le juge avait affirmé mettre fin à la procédure de première instance sur l'opposition; il avait classé le dossier ouvert par le tribunal de police, soit l'opposition, ce qui laissait subsister l'ordonnance pénale. Le dispositif n'était ainsi que la suite logique des considérants et n'entrait pas en contradiction avec ces derniers. La cour cantonale a de même nié que le dispositif fût incomplet. En effet, dans la mesure où seul l'<ref-law> était applicable, le juge n'avait pas à statuer sur la validité de l'ordonnance pénale et de l'opposition, cette dernière étant réputée retirée.
En bref, la cour cantonale a retenu que, bien qu'il soit vrai que le choix des termes du dispositif attaqué était maladroit et que ce dernier aurait pu constater le retrait de l'opposition, on ne saurait pour autant le qualifier de " peu clair, contradictoire, incomplet ou en contradiction avec l'exposé des motifs " au sens de l'<ref-law>. Il n'y avait, partant, pas lieu de l'expliquer ou de le rectifier.
2.3. On ne saurait suivre la cour cantonale lorsqu'elle affirme que l'expression " classement du dossier " ne pouvait équivaloir à un abandon des charges dans la mesure où celles-ci n'avaient pas encore été examinées. En effet, un classement au sens des <ref-law> peut être prononcé même lorsque les charges n'ont pas été examinées, notamment dans les cas prévus par l'art. 319 al. 1 let. d CPP (par exemple, comme l'illustre le recourant, en cas de retrait de plainte ou de prescription de l'action pénale; cf. GRÄDEL/HEINIGER, in: Basler Kommentar, Schweizerische Strafprozessordnung, 2e éd., 2014, n° 13-15 ad <ref-law>; NIKLAUS SCHMID, op. cit., n° 8 ad <ref-law>).
Le recourant soutient avoir compris le dispositif attaqué comme signifiant qu'il était libéré de toute charge et souligne avoir même exprimé sa gratitude au juge par courrier du 27 janvier 2014. Que le recourant ait pu mal comprendre le disposif ne suffit certes pas encore à démontrer qu'il serait peu clair (cf. arrêt 4C.86/2004 du 7 juillet 2004, consid. 1.4), mais cela constitue un indice de la bonne foi du recourant dans sa démarche visant à obtenir la clarification dudit dispositif.
Comme le relève le recourant, dans le Code de procédure pénale, le terme " classement " est systématiquement employé pour désigner le prononcé par lequel le ministère public (<ref-law>) ou le tribunal (<ref-law>) classe la procédure, en ce sens qu'il est mis définitivement fin à la procédure après l'ouverture de l'instruction sans que d'autres mesures de poursuite pénale, telles qu'une mise en accusation ou le prononcé d'une ordonnance pénale, ne soient prises (NIKLAUS SCHMID, op. cit., n° 1 ad <ref-law>). Le code précise que le classement équivaut à un acquittement (<ref-law>). En conséquence, l'utilisation dans le dispositif de l'ordonnance des termes " ordonne le classement du dossier ouvert à l'encontre de... " pouvait, à première vue, être compris comme ordonnant un classement au sens des art. 329 al. 4 et 320 CPP.
La décision constatant le retrait fictif de l'opposition est lourde de conséquences pour le prévenu. Dans ce contexte, il convient de se montrer exigeant en ce qui concerne la clarté d'une telle décision, en particulier de son dispositif, qui jouit seul de la force de chose jugée. Au regard de ce qui précède, on doit admettre avec le recourant que le dispositif en cause, pris pour lui seul, laisse supposer que la procédure est classée au sens des art. 329 al. 4 et 319 ss CPP. A tout le moins est-il équivoque, car le fait que la procédure soit clôturée - comme dans tous les cas de prononcés d'un jugement final - ne dit encore rien sur la façon dont le litige a été tranché. D'ailleurs, en s'appuyant sur les motifs pour déterminer la signification du dispositif, la cour cantonale reconnaît ainsi que son sens ne peut être déterminé avec certitude qu'en ayant recours aux motifs de la décision, alors même que le dispositif ne renvoie pas expressément à ceux-là. Ce faisant, elle procède déjà à l'interprétation qu'elle refuse pourtant.
Il s'ensuit qu'en confirmant le refus du tribunal de police d'interpréter le dispositif ordonnant le " classement du dossier ouvert à l'encontre de X._ " alors que la décision prononçait le retrait fictif de l'opposition et entraînait l'entrée en force d'une ordonnance pénale condamnant le recourant, qui plaidait en personne, à diverses infractions pénales, la cour cantonale a violé le droit fédéral dans l'application de l'<ref-law>.
2.4. Le recours devant être admis pour ce motif déjà, il n'y a pas lieu d'examiner les autres griefs soulevés.
3.
L'arrêt attaqué est annulé. La compétence pour interpréter une décision appartient à l'autorité qui l'a prise, le recours n'ayant pas d'effet dévolutif (NILS STOHNER, in Basler Kommentar, Schweizerische Strafprozessordnung, 2011, n° 11 ad <ref-law>). Par conséquent, il convient de renvoyer la cause au tribunal de police pour qu'il procède à l'interprétation du dispositif de l'ordonnance du 21 janvier 2014 (<ref-law>).
4.
Le recourant obtient gain de cause. Une part des frais est mise à la charge de l'intimée qui s'est déterminée en concluant au rejet du recours, le canton de Neuchâtel n'ayant pas à en supporter (art. 66 al. 1 et 4 LTF). Le recourant peut prétendre à une indemnité de dépens, à la charge, pour moitié chacun, d'une part du canton de Neuchâtel et, d'autre part, de l'intimée (art. 68 al. 1 et 2 LTF), ce qui rend sans objet la requête d'assistance judiciaire (<ref-law>). La cause est renvoyée à la cour cantonale pour nouvelle décision sur les frais et dépens de la procédure cantonale et au Tribunal de police pour procéder à l'interprétation requise par le recourant.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, l'arrêt attaqué est annulé et la cause est renvoyée au Tribunal de police du Littoral et du Val-de-Travers pour nouvelle décision.
2.
Une partie des frais judiciaires, arrêtée à 1000 fr., est mise à la charge de l'intimée A._.
3.
A._ versera en mains du conseil de X._ une indemnité de 1500 fr. à titre de dépens.
4.
Le canton de Neuchâtel versera en mains du conseil de X._ une indemnité de 1500 fr. à titre de dépens.
5.
La cause est renvoyée à l'Autorité de recours en matière pénale du Tribunal cantonal de la République et canton de Neuchâtel pour nouvelle décision sur les frais et dépens de la procédure cantonale.
6.
Le présent arrêt est communiqué aux parties, au Tribunal cantonal de la République et canton de Neuchâtel, Autorité de recours en matière pénale, et au Tribunal de police du Littoral et du Val-de-Travers.
Lausanne, le 17 mars 2016
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Musy