Zähle die ASCII-Hamantaschen!

18

Heute ist Purim, auf dem man dreieckige Kekse mit einer Füllung namens hamantaschen (Singular: hamantasch ) verteilen soll . Ein anderer Brauch ist es, viel zu trinken.

Ich bin nicht der perfekteste Bäcker ... Ich habe so viele unregelmäßig große Hamantaschen zu verteilen und so viele Freunde, denen ich sie geben kann! Wenn ich Ihnen ein Bild von meinen Keksen schicke, können Sie mir sagen, wie viele ich in welcher Größe und mit welcher Füllung habe? Aber weil es Purim ist und ich zu betrunken bin, um viel Code zu lesen, muss es so kleiner Code sein, wie Sie machen können.

Definitionen

Größe

Ein Hamantasch kann beliebig groß sein . Der kleinste Hamantasch ist Größe 1 und sieht so aus:

/\  --
--  \/

Manchmal können sich mehrere Hamantaschen überlappen . Die folgende Form zählt als zwei Hamantaschen (eine Größe 1, eine Größe 2):

 /\
/\ \
----

Einige Hamantaschen haben Füllung . Dies wird angezeigt, indem das gesamte Leerzeichen mit einem Zeichen gefüllt wird. Beachten Sie, dass Hamantaschen der Größe 1 nicht gefüllt werden können.

Wir nennen hamantaschen basierend auf Füllung und Größe. Verwenden wir das Format <filling> <size>und wenn es nicht ausgefüllt ist - <size>(Sie können ein Leerzeichen anstelle eines verwenden -, aber das gefällt Markdown nicht).

Hier sind a . 2, a . 4und a - 3:

          /\
         /./\
 ----   /./  \
 \../  /./    \
  \/   --------

Dies sind a @ 3, a . 2und a - 4:

          /\
         / /\
  /\    / /@@\
 /..\  / /@@@@\
 ----  --------

Hier ist etwas schwieriger. Sehen Sie, wie das & 2weniger Füllung hat, als Sie aufgrund der Neigung von der Überlappung erwartet haben - 3? Es hat ein - 1, & 2ein - 3und ein & 4:

--------
\   \/&/
 \  /\/
  \/&/
   \/

Eingang

Sie erhalten eine Textdatei oder eine einzelne Zeichenfolge von hamantaschen (optional abschließende Zeilenumbrüche und optional gepolsterte abschließende Leerzeichen, um gerade zu sein).

Grenzen

  • Sie können erwarten, dass die Zeichenfolge gültig ist - das heißt, dass jedes Nicht-Leerzeichen zu einem köstlich süßen Hamantasch beiträgt (warum Teig verschwenden?).
  • Sie können auch erwarten, dass es richtig gefüllt ist oder nicht - das heißt, dass jedes hamantasch vollständig mit einem konsistenten ASCII-Zeichen gefüllt wird - ASCII 32 für ungefüllt oder alles 32..127 für gefüllt (außer /, \und -).
  • Diese hamantaschen sind nicht im 3er Raum gestapelt . Alles /und \wird sichtbar sein. Alle -, die nicht von blockiert werden /und \sichtbar sein werden. Die Befüllung erfolgt zum Schluss.
  • Bei allen Hamantaschen ist mindestens die Hälfte der horizontalen Linie (Aufrundung) sichtbar.
  • Jeder zusammenhängende Füllblock füllt nur den kleinsten Hamantasch , der ihn umgibt.

Ausgabe

Geben Sie eine Liste mit "Namen" aller Hamantaschen zurück, die die oben genannten Kriterien erfüllen. Die Ausgabe kann in einer beliebigen Form erfolgen (ein String, ein Hash, ein stdout usw.).

Testfälle

Testfall Nr. 1

