13
\$\begingroup\$

An interesting puzzle came to me looking at the elevator buttons this morning.

You are required to generate a list of all Braille patterns that fit in a 2x3 grid. Use a hash # to denote a bump and a hyphen - to denote a flat area.

Expected output sample:

#-
--
--

##
--
--

#-
#-
--

(and so on...)

Rules:

  • Your program must separate each pattern by at least one character or line.
  • The patterns may be generated in any order.
  • All patterns, regardless of what the Braille alphabet actually uses, should be produced. The completely blank pattern is optional.
  • Only unique bump patterns should be generated. The following patterns are considered equivilent as the bumps are in an identical arangement. In these cases, use the pattern that is closest to the top-left corner (ie. the first option in this example.)
#-  -#  --  --
#-  -#  #-  -#
--  --  #-  -#

Bonus points if you can make it work for any x by y sized grid. (EDIT: Within reasonable bounds. Up to 4x4 is enough for proof of concept.)

Reading the wiki article, it appears there are 45 patterns (including the blank) that meet this puzzle's rules.

\$\endgroup\$
  • \$\begingroup\$ It's not quite counting, but it's very close. For x x y grids you generate the first 2^(xy) numbers and filter out those which mask to 0 against 2^x - 1 or (2^(xy+1) - 1)/(2^y - 1). \$\endgroup\$ – Peter Taylor Sep 26 '12 at 8:11
6
\$\begingroup\$

GolfScript, 34 32 chars

