Recognise a Digit from a Positional Encoding

Question

Starting an the origin on an infinite grid, you follow a predetermined path going up (U), down (D), left (L), or right (R). You paint every square you visit, including the square you started at and the square you finish at. Using this method, we can paint the number six using the instructions RRDDLLUUUURR:

The origin is shown as a green star. We call this a positional encoding of the number six. Note that a positional encoding is not unique; the encoding LLUURRDDUULLUURR also encodes the number six with some redundancy:

Note that if you visit a square you've already painted in your path, you leave it as is.

Challenge

Given a positional encoding of one of the digits zero through nine taken as a string, output which digit it encodes.

All digits will be encoded in a \$3\times5\$ format as follows:

#     ###   ###   # #   ### 
#       #     #   # #   #   
#     ###   ###   ###   ### 
#     #       #     #     # 
#     ###   ###     #   ### 

###   ###   ###   ###   ###
#       #   # #   # #   # #
###     #   ###   ###   # #
# #     #   # #     #   # #
###     #   ###   ###   ###

Note that:

• The positional encoding given will always map to one of the ten digits given above exactly; the input string is guaranteed to be valid.
• The digit will never be mirrored or rotated.
• There may be redundancy in the encoding (eg LR).
• The square you start at is always painted.

Test Cases

Input                -> Output
DDDD                 -> 1
UUUU                 -> 1
DDUDDUDD             -> 1
DDUUUUDDUUDD         -> 1
LRRDDLLDDRLRR        -> 2
LDDRRLLUURRUULL      -> 2
RRDDLLRRDDLL         -> 3
LLRRUULLRLRRUUDULL   -> 3
LUUDDRRUUDDDD        -> 4
DDLLUUDDRRDD         -> 4
LLDDRRDDLL           -> 5
DLLRRUULLUURRLLRR    -> 5
RRDDLLUUUURR         -> 6
LLUURRDDUULLUURR     -> 6
RRDDLLUURRDDLLUUUURR -> 6
RRDDDD               -> 7
LLRRDDDD             -> 7
LUURRDDDDLLU         -> 8
RUULLUURRDDLLDD      -> 8
RRDDLLUURRDDDDLL     -> 9
DUDLRLLRRUULLRRUULLD -> 9
RRUUUULLDDD          -> 0
UUUUDDDDRRUUUULRDDDD -> 0

Also in list form:

[['DDDD', 1], ['UUUU', 1], ['DDUDDUDD', 1], ['DDUUUUDDUUDD', 1], ['LRRDDLLDDRLRR', 2], ['LDDRRLLUURRUULL', 2], ['RRDDLLRRDDLL', 3], ['LLRRUULLRLRRUUDULL', 3], ['LUUDDRRUUDDDD', 4], ['DDLLUUDDRRDD', 4], ['LLDDRRDDLL', 5], ['DLLRRUULLUURRLLRR', 5], ['RRDDLLUUUURR', 6], ['LLUURRDDUULLUURR', 6], ['RRDDLLUURRDDLLUUUURR', 6], ['RRDDDD', 7], ['LLRRDDDD', 7], ['LUURRDDDDLLU', 8], ['RUULLUURRDDLLDD', 8], ['RRDDLLUURRDDDDLL', 9], ['DUDLRLLRRUULLRRUULLD', 9], ['RRUUUULLDDD', 0], ['UUUUDDDDRRUUUULRDDDD', 0]]

Scoring

Shortest code in bytes wins.

Answer 1

JavaScript (Node.js),  89 ... 77  71 bytes

Saved 6 bytes by using the modulo chain provided by @KjetilS.

s=>Buffer(s).map(c=>o|=p*=4**(c%5)/8,o=p=4**8)|(o/=o&-o)*321%3081%53%11

Try it online!

How?

We take the ASCII code \$c\$ of the direction character modulo \$5\$ to map it to an index in \$\{0,1,2,3\}\$.

For each direction, we update a bit mask \$p\$ by shifting it by a specific amount and mark the bits that are visited in another bit mask \$o\$.

 char. | ASCII | mod 5 | shift
-------+-------+-------+-------
  'U'  |   85  |   0   | >> 3
  'L'  |   76  |   1   | >> 1
  'R'  |   82  |   2   | << 1
  'D'  |   68  |   3   | << 3

Conveniently, the shift is equivalent to multiply \$p\$ by:

$$\frac{4^{(c\bmod 5)}}{8}$$

We start with both \$p\$ and \$o\$ set to \$4^8=2^{16}\$. This value is safe because we will never right-shift by more than \$4\times 3 + 2\times 1=14\$ (e.g. with "UUUULL", which draws a \$7\$, or any other path going from the bottom-right to the top-left corner). Likewise, we will never left-shift by more than \$14\$ and never exceed \$2^{30}\$. So, both \$p\$ and \$o\$ remain 32-bit values.