Eingang 1:

          /\
         / /\
  /\    / /@@\
 /..\  / /@@@@\
 ----  --------
    /\
   /**\
  /*/\*\
 /*/..\*\
 --------

Ausgang 1:

. 2
. 2
- 4
@ 3
* 4

Testfall Nr. 2

Eingang 2:

  /\----
 /\/\*\/
/ /\d\/
------

Ausgang 2:

- 3
- 2
d 2
- 1    
* 2
- 1

Test Nr. 3

Eingang 3:

----
\/\/
/\/\  /\
---- /::\
     ----

Ausgang 3:

- 1
- 1
- 2
- 1
- 1
- 2
: 2

Test Nr. 4

Eingang 4:

 /\/\
/ /\$\
-/--/\\
 --/--\
  /xxx/\
 /xxx/##\
 ---/----\
   /      \
   -------- 

Ausgang 4:

$ 2
x 4
- 3
- 2
- 4
- 1
- 1
# 2

Ungültiger Testfall Nr. 5

Eingang:

/\
\/

Ausgabe:

Sie brauchen damit nicht umzugehen.

Nicht dieser Charles
quelle
Wie wäre es mit einem Testfall, bei dem sich Hamentaschen überlappen, aber nicht die gleiche horizontale Linie haben? Man kann sogar die horizontale Linie eines anderen blockieren.
stolzer Haskeller
@ proudhaskeller Ok, fertig. Und ich habe dies nur in den Text eingefügt, dies ist ein 2-Leerzeichen. Wir werden immer sehen alle /und \ , und -wird immer Trumpf Füllung.
Nicht dass Charles
2
@EasterlyIrk Es gibt noch andere wichtige Dinge - das Buch Esther lesen (und die Bösen anfeuern), den Armen etwas geben - und weniger grundlegende Dinge wie das Anziehen von Kostümen.
Nicht dass Charles
1
wieder relevant gemacht!
Downrep_nation
1
Basierend auf einer anfänglichen Spalte von Null sind alle Ihre Scheitelpunktspalten außer (1,0)um deaktiviert +1. Trotzdem weiß ich, was du meinst, und ich bin anderer Meinung. Welche Anzeige gibt es, (2, 2)die die obere Mitte von a - 2und nicht nur die obere rechte und linke der beiden oberen - 1s ist? Keine, die ich sehen kann. Und die gleiche Logik gilt für (3, 2). Es sei denn, Sie möchten eine Regel hinzufügen, um ein Maximum an möglichen Hamantaschen anzunehmen ...
Michael Plotke

Antworten:

4

C #, 496 452 Bytes

Bearbeiten: habe einen Fehler gefunden, bei dem die Grenzen überprüft wurden ... aber auch eine Menge Bytes entfernt wurden, die gezwungen waren, meinen eigenen Code zu verstehen. Das Aufrollen der lokalen Funktion hat ein wenig geholfen und den C # 7-spezifischen Code entfernt. Diese Frage hat sehr viel Spaß gemacht.

using C=System.Console;class P{static void Main(){string D="",L;int W=0,H=0,z=0,d,q,c,j,b;for(;(L=C.ReadLine())!=null;H+=W=L.Length)D+=L;var B=new int[H];for(d=W;(d=-d)>0||++z<H*H;)for(c=1,q=z%H;c<=z/H&q%W+c<W&q>=d&q<H+d&&D[q]==(d>0?92:47)&D[j=q+c]==(d<0?92:47);q-=d+1,c+=2){for(b=0;j>q;)b+=D[--j-d]==45?2:0;for(char h='-',e;c==z/H&b>c;C.WriteLine(h+" "+c/2))for(b=c++;b>1;j=q+=d+1,b-=2)for(;j<q+b;)B[j]=h=B[j]<1&h==45&(e=D[j++])!=47&e!=92&e>32?e:h;}}}

Probieren Sie es online

Komplettes Programm, erwartet eine mit Leerzeichen aufgefüllte Eingabe für den Standardeingang, Ausgänge für den Standardausgang. Die Ausgabe ist ein Eintrag pro Zeile mit nachfolgendem Zeilenvorschub. Cookies werden in aufsteigender Reihenfolge ausgegeben, ganz oben links. Es hat eine Weile gedauert, bis ich die Regeln verstanden habe, aber ich glaube, es hat alle Beispiele bestanden.

Dies funktioniert, indem das gesamte Raster wiederholt nach gültigen Hamantaschen durchsucht wird, wobei die zulässige Größe erhöht wird. Für jede Zelle, prüft sie nach oben und unten, nach dem \und /auf beiden Seiten so weit wie möglich. Wenn es feststellt, dass die nächste Zeile viele enthält -und die aktuelle Größe die zulässige Größe ist, wird die Füllung bestimmt und der Eintrag ausgedruckt.

Die Füllung wird gefunden, indem der gesamte Bereich des Kekses auf der Suche nach einer "unbenutzten" Zelle durchsucht wird. Wenn eine nicht verwendete Zelle gefunden wird, wird sie als verwendet markiert (da wir die zulässige Größe erhöhen, wissen wir, dass wir das kleinste Cookie sind, das sie enthält), und wir zeichnen die Füllung auf.

Formatierter und kommentierter Code:

using C=System.Console;

class P
{
    static void Main()
    {
        //   32
        // - 45
        // / 47
        // \ 92
        // range 32..127 (no mod for you)

        string D="", // the whole map
            L; // initally each line of the map, later each line of output

        int W=0, // width
            H=0, // length (width * height)
            z=0, // search tracker
            d, // check direction (this is backwards (1 byte saving!))
            q, // check tracker
            c, // counter (truely, this is the distance from the right to the left)
            //M, // c max (now inlined as z/H)
            j, // horiontal tracker
            b; // - count, and reverse counter

        // read map and width
        for(;(L=C.ReadLine())!=null; // read a line, while we can
                H+=W=L.Length) // record the width, and increment height
            D+=L; // add the line to the map

        var B=new int[H]; // whether this filling has been used already (0 -> false, >0 -> true)

        for(d=W; // init direction
            (d=-d)>0|| // swap direction, else increment z (this allows us to run the check for the same z twice with opposite direction)
            ++z<H*H; // for all M, for all q (z<H -> M=z/H=0 -> no valid cookies, so we can safetly skip them)
            )
            for(//M=z/H, // c allow (now inlined)
                c=1, // reset counter
                q=z%H; // note position
                c<=z/H& // counter check
                // no need for a left check: if we run off the left end, then the right check will necessarily fail
                q%W+c<W& // right check
                q>=d& // high check
                q<H+d&& // low check (short-circuit lookups)
                D[q]==(d>0?92:47)&D[j=q+c]==(d<0?92:47); // /\ or \/ check, and set j=q+c
                    q-=d+1, // move left tracker
                    c+=2) // increase counter (move right tracker)
            {
                // count the number of '-' into b
                for(b=0; // zero b
                    j>q; // for each element in the row below
                        ) // empty
                    b+=D[--j-d]==45?2:0; // add 2 to b if we tap a '-'

                // j = q

                // check valid before looking up cHaracter (so we don't mark unused stuff as taken)
                // if we are at the current max count, and we have enough -, then we are valid and should be commited
                for( // this runs either one or zero times, we only have a for here (rather than an if) so we can ditch a pair of braces
                    char h='-', // default filling
                         e; // filling we are considering
                    c==z/H&b>c;
                        C.WriteLine(h+" "+c/2)) // print filling and count
                    // continuously compute character
                    for(b=c++; // count b backwards, starting from c (add 1 to c so we can /2 in print)
                        b>1;j=q+=d+1,b-=2) // count q backwards toward z%H (where q came from), and b backwards toward 1 (for each row)
                        for(;j<q+b;) // for each cell in row
                            B[j]= // mark cell as taken (h,e > 0)
                            h= // record filling
                                B[j]<1& // check cell not already used
                                h==45& // '-'
                                (e=D[j++])!=47& // '/'
                                e!=92& // '\'
                                e>32 // ' '
                                ?e:h; // take first filling we can
                    // c runs out after this (exists both loops), so no need to action
            }
    }
}

Ausgänge für die 4 Testfälle:

testcase #1
. 2
. 2
@ 3
- 4
* 4

testcase #2
- 1
- 1
- 2
d 2
* 2
- 3

testcase #3
- 1
- 1
- 1
- 1
- 2
- 2
: 2

testcase #4
- 1
- 1
- 2
$ 2
# 2
- 3
x 4
- 4
VisualMelon
quelle
Ich bin erstaunt, wie kompakt das in C # ist! Gut gemacht!
Nicht dass Charles
Die einzig gültige Antwort! Ich habe etwas, das beinahe funktioniert, aber ein paar Fehler aufweist (aber ich würde mich sowieso nicht als Sieger festlegen)
Nicht dass Charles am