Sachverhalt:
A.
Zu beurteilen sind Ansprüche aus einem (bestrittenen) Vertrag zwischen der B._ GmbH (Klägerin, Beschwerdegegnerin) und der A._ AG (Beklagte, Beschwerdeführerin) über einen letztlich nicht durchgeführten Shisha-Service (nachfolgend: der Service) im Jahr 2018. Nach klägerischer Ansicht war nach der Durchführung des Services in den Jahren 2016 und 2017 auch für 2018 ein Vertrag zustande gekommen. Die Dienstleistung der Klägerin bestand darin, dass sie auf Bestellung der Gäste auf dem Areal der Beklagten Shishas (Wasserpfeifen) konsumfertig vorbereitete und den Gästen anschliessend durch eigenes Personal servierte. Die Klägerin ist der Ansicht, die Beklagte habe den Service zu spät abgesagt und habe sie entsprechend schadlos zu halten.
B.
Mit Klage vom 29. April 2020 beantragte die Klägerin beim Handelsgericht des Kantons Bern, die Beklagte sei zu verpflichten, ihr den Betrag von Fr. 96'111.15 nebst Zins zu bezahlen.
Mit Urteil vom 19. Juli 2021 hiess das Handelsgericht die Klage teilweise gut. Es verpflichtete die Beklagte, der Klägerin einen Betrag von Fr. 90'000.-- nebst Zins zu bezahlen. Soweit weitergehend wies es die Klage ab.
Es erwog, es sei nach dem Vertrauensprinzip ein Vertrag zwischen den Parteien zustande gekommen. Der Service hätte im Zeitraum vom 15. Juni 2018 bis zum 30. September 2018 durch die Klägerin bei der Beklagten durchgeführt werden sollen. Im Vordergrund des Vertrages habe die Lieferung und die Herstellung des Materials bzw. der einzelnen konsumfertigen Shishas gestanden. Die Klägerin habe hierzu Rohmaterial im Sinne eines Werkvertrages verarbeitet. Es seien somit die Regelungen über den Werkvertrag anwendbar (<ref-law>). Die Beklagte sei jedoch noch vor Beginn des eigentlichen Services vom Vertrag zurückgetreten. In Anwendung von <ref-law> sprach das Handelsgericht der Klägerin einen Schadenersatz von Fr. 90'000.-- (hypothetischer Umsatzanteil) zu.
C.
Mit Beschwerde in Zivilsachen vom 8. September 2021 beantragt die Beklagte dem Bundesgericht, der Entscheid des Handelsgerichts sei kostenfällig aufzuheben und die Klage sei vollumfänglich abzuweisen. Eventualiter sei die Sache zur Neubeurteilung an das Handelsgericht zurückzuweisen. Die Beschwerdegegnerin beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten ist. Das Handelsgericht hat auf Vernehmlassung verzichtet.