Because we don't know which cell in the digit was our starting point, we normalize the final value of \$o\$ by removing all trailing zeros:

o /= o & -o

We end up with a unique 15-bit key identifying the digit.

 digit |   binary mask   | decimal
-------+-----------------+---------
   0   | 111101101101111 |  31599
   1   | 001001001001001 |   4681
   2   | 111001111100111 |  29671
   3   | 111100111100111 |  31207
   4   | 100100111101101 |  18925
   5   | 111100111001111 |  31183
   6   | 111101111001111 |  31695
   7   | 100100100100111 |  18727
   8   | 111101111101111 |  31727
   9   | 111100111101111 |  31215

It can be seen as a binary representation of the digit shape rotated by 180°. For instance:

                       100    111
                       100    001
100 100 100 100 111 -> 100 -> 001 -> "7"
                       100    001
                       111    001

We apply the following function to turn it into the expected digit:

$$f(n)=\big(((n\times 321)\bmod 3081)\bmod 53\big)\bmod 11$$

Answer 2

Charcoal, 70 65 63 60 58 43 38 bytes

Ｆ⁺ＳR«ＵＭＫＶＩΣκ✳ι1»≔↨ＫＡ²θ⎚§”←＆Φ⁴.º!Ｈ”﹪θ⁹⁴

Try it online! Link is to verbose version of code. Explanation:

Ｆ⁺ＳR«

Append a dummy instruction to the input to ensure that both ends get drawn, and loop over the instructions.

ＵＭＫＶＩΣκ

Pad the neighbourhood of each cell. (This is because PeekAll() only returns the drawn cells and not their positions, so it would be impossible to distinguish between the groups 69, 08 and 235.) Each orthogonally adjacent cell is replaced with its digital sum, which is 1 for cells on the path and 0 for all other cells (whether new or previously padded).

✳ι1»

Draw the path using literal 1s and move in the appropriate direction.

≔↨ＫＡ²θ

Record which of the cells were drawn and which were just padding, and interpret that as if it was binary.

⎚

Clear the canvas.

§”←＆Φ⁴.º!Ｈ”﹪θ⁹⁴

