Sachverhalt:
A.
Der Amtsgerichtspräsident von Bucheggberg-Wasseramt verurteilte X._ am 7. Februar 2013 zu einer bedingten Geldstrafe von 120 Tagessätzen zu Fr. 70.- wegen mehrfacher Widerhandlung gegen das Betäubungsmittelgesetz. Gegen dieses Urteil meldete X._ am 19. Februar 2013 fristgerecht die Berufung an. Das begründete Urteil wurde ihm am 29. April 2013 zugestellt. X._ übergab die schriftliche Berufungserklärung der Post am 21. Mai 2013. Das Obergericht des Kantons Solothurn trat auf das Rechtsmittel am 1. Juli 2013 nicht ein. Es erachtete die Berufungserklärung vom 21. Mai 2013 als verspätet.
B.
Mit Beschwerde in Strafsachen beantragt X._, den Beschluss vom 1. Juli 2013 aufzuheben und die Strafkammer des Obergerichts des Kantons Solothurn anzuweisen, auf die Berufung einzutreten.
C.
Das Obergericht des Kantons Solothurn beantragt, die Beschwerde abzuweisen. Die Staatsanwaltschaft verzichtet auf eine Vernehmlassung. X._ wurde das Replikrecht gewährt.

Erwägungen:
1.
Die Berufung ist gemäss <ref-law> innert 20 Tagen seit der Zustellung des begründeten Urteils schriftlich zu erklären. Fällt der letzte Tag der Frist auf einen Samstag, einen Sonntag oder einen vom Bundesrecht oder vom kantonalen Recht anerkannten Feiertag, so endet sie am nächstfolgenden Werktag. Massgebend ist das Recht des Kantons, in dem die Partei oder ihr Rechtsbeistand den Wohnsitz oder den Sitz hat (<ref-law>).
1.1. Das erstinstanzliche Urteil wurde dem Beschwerdeführer am 29. April 2013 zugestellt. Der Beschwerdeführer reichte die Berufungserklärung am Dienstag nach Pfingstmontag, den 21. Mai 2013 ein. Die Vorinstanz erwägt, dass die Berufungsfrist am Pfingstsonntag, den 19. Mai 2013 abgelaufen sei und die Berufungserklärung somit spätestens am darauffolgenden Pfingstmontag, welcher im Kanton Solothurn nicht zu den Feiertagen zählt, hätte eingereicht werden müssen. Obwohl am Pfingstmontag die kantonale Verwaltung und die Schalter der Post im Kanton Solothurn geschlossen waren, hätte der Beschwerdeführer die Berufung rechtzeitig einreichen können. So hätte er diese an der Schanzenpost in Bern oder an der Hauptpost in Aarau fristgerecht aufgeben oder im Beisein von Zeugen in einen beliebigen Briefkasten der Post werfen können. Das Obergericht erachtete das Rechtsmittel daher als verspätet und trat darauf nicht ein. Der Beschwerdeführer rügt, dass der Pfingstmontag ein vom kantonalen Recht anerkannter Feiertag sei, womit der erste Werktag nach Pfingstsonntag der darauffolgende Dienstag sei. Ausserdem übersehe die Vorinstanz, dass der Pfingstmontag auch im Nachbarkanton Bern als Feiertag behandelt wird und die Beschaffung von (unabhängigen) Zeugen am Pfingstwochenende die Wahrnehmung prozessualer Rechte erheblich erschweren würde.
1.2. Nach § 4 des solothurnischen Gesetzes vom 24. Mai 1964 über die öffentlichen Ruhetage (BGS 512.41) können die Einwohnergemeinden den Pfingstmontag als lokalen Ruhetag bezeichnen. Ein Rechtsakt, welcher den Pfingstmontag in der Wohnsitzgemeinde des Beschwerdeführers als lokalen Ruhetag bezeichnet, besteht nicht, und das kantonale Einführungsgesetz zur Schweizerischen Strafprozessordnung und zur Schweizerischen Jugendstrafprozessordnung vom 10. März 2010 (EG StPO, BSG 321.3) enthält keine Fristbestimmungen. Daraus ergibt sich, dass das kantonale Recht den Pfingstmontag am Wohnsitz des Beschwerdeführers nicht ausdrücklich als Feiertag anerkennt.
1.3.
1.3.1. <ref-law> verbietet überspitzten Formalismus als besondere Form der Rechtsverweigerung. Ein solcher liegt vor, wenn für ein Verfahren rigorose Formvorschriften aufgestellt werden, ohne dass die Strenge sachlich gerechtfertigt wäre, wenn die Behörde formelle Vorschriften mit übertriebener Schärfe handhabt oder an Rechtsschriften überspannte Anforderungen stellt und den Bürgern und Bürgerinnen den Rechtsweg in unzulässiger Weise versperrt. Wohl sind im Rechtsgang prozessuale Formen unerlässlich, um die ordnungsgemässe und rechtsgleiche Abwicklung des Verfahrens sowie die Durchsetzung des materiellen Rechts zu gewährleisten. Nicht jede prozessuale Formstrenge steht demnach mit <ref-law> im Widerspruch. Überspitzter Formalismus ist nur gegeben, wenn die strikte Anwendung der Formvorschriften durch keine schutzwürdigen Interessen gerechtfertigt ist, zum blossen Selbstzweck wird und die Verwirklichung des materiellen Rechts in unhaltbarer Weise erschwert oder verhindert (<ref-ruling> E. 2.1; <ref-ruling> E. 5.4.1, je mit Hinweisen).
1.3.2. Das Bundesgericht verneinte verschiedentlich überspitzten Formalismus, wenn die kantonale Behörde Fristablauf an einem Tag annahm, den das kantonale Recht nicht als Feiertag anerkannte. Dies auch, wenn am betreffenden Tag Verwaltung und Geschäfte geschlossen waren und niemand arbeitete (Urteile 1P.322/2006 vom 25. Juli 2006 und 1P.184/2001 vom 18. Juni 2001 [Stephanstag im Kanton Solothurn]; Urteil 1P.469/1999 vom 14. Oktober 1999 [Pfingstmontag im Kanton Zug]; Urteil 1P.481/1994 vom 26. Oktober 1994 [Pfingstmontag im Kanton Wallis]; Urteil 1P.440/1992 vom 7. September 1992 [Ostermontag im Kanton Zug]).
In einem Genfer Entscheid erachtete das kantonale Gericht eine erst nach Ablauf der Appellationsfrist am Berchtoldstag (2. Januar) eingereichte Appellationserklärung als verspätet. Das Bundesgericht wies eine dagegen gerichtete Beschwerde ab. Obwohl die Büros der kantonalen Verwaltung an jenem Tag geschlossen waren, erwog es, dass die Poststelle von Montbrillant von 12 bis 20 Uhr geöffnet war. Diese befinde sich in angemessener Entfernung der Kanzlei des Rechtsvertreters des Beschwerdeführers. Die Appellationserklärung hätte somit fristgerecht erfolgen können (Urteil 1P.259/1996 vom 8. Juli 1996 E. 3c, in: Pra 1996 Nr. 217). In einem anderen Fall bestätigte das Bundesgericht ein Urteil des Kantonsgerichts von Graubünden, wonach ein in der Stadt Zürich wohnhafter Beschwerdeführer am Berchtoldstag - unabhängig davon, ob dieser dort als Feiertag gilt - die Möglichkeit gehabt hätte, seine Eingabe rechtzeitig an der Zürcher Sihlpost aufzugeben. Diese sei am Berchtoldstag von 10 bis 22.30 Uhr geöffnet gewesen und 2,5 bis 3 Kilometer vom Wohnort des Beschwerdeführers entfernt (Urteil 1P.456/2006 vom 24. Oktober 2006 E. 2.3).
Die Frage, ob eine Eingabe an einem nicht offiziell anerkannten Feiertag der Post oder direkt dem zuständigen Gericht gegen Empfangsbestätigung faktisch überreicht werden konnte, blieb in der erwähnten Rechtsprechung zum Teil unbeantwortet (Urteile 1P.184/2001 E. 2c/bb; 1P.481/1994 E. 2b; 1P.440/1992 E. 2b). Überspitzter Formalismus wurde mit dem Argument verneint, dass der jeweilige Tag im entsprechenden Kanton nicht gesetzlich als Feiertag anerkannt ist. Zusätzlich wurde berücksichtigt, dass für den Beschwerdeführer die Möglichkeit bestand, seine Eingabe bei einer offenen und in angemessener Entfernung sich befindlichen Poststelle aufzugeben. Diese Rechtsprechung ist zu präzisieren. <ref-law> verbietet die strikte Anwendung von Formvorschriften, welche die Verwirklichung des materiellen Rechts in unhaltbarer Weise erschwert oder verhindert (siehe oben, E. 1.3). Dies ist der Fall, wenn die Behörde Fristablauf an einem Tag annimmt, an welchem für die Partei oder für ihren Vertreter keine Möglichkeit bestand, die Eingabe der Behörde selbst oder zu ihren Händen einer offenen und in vernünftiger Distanz sich befindlichen Poststelle oder Postagentur gegen Empfangsbestätigung zu übergeben. Die Möglichkeit, die Eingabe in einen beliebigen Postbriefkasten im Beisein von Zeugen einzuwerfen, genügt nicht. Einerseits kann sich die Beschaffung von Zeugen als schwierig erweisen, andererseits unterliegen diese nicht dem Post- oder Amtsgeheimnis, womit der Betroffene seines Anspruchs auf Geheimhaltung verlustig ginge. Schliesslich wird die Aussage der Zeugen einer Beweiswürdigung unterzogen, deren Ausgang für den Betroffenen nicht voraussehbar ist.
1.3.3. Die Vorinstanz erwägt, dass der Beschwerdeführer sich der Schanzenpost in Bern oder der Hauptpost in Aarau hätte bedienen können, um die Berufung rechtzeitig einzureichen. Diese Poststellen befinden sich ausserhalb des Kantons Solothurn und sind 38 bzw. 56 Kilometer vom Wohnort des Beschwerdeführers entfernt. Diese Distanz kann nicht als angemessen angesehen werden. Die Gelegenheit, die Berufung am Pfingstmontag direkt beim Obergericht einzureichen, wurde im angefochtenen Beschluss nicht erwähnt. Dem Beschwerdeführer war es somit nicht möglich, seine Berufung rechtzeitig und in angemessener Distanz von seinem Wohnort nachweislich einzureichen. Der angefochtene Beschluss erweist sich somit als überspitzt formalistisch. Er ist aufzuheben und die Sache ist zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
2.
Die Beschwerde ist gutzuheissen. Bei diesem Verfahrensausgang sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Solothurn hat dem Beschwerdeführer für das bundesgerichtliche Verfahren eine angemessene Parteientschädigung auszurichten (<ref-law>). Mit dem Entscheid in der Sache ist das Gesuch um aufschiebende Wirkung gegenstandslos geworden.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der angefochtene Beschluss des Obergerichts des Kantons Solothurn vom 1. Juli 2013 wird aufgehoben und die Sache zur neuen Beurteilung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Solothurn hat dem Beschwerdeführer für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 3'000.-- zu bezahlen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Solothurn, Strafkammer, schriftlich mitgeteilt.
Lausanne, 10. Dezember 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Moses