Erwägungen:
1.
Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es prüft aber unter Berücksichtigung der allgemeinen Begründungsanforderungen (Art. 42 Abs. 1 und 2 BGG) grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind. Es ist nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (<ref-ruling> E. 2, 115 E. 2). Die Beschwerde ist dabei hinreichend zu begründen, andernfalls wird darauf nicht eingetreten. Unerlässlich ist im Hinblick auf <ref-law>, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt. Die beschwerdeführende Partei soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die sie im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (vgl. <ref-ruling> E. 2.1).
2.
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Dazu gehören sowohl die Feststellungen über den streitgegenständlichen Lebenssachverhalt als auch jene über den Ablauf des vor- und erstinstanzlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt (<ref-ruling> E. 1.3.1 mit Hinweisen). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 2, 264 E. 2.3). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein können (<ref-law>).
Für eine Kritik am festgestellten Sachverhalt gilt das strenge Rügeprinzip von <ref-law> (<ref-ruling> E. 2.3 mit Hinweisen). Die Partei, welche die Sachverhaltsfeststellung der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern die genannten Voraussetzungen erfüllt sein sollen (<ref-ruling> E. 1.3.1 mit Hinweisen). Wenn sie den Sachverhalt ergänzen will, hat sie zudem mit präzisen Aktenhinweisen darzulegen, dass sie entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen prozesskonform eingebracht hat (<ref-ruling> E. 2). Genügt die Kritik diesen Anforderungen nicht, können Vorbringen mit Bezug auf einen Sachverhalt, der vom angefochtenen Entscheid abweicht, nicht berücksichtigt werden (<ref-ruling> E. 1.3.1).
3.
Zu beachten ist, dass das Bundesgericht in die Beweiswürdigung des Sachgerichts nur eingreift, wenn diese willkürlich ist. Willkür liegt nach der Rechtsprechung nicht schon dann vor, wenn eine andere Lösung ebenfalls in Betracht zu ziehen oder gar vorzuziehen wäre, sondern bloss, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 4.1; <ref-ruling> E. 2.1; je mit Hinweisen). Die Beweiswürdigung ist mithin nicht schon dann willkürlich, wenn sie nicht mit der Darstellung der beschwerdeführenden Partei übereinstimmt, sondern bloss, wenn sie offensichtlich unhaltbar ist (<ref-ruling> E. 4.1; <ref-ruling> E. 4.2.1). Dies ist dann der Fall, wenn das Gericht Sinn und Tragweite eines Beweismittels offensichtlich verkannt, wenn es ohne sachlichen Grund ein wichtiges und entscheidwesentliches Beweismittel unberücksichtigt gelassen oder wenn es auf der Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen gezogen hat (<ref-ruling> E. 2.3; <ref-ruling> E. 4.2). Inwiefern die Beweiswürdigung willkürlich sein soll, ist in der Beschwerde klar und detailliert aufzuzeigen (<ref-ruling> E. 2.2).
4.
Soweit ein Entscheid auf mehreren selbständigen alternativen Begründungen beruht, ist für jede einzelne darzutun, weshalb sie Recht verletzt, denn soweit nicht beanstandete Begründungen das angefochtene Urteil selbständig stützen, fehlt das Rechtsschutzinteresse an der Beurteilung der gehörig begründeten Rügen (<ref-ruling> E. 6.3; vgl. auch <ref-ruling> E. 3.2; je mit Hinweisen).
5.
Umstritten ist die Aktivlegitimation der Beschwerdegegnerin.
5.1. Die Vorinstanz erwog, es sei unbestritten, dass in den Jahren 2016 und 2017 unter der Regie von Herrn C._ ([Teil-]Inhaber der Beschwerdegegnerin) bei der Beschwerdeführerin ein Shisha-Service durchgeführt worden sei. Im Jahr 2016 sei er gegenüber der Beschwerdeführerin als Einzelperson aufgetreten. Auch der (einzige) schriftliche Vertrag betreffend den Service 2016 sei zwischen ihm und der Beschwerdeführerin abgeschlossen worden. Die Beschwerdegegnerin habe zu diesem Zeitpunkt noch gar nicht existiert. Sie sei erst am 26. April 2017 in das Handelsregister eingetragen worden. Anlässlich der Parteibefragung habe Herr C._ glaubhaft dargelegt, dass die Gründung der Beschwerdegegnerin im Hinblick auf den Service 2017 erfolgt sei. Ein schriftlicher Vertrag zwischen der Beschwerdeführerin und der Beschwerdegegnerin betreffend den Service 2017 bestehe allerdings nicht. Zusammenfassend sprächen aber die vorhandenen schriftlichen Dokumente der Beschwerdeführerin und die zwischen den Parteien gelebten Vertragsmodalitäten dafür, dass sowohl zu diesem Zeitpunkt als auch im Jahr 2018 (zum Zustandekommen eines Vertrages für das Jahr 2018 vgl. hiernach E. 6) die Beschwerdegegnerin und nicht Herr C._ die Vertragspartnerin der Beschwerdeführerin gewesen sei. Die Beschwerdegegnerin sei somit aktivlegitimiert.
5.2.
5.2.1. Was die Beschwerdeführerin dagegen vorbringt, überzeugt nicht. Sie beschränkt sich über weite Strecken in appellatorischer Kritik, ohne sich hinreichend mit den vorinstanzlichen Erwägungen auseinanderzusetzen. So genügt es nicht, den vorinstanzlichen Ausführungen ohne eigentliche Auseinandersetzung ausführliche Zitate aus den vorinstanzlichen Rechtsschriften gegenüberzustellen. Wenn die Beschwerdeführerin über mehrere Seiten widergibt, was anlässlich der Befragungen von wem gesagt wurde, übergeht sie zudem, dass das Bundesgericht keine eigene Beweiswürdigung vornimmt, sondern vielmehr einzig die vorinstanzliche Beweiswürdigung auf Willkür überprüft, was eine hinreichende Rüge voraussetzt.
Die Rüge der Beschwerdeführerin, die Vorinstanz habe den Sachverhalt offensichtlich unrichtig festgestellt, weil sie darauf aufbaue, dass die Beschwerdegegnerin bereits 2016 einen Service bei ihr organisiert habe, was gar nicht möglich sei, weil diese erst 2017 gegründet worden sei, ist sodann offensichtlich unbegründet. Die Vorinstanz hat ausdrücklich festgehalten, dass im Jahr 2016 Herr C._ (und nicht die Beschwerdegegnerin) gegenüber der Beschwerdeführerin als Einzelperson aufgetreten sei. Ebenso wenig willkürlich ist die vorinstanzliche Feststellung, es bestehe für den Service 2017 kein schriftlicher Vertrag. Diese Feststellung ist so zu verstehen, dass - im Gegensatz zum Service 2016 - kein schriftlicher Vertrag im Sinne eines Dokuments besteht, das die Unterschriften der Parteien trägt. Die Beschwerdeführerin zeigt denn auch nicht mit Aktenhinweis auf, dass sie einen schriftlichen Vertrag betreffend den Service 2017 als Urkunde eingereicht hätte.
Entgegen der Beschwerdeführerin verfällt die Vorinstanz auch nicht in Willkür, wenn sie aufgrund der Aussagen von Herrn C._ nicht ableitet, es sei für den Service 2017 ein Vertrag zwischen der Beschwerdeführerin und ihm persönlich (statt der Beschwerdegegnerin) entstanden. Herr C._ sagte anlässlich der Befragung Folgendes aus: "Ich habe per E-Mail eine Bestellung erhalten, geschrieben wie letztes Jahr. Für mich war das ein Vertrag. Es ist mir gesagt worden, es gelten die gleichen Bedingungen wie 2016." Diese Aussage bezieht sich primär auf den Inhalt der zu erbringenden Dienstleistung. Daraus musste die Vorinstanz jedenfalls nicht ableiten, Herr C._ und die Beschwerdeführerin hätten einen tatsächlichen Willen dahingehend gehabt, dass der Vertrag erneut zwischen ihnen beiden und nicht mit der Beschwerdegegnerin entstehen soll. Dies gilt namentlich vor dem Hintergrund, dass Herr C._ weiter ausführte, "[w]ir hatten aber ein Problem mit der Bezahlung, ich durfte nicht Mehrwertsteuer abrechnen mit der Einzelfirma, darum habe ich die GmbH gegründet [...]".
Zusammenfassend vermag die Beschwerdeführerin nicht aufzuzeigen, dass die Vorinstanz in Willkür verfallen wäre, indem sie zum Ergebnis gelangte, ein tatsächlicher Wille hinsichtlich der Vertragsparteien für den Service 2017 sei nicht erstellt.
5.2.2. Durfte die Vorinstanz, ohne in Willkür zu verfallen, davon ausgehen, ein natürlicher Konsens betreffend die Vertragsparteien für die Durchführung des Services 2017 sei nicht erstellt, hatte sie in der Folge zu prüfen, ob ein normativer Konsens bestand. Die Vorinstanz hat in diesem Sinne ausführlich begründet, weshalb die Beschwerdeführerin nach Treu und Glauben davon habe ausgehen müssen, der Vertrag für den Service 2017, wie auch für den Service 2018, dessen Zustandekommen sie bejahte (vgl. dazu hiernach E. 6), sei zwischen der Beschwerdeführerin und der Beschwerdegegnerin entstanden.
Damit setzt sich die Beschwerdeführerin in ihrer Beschwerde nicht hinreichend auseinander.
Sie beanstandet zwar über mehrere Seiten, die Vorinstanz sei offensichtlich unrichtig zum Schluss gekommen, dass sie keine Begründung vorlege, weshalb es auf die Persönlichkeit von Herrn C._ angekommen wäre. Dabei übergeht sie aber die Eventualbegründung der Vorinstanz. Diese hielt nicht nur fest, die Beschwerdeführerin lege keine Begründung dafür vor, dass es auf die Persönlichkeit von Herrn C._ angekommen wäre und eine solche sei auch nicht ersichtlich. Vielmehr erwog sie darüber hinaus auch, es sei im Übrigen gang und gäbe, dass selbst für Leistungen, bei denen es auf die Persönlichkeit der ausführenden (natürlichen Person) ankomme, Verträge mit juristischen Personen abgeschlossen würden, so etwa bei entsprechend organisierten Anwaltskanzleien, Arztpraxen oder Architekturbüros. Mit dieser Begründung setzt sich die Beschwerdeführerin in ihrer Beschwerde nicht auseinander. Damit hat sie betreffend die Frage, ob es auf die Persönlichkeit von Herrn C._ angekommen wäre und was sich daraus hinsichtlich der Aktivlegitimation der Beschwerdegegnerin ableiten lässt, nicht alle vorinstanzlichen Begründungen angefochten, womit auf ihre diesbezüglichen Rügen nicht einzutreten ist (vgl. hiervor E. 4).
Weiter tut die Beschwerdeführerin auch nicht dar, inwiefern die Vorinstanz Bundesrecht verletzt haben sollte, indem sie als gewichtiges Indiz für einen Vertrag zwischen der Beschwerdeführerin und der Beschwerdegegnerin (statt Herrn C._) namentlich auf die Abrechnungen für das Jahr 2017 abstellte.
5.2.3. Die Beschwerdeführerin vermag insgesamt nicht darzutun, dass die Vorinstanz Bundesrecht verletzt hat, indem sie zum Ergebnis gelangte, der Vertrag betreffend den Service 2017 sei zwischen ihr und der Beschwerdegegnerin zustande gekommen. Somit kann sie auch nicht argumentieren, die Vorinstanz gehe für den Service 2017 von offenkundig falschen Vertragsparteien aus und bejahe als Folge dessen zu Unrecht die Aktivlegitimation der Beschwerdegegnerin im Zusammenhang mit dem (bestrittenen) Service 2018. Die Vorinstanz durfte folglich ohne Verletzung von Bundesrecht davon ausgehen, die Beschwerdegegnerin sei für die geltend gemachte Klage aktivlegitimiert.
6.
Umstritten ist weiter, ob zwischen den Parteien überhaupt ein Vertrag betreffend die Durchführung eines Services im Sommer 2018 zustande gekommen ist.
6.1. Die Vorinstanz erwog, da die Beschwerdeführerin das Zustandekommen des Vertrages bestreite, hätten sich die Parteien nicht übereinstimmend geäussert, verstanden und in diesem Verständnis geeinigt, womit keine tatsächliche Willensübereinstimmung und damit kein tatsächlicher Konsens bestehe. Entsprechend sei zu beurteilen, ob zwischen den Parteien ein normativer Konsens entstanden sei. Dabei gelte das Vertrauensprinzip. Vorliegend bestehe zwar keine direkte schriftliche Willenserklärung, die auszulegen wäre, vorhanden sei jedoch der schriftliche E-Mail-Verkehr zwischen den Parteien, der die mündlichen Aussagen der Parteivertreter und Zeugen anlässlich ihrer Befragungen in einen Kontext setze. Ausserdem bestehe ein internes Dokument der Beschwerdeführerin (mit der Bezeichnung "Regelungen Shisha Service 2018"), das im Rahmen der Vorbereitungen durch einen ihrer Mitarbeiter, Herr D._, erstellt worden sei. Nach dem Vertrauensprinzip sei ein Vertrag zwischen den Parteien zustande gekommen. Selbst wenn dieser nicht bis in die letzten Details ausgearbeitet worden sei, so seien die wesentlichen Punkte klar gewesen. Der Service habe im Zeitraum vom 15. Juni 2018 bis zum 30. September 2018 bei der Beschwerdeführerin durchgeführt werden sollen, und zwar im vorderen Bereich der Hotelanlage. Vom erwirtschafteten Umsatz hätten der Beschwerdegegnerin 80 % weitergeleitet werden müssen.
6.2. Vertragsbezogene Willenserklärungen sind - wenn kein übereinstimmender tatsächlicher Parteiwille festgestellt werden kann - nach dem Vertrauensgrundsatz so auszulegen, wie sie vom Empfänger nach Treu und Glauben verstanden werden durften und mussten. Dies beurteilt sich nicht nur nach ihrem Wortlaut und dem gesamten Zusammenhang, in dem sie stehen, sondern auch nach den Umständen, die ihnen vorausgegangen und unter denen sie abgegeben worden sind (<ref-ruling> E. 5.2.3; <ref-ruling> E. 2.2.1). Zu welchem Ergebnis eine solche Auslegung führt, ist eine Frage der Rechtsanwendung, über welche das Bundesgericht frei entscheidet. Grundsätzlich gebunden ist es aber an die Feststellungen des kantonalen Gerichts über die Umstände des Vertragsschlusses und das Wissen der Vertragsparteien (<ref-ruling> E. 5.2.3; <ref-ruling> E. 2.2.1; <ref-ruling> E. 4; je mit Hinweisen).
6.3. Die Beschwerdeführerin rügt, die Vorinstanz habe den Sachverhalt (betreffend die Umstände des Vertragsschlusses bzw. das Wissen der Parteien) offensichtlich unrichtig festgestellt, indem sie erwogen habe, die Zustimmung des Hoteldirektors zur Durchführung des Service 2018 sei nicht notwendig gewesen.
6.3.1. Die Vorinstanz erwog, es sei gegenüber der Beschwerdegegnerin kein Vorbehalt geäussert worden, dass noch interne Absprachen getätigt werde müssten bzw. gar noch eine Zustimmung des Hoteldirektors (Herr G._) erforderlich wäre. Einer solchen Zustimmung habe es - zumindest im Aussenverhältnis - auch nicht bedurft. Vielmehr seien sämtliche Ansprechpersonen der Beschwerdegegnerin (Herr D._, sein Nachfolger Herr E._ sowie Herr F._) Mitglieder der Geschäftsleitung der Beschwerdeführerin und direkt dem Hoteldirektor unterstellt. Herr C._ (als Vertreter der Beschwerdegegnerin) habe, namentlich mit Blick auf die beiden vorangegangenen Jahre, davon ausgehen dürfen, die Beschwerdeführerin sei gültig durch (dieselben) Personen des Kaders vertreten worden und eine interne Kommunikation habe bereits stattgefunden.
6.3.2. Die Beschwerdeführerin vermag nicht darzutun, inwiefern die Vorinstanz mit diesen Feststellungen in Willkür verfallen sein sollte. Stattdessen übt sie appellatorische Kritik. Sie scheint dabei namentlich zu übersehen, dass es nicht darum geht, welche internen Abläufe bei ihr bestanden haben, sondern von welchen internen Abläufen die Beschwerdegegnerin (bzw. Herr C._ als ihr Vertreter) nach Treu und Glauben ausgehen durfte. Diesbezüglich hat die Vorinstanz kein Bundesrecht verletzt. Ihr Einwand, die Beschwerdegegnerin hätte wie in den Vorjahren von einer förmlichen Bestellung ausgehen müssen, basiert sodann auf einer Ergänzung des Sachverhalts, ohne dass die entsprechenden Voraussetzungen erfüllt wären (vgl. hiervor E. 2). Nichts ändert schliesslich auch, dass noch gewisse Unsicherheiten betreffend die genaue Lokalität des Services 2018 auf dem Hotelareal bestanden haben sollen, zumal sich die Vorinstanz in ihrem Entscheid (dort E. 7.5.3) damit ausführlich auseinandergesetzt hat.
Soweit die Beschwerdeführerin die vorinstanzliche Erwägung beanstandet, dass die Beschwerdegegnerin nicht mit der Notwendigkeit eines schriftlichen Vertrages für den Service 2018 zu rechnen hatte, basiert ihre Rüge einzig auf ihrem unbegründeten Vorwurf, die Vorinstanz habe zu Unrecht festgestellt, es habe keinen schriftlichen Vertrag zwischen den Parteien betreffend den Service 2017 gegeben. Diesbezüglich kann auf die Ausführungen in E. 5.2.1 hiervor verwiesen werden. Auch vermag die Beschwerdeführerin nicht aufzuzeigen, dass die Vorinstanz in Willkür verfallen wäre, indem sie feststellte, die Beschwerdegegnerin habe im Hinblick auf den Shisha Service 2018 Dispositionen getroffen. So ist insbesondere ihr Einwand, Herr C._ und dessen Mitarbeiter seien bloss angereist, um vollendete Tatsachen zu schaffen, nicht glaubwürdig.
6.3.3. Die Beschwerdeführerin rügt weiter, die Vorinstanz habe offensichtlich unrichtig festgestellt, die Angebotszeit des Services 2018 sei vom 15. Juni 2018 bis 30. September 2018 festgelegt worden. Sie macht insbesondere geltend, ein Beginn am 15. Juni 2018 widerspreche ihrem internen Dokument "Regelungen Shisha Service 2018".
Die Vorinstanz erwog, auch beim zeitlichen Rahmen des Shisha-Services 2018 könne davon ausgegangen werden, dass sich Herr C._ und Herr D._ anlässlich des Gesprächs vom 27. April 2018 auf einen Beginn am 15. Juni 2018 geeinigt hätten. Es sei nicht ersichtlich, weshalb die Beschwerdegegnerin (bzw. ihre Mitarbeitenden) bei einer anderslautenden Vereinbarung zwei Wochen zu früh hätte anreisen sollen. Der zeitliche Rahmen des Shisha-Services 2018 sei im Übrigen auch durch die Reservation des Mitarbeiterzimmers bestätigt worden.
Die Beschwerdeführerin vermag diesbezüglich keine Bundesrechtsverletzung aufzuzeigen. Der Umstand, dass im internen Dokument "Regelungen Shisha Service 2018" andere Angebotszeiten (1. Juli 2018 bis 30 September 2018) genannt wurden, ist insofern nicht entscheidend, als damit nicht ausgeschlossen ist, dass sich die Parteien anlässlich der Besprechung vom 27. April 2018 auf einen früheren Beginn des Services geeinigt hätten. Dies gilt insbesondere vor dem Hintergrund, dass im betreffenden Dokument bloss - wenn auch relativ ausführlich - Eckpunkte des Services skizziert wurden. Zudem ist (wie bereits erwähnt) nicht glaubwürdig, dass die Mitarbeitenden der Beschwerdegegnerin zwei Wochen zu früh angereist wären (einschliesslich der Reservation des Mitarbeiterzimmers).
6.3.4. Zusammenfassend hat die Vorinstanz kein Bundesrecht verletzt, indem sie gestützt auf das Vertrauensprinzip davon ausging, es sei zwischen den Parteien ein Vertrag betreffend die Durchführung eines Shisha-Services vom 15. Juni 2018 bis 30. September 2018 auf dem Areal der Beschwerdeführerin entstanden.
7.
Strittig ist weiter die Vertragsqualifikation. Die Vorinstanz hat den streitgegenständlichen Vertrag zwischen den Parteien - wie erwähnt -als Werkvertrag qualifiziert, den Rücktritt vom Vertrag entsprechend nach <ref-law> beurteilt und der Beschwerdegegnerin das positive Vertragsinteresse zugesprochen. Die Beschwerdeführerin stellt sich hingegen (eventualiter) auf den Standpunkt, es handle sich um einen Auftrag, womit sich ein allfälliger Rücktritt nach <ref-law> beurteile.
7.1. Die Vertragsqualifikation ist eine Rechtsfrage (<ref-ruling> E. 3; Urteile 4A_360/2021 vom 6. Januar 2022 E. 5.1.1; 4A_141/2019 vom 26. September 2019 E. 4.1; 4A_602/2013 vom 27. März 2014 E. 3.1). Das Bundesgericht prüft die vorinstanzliche Vertragsqualifikation aufgrund der von der Vorinstanz festgestellten Tatsachen (Urteil 4A_64/2020 vom 6. August 2020 E. 5 mit Hinweisen; <ref-ruling> E. 2).
7.2. Ein Werkvertrag liegt vor, wenn sich der Unternehmer zur Herstellung eines Werkes und der Besteller zur Leistung einer Vergütung verpflichtet (<ref-law>). Typisch für den Werkvertrag ist, dass der Unternehmer nicht nur Arbeit, sondern einen Arbeitserfolg in Form eines Werkes schuldet. Durch die Annahme eines Auftrags hingegen verpflichtet sich der Beauftragte, die ihm übertragenen Geschäfte oder Dienste vertragsgemäss zu besorgen (<ref-law>). Er haftet dem Auftraggeber für getreue und sorgfältige Ausführung des ihm übertragenen Geschäfts (<ref-law>). Der Beauftragte hat grundsätzlich nicht für den Erfolg seiner Tätigkeit einzustehen (<ref-ruling> E. 2a; Urteile 4A_594/2017 vom 13. November 2018 E. 4.1; 4A_129/2017 vom 11. Juni 2018 E. 4.1; 4A_252/2010 vom 25. November 2010 E. 4.1).
7.3. Die Vorinstanz erwog, da der zu beurteilende Vertrag betreffend den Shisha-Service 2018 grösstenteils den bereits beidseitig erfüllten Verträgen der beiden vorangegangenen Jahre 2016 und 2017 entspreche, könne der Inhalt des Vertrages 2018 diesen gelebten Verhältnissen entsprechend festgelegt werden. Die Beschwerdegegnerin habe das Material für den Service geliefert, habe auf Bestellung der Gäste auf dem Areal der Beschwerdeführerin die Raucherware konsumfertig vorbereitet und diese sodann durch eigenes angestelltes Personal serviert. Hierfür hätten die Wasserpfeifen vorbereitet, mit Wasser, Alufolie sowie dem gewünschten Tabak ausgestattet, anschliessend zusammengesetzt und mittels Kohle entzündet werden müssen. Die Beschwerdeführerin sei demgegenüber verpflichtet gewesen, der Beschwerdegegnerin 80 % des durch den Shisha-Service entstandenen Umsatzes zu vergüten. Im Vordergrund des Vertrages hätten die Lieferung und die Herstellung des Materials bzw. der einzelnen konsumfertigen Shishas gestanden. Die Beschwerdegegnerin habe hierzu Rohmaterial im Sinne eines Werkvertrages verarbeitet. Geschuldet gewesen sei mithin kein reines Tätigwerden, sondern zentral sei das Endprodukt zum Konsum der Gäste gewesen. Zusätzlich habe insofern ein mietvertragliches Element bestanden, als die Shishas während der ganzen Dauer des geplanten Services zur Verfügung gehalten worden seien. Im Vergleich zu den Hauptleistungspflichten falle dieses Element aber in den Hintergrund, ebenso wie das eigentliche Servieren durch die Arbeitnehmer der Beschwerdegegnerin, worin ein eigentliches auftragsrechtliches Element bestanden habe. Hauptsächlich sei es um die Vorbereitung der Shishas auf Bestellung der Gäste gegen Entgelt gegangen, womit die Regelungen über den Werkvertrag Anwendung fänden.
7.4. Diesen Ausführungen der Vorinstanz ist nicht zu folgen. Die Beschwerdeführerin macht zu Recht geltend, entscheidend seien nicht die Leistungen im Verhältnis der Beschwerdegegnerin zu den Hotelgästen, sondern die Leistungen, zu denen sich die Beschwerdegegnerin ihr gegenüber verpflichtet habe. Die Vorinstanz unterscheide nicht zwischen diesen beiden Ebenen. Die Leistungen der Beschwerdegegnerin gegenüber der Beschwerdeführerin bestanden in der Bewirtschaftung der Gäste, welche eine Shisha rauchen wollten. Die Beschwerdegegnerin übernahm sämtliche damit einhergehende Arbeiten, wie sich auch aus den vorinstanzlichen Feststellungen ergibt. Dazu gehörte insbesondere auch das Servieren der Shishas durch eigenes Personal sowie die Organisation des Shisha-Services an sich. Die Beschwerdegegnerin verpflichtete sich - wie sich aus den vorinstanzlichen Feststellungen ergibt und wie die Beschwerdeführerin zu Recht ausführt - (in enger Zusammenarbeit mit der Beschwerdeführerin) einen Shisha-Service zu organisieren. Dies ergibt sich zusätzlich auch aus der Vereinbarung betreffend den Service 2016. Der Vorinstanz ist nicht zu folgen, wenn sie im Rahmen der Vertragsqualifikation bloss auf die eigentliche Vorbereitung der Shishas abstellt und infolge dessen das Vertragsverhältnis als Werkvertrag qualifiziert. Wie die Beschwerdeführerin zu Recht ausführt, bestanden die Leistungen der Beschwerdegegnerin darin, auf ihrem Areal in enger Zusammenarbeit mit ihr einen Shisha-Service anzubieten. Die Beschwerdeführerin macht in diesem Sinne weiter zu Recht auch geltend, die Pflicht zur Bereitstellung einer Dienstleistung gegenüber Dritten, deren Anzahl und Konsumverhalten nicht durch die Parteien direkt bestimmt werden könne, sondern von äusseren Umstände abhänge, spreche nicht für einen Werkvertrag. Dass die eigentliche Herstellung der Shisha-Raucherware durch die Beschwerdegegnerin (Vorbereitung der Wasserpfeifen mit Wasser, Alufolie und Tabak sowie anschliessendes Zusammensetzen und Anzünden mittels Kohle) ein "überprüfbarer Arbeitserfolg" bildet, vermag das Vertragsverhältnis zwischen den Parteien - entgegen der Vorinstanz - in seiner Gesamtheit nicht als Werkvertrag zu qualifizieren. Vielmehr ist von einem gemischten Vertrag auszugehen, bei dem auftragsrechtliche Elemente dominieren.
Zusammenfassend ist die Vorinstanz somit zu Unrecht davon ausgegangen, dass die werkvertraglichen Regelungen Anwendung fänden.
8.
Umstritten ist weiter, ob der Beschwerdegegnerin ein valables Alternativangebot im Sinne einer Ausweichlocation angeboten wurde.
8.1. Die Vorinstanz erwog, Herr G._ habe dazu ausgeführt, es sei keine Ersatzlösung angeboten worden, sondern man habe gesagt, wenn sie wollten, könnten sie den Service auf dem alten X._-Areal machen. Auch Herr E._ habe angegeben, dass es keine Ausweichlocation gegeben habe bzw. die Lösung hinter dem Hotel "nicht so zur Debatte" gestanden habe. Selbst wenn ein solches Angebot gemacht worden wäre, entspräche dies bereits aus Sicht der Beschwerdeführerin nicht einer ernsthaften Alternative für die Durchführung des Services 2018. Wie dargelegt, habe die Beschwerdegegnerin davon ausgehen dürfen, dass ihr für den Service 2018 ein geeigneter, den Vorjahren ungefähr entsprechender Platz zur Verfügung gestellt würde.
8.2. Was die Beschwerdeführerin dagegen vorbringt, überzeugt nicht. Sie wendet sich gegen die vorinstanzliche Beweiswürdigung, vermag diese aber nicht als willkürlich auszuweisen (vgl. hiervor E. 3). Sie macht geltend, die Vorinstanz habe verneint, dass ein Alternativstandort angeboten worden sei und es sich dabei um eine ernsthafte Alternative gehandelt habe. Dabei sei sie offensichtlich zu Unrecht über die relevanten Aussagen der Herren E._ und G._ hinweggegangen, ohne sich dabei des Sinns und der Tragweite der Aussagen der beiden Herren bewusst zu sein und sich mit diesen auseinanderzusetzen. Die Vorinstanz hat in ihrem Entscheid aber sowohl auf die Aussage von Herrn G._ als auch auf diejenige von Herrn E._ Bezug genommen. Dass die Vorinstanz die Aussagen nicht vollständig widergegeben hat, begründet keine Willkür, zumal nicht ersichtlich ist, dass die Vorinstanz die Aussagen aus dem Zusammenhang gerissen oder ihnen eine offensichtlich unrichtige Bedeutung zugemessen hat.
Die Vorinstanz durfte zusammenfassend, ohne in Willkür zu verfallen, davon ausgehen, dass der Beschwerdegegnerin keine ernsthafte Alternative zur Durchführung des Shisha-Services 2018 auf dem Areal der Beschwerdeführerin angeboten worden ist.
9.
9.1. Da der Vertrag betreffend den Shisha-Service 2018 als gemischter Vertrag zu qualifizieren ist, bei dem auftragsrechtliche Elemente dominieren (vgl. hiervor E. 7.4), beurteilen sich die Rechtsfolgen des Verzichts der Beschwerdeführerin auf die Durchführung des Shisha-Service grundsätzlich nach <ref-law>, sofern dessen Bestimmungen als sachgerecht erscheinen.
9.2. Nach <ref-law> kann ein Auftrag jederzeit widerrufen oder gekündigt werden. Dieses Beendigungsrecht ist zwingend und darf weder vertraglich wegbedungen noch eingeschränkt werden. Es besteht daher auch, wenn ein Auftrag mit einer festen Dauer vereinbart wurde (<ref-ruling> E. 4). Es gilt sowohl für reine Auftragsverhältnisse als auch für gemischte Verträge, für welche hinsichtlich der zeitlichen Bindung der Parteien die Bestimmungen des Auftragsrechts als sachgerecht erscheinen (<ref-ruling> E. 2; <ref-ruling> E. 3d). Auch auf atypische Auftragsverhältnisse findet es Anwendung. Das Bundesgericht hat trotz Kritik der Lehre an dieser Praxis festgehalten (<ref-ruling> E. 2a; Urteile 4A_284/2013 vom 13. Februar 2014 E. 3.5.1; 4A_141/2011 vom 6. Juli 2011 E. 2.2 und 2.3 mit Hinweisen). Für die Frage, ob hinsichtlich der zeitlichen Bindung der Parteien die Bestimmungen des Auftragsrechts als sachgerecht erscheinen, wird vor allem darauf abgestellt, ob nach Art des Vertrages ein Vertrauensverhältnis zwischen den Parteien unerlässlich ist und ihm besondere Bedeutung zukommt (zit. Urteil 4A_284/2013 E. 3.5.1 mit Hinweis).
9.3. Vorliegend ist ein Vertrauensverhältnis zwischen den Parteien bzw. der Beschwerdeführerin und Herrn C._ zu bejahen. Die Leistungen der Beschwerdegegnerin bestanden namentlich auch im Servieren der Shishas und damit im Kontakt zu den Kunden. Es liegt auf der Hand, dass die Beschwerdeführerin als renommiertes Grand Hotel nicht einfach ein beliebiges Unternehmen auf ihrem Areal einen Shisha-Service hätte organisieren lassen. Das Vertragsverhältnis mit der Beschwerdegegnerin, dessen (Teil-) Inhaber Herr C._ ist, bestand namentlich auch aufgrund eines Vertrauensverhältnisses zu Letzterem. Wie die Beschwerdeführerin zudem in anderem Zusammenhang ausführt, ist das Projekt des Shisha-Services 2016 entstanden, weil sie sich anlässlich des Personalfests von den Leistungen von Herrn C._ überzeugt hatte. Daran ändert nichts, dass die Verträge betreffend die Services 2017 und 2018 nicht mehr mit Herrn C._ persönlich, sondern mit der Beschwerdegegnerin abgeschlossen worden sind. Das Vertrauensverhältnis zwischen der Beschwerdeführerin und der Beschwerdegegnerin ergibt sich denn bereits daraus, dass der Service in der Vergangenheit bereits zur Zufriedenheit der Beschwerdeführerin ausgeführt worden ist.
Zusammenfassend ist ein Vertrauensverhältnis zwischen den Parteien zu bejahen, womit die Anwendung der Bestimmungen des Auftragsrechts hinsichtlich der zeitlichen Bindung vorliegend als sachgerecht erscheint.
9.4. <ref-law> sieht vor, dass die Partei, die den Vertrag zur Unzeit widerruft oder kündigt, der anderen Partei den Schaden zu ersetzen hat, der ihr dadurch entsteht. Damit ein Schadenersatzanspruch besteht, müssen zwei Voraussetzungen erfüllt sein. Es dürfen keine ernsthaften Gründe für die Kündigung vorliegen und der Schadenersatz beanspruchenden Partei muss aufgrund von Dispositionen, die sie zur Erfüllung des Auftrags getroffen hat, ein Schaden entstanden sein (<ref-ruling> E. 3b; Urteile 4A_680/2016 und 4A_686/2016 vom 12. Juli 2017 E. 3.1; 4A_36/2013 vom 4. Juni 2013 E. 2.5; 4C.78/2007 vom 9. Januar 2008 E. 5.4). Mit anderen Worten liegt keine Kündigung des Auftrags zur Unzeit vor, wenn der Beauftragte dem Auftraggeber begründeten Anlass zur Auftragsauflösung gegeben hat (BGE <ref-ruling> E. 4c).
Für die Anwendbarkeit von <ref-law> ist es daher insbesondere erforderlich, dass der Beauftrage seinem Vertragspartner keinen ernsthaften Grund zur Kündigung geliefert hat (zit. Urteil 4A_680/2016 und 4A_686/2016 E. 3.1).
9.5. Die Beschwerdeführerin macht in ihrer Beschwerde nicht geltend, dass die Beschwerdegegnerin bzw. Herr C._ ihr ernsthafte Gründe zur kurzfristigen Kündigung des Auftrags (diese erfolgte kurz vor Beginn des Services bzw. während den kurzfristigen Vorbereitungshandlungen) geliefert hätte. Solche Gründe sind im Übrigen auch nicht ersichtlich. Damit ist die Kündigung (d.h. der Verzicht auf die Durchführung des Shisha-Services 2018) seitens der Beschwerdeführerin zur Unzeit erfolgt.
9.6. Bei einer Kündigung zur Unzeit ist - wie erwähnt - nach <ref-law> Schadenersatz geschuldet. Grundsätzlich ist das negative Interesse zu ersetzen. So kann beispielsweise Ersatz verlangt werden für nutzlos gewordene Aufwendungen, die mit Blick auf den Auftrag getätigt wurden, oder für Gewinn, auf den der Beauftragte verzichtet hat, um sich dem Auftrag zu widmen. Das Interesse an der Fortdauer des Auftrags wird durch <ref-law> nicht geschützt (Urteil 4A_196/2020 vom 16. Juli 2020 E. 6.1; zit. Urteil 4A_284/2013 E. 3.6.1 mit Hinweisen).
Gemäss den vorinstanzlichen Feststellungen machte die Beschwerdegegnerin einerseits nutzlos gewordenen Aufwand, andererseits einen Gewinnausfall geltend. Es seien ihr - so die Beschwerdegegnerin - neben dem Gewinnausfall Materialkosten von Fr. 15'500.--, Personalkosten von Fr. 59'388.90 sowie Transportkosten von Fr. 2'000.-- entstanden, welche durch die Beschwerdeführerin zu ersetzen seien. Die Vorinstanz hat aufgrund ihrer Vertragsqualifikation die Beschwerdegegnerin so gestellt, wie wenn der Vertrag beidseitig korrekt erfüllt worden wäre und hat ihr einen (anhand der Zahlen des Vorjahres geschätzten) hypothetischen Umsatzanteil von Fr. 90'000.-- zugesprochen. Da aber vorliegend das negative Vertragsinteresse zu ersetzen ist, wird die Vorinstanz vielmehr zu prüfen haben, ob die Beschwerdegegnerin die geltend gemachten Kosten für Material, Transport und Personal im Sinne eines Vertrauensschadens aufgrund der Kündigung zur Unzeit hinreichend substanziiert und nachgewiesen hat.
10.
Nach dem Gesagten ist die Beschwerde teilweise gutzuheissen, soweit darauf einzutreten ist. Das Urteil des Handelsgerichts des Kantons Bern vom 19. Juli 2021 ist aufzuheben und die Sache zu neuer Entscheidung im Sinne der Erwägungen an dieses zurückzuweisen. Es wird zu prüfen haben, ob die Beschwerdegegnerin ihr negatives Vertragsinteresse (Material-, Transport- und Personalkosten) hinreichend substanziiert und nachgewiesen hat. Bei diesem Ergebnis wird die Beschwerdegegnerin kosten- und entschädigungspflichtig (<ref-law> und Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen, soweit darauf einzutreten ist. Das Urteil des Handelsgerichts des Kantons Bern vom 19. Juli 2021 wird aufgehoben und die Sache zu neuer Entscheidung im Sinne der Erwägungen an dieses zurückgewiesen.
2.
Die Gerichtskosten von Fr. 4'500.-- werden der Beschwerdegegnerin auferlegt.
3.
Die Beschwerdegegnerin hat die Beschwerdeführerin für das bundesgerichtliche Verfahren mit Fr. 5'500.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Bern, Handelsgericht, schriftlich mitgeteilt.
Lausanne, 22. März 2022
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Gross