Garbled Phone Numbers

Question

You know how you get a voicemail message and the person's connection wasn't great, and you're trying to figure out how to call them back, but you're not sure if that was a "5" or an "8" they said?

That's this challenge.

The good news is that the caller read off their number twice, but it's garbled in both places.

Your program should take input like this:

5551231234 / 5551231234

Where the first ten digits are the first time the phone number is said in the voice mail and the second set are the second time it's said. Only...it'll look more like this:

555?ABC1_36? / 55?522_1?234

• A digit followed by a question mark means that that's the best-guess for that digit (e.g. "5?" means "probably a 5, compare with repeat").
• An underscore indicates a known missing digit, something too fuzzed by static to be deciphered at all.
• Letters are just that: letters. Treat them as their respective digits
  • ABC -> 2, DEF -> 3, GHI -> 4, JKL -> 5, MNO -> 6, PQRS -> 7, TUV -> 8, WXYZ ->9
  • All sample inputs use uppercase (you can safely omit a ToUpper() call)
  • If your language works better in lower case, you can freely use lowercase for the input and omit a ToLower() call. Just note that in your answer.

You can additionally assume the following judgement calls:

5? / _     -> 5  //5 is the best guess we have, use it
5? / 5?    -> 5  //uncertain, but matching
5? / 4?    -> ?  //conflict
 5 / 4     -> ?  //conflict
5? / 4     -> 4  //solid information overrides possible value
 5 / 4?    -> 5  //solid information overrides possible value
 _ / _     -> ?  //no information available

Additionally you can assume that all inputs will contain ten-digit phone numbers, not including the question marks. Inputs that aren't ten digits (e.g. 1234567 / 1234567) can either be treated as unsolvable (falsey output) or throw an error.

Input

One line of characters 0-9A-Z _?/, as described above.

Output

If it can be parsed to a single valid ten-digit phone number, output the phone number. Otherwise output some form of error indication (e.g. -1, false, or an empty line).

Shortest wins, as per usual.

Sample inputs:

1234567890 / 1234567890
1234567890? / 1234567890
123456789_ / 1234567890
1234567890? / 123456789_
1234567890 / 1234567890?
1234567890 / 123456789_
123456789_ / 1234567890?
1234567890? / 1234567890?
1234567890? / 1234567891?
123456789_ / 123456789_
555CALLUS1 / 5552255871
404_12?6039 / 4041?1560_9
_GETREVENGE / 16?36?_2838_
1?691460_50 / 16_14609?50
61?08977211 / 612?897725?1
40?0INSTA__ / 8?00_NSTI?LL
3985_534?10 / 39?8?5053_10
7__7294?737 / 7797299?_37
28?897_384?1 / _8?89763861
271168090_ / 27116800?09
6802?148343 / 67?01148343
94_11628?2?6? / 9491162_47?
17?4285_689 / 1__26?52689
6_311?95_38 / 6731194?7?38
380?7DRAGON / 3807378?5?66
4?647_93236 / 5646?6?9__36
365?268898_ / 366267?7?984
GRATEDBATE / IRATEDBATE
5307_079?93 / ____8_____
535_3_0255 / 52?5_3_024?5
55_____088 / 54?2397207?7?
6_48398_95 / _946?398?6_5?
_0_312_3_1 / 81?53123?1?71
____1_____ / 64?255?508?61
8427820607 / 6?424?8?__6?07
50_3707__6 / 52?8375?74?56
615___8255 / 62?526?983?2?1?
__652618__ / 8365261__0
149___933_ / 1_9677?92?31
___7?281562 / 3438?28154?2
5?7?7?___8?3?7?4 / 57_855837_
605_272481 / 605427__81
86?569__731 / 88560?0?7721
1__91654?15 / 17?9?9165715
800NWABODE / 80069ABI?DE
8___9017_0 / 8_2494?12?9_
_024?5?91?470 / 304?17908?7_
42510704_2 / 4_51070492
9338737_89 / 93_873PLUS
327762_401 / 327_MASH01
33093_2058 / 3309_12058
4061_33578 / 40619_3578
559_383197 / 559938_197
94_9746084 / 9459746_84
1_37655238 / 163POLKA_T
_672FRIZZY / 767237499_
8_76318872 / TIP63188_2
51_8404321 / 5178404_21
358_030314 / 358603_314
2597_85802 / 25979_5802
77141_1408 / 7714_91408
330858_457 / 330_586457
4686079_39 / 46_6079239
86457508_6 / 8_45750826
523226626_ / _23BANNANA
_ISSY_ISSY / 44__9548?79?
6?00B_YJILT / 800289KILL?
2?52803___0 / 1526?0390?61?
FI?ND___T?HE / EAS?T?EREGGS?
0_231?95_38 / 0723194?7?38
0?647_39236 / 0646?6?3__36
025?267798_ / 06?6265?9?984
0061_33578 / _0619_3578