Cyclically index the compressed lookup table 56 0817 934 2 (where the spaces are don't care values) with the base 2 number captured above modulo 94 and output the result.

It's possible to shrink the uncompressed lookup table to 11 bytes 0473125869_ by taking the number modulo 378 for the same byte count, or to 10 bytes 8739651204 by taking the number modulo 4207, but this ends up actually a byte longer after compression, so instead if you capture the number in base 5 rather than base 2, then by taking it modulo 579 you can cyclically index the result in the table 7269105348 also for the same byte count.

Example digit decoding: Drawing RRDDDD results in the following canvas:

 000
01110
 0010
  010
  010
  010
   0

Reading these gives 0000111000100100100100 which is 231716 in binary, then reducing modulo 94 gives 6, which (cyclically) indexed into the lookup table produces 7, the desired result.

Answer 3

J, ^{75 65 59} 55 bytes

-10 thanks to Jonah!

-6 thanks to Bubbler!

-4 thanks to FrownyFrog!

Identifies the numbers by their bit mask of the following positions:

#0# 
1 2 
#3# 
4 # 
###

So 8 would be 11111, and 7 would be 10100

'=)76.:;4?'i.4 u:2#.1,i.@5(e.>./-:@->:)0+/\@,3-2*5|3&u:

Try it online!

How it works

3-2*5|3&u:

Map DRLU to -3 -1 1 3. (Thanks to Arnauld!)

(>./…-…)0+/\@,

Append 0 (the drawn starting tile), and fold every prefix to absolute indices, e.g. 0 1 2 5 8 11 14. As an index might be negative, get the highest number and subtract it from every index.

i.@5(e.…-:@…>:)

Checks which of the indices 1 3 5 7 9 are set: 1 0 1 0 0.

'=)76.:;4?'i.4 u:2#.1,

The bit masks with a 1 prepended (so the numbers neatly fit into ASCII) is looked up in the table.

Answer 4

Jelly, 35 34 32 bytes

O%15Żı*ÄÆiḞ_Ṃ$‘ŒṬFḄ%29ị“ẆA⁻R§’D¤

Try it online!

-1 thanks to Zgarb fixing my brainfart

-2 thanks to Jonathan Allan reminding me of Ż and rearranging to remove a space

I have no idea what I'm doing... Going all the way through Ḟ‘ŒṬ feels like it may not be necessary with a smart choice of hash function, and it's not a terrible idea to just try translating Arnauld's JS answer outright. I've tried quite a few dumber hash functions, and they've all gotten tripped up on 2 versus 5, but maybe if I keep using base conversion...

       Ä          Cumulative sums of
     ı*           sqrt(-1) to the (vectorized) power of
O                 the codepoints of the input
 %15              mod 15 (U,D,L,R -> 10,8,1,7 ≡ 2,0,1,3 mod 4)
    Ż             with 0 prepended.
        Æi        a + bi -> [a, b],
          Ḟ       convert the floats to integers,
           _Ṃ$    and subtract the minimum.

‘                     Increment so that all indices are positive,
 ŒṬ                   then convert them to a multidimensional Boolean array,
   F                  flatten it,
    Ḅ                 convert from binary,
     %29              mod 29,
        ị             modular index into
                D¤    the decimal digits of
         “ẆA⁻R§’      813540020976.

Answer 5

Perl 5, 96 84 bytes

$s=0 x99;substr$s,$p+=ord()*9%45%7-3,1,1for$p=49,@F;$s=~/1.*1/;$_=$&*8%29014%1637%11

Try it online!

Somewhat ungolfed:

cat <<'.' > recognise.pl
$s=0 x99;                                   #init string of 100 zeros
substr$s,$p+=ord()*9%45%7-3,1,1for$p=49,@F; #replace 0 with 1 for each step of
                      #input char, start at pos 49, -3 for U, 3 for D, -1 for L,
                      #1 for R. ord() is ascii val of UDLR
$s=~/1.*1/;           #find longest substring that starts and ends with 1, treat
                      #that string as a long int, i.e. 8 = 111101111101111
$_=$&*8%29014%1637%11 #modulus voodoo to get the digit
.
cat <<. | perl -F"" -apl recognise.pl
DDDD
UUUU
DDUDDUDD
DDUUUUDDUUDD
LRRDDLLDDRLRR
LDDRRLLUURRUULL
RRDDLLRRDDLL
LLRRUULLRLRRUUDULL
LUUDDRRUUDDDD
DDLLUUDDRRDD
LLDDRRDDLL
DLLRRUULLUURRLLRR
RRDDLLUUUURR
LLUURRDDUULLUURR
RRDDLLUURRDDLLUUUURR
RRDDDD
LLRRDDDD
LUURRDDDDLLU
RUULLUURRDDLLDD
RRDDLLUURRDDDDLL
DUDLRLLRRUULLRRUULLD
RRUUUULLDDD
UUUUDDDDRRUUUULRDDDD
.

Answer 6

R, 314 bytes

Not very short unfortunately, feels like the extra illegibility isn't worth it here.

{f=pryr::f
f(w,{s=switch
l=f(t,t[length(t)])
a=f(t,s=0,c(t,l(t)+s))
v=f(c,s(c,U=-1,D=1,0))
h=f(c,s(c,L=-1,R=1,0))
m=f(l,b,x=0,{for(c in l)x=a(x,b(c))
    x})
z=el(strsplit(w,''))
x=m(z,h)
y=m(z,v)
p=x-min(x)
q=y-min(y)
r=p+q*3
u=unique(r)
d=trunc(10*(var(u)+median(u)))%%28
match(d,c(0,5,20,3,2,16,1,26,8,19))-1})}

Try it online!

Intermediate calculations from:

letters=list(
x1=c(0,3,6,9,12),
x2=c(0,1,2,5,6,7,8,9,12,13,14),
x3=c(0,1,2,5,6,7,8,11,12,13,14),
x4=c(0,2,3,5,6,7,8,11,14),
x5=c(0,1,2,3,6,7,8,11,12,13,14),
x6=c(0,1,2,3,6,7,8,9,11,12,13,14),
x7=c(0,1,2,5,8,11,14),
x8=c(0,1,2,3,5,6,7,8,9,11,12,13,14),
x9=c(0,1,2,3,5,6,7,8,11,12,13,14),
x0=c(0,1,2,3,5,6,8,9,11,12,13,14)
)
sapply(letters,function(letter){trunc(10*(var(letter)+median(letter)))%%28})

Answer 7

Jelly,  31  28 bytes

^{Yes, it's very similar to Unrelated String's, but it's slightly different and was completely independently found.}

O%15Żı*ÄÆi_Ṃ$QṢ“X|cE’Dṭ⁽½ȯ¤ḥ

Try it online!

If a larger salt (which is also less than \$250^6\$) for the hash built-in is found which removes the need to permute \$[0,9]\$ (making “X|cE’Dṭ⁽½ȯ¤ḥ become “?????’,⁵¤ḥ’) we get 27 (or less).

How?

O%15Żı*ÄÆi_Ṃ$QṢ“X|cE’Dṭ⁽½ȯ¤ḥ - Link: listof characters
O%15                         - mod 15 of ordinals
    Ż                        - prepend a zero
     ı*                      - root(-1) raised to each of those
       Ä                     - cumulative sums
        Æi                   - convert each to [real, imaginary]
          _Ṃ$                - subtract of the minimum from each
             Q               - distinct values
              Ṣ              - sort
                          ¤  - nilad followed by link(s) as a nilad:
               “X|cE’        -   1398462570
                     D       -   to decimal digits (our domain)
                       ⁽½ȯ   -   3742 (our salt)
                       ṭ     -   tack -> [3742,[1,3,9,8,4,6,2,5,7,0]]
                           ḥ - hash (the sort results using that [salt, domain])

---

Previous version at 31 bytes using no built-in hash function...

O%15Żı*ÄÆi_Ṃ$QṢFḞḌ%⁽¥Ƭị“ċḞƒø’D¤

A monadic Link accepting a list of characters which yields an integer in \$[0,9]\$.

Try it online!

How?

O%15Żı*ÄÆi_Ṃ$QṢFḞḌ%⁽¥Ƭị“ċḞƒø’D¤ - Link: listof characters
O%15Żı*ÄÆi_Ṃ$QṢ                 - as above
               F                - flatten
                Ḟ               - floor (so Ḍ gives an integer rather than a float)
                 Ḍ              - convert from base ten
                  %⁽¥Ƭ          - modulo 2153
                       “ċḞƒø’D¤ - decimal digits of 3652914780
                      ị         - 1-indexed modulo index into

Answer 8

R, 217 200 192 bytes

(or only 169 bytes by stealing Arnauld's modulo chain to get the final digit without a look-up table...)

function(s,u=utf8ToInt){d=sapply(c(0,u(s)),`%in%`,x=u("DRUL"))
n=apply(d[1:2,]-d[3:4,],1,function(x)(y=cumsum(x))-min(y))
match(sum(2^unique(n[,1]+5*n[,2]))%%27%%11,c(0,4,7,10,8,5,2,3,9,1))-1}

Try it online!

How? Original code (before significant golfing changes...):

recognize_digit=
function(s){
                                # first we 'construct' the digit from the encoding:
                                
 d=sapply(                      # d is direction of each step, calculated by...
    c("D","R","U","L"),         # ...using each letter...
    grepl,                      # ...as a regex...
          el(strsplit(s,'')))   # ...to search each letter of the encoding.
 m=matrix(!-40:40,9)            # m is a matrix big enough to fit the letters (9x9)
 m[                             # we set the elements of m, selected by...
   apply(d[,1:2]-d[,3:4],       # ...subtracting L from R, and U from D...
   2,                           # ...and for each of the L-R and U-D columns...
   cumsum)+5                    # ...calculating the cumulative sum +5, 
            ]=T                 # to 'TRUE'.  
 l=m[(c=t(which(m,T)))[1]+0:4,  # l is the 3x5 'letter' matrix, starting at the  
   c[2]+0:2]                    # first TRUE elment of m
                                
                                # now we have the digit in l, so we just have to
                                # recognize it: 
 match(                         # we find the match between...
  sum(l*2^(0:14))               # the number formed by using the pixels of the digit as bits...
   %%27%%11,                    # MOD 27 MOD 11 (reduces each number to a smaller number
  c(0,4,7,10,8,5,2,3,9,1))-1    # and the 'lookup' table of results for each digit.
}

Answer 9

05AB1E, 36 35 bytes

•7‡šмÓ•žFDIÇv4y5%m8/*DŠ~s}\b0ÚC45%è

Port of @Arnauld's 78 bytes version, so make sure to upvote him as well! (His 78→77 and 77→71 golfs would be longer in 05AB1E.)

Try it online or verify all test cases.

Explanation:

•7‡šмÓ•              # Push compressed integer 31846207905
 žF                  # Push builtin 16384 (2**14)
   D                 # Duplicate it
    I                # Push the input-string
     Ç               # Convert it to a list of codepoint integers
      v              # Loop over each codepoint `y`:
        y5%          #  Take `y` modulo-5
       4   m         #  Take 4 to the power this value
            8/       #  Divide it by 8
              *      #  Multiply it by the top of the stack
               D     #  Duplicate it
                Š    #  Tripleswap (a,b,c → c,a,b) the top three values on the stack
                 ~   #  Bitwise-OR the top two
                  s  #  And swap so the other value is at the top again
      }\             # After the loop: discard the top value
        b            # Convert the integer to binary
         0Ú          # Remove all leading/trailing 0s
           C         # Convert it from binary back to an integer
            45%      # Modulo-45
               è     # And index it into the digits of 31846207905 (0-based modulair)
                     # (after which the digit is output implicitly as result)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why •7‡šмÓ• is 31846207905.