Cube digit pairs

2016-05-21

Problem 090: Cube digit pairs

Description:

Each of the six faces on a cube has a different digit (0 to 9) written on it; the same is done to a second cube. By placing the two cubes side-by-side in different positions we can form a variety of 2-digit numbers.

For example, the square number 64 could be formed:

  +-------+     +-------+
 /       /|    /       /|
+-------+ |   +-------+ |
|       | |   |       | |
|   6   | +   |   4   | +
|       |/    |       |/
+-------+     +-------+

In fact, by carefully choosing the digits on both cubes it is possible to display all of the square numbers below one-hundred: 01, 04, 09, 16, 25, 36, 49, 64, and 81.

For example, one way this can be achieved is by placing {0, 5, 6, 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other cube.

However, for this problem we shall allow the 6 or 9 to be turned upside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 6, 7} allows for all nine square numbers to be displayed; otherwise it would be impossible to obtain 09.

In determining a distinct arrangement we are interested in the digits on each cube, not the order.

{1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}

But because we are allowing 6 and 9 to be reversed, the two distinct sets in the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9} for the purpose of forming 2-digit numbers.

How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?

Solution:

v X_XXOO #########                v6$<                 > #g #0 #+ #8 #: #:v#<>v
2 X ##########v 2+4\1p22+g22!g2+4:< _^#-9:%+55*:p1+4\1p12+g12!g1+4:/+55*::_v 1g
9 X ##########v1+4\1p12+g12!g1+4:<   _v#-9:%+55*:p2+4\1p22+g22!g2+4:/+55*::< 26
3  C          >p                #^6$ #<     #v      >#      #<           1-:|$`
*>020p8>:0\9+0p:#v_$021p022p9>:0\4+1p:0\4+2p:#v_$55+^vg0+9p0+9\!g0+9::::<   >^2
+p     ^-1       <^00       <^-1              <   v$$_!#v_1- #  #v #! #+^#`6g2<
33                          ^                     <     >$   ^  v_8     ^
>^                                      @.g02< >:1-\#v_$         >     8^
              >:0\4+1p  >:1-\#v_$     v        |g1+4:<9_v#-g12 6<
               vp1+4\1:<|g1+4:<9_v#-g125p1+4\1:<        2>       ^
              ^0       ^<      >#1>:0\4+1p     >:1-\#^_$         ^
              $#               ^  $$  <                 #$
            >#^_1-             :!#^_1-                :!#^_@
            !  >                 >                      >22g6- #v _v
  >v        ^:                   ^#                  < >:1-\#v_$  #2v
  p                   >:0\4+2p  >:1-\#v_$     v        |g2+4:<9<< > v
  2                    vp2+4\1:<|g2+4:<9_v#-g225p2+4\1:< v          <   >g1+20pv
  +                   ^0       ^<      >#1>:0\4+2p   # >:1-\#^_$  ^     ^02p+g<
  9                   $#               ^ #$$  <      ^  $<        $# >%\"P"/33^
>#4>               :!#^_1-             :!#^_1-                 :!#^_@^"P":\g03<
  0 v+64p04+g1+94!g1+64<   >#           #<           #v#          #<     v     #
  p >2g!49+2g+50pv>40g50g+#^_046+1p149+1p046+2p149+2pv>146+1p049+1p146+2p 049vv<
^<^2+641< v0p2+9$0 41p2+640_v#!g05<p1+940p1+641< v p 2#1+941p1+640_v#!g04<p2+<#
v       $#        $#      <   >v          v    $#     $#           #     <  > ^
>  1+:!#^_1-   :!#^_1-   #^              #< :!#^_1-:!#^_@>33g+g:30g-#v_$$^     <
^        -#                < 9   ^                                < >57*- !|  #
          >      >060p070p9v<           9p070p060<   <   ^/"P"\%"P"::<  v   <
                v*2g06g1+4:<  $v                   <              >\v^-1<*" ("<#
                >+60p:1-\  #^_^>:4+2g70g2*+70p:1-\#^_$70g60g:70g`#^_>48*:**+30p^
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################

Start

Pause

Reset

Download

Output:

Stack: (0)

Explanation:

We have nine square numbers that need to be represented. For each number we can either use dice one for the first digit and dice two for the second or the other way around. Together there are 2^9 (=512) possibilities. In our program we iterate through them all (a simple binary counter at program position [9,0]).

In each turn we remember which numbers would need to be written on the first dice and which on the second one (we have two boolean arrays at [4,1] and [4,2]). If one dice needs more than six numbers on it we can directly throw this combination away and go on with the next number in our binary counter.

It's important that in this phase we have no nines. Every nine is replaced with a six (so we use 3*3 = 09 and 7*7 = 46) The nines are later taken into account.

Now most of the time one or both dices have less than six digits on it (sometimes even only four). We iterate now through all possible combinations of six digits with our found set as a basis. (So if one dice has 5 digits and the other one 4 we generate an additional 150 combinations (5*5*6).

Then in the last step we look at each dice and see if it contains a six and no nine. If this is the case we generate another combination where the six and the nine is exchanged. (Because we do this for each dice individually we can for each given combination possibly generate four new ones (original, D1 exchanged, D2 exchanged, both exchanged)).

Now we have every possible combinations that fits our initial condition. To weed out all the duplicates we generate a hash from the combination and remember previously found values in an 80x16 big hashmap (originally I had the map way bigger, but after my first successful run I could shrink the size to a more fitting value).

The hash is simply the binary representation of D1 and D2 concatenated (one for "has this digit", zero for "does not have this digit"). Because the order of the dices is irrelevant in our result we ignore it also in our hash and always use the dice with the smaller hash value as the lower bits of the total hash (this way HASH(D1,D2) == HASH(D2,D1)).

One problem of writing this program (except the metric fuck-ton of code all this needs, seriously I filled a 80x30 grid only with logic, there is more raw code than space for the 1280-elements hashmap) were the filling methods.

In my C# test program I had three functions:

PadLeft fills the left digit up to six digits with all possible values
PadRight fills the right digit up to six digits with all possible values
PadNine exchanges 6 with 9 in the left and right digit to generate all possible combinations
Output Test if a is already in the hashmap, if not increments the counter

Now the function PadLeft() calls PadRight() which calls PadNine(), which calls Output(). Each at three to four different places. So in my befunge program I needed to do the same thing every sane procedural language does: Remember the back jump address, so after PadNine() is called we know where in PadRight() we have to continue the program flow.

Unfortunately this is in befunge not really good to write and leads to a lot of boilerplate code, but it's still better than writing the Output function twenty-seven times in different places.

A last note: This is the first program where I put the big data structures below the actual code. It's nice to have all the program logic at the top of the file, but every time I address something down there the constants for the Y value take more space. This is also the reason my variables are always in the top left corner, there I can address them with only three commands (xyg bzw xyp) as long as x and y are below ten. So I think it's not too bad to have the data below the code but for the future I will keep my old organization.