44,{84+2base(;{'-#'=}/@\n.}%2/n*

Turns out that there are shorter solutions than simply generating all 64 patterns and filtering out the bad ones. In fact, by suitably mapping bits to grid positions, it's possible to map all valid (non-empty) patterns to a consecutive range of numbers, as this program does.

Specifically, the mapping I use is:

5 4
3 1
2 0

where the numbers denote the bit position (starting from the least significant bit 0) mapped to that position in the grid. With this mapping, the valid grids correspond to the numbers 20 to 63 inclusive.

This is almost the same as the obvious mapping obtained by writing out the 6-bit number in binary and adding line breaks between every second bit, except that the bits 1 and 2 are swapped — and indeed, that's exactly how my program computes it. (I also add 64 to the numbers before converting them to binary, and then strip the extra high bit off; that's just to zero-pad the numbers to 6 bits, since GolfScript's base would otherwise not return any leading zeros.)

Ps. Online demo here. (Server seems overloaded lately; if you get a timeout, try again or download the interpreter and test it locally.)

Edit: Managed to save two chars by avoiding unnecessary array building and dumping. Phew!

\$\endgroup\$
  • 2
    \$\begingroup\$ Do you mind adding some details? I'm interested to see how you're defining this mapping. \$\endgroup\$ – ardnew Sep 27 '12 at 2:02
  • \$\begingroup\$ @ardnew: Done, see above. \$\endgroup\$ – Ilmari Karonen Sep 27 '12 at 11:31
  • \$\begingroup\$ I think this is going to change a lot of people's answers. :-) \$\endgroup\$ – Hand-E-Food Sep 27 '12 at 20:41
3
\$\begingroup\$

Mathematica 97

Grid /@ Cases[(#~Partition~2 & /@ Tuples[{"#", "-"}, 6]), x_ /; 
         x[[All, 1]] != {"-", "-", "-"} && x[[1]] != {"-", "-"}]

braille


Blank is not included:

Length[%]

44

N.B. != is a single character in Mathematica.

\$\endgroup\$
3
\$\begingroup\$

C# – 205

class C{static void Main(){var s="---##-##";Action<int,int>W=(i,m)=>{Console.WriteLine(s.Substring((i>>m&3)*2,2));};for(int i=0;i<64;++i){if((i&3)>0&&(i&42)>0){W(i,0);W(i,2);W(i,4);Console.WriteLine();}}}}

Readable version:

class C
{
    static void Main()
    {
        var s = "---##-##"; // all two-bit combinations
        // a function to write one two-bit pattern (one line of a Braille character)
        Action<int,int> W = (i,m) => { Console.WriteLine(s.Substring(((i >> m) & 3) * 2, 2)); };
        // for all possible 6-bit combinations (all possible Braille characters)
        for(int i = 0; i < 64; ++i)
        {
            // filter out forbidden (non-unique) characters
            if ((i & 3) > 0 && (i & 42) > 0)
            {
                // write three rows of the Braille character and an empty line
                W(i,0);
                W(i,2);
                W(i,4);
                Console.WriteLine();
            }
        }
    }
}
\$\endgroup\$
3
\$\begingroup\$

Perl, 71 67 65 char

y/10/#-/,s/../$&
/g,/^#/m&&print
for map{sprintf"%06b
",$_}18..63

Convert int to binary, perform transliteration, and add a newline after every two chars. The /^#/m test eliminates two patterns (20 and 21) that don't have a raised bump in the leftmost column.

General solution, 150 106 103 100 char

Read x and y from command line args. Newlines are significant

y/01/-#/,s/.{$x}/$&
/g,/^#/m*/^.*#/&&print
for map{sprintf"%0*b
",$x*$y,$_-1}1..1<<($y=pop)*($x=pop)

Iterate over 0..2xy like before, converting each int to binary, substituting - and # for 0 and 1, and inserting a newline after every $x characters.

/^#/m tests that there is a raised bump in the leftmost column, and /^.*#/ tests that there is a raised bump in the top row. Only the patterns that pass both tests are printed.

\$\endgroup\$
  • \$\begingroup\$ How does this account for the invalid combinations? \$\endgroup\$ – scleaver Sep 26 '12 at 20:11
  • \$\begingroup\$ Because the loop excludes the patterns for 1..17, 20, and 21. \$\endgroup\$ – mob Sep 26 '12 at 20:40
2
\$\begingroup\$

Python, 120 118 113 95 118

for j in range(256):
    if j/4&48and j/4&42:print''.join('_#'[int(c)]for c in bin(j/4)[2:].rjust(6,'0'))[j%4*2:j%4*2+2]

Edit: used Winston Ewert suggestion and added x by y grid solution

Edit: I somehow missed the last constraint about uniqueness. This script generates all the possible sequences, not just the 45.

Edit: Back up to 118 but now correct

\$\endgroup\$
  • \$\begingroup\$ Replace ['#','-'] with '#-' \$\endgroup\$ – Winston Ewert Sep 26 '12 at 15:37
2
\$\begingroup\$

J, 35 33 chars

3 2$"1'-#'{~(2 A.i.6){"1#:20+i.44

Uses the approach Ilmari Karonen came up with in their Golfscript solution. However, since the J verb #: (antibase) stores the bits (or, well, digits in the generic case) in a list, we need to index it from the left instead of right (i.e. index 0 is the leftmost, highest bit).

The solution is rather straightforward: 20+i.44 gives a list of the numbers 20..63, inclusive. #: takes the antibase-2 of each element in this list, and thus produces a list of bitpatterns for each number in that range. { selects (basically reorders) the bits into the right pattern, and then { is used again in order to use the digits as indices in the string '-#' in order to prepare the output. Finally, we arrange each entry into a 2-by-3 rectangle with $ (shape).


3 2$"1'-#'{~(2 A.i.6){"1#:20+i.44      N.B. use A. (anagram) to generate the right permutation

3 2$"1'-#'{~0 1 2 4 3 5{"1#:20+i.44

\$\endgroup\$
  • \$\begingroup\$ Does anyone know how something like (0 2 3 ,. 1 4 5) { #: 44 could be tweaked to work with a list of numbers rather than a single number? Would probably shave off a few more chars. \$\endgroup\$ – FireFly Sep 27 '12 at 22:29
1
\$\begingroup\$

Python - 121 112

blank is not included

from itertools import*
print'\n'.join('%s%s\n'*3%b for(b,n)in zip(product(*['_#']*6),range(64))if n&48and n&42)
\$\endgroup\$
  • \$\begingroup\$ you can trim that product up with '_#',repeat=6 -> *['_#']*6 \$\endgroup\$ – boothby Sep 28 '12 at 1:43
  • \$\begingroup\$ @boothby: thanks. Also, b is already a tuple, so no need to convert it :) \$\endgroup\$ – quasimodo Sep 29 '12 at 20:32

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.