18
\$\begingroup\$

Today is Purim on which one custom is to give out triangle-shaped cookies with filling called hamantaschen (singular: hamantasch). Another custom is to drink heavily.

I'm not the most perfect baker.... I have so many irregularly-sized hamantaschen to give out and so many friends to give them to! If I sent you a picture of my cookies, can you tell me how many I have of which size and filling? But because it's Purim and I'm too drunk to read much code, it needs to be as small code as you can make.

Definitions

Size

A hamantasch can be any size. The smallest hamantasch is size 1 and looks like these:

/\  --
--  \/

Sometimes, multiple hamantaschen can overlap. The shape below counts as two hamantaschen (one size 1, one size 2):

 /\
/\ \
----

Some hamantaschen have filling. This will be indicated by filling all whitespace inside with a character. Note that size 1 hamantaschen cannot have filling.

We will name hamantaschen based on filling and size. Let's use the format <filling> <size> and if unfilled, - <size> (you can use a space instead of a -, but markdown doesn't like that).

Here are a . 2, a . 4, and a - 3:

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

These are a @ 3, a . 2 and a - 4:

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

Here's something more difficult. See how the & 2 has less filling than you've come to expect due to the slant from the overlapping - 3? It has a - 1, a & 2 a - 3 and a & 4:

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

Input

You will be given a text file or single string of hamantaschen (optional trailing newline and optionally padded trailing whitespace to be even).

Limits

  • You can expect the string to be valid - that is, every non-whitespace character contributes to a deliciously sweet hamantasch (why waste dough?).
  • You can also expect it to be properly filled or not - that is, each hamantasch it will be entirely filled with a consistent ASCII character - ASCII 32 for unfilled, or anything 32..127 for filled (excluding /, \ and -).
  • These hamantaschen are not stacked in 3-space. All / and \ will be visible. All - that are not blocked by / and \ will be visible. Filling comes very last.
  • All hamantaschen will have at least half of their horizontal line (rounding up) visible.
  • Any contiguous block of filling only fills the smallest hamantasch that surrounds it.

Output

Return a list of "names" of all the hamantaschen that can be found meeting the above criteria. The output can be in whatever form you'd like (a string, a hash, stdout, etc).

Test cases

Test case #1

Input #1:

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

Output #1:

. 2
. 2
- 4
@ 3
* 4

Test Case #2

Input #2:

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

Output #2:

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

Test #3

Input #3:

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

Output #3:

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

Test #4

Input #4:

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

Output #4:

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

Invalid Test Case #5

Input:

/\
\/

Output:

You do not need to handle this.

\$\endgroup\$
  • \$\begingroup\$ How about a test case in which hamentaschen are overlapping but do not have the same horizontal line? One may even block another's horizontal line. \$\endgroup\$ – proud haskeller Mar 24 '16 at 21:56
  • \$\begingroup\$ @proudhaskeller Ok, done. However, and I just put this in the text, this is 2-space. We will always see all / and \ , and - will always trump filling. \$\endgroup\$ – Not that Charles Mar 24 '16 at 22:17
  • 2
    \$\begingroup\$ @EasterlyIrk There are other important bits, too - reading the Book of Esther (and booing at the bad guys), giving to the poor - and less foundational things like dressing in costume. \$\endgroup\$ – Not that Charles Mar 28 '16 at 15:28
  • 1
    \$\begingroup\$ made relevant again! \$\endgroup\$ – downrep_nation Mar 8 '17 at 6:53
  • 1
    \$\begingroup\$ Based on an initial column of zero all your vertex columns, except (1,0), are off by +1. Still, I know what you mean, and I disagree. What indication is there that (2, 2) is the top center of a - 2 and not just the top right and left of the two upper - 1s? None that I can see. And the same logic applies to (3, 2). Unless you want to add a rule to assume maximum possible hamantaschen... \$\endgroup\$ – Michael Plotke Mar 22 '17 at 20:28
4
\$\begingroup\$

C#, 496 452 bytes

Edit: found a bug with bounds checking... but also striped a load of bytes having been forced to understand my own code. Unrolling the local function helped a bit, and removed the C# 7 specific code. This question has been a lot of fun.

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;}}}

Try it Online

Complete program, expects space-padded input to standard in, outputs to standard out. The output is one entry per line, with trailing line feed. Cookies are outputted in increasing size order, upper-left most first. It took me a good while to understand the rules, but I think it passes all the examples provided.

It works by repeatedly searching the entire grid for valid Hamantaschen, incrementing the 'allowed' size. For each cell, it checks up and down, following the \ and / on either side as far as it can. If it notices that the next row has lots of -, and the current size is the 'allowed' size, then it determines the filling and prints out the entry.

The filling is found by exploring the entire space of the cookie, looking for an 'unused' cell. When an unused cell is found, it is marked as used (since we increase the allowed size, we know we are the smallest cookie that contains it), and we record the filling.

Formatted and commented 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
            }
    }
}

Outputs for the 4 test cases:

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
\$\endgroup\$
  • \$\begingroup\$ I'm amazed at how compact this is in C#! Well done! \$\endgroup\$ – Not that Charles Mar 27 '17 at 13:48
  • \$\begingroup\$ The only valid answer! I have something that's nearly functional, but has a few errors (but I wouldn't set myself as winner anyway) \$\endgroup\$ – Not that Charles Mar 30 '17 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.