I've only insured that every possible edge-case is covered (the first 11 entries), but other than that, it's pretty much random.

Update

Four entries at the bottom added with leading zeros (at Jonathan Allan's suggestion).

Correct output for the sample inputs:

https://pastebin.com/gbCnRdLV

Based on the output from Jonathan Allan's entry (the formatted output was ideal).

Answer 1

Jelly, 84 bytes

+4 bytes - I think it should probably behave the same in all cases, so I've converted the keypad lookup integers back to digit-characters using +49Ọ.

”?e‘ḣ@µ”_eḤ‘ẋ@
;Ṃµ68DṬ+3RØAṁẇ@€FT+49Ọȯµ€Fṡ2i”?Ḃ$ÐḟÇ€
ḟ⁶ṣ”/Ç€ZLÐṂ€Q€LỊ$ÐfF€Ḣ€ḟ”_µL⁼⁵ȧ

A function which takes the string in the specified format and returns the phone number as a list of character or zero if invalid. As a program this is printed as if it were a string.

The way it works they could repeat the number more times
(e.g. "123456789_ / 123456789_ / 1234567890")
...or even only say it once, and the logic defined will apply.

Try it online!, or see all the sample inputs.

How?

”?e‘ḣ@µ”_eḤ‘ẋ@ - Link 1, helper to vary the length of a 2-slice: list s
”?             - literal '?'
  e            - exists in s                   (1 or 0)
   ‘           - increment                     (2 or 1)
    ḣ@         - head with reversed @rguments  (s or s[:1] - removes 2nd value if not '?')
      µ        - monadic chain separation, call that t
       ”_      - literal '_'
         e     - exists in t                   (1 or 0)
          Ḥ    - double                        (2 or 0)
           ‘   - increment                     (3 or 1)
            ẋ@ - repeat t that many times      (t*3 or t - [`_`]->['_','_','_'])

;Ṃµ68DṬ+3RØAṁẇ@€FT+49Ọȯµ€Fṡ2i”?Ḃ$ÐḟÇ€ - Link 2, reformat a phone number: char list of [0-9][A-Z], p
;                                     - concatenate p with
 Ṃ                                    - minimum of p - (?<_<0<1<...<9<A<...<Z - never "?" however, since it only follows a digit.)
                                      -   - this is simply to make a 2-slice with the last character on the left, as used at the very end of this link.
  µ                                   - monadic chain separation call that q
                       µ€             - monadic chain separation, for €ach v in q do:
   68                                 -   literal 68
     D                                -   cast to a decimal list -  [6,8]
      Ṭ                               -   untruth                -  [0,0,0,0,0,1,0,1]
       +3                             -   add 3                  -  [3,3,3,3,3,4,3,4]
         R                            -   range                  -  [[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3,4],[1,2,3],[1,2,34]]
          ØA                          -   uppercase alphabet     -  ABCDEFGHIJKLMNOPQRSTUVWXYZ
            ṁ                         -   mould like the range ^ -  [ABC,DEF,GHI,JKL,MNO,PQRS,TUV,WXYZ]
             ẇ@€                      -   sublist v exists in that? for €ach, with reversed @rguments
                F                     -   flatten        (e.g. 'E' -> [0,1,0,0,0,0,0,0]; '4' -> [0,0,0,0,0,0,0,0]
                 T                    -   truthy indexes (e.g. 'E' -> [2]; '4' -> [])
                  +49                 - add 49
                     Ọ                - cast to character
                      ȯ               -   or             (e.g. 'E' -> [3]; '4' -> '4')
                         F           - flatten
                          ṡ2          - all slices of length 2
                                 Ðḟ   - filter discard if:
                                $     -   last two links as a monad:
                            i         -     first index of
                             ”?       -     literal '?'   (first index returns 0 if none exists)
                               Ḃ      -   mod 2 (so this filter discards pairs starting with '?')
                                   Ç€ - call the last link (1) as a monad for €ach slice

ḟ⁶ṣ”/Ç€ZLÐṂ€Q€LỊ$ÐfF€Ḣ€ḟ”_µL⁼⁵ȧ - Main link: string (or char list) s
ḟ                               - filter discard any:
 ⁶                              - literal ' '
  ṣ                             - split on:
   ”/                           - literal '/'
     Ç€                         - call the last link (2) as a monad for €ach
       Z                        - transpose
         ÐṂ€                    - filter, for €ach, keep items with minimal:
        L                       -   length
            Q€                  - de-duplicate €ach
                 Ðf             - filter keep items with:
                $               - last two links as a monad:
              L                 -   length
               Ị                -   insignificant? (=1 effectively here)
                   F€           - flatten €ach
                     Ḣ€         - head €ach
                       ḟ        - filter discard any of:
                        ”_      -   literal '_'
                          µ     - monadic chain separation, call that r
                           L    - length(r)
                             ⁵  - literal 10
                            ⁼   - equal?
                              ȧ - and r (0 if r did not result in a 10-digit list, else r)

Answer 2

Python 2, 314 307 274 bytes

lambda s:g(*''.join(q<n<"["and`(int(n,36)-4-(n>"R")-(n>"Y"))//3`or n for n in s).split(" / "))
def g(a,b,s=str.startswith):
 if b:c,d,e,f=a[0],a[1:],b[0],b[1:];b=(c==e and[c,q][c=="_"]or"_"in c+e and min(c,e)or[q,c,e][s(f,q)-s(d,q)])+g(d[s(d,q):],f[s(f,q):])
 return b
q="?"

Try it online!

Answer 3

Python 3, 549 530 509 453 449 410 406 394 393 391 bytes

I'm sure this can be improved, but it's a start:

def f(e,z,q="?",u=str.isnumeric):
 if e+z in(e,z):return""
 o,O,t,T,*x=e[0],e[1:2],z[0],z[1:2],e[1:],z[1:]
 if"?"in o+t:return f([e,x[0]][o==q],z)
 if u(o):
  if u(t):return t+f(*x)if O==q!=T else o+f(*x)if o==t or T==q!=O else 1
  return o+f(*x)
 if u(t):return t+f(*x)
def g(s):
 for a,b in zip(map(chr,range(65,91)),"2223334445556667777888999"):s=s.replace(a,b)
 return f(*s.split(" / "))

I'm using str.translate for the letters, and a wrapper function g to make the inputs in the format in which I want them. The actual function f is recursive, and will fail for ambiguous inputs. I still have lots of repititions in there though, so I'm sure there's lots of room for improvement.

Improvements:

• saved 19 bytes by combining conditions
• saved 21 bytes with ternaries
• saved 56 bytes using a dictionary comprehension instead of the manual dictionary, thanks to @TuukkaX
• saved 4 bytes by switching to the method suggested by @ovs, with @TuukkaX's improvement
• saved 38 bytes with improvements from @ovs (and the last removable whitespace removed)
• saved 4 bytes by putting defining str.isnumeric in a keyword argument
• saved 12 bytes with combined comparison operators (e.g. T==q!=O)
• saved 1 byte by turning not(e or z) into e+z in(e,z).
• saved 2 bytes by saving the frequently used (E,Z)

Answer 4

JavaScript (ES6), 180 190 188 bytes

Edit: +10 +9 bytes to comply with the falsy output rule

---

Takes the two input strings in currying syntax (a)(b). Returns either false or a string representing the guessed phone number.

a=>b=>!(s=(F=a=>a.match(/(.\??)|_/g).map(([x,y])=>(x<=9?++x:parseInt(x,36)*.32-(x>'Y'))|(x!='_'&!y)*16))(a).map((x,i)=>(x=(d=x^(y=F(b)[i]),x>y)?x:y)&&(d&16|!(d%x))?--x&15:a).join``)[10]&&s

How it works

Step #1 - Parsing the input strings

We first define the F() function which translates a string into an array of integers by applying the following rules:

• the underscore is converted to 0
• a digit N or an equivalent letter is converted to (N+1) OR 16 (e.g. "2" → 19, "R" → 24)
• a digit N or an equivalent letter followed by an interrogation mark is converted to N+1 (e.g. "2?" → 3, "R?" → 8)

Which can be interpreted the other way around as follows:

• 0 → unknown
• [ 1 .. 10 ] → unreliable
• [ 17 .. 26 ] → reliable

We apply F() to both a and b. This gives us a pair of integers (x, y) for each digit in the phone number, corresponding to the two possible interpretations.

Step #2 - Guessing the digits

For each pair (x, y), we compute:

• d = x XOR y
• x = MAX(x, y) → reliable values are always preferred to unreliable ones

If x == 0, it means that both inputs are underscore characters. So, the digit is unknown in this case.

If x != 0, we can safely deduce the digit if one of the following conditions is true:

condition       | interpretation
----------------+------------------------------------------------------
(d AND 16) != 0 | one input is unreliable and the other one is reliable
d == 0          | both inputs are identical
d == x          | one input is an underscore

The last two conditions can be merged with !(d % x). Hence the final formula:

x && (d & 16 || !(d % x))

If true, we convert x back to the guessed digit by computing (x - 1) AND 15.

Test cases

(Only the 50 first ones because the console snippet can't support more output history.)

let f =

a=>b=>!(s=(F=a=>a.match(/(.\??)|_/g).map(([x,y])=>(x<=9?++x:parseInt(x,36)*.32-(x>'Y'))|(x!='_'&!y)*16))(a).map((x,i)=>(x=(d=x^(y=F(b)[i]),x>y)?x:y)&&(d&16|!(d%x))?--x&15:a).join``)[10]&&s

console.log(f('1234567890')('1234567890'))
console.log(f('1234567890?')('1234567890'))
console.log(f('123456789_')('1234567890'))
console.log(f('1234567890?')('123456789_'))
console.log(f('1234567890')('1234567890?'))
console.log(f('1234567890')('123456789_'))
console.log(f('123456789_')('1234567890?'))
console.log(f('1234567890?')('1234567890?'))
console.log(f('1234567890?')('1234567891?'))
console.log(f('123456789_')('123456789_'))
console.log(f('555CALLUS1')('5552255871'))
console.log(f('404_12?6039')('4041?1560_9'))
console.log(f('_GETREVENGE')('16?36?_2838_'))
console.log(f('1?691460_50')('16_14609?50'))
console.log(f('61?08977211')('612?897725?1'))
console.log(f('40?0INSTA__')('8?00_NSTI?LL'))
console.log(f('3985_534?10')('39?8?5053_10'))
console.log(f('7__7294?737')('7797299?_37'))
console.log(f('28?897_384?1')('_8?89763861'))
console.log(f('271168090_')('27116800?09'))
console.log(f('6802?148343')('67?01148343'))
console.log(f('94_11628?2?6?')('9491162_47?'))
console.log(f('17?4285_689')('1__26?52689'))
console.log(f('6_311?95_38')('6731194?7?38'))
console.log(f('380?7DRAGON')('3807378?5?66'))
console.log(f('4?647_93236')('5646?6?9__36'))
console.log(f('365?268898_')('366267?7?984'))
console.log(f('GRATEDBATE')('IRATEDBATE'))
console.log(f('5307_079?93')('____8_____'))
console.log(f('535_3_0255')('52?5_3_024?5'))
console.log(f('55_____088')('54?2397207?7?'))
console.log(f('6_48398_95')('_946?398?6_5?'))
console.log(f('_0_312_3_1')('81?53123?1?71'))
console.log(f('____1_____')('64?255?508?61'))
console.log(f('8427820607')('6?424?8?__6?07'))
console.log(f('50_3707__6')('52?8375?74?56'))
console.log(f('615___8255')('62?526?983?2?1?'))
console.log(f('__652618__')('8365261__0'))
console.log(f('149___933_')('1_9677?92?31'))
console.log(f('___7?281562')('3438?28154?2'))
console.log(f('5?7?7?___8?3?7?4')('57_855837_'))
console.log(f('605_272481')('605427__81'))
console.log(f('86?569__731')('88560?0?7721'))
console.log(f('1__91654?15')('17?9?9165715'))
console.log(f('800NWABODE')('80069ABI?DE'))
console.log(f('8___9017_0')('8_2494?12?9_'))
console.log(f('_024?5?91?470')('304?17908?7_'))
console.log(f('42510704_2')('4_51070492'))
console.log(f('9338737_89')('93_873PLUS'))
console.log(f('327762_401')('327_MASH01'))

Answer 5

Perl 5, 211 bytes

...without indentation and \n newlines

@i=map{y/ABCDEFGHIJKLMNOPQRSTUVWXYZ/22233344455566677778889999/;$_}split' / ',shift;
print map{
  $_=join'',map{s,(\d\??|_),,;$1}@i;
  /((\d)\??\2\??|(\d)\??_|_(\d)\??|(\d)\d\?|\d\?(\d))$/;$2//$3//$4//$5//$6//'?'
}1..10

Try it online!

Answer 6

Retina, 150 140 136 bytes

Saved a few bytes thanks to Kritixi Lithos

T`?L`#22233344455566677778889
./.

(?<=(\d)(\w#?){9}).#|.#(?=(\w#?){9}(\d)(?!#))
$1$4
#

_(?=.{9}(.))|(?<=(.).{9})_
$1$2
^(\d*)\1$|.*
$1

Try it Online!

Explanation:

The first line transforms all ? in the input into # and all letters into their numeric equivalents. We then remove the spaces and / from the input. The next two lines take care of "guess vs. certainty" cases (eg. 5? \ 4 would be replaced by 4 \ 4). After removing all #s, lines 8 and 9 deal with "number vs. _" cases (_ \ 3 becomes 3 \ 3). Then, if both halves of the string match, we keep the first 10 digits. Otherwise, the phone number is invalid so we remove everything.

Alternative 160-byte solution that works for phone numbers of arbitrary length (and equal size): TIO

Answer 7

PHP, 251 236 bytes

for(;a&$c=preg_replace(["#[^_?](?!\?)#","#_#"],["$0k","?<"],join("-",$argv))[++$i];)${$k+="-"==$c}.=$c<_&$c>=A?0|(ord($c)-($c>W)-($c>P)-59)/3:$c;for(;$c=${1}[$k+1];)echo($n=${1}[$k])==($m=${2}[$k++])|($b=${2}[$k++])!=$c?$c>$b?$n:$m:"?";

takes input from command line; run with -nr or try it online.

breakdown

# A: transform input
                                    # 2. replace single chars with two-character chunk and make sortable:
                                    #   replace "_" with "?<", append "k" to everything else not followed by "?"
for(;a&$c=preg_replace(["#[^_?](?!\?)#","#_#"],["$0k","?<"],join("-",$argv))[++$i];)    # (unknown "<" < unsure "?" < certain "k")
${$k+="-"==$c}.=                # if "-", next argument
        $c<_&$c>=A              # if letter
            ?0|(ord($c)-($c>W)-($c>P)-59)/3 # then translate to digit
            :$c                             # else don´t
    ;
# B: evaluate
for(;$c=${1}[$k+1];)            # loop through arguments: $c=command 2
    echo
        ($n=${1}[$k])                   # $n=digit 2
        ==                          # if digits are equal
        ($m=${2}[$k++])                 # $m=digit 3
        |
        ($b=${2}[$k++])             # $b=command 3
        !=$c                        # or "commands" are not
            ?$c>$b?$n:$m            # then get the one with the more definitive "command"
            :"?"                    # else conflict/unknown
    ;

golfings

• preg_replace first: -8 bytes
• join: -2
• $$k instead of $t[$k]: -5

Answer 8

PHP, 200+8 bytes

inspired by Arnaulds solution.

for($s=join($argv);$c=ord($s[$i++]);$i+=$x)$t[]=$c>90?63:15&($c<65?$c:($c-($c>80)-($c>87)-59)/3)|16*$x="?"==$s[$i];for(;$p++<10;)echo chr(($e=$t[$p]^$d=$t[$p+10])&48|!(15&$e)?min($t[$p],$d)&15|48:63);

takes input from command line arguments; run with -nr or try it online.

modifications to comply with the error output restriction: (print X for an incomplete number):

• remove |48 (-3 bytes)
• replace echo chr(...); with $r.=...;echo$r>1e10?X:$r; (+11 bytes)

breakdown

for($s=join($argv);$c=ord($s[$i++]);    # loop through characters of arguments
    $i+=$x)                             # skip "?"
$t[]=
    $c>90                               # if "_"
        ?63                             # then 32+16+15
        :                               # else
            15&(                            # lower 4 bits of
            $c<65                               # if digit
            ?$c                                 # then digit
            :($c-($c>80)-($c>87)-59)/3          # else letter mapped to digit
        )
        |16*$x="?"==$s[$i]                  # if next char is "?", add 16
;
for(;$p++<10;)echo chr( # loop through translated arguments
    (
        $e=$t[$p]^      # 2. $e=difference
        $d=$t[$p+10]    # 1. $d=char from 2nd argument
    )&48                # if certainties differ
    |!(15&$e)           #    or digits do not
    ?min($t[$p],$d)&15|48   # then pick the more definite digit (15|48 -> "?")
    :63             # else "?"
);

golfings

• work around preg_replace_callback (-10 bytes)
• rely on 10 digit input (-9)
• and additional golfing (-8)
• removed join delimiter (-7)
• moved $x assignment to the end (-2)

Answer 9

Perl 5 -pl, 173 bytes

sub t{$_=pop;y/A-Z/22233344455566677778889999/;/_|\d\??/g}@e=m|\S+|g;@a=t$e[0];$_=join"",map{$_.=shift@a;s/^(.+)\1$/$1/||s/_//||s/..../_/||s/.\?//;$_}t$e[2];s/\?//;$_ x=!/_/

Try it online!