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'art. 83 CPP 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'art. 320 al. 4 CPP avec l'art. 329 al. 4 CPP, 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.