Mathematics is fact. Programming is not

  • In mathematics an exclamation mark ! often means factorial and it comes after the argument.


    In programming an exclamation mark ! often means negation and it comes before the argument.


    For this challenge we'll only apply these operations to zero and one.


    Factorial
    0! = 1
    1! = 1

    Negation
    !0 = 1
    !1 = 0

    Take a string of zero or more !'s, followed by 0 or 1, followed by zero or more !'s (/!*[01]!*/).

    For example, the input may be !!!0!!!! or !!!1 or !0!! or 0! or 1.


    The !'s before the 0 or 1 are negations and the !'s after are factorials.


    Factorial has higher precedence than negation so factorials are always applied first.

    For example, !!!0!!!! truly means !!!(0!!!!), or better yet !(!(!((((0!)!)!)!))).


    Output the resultant application of all the factorials and negations. The output will always be 0 or 1.


    Test Cases


    0 -> 0
    1 -> 1
    0! -> 1
    1! -> 1
    !0 -> 1
    !1 -> 0
    !0! -> 0
    !1! -> 0
    0!! -> 1
    1!! -> 1
    !!0 -> 0
    !!1 -> 1
    !0!! -> 0
    !!!1 -> 0
    !!!0!!!! -> 0
    !!!1!!!! -> 0

    The shortest code in bytes wins.


    But 0!=1!, so what's the point of handling multiple factorials?

    @boboquack Because that's the challenge.

    What type can the output have? (String, char, integer, boolean, float...)

    @Zgarb The type doesn't matter as long as it would be represented as plain 0 or 1 (not 0.0, not True, etc.)

    I may be wrong here but can't any number with any factorials after it simply be removed and replaced with 1? Like 0!!!! = 1!! = 0!!!!!!!! = 1!!! = 1! = 0! = 1 etc

    @AlbertRenshaw That is correct.

    @AlbertRenshaw - my answer is just one (humble) example of how and why this works for this challenge.

    Do we have to handle invalid inputs in any way?

    @theonlygusti since he didn't say anything about invalid inputs, you don't have to worry about them (that's the standart rules of codegolf).

    You need to talk to Alan Turing about the title.

    You could take this one step further and require !! to mean the double factorial etc.

    *I finally get it.*

    @TobiasKienzler That wouldn't change the results.

    @MartinEnder It sure would: `5!! = 5•3•1 = 15` while `(5!)! = 120! > 6.6e198`.

    @TobiasKienzler You don't ever get a value other than `0` or `1` as an argument to the (multi-)factorial though.

    @MartinEnder Ah yes, of course. The difference only matters when any integer is permitted. And in contrast to the recursive factorial the double, triple etc. factorial would not overflow so quickly :)

    Can we output `True` for `1` and `False` for `0`?

  • Mathematica, 25 17 bytes



    Input[]/.!x_:>1-x


    Takes input from a user prompt. Assumes Mathematica's notebook environment for implicit printing. To make it a command-line script, wrap it in Print[...] or to make it an argumentless function (which then takes input from the prompt), append &.



    Mathematica has both of the required operators (with the required precedence), so we can just "eval" the input (which is done automatically by Input[]), but the logical negation operator doesn't work on integers (so it will remain unevaluated). If there's a !x left in the result, we replace it with 1-x.



    A couple of fun facts about the evaluation:




    1. Mathematica actually also has the double factorial operator !!, which computes n*(n-2)*(n-4)*..., but applied to 0 or 1 it still gives 1, so it doesn't matter that 0!!!!! will actually be parsed as ((0!!)!!)!.

    2. Even though Mathematica leaves !0 and !1 unevaluated, it does know that ! is self-inverse, so it will automatically cancel all pairs of leading !. After the ToExpression we're always left with one of 0, 1, !0, !1.


    Since when was a REPL snippet allowed by default?

    @LegionMammal978 Apparently since December 2015, but I keep forgetting about it. To be fair, it's not a "snippet" in that it doesn't assume that the input is already stored somewhere in memory. And assuming the notebook environment is then not very different from having a language with implicit output.

    Just curious, could a meta link be provided? (Trying to find information there is stressful, yet another problem of the SE Q&A format...)

    @LegionMammal978 it's already in the answer.

  • Bash + Unix utilities, 21 17 bytes





    sed s/.!!*$/1/|bc


    Verify the test cases online!



    Added a TIO link to the test suite.



    This must be saved in a file and run as a program. If you try to enter the command directly from the command line, it won't work because !! is expanded due to history substitution being enabled in bash's interactive mode. (Alternatively, you can turn history substitution off with set +H.)


    The old version works, this one doesn't

    I used the TIO link

    @KritixiLithos It worked fine when I tried it on my Linux box. The problem was apparently that TIO requires a newline at the end of the simulated input line. It's a confusing situation, so I took out the TIO link. If you want to try it out there, here's the link again (but be sure to include a newline at the end of the input if you change the input to test it out): https://tio.run/nexus/bash#@[email protected]@[email protected]/[email protected]/oqKiIRArcn3Ny9dNTkzOSAUA

    But what if someone has run `mkdir -p 's/.!!'{bunch,of,different,directories}\$/1`? Then you'll get Pathname Expansion and Sed will be attempting to read directories as though they were files, instead of reading standard input, and it won't output anything! :)

    @Wildcard Yes, that's true, of course. You can avoid this issue by writing `\*` instead of `*` in the regex, at the cost of 1 byte, but it seems to be considered acceptable on PPCG to assume that the program is being run in a directory without strangely-named files that expressions like s/.!!*$/1/ would expand to.

    Of course. :) Just commenting. In general, and in Production scripts, I wish people would play a little less fast and loose with assumptions relating to glob characters...but it's perfectly appropriate for code golf. Consider my comment a token of my wish that some reader will actually learn when quotes should be used in the shell.

    @Wildcard I agree completely. In production scripts, I always use quotes in situations like this. (In this case, I would actually put double-quotes around the argument to sed, rather than just escaping the *. It's easier to read than using backslashes, and it avoids the possibility of missing some special character.)

    @MitchellSpector, ha—I always use single quotes unless I *specifically* need parameter expansion or command substitution. Or unless I'm nesting the command inside `find ... -exec sh -c 'for f; do ... ; done' sh {} +` or similar. Notably, history expansion is not prevented by double quotes. :) (Note: I'm surprised to see you don't have an account on Unix & Linux SE!)

    @Wildcard You're right -- this one would actually go in single quotes. I glanced at it quickly, saw the $, and commented as if it used parameter expansion, but it doesn't.

  • Retina, 20 15 14 bytes



    Thanks to Leo for saving 1 byte.



    0!
    1
    !!

    ^1|!0


    Try it online!



    Explanation



    0!
    1


    Turn 0! into 1. We don't care about any other trailing !s, the resulting number is the same as if we had applied all factorials.



    !!



    Cancel pairs of negations. This may also cancel some factorials, but that's irrelevant.



    ^1|!0


    Count the number of matches of this regex, which is either 1 or 0 and gives the desired result.


    Alternate solution for same bytecount: `\d.+`...

    @KritixiLithos Found a way to avoid that altogether.

    You can remove the `^` before `!0`

  • Grime, 14 12 9 bytes



    e`\0!~\!_


    Try it online!



    Explanation



    This matches the input against a pattern, printing 1 for match and 0 for no match.



    e`\0!~\!_
    e` Match entire input against this pattern:
    ! not
    \0 a sole 0
    ~ xor
    \! exclamation mark
    _ followed by this pattern matched recursively.


    The idea is this.
    If the input begins with a digit, then the recursive part \!_ always fails, and \0! succeeds unless we have a single 0.
    Their xor succeeds unless the input is a single 0.
    If the input begins with a !, then \0! always succeeds, and \!_ succeeds if the recursive match succeeds.
    Their xor succeeds exactly when the recursive match fails, thus negating it.


  • Brainfuck, 85 72 (84) bytes



    ,[>-[-----<->]<++[>++++[-<++++>]+<[[+],[[-]>-<]]]>[<<+[-->]>[<],>-]<]<+.


    to return numerically, or



    ,[>-[-----<->]<++[>++++[-<++++>]+<[[+],[[-]>-<]]]>[<<+[-->]>[<],>-]<]-[-----<+>]<--.


    for ASCII text. > may also be prefixed to avoid memory wrapping.



    Try it online!






    Loops over the input.
    On 1, ends.
    On "!", toggles bool a stored as 0 or 255.
    On "0", toggles if there is no trailing bit, then ends.

    Memory labels | BOOL | INPUT | FLAG |

    , first input
    [ # loop on INPUT
    >-[-----<->]<++ subtract 49 == "1"

    [ # case not "1"
    >++++[-<++++>] add 16 since 49 take 16 == "!"

    + set FLAG
    < move to INPUT
    [ # case "0"
    [+], clear and new INPUT
    [ # case "0!"
    [-]>-< clear INPUT and FLAG
    ]
    ]
    ]

    > move to FLAG
    [ # case "!" or "0" without tail
    <<+[-->]>[<] not the BOOL
    , take new input
    >- clear FLAG
    ]
    < move to INPUT
    ]

    +. return 0 or 1


    Or for text response, replace the last line with



    -[-----<+>]<--.       add 49 for "0" or "1" conversion and return

  • Brainfuck - way to many bytes (232 bytes)



    Clearly the wrong language for winning in code golf. Mainly I noticed a lack of anyone using this esolang. There is a good online interpreter bf interpeter or you can actually watch what the program does using this bf visualizer.



    >>>>>,[>+++[<---------------->-]<<<<<<[-]+>[-]>>>>[-[<<[>+<<<<->>>[<<+>>-] ]<<[>>+<<-]<[>>+<<[-]]>>>>>[-]]<<<<<[>>>++<<<-]>+>>>>[-]]<<<<-[>>+<<[-]]>>>>,]<<->[<[-]+>[-]]<<[<[-]>>[<<+>>[-]]+<<[->>-<<]>-]>>[-]+++[<++++++++++++++++>-]<.

    You crazy man!!

    Love it, can you do that in malbolge? XD

    Information: There are too much shorter solutions below.

  • Python, -44- 42 bytes



    Saved 2 bytes thanks to Zgarb!



    lambda x:(x[-1]=='0')^len(x.rstrip('!'))%2


    Step by step:




    1. x[-1]!='0'

      if x ends with 1 or !x doesn't end with 0, the factorial portion must have value 1, else 0

    2. ^len(x.rstrip('!'))%2

      exploit xor's property as a "conditional not". The condition in this case is if the length of initial !s is odd. However, .rstrip doesn't remove the number from the string so the length calculated is offset by 1, therefore the condition is inverted

    3. The offset by 1 in step 2 is corrected by changing != to == in step 1. Zgarb suggested using a difference comparison operator rather than applying another inversion, saving 2 bytes.



    Try it online!


    Fails on an input of `!!0`; it is currently returning `1`.

    @ValueInk should be working now

    `lambda x:(x[-1]=='0')^len(x.rstrip('!'))%2` avoids the extra inversion.

    @Zgarb Cool, thanks!

    _crossed out 44 is still regular 44_

    @EasterlyIrk What do you mean?

    I think he's stating that a crossed out 44 in the font used doesn't look crossed out... :) The cross out portion overlaps with the horizontal portion of the 4s.

  • JavaScript (ES6), 43 41 29 bytes



    s=>+eval(s.replace(/.!+$/,1))


    Non-regex method (41 31 bytes)



    Below is my initial approach. It's slightly more interesting, but significantly longer still a bit longer even after a significant optimization by Neil (10 bytes saved).



    f=([c,...s])=>1/c?c|s>'':1-f(s)


    Test cases





    let f =

    s=>+eval(s.replace(/.!+$/,1))

    ;[
    "0", "1", "0!", "1!", "!0", "!1", "!0!", "!1!", "0!!",
    "1!!", "!!0", "!!1", "!0!!", "!!!1", "!!!0!!!!", "!!!1!!!!"
    ].map(
    s => console.log(s, '=>', f(s))
    )




    I can only save 10 bytes from your non-regex method, so it's still too long: `f=([c,...s])=>1/c?c|s>'':1-f(s)`.

    @Neil Since it's much better than my 1st attempt anyway, I took the liberty to include your suggestion.

    Ha, I had the same idea but you golfed it better. :)

  • Retina, 13 bytes



    A somewhat weird approach, but it's short and it works.



    0$
    !1
    !!

    ^\d


    With the first two lines we replace an ending 0 with !1: with this replacement we now know that the part of our string from the digit onwards is equal to 1.



    Next two lines, remove pairs of !: double negation erases itself, and we already accounted for factorial with the previous step.



    Last line, match a digit at the start of the string and return the number of matches: if the negations have all been eliminated we'll find a match (and as we said before we know this is equal to 1), if there's still a negation this won't match.



    Try it online!


    Wouldn't the final digit necessarily always be a 1? In that case, you could use `1` rather than `\d`.

    @ais523 no, because the first part will only replace an ending 0, so for example the input `0!` will stay unchanged until the last line

    Really lovely solution, nice work! :)

  • Jelly, 5 bytes


    VeMḂ$

    Try it online!


    Monadic function expecting a string. Inputs with leading !s cause a 1 to be printed to STDOUT along the way, so the TIO link I give is a test harness that prints the input-output pairs beneath the first line of output.


    How?


    VeMḂ$ - Monadic link: string
    V - eval the string
    - the implicit input of 0 causes !...! to evaluate to 1 (which gets printed),
    - the result is the evaluation of the rest: "0"=0; "0!"=1; "1"=1; "1!"=1; ...
    e - exists in?
    $ - last two links as a monad:
    M - Maximal indexes - the "0" and "1" characters are greater than "!",
    - so this results in a list of one item [i] where
    - i is the 1-based index of the 0 or 1 character.
    Ḃ - %2 (vectorises) - [i%2], so a 0 if we need to logically negate and a 1 if not
    - hence we check equality with e rather than inequality.

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM