Parity of a number with missing digits

Question

It turns out that you need every digit of a number to determine its parity, if it is written in an odd base.

Your programs should take input as a number between 2 and 36 inclusive, and a nonempty string consisting of the base digits 0-9a-z (letters are lowercase) and a missing/unknown digit, which can be any other character (let's use ? for this challenge).

Your program should produce consistent, distinct outputs for:

1. The number is even in the given base, no matter what the missing digits are.

2. The number is odd in the given base, no matter what the missing digits are.

3. Ambiguous: the parity of the number cannot be determined, because of missing digits, for example (10, 123?) or (15, ???2).

4. Syntax error: The number contains digits not allowed in the base, for example a 2 in binary, or a letter in base 10.

Examples:

E = Even
O = Odd
A = Ambiguous
S = Syntax error

10, 123 -> O
15, ee -> E
2, 101 -> O
3, 101 -> E
2, 1?1 -> O
3, 1?1 -> A
25, ?2345 -> A
10, ?????? -> A
10, ??????502 -> E
9, ??????502 -> A
36, ppcg -> E
10, ppcg -> S
5, 5 -> S
4, ??????3 -> O
4, ??????5 -> S

Answer 1

Python 3.8 (pre-release), 61 bytes

lambda b,s,a=0:[a:=c<'0'or b%2*a^int(c,b)%-2for c in s][-1]%3

Try it online!

Use * (or any character with code point <48) for unknown digits. Outputs 2/0/1 for odd/even/ambiguous. Throws on syntax error.

a=0                                                 starting from empty (0),
    [a:=                         for c in s]        compute running parities a:
        c<'0'                                         missing digit: ambiguous
             or       int(c,b)                        else validate,
                              %-2                     parity,
                    a^                                base odd : xor a
                b%2*                                  base even: discard a
                                            [-1]    final parity
                                                %3  collapse ambiguous outputs

Answer 2

Python 2, 48 bytes

Exactly as below, just with / rather than // (we need an integer as the second argument to int)

Try it online!

---

Python 3,  56 55 50  49 bytes

-5 bytes thanks to Albert.lang (use max to convert the greatest character from base 36 and compare to the base rather than replacing wildcards and converting from base b).

-1 byte thanks to att (splat args of replace and revert to using ? as the wildcard).

lambda n,b:int(n[b%2-1:],b//(b>int(max(n),36)))%2

An unnamed function that accepts a non-empty string, n, of 0-9a-z plus * (the wildcard) and an integer, b, from \$[2,36]\$ and:

• returns the integer \$0\$ if n is unambiguously even in base b
• returns the integer \$1\$ if n is unambiguously odd in base b
• raises a ValueError if n is of ambiguous parity in base b
• raises a ZeroDivisionError if n is unparseable in base b

Try it online!

^{(The wildcards may actually be any character less than 0)}

How?

lambda n,b:int(n[b%2-1:],b//(b>int(max(n),36)))%2
lambda n,b:                                       # Accept string n and integer b
                 b%2-1                            # b mod 2 minus one
                                                  #  -> if b is odd: 0
                                                  #     else: -1
               n[     :]                          # slice n from that index
                                                  # -> if b is odd: n
                                                  #    else: last character of n
                                                  # (let's call that X)
                                   max(n)         # maximum character in n
                               int(      ,36)     # convert from base 36
                                                  #  -> if n is only wildcards
                                                  #        (one case of Ambiguous)
                                                  #     then: raise ValueError
                                                  #     else: base 36 value of max character of n
                            (b>              )    # is b greater than that?
                         b//                      # b integer divided by that
                                                  #  -> if any digit of n is too big
                                                  #        (i.e. Unparsable)
                                                  #     then: b//False -> raise ZeroDivisionError
                                                  #     else: b//True -> b
         int(           ,                     )   # convert X from base b
                                                  #   -> if wildcards present in X
                                                  #         (i.e. Ambiguous)
                                                  #      then: raise ValueError
                                               %2 # that modulo two 
                                                  #   -> if even:
                                                  #      then: 0
                                                  #      else: 1

Answer 3

Python 3.8 (pre-release),  119  109 bytes

-10 bytes: if'0'>n[-1]or(b%2 and'/'in n)else → if'/'in n[-(~b%2):]else.

lambda b,n:''if max(i<'0'or int(i,36)for i in n)>=b else[]if'/'in n[-(~b%2):]else int(n.replace('/','0'),b)%2

Takes input like print(f(10, '//////502')), where / is the unknown character.
Returns '' if the string is invalid, [] if the parity is ambiguous, 0 for even, and 1 for odd.

Try it online!

Answer 4

JavaScript (ES6), 76 bytes

Expects (base)(string), with . for missing digits.

Returns 0 for syntax error, 1 for even, 2 for odd or 3 for ambiguous.

b=>s=>eval("for(m=i=0;!(q=i.toString(b))[s.length];)m|=!!q.match(s)<<i++%2")

Try it online!

---

Recursive version, 67 bytes

Same I/O format.

(b,i=0)=>g=s=>(q=i.toString(b))[s.length]||!!q.match(s)<<i++%2|g(s)

Try it online!

Commented

( b,            // b = base
  i = 0         // i = counter
) =>            //
g = s =>        // s = input string
( q =           // set q to the representation of ...
  i.toString(b) // ... i in base b
)[s.length]     // stop if the n-th (0-indexed) character of q exists,
                // where n is the length of s
                // if it does, it must be "0" (truthy but zero'ish)
                // and will have no incidence on the final result
||              // otherwise,
!!q.match(s)    // if q matches s (interpreted as a regular expression),
<< i++ % 2      // set either bit #0 or bit #1 depending on the parity
|               // of i; increment i afterwards
g(s)            // do a bitwise OR with the result of a recursive call

Answer 5

Charcoal, 43 31 bytes

Ｎθ≔⍘⁻η?⭆θ⍘ιθζ¿⊙⌕Ａ⮌η?∨¬ι﹪θ²A§EOζ

Try it online! Link is to verbose version of code. Outputs O/E/A but throws for invalid input. Explanation:

Ｎθ

Input the base.

≔⍘⁻η?⭆θ⍘ιθζ

Tries to convert the number, with ?s removed, from the given base, but throws if there are any disallowed digits (Charcoal's base conversion normally allows overlarge digits but explicitly specifying the digit characters overrides this).

¿⊙⌕Ａ⮌η?∨¬ι﹪θ²A

If the reverse of the string contains any ?s and either the base is odd or one is at the beginning of the reversed string then the parity is ambiguous.

§EOζ

Otherwise use the base conversion result to determine the parity.

Answer 6

05AB1E, 31 28 bytes

L<Ið¢ãεðs.;Aā9+‡D¹‹Pi¹βÉë2]ê

Inputs in the order \$base,input\$, where \$input\$ is a list of characters with spaces as fillers.
Outputs [0]/[1]/[0,1]/[2] for E/O/A/S respectively.

Try it online or verify all test cases.

Explanation:

L         # Push a list in the range [1, first (implicit) input-integer] 
 <        # Decrease each by 1 to the range [0,input-integer)
  I       # Push the second input-list
   ð¢     # Pop and count how many spaces are in it
     ã    # Get the cartesian power of the earlier list and this count
          # (if the count was 0, the list will be `[[]]`, so it'll still
          # continue inside the map)
ε         # Map over this list of values:
 ð        #  Push a space character
  s       #  Swap so the current map-list is at the top of the stack
   .;     #  In the second (implicit) input-list, replace every space one-by-one
          #  with the values in the current map-list
 A        #  Push the lowercase alphabet
  ā       #  Push a list in the range [1,length] (without popping): [1,26]
   9+     #  Add 9 to each: [10,35]
     ‡    #  Transliterate all letters to these values
 D        #  Duplicate the resulting list
  ¹‹      #  Check for each value whether it's smaller than the first input
    Pi    #  If this is truthy for all of them:
      ¹β  #   Convert the list from base-firstInput to a base-10 integer
        É #   Pop and check whether it's odd
     ë    #  Else:
      2   #   Push a 2 as Synthax Error value instead
]         # Close the if-else statement and map
 ê        # Sort and uniquify the resulting values
          # (after which the result is output implicitly)

Answer 7

ELisp, 497 389 chars

I don't know how people did this in so few bytes. I don't know the math behind checking for ambiguous results besides brute force. I actually calculate all the possibilities and make sure the output is all the same or different. Here is my code. Caveat, ELisp only allows bases 2-16.

(let((o)(base(string-to-number(pop argv))))(dolist(a argv nil)(let((pos(string-match "\\?" a)))(if pos(progn(aset a pos ?0)(push a(cdr(last argv)))(let((i 1))(while(< i base)(aset a pos(aref(format "%x" i)0))(push(concat a)(cdr(last argv)))(setq i(1+ i)))))(let((p(if(cl-oddp(string-to-number a base))"O""E")))(if(not(member p o))(setq o(cons p o)))))))(princ(if(=(length o)2)"A"(car o))))

Try it Online

ungolfed

(require 'cl-lib)
(let ((o)(base (string-to-number (pop argv))))
  (dolist (a argv nil)
(let ((pos (string-match "\\?" a)))
  (if pos
      (progn
    ;; push possibilies of number to arguments array
    (aset a pos ?0)
    ;; add original to end of arguments array in case there are more '?'
    (push a (cdr (last argv)))
    (let ((i 1))
      (while (< i base)
        (aset a pos (aref (format "%x" i) 0))
        (push (concat a) (cdr (last argv))) ; deep copy string with concat
        (setq i (1+ i))
        )
      )
    )
    (let ((p (if (cl-oddp (string-to-number a base))"O""E")))
      (if (not (member p o)) (setq o (cons p o))))
    )
  )
)
  (princ (if (= (length o) 2) "A" (car o)))
  )