0
\$\begingroup\$

Write a program to determine if a number is a factorial. You should take the number from standard input.

Rules:

  • No using any loops (hint: recursion)
  • Maximum of one if statement
  • No accessing the Internet or external resources

Scoring:

  • +1 per character
  • -20 for each of the following: (I don't know if any of these are possible)
    • Don't use any if statements
    • Don't use recursion

Lowest score wins.

Clarification:

  • Only if statements in your source code count, but any form of if counts.
  • Any loop constructs in source code count.
  • You may assume int32
\$\endgroup\$

closed as unclear what you're asking by Peter Taylor, Howard, boothby, ProgramFOX, manatwork Dec 27 '13 at 10:03

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ What will be the maximum input size; can we assume int32 or int64? \$\endgroup\$ – John Dvorak Dec 26 '13 at 20:49
  • \$\begingroup\$ one if statement? What about switch, the ternary operator and short-circuiting boolean operators? \$\endgroup\$ – John Dvorak Dec 26 '13 at 20:56
  • 1
    \$\begingroup\$ What about higher order functions that do recursion internally? Or pattern matching? \$\endgroup\$ – shiona Dec 26 '13 at 21:05
  • \$\begingroup\$ Any solution, if you compile it down to assembly, there will be branching statements. Any kind of actual logic, requires branching. \$\endgroup\$ – Cruncher Dec 27 '13 at 1:56
  • 1
    \$\begingroup\$ Does indexing an array of functions count as an if? \$\endgroup\$ – John Dvorak Dec 27 '13 at 15:20
3
\$\begingroup\$

Mathematica 42 41-40 = 1

No recursion or If is used (-40)

MemberQ[Table[Times@@Range@k,{k,9^4}],#]&

How it works.

Times is Listable. It does not loop when applied to a list. It does the multiplication all at once.

Range[6]

{1,2,3,4,5,6}

Times@@Range[6]

720


Testing

MemberQ[Table[Times@@Range@k,{k,9^4}],#]&[720]
MemberQ[Table[Times@@Range@k,{k,9^4}],#]&[721]
MemberQ[Table[Times@@Range@k,{k,9^4}],#]&[10000!]

True
False
True

\$\endgroup\$
  • \$\begingroup\$ NestWhile uses If internally \$\endgroup\$ – John Dvorak Dec 26 '13 at 22:56
  • \$\begingroup\$ @Jan How can you be sure? \$\endgroup\$ – DavidC Dec 26 '13 at 22:57
  • \$\begingroup\$ Can you suggest an alternative implementation? \$\endgroup\$ – John Dvorak Dec 26 '13 at 22:58
  • \$\begingroup\$ This will almost certainly be the accepted answer but I'm going to wait a day or so first. \$\endgroup\$ – ike Dec 27 '13 at 1:39
2
\$\begingroup\$

GolfScript: 13, no loops or recursion

.,{,(;{*}*}%?

Admittedly very inefficient. Compute every factorial up to n! and find n in the list. The top of the stack will be -1 if and only if the input was not a factorial.

Changed to a GolfScript answer I liked better because question was closed.

\$\endgroup\$
  • \$\begingroup\$ I'd say the foreach falls into the "loop" category. \$\endgroup\$ – Howard Dec 26 '13 at 21:33
  • \$\begingroup\$ @Howard true. What about Select, though? \$\endgroup\$ – Ben Reich Dec 26 '13 at 21:41
  • 1
    \$\begingroup\$ I don't know - ask the questioner (also range, aggregate and contains are actually loops - although they can be implemented without any loop). As it currently stands the task is not defined as clearly that we can tell. \$\endgroup\$ – Howard Dec 26 '13 at 21:42
  • \$\begingroup\$ I don't know C# so I don't know enough to determine what is or is not a loop. \$\endgroup\$ – ike Dec 27 '13 at 1:40
1
\$\begingroup\$

GolfScript, 32

Plain approach using recursion (no loops, also no internal loops) and exactly one if:

~1{1$1$%!@2$/*\)1$2<{;}{f}if}:f~

Test the code online. It'll print 1 if the input is a factorial number, 0 if not.

We can hide also the if using string evaluation:

~1{1$1$%!@2$/*\)1$2<'f;'1/=~}:f~
\$\endgroup\$
1
\$\begingroup\$

Ruby, 46 characters (26 points?)

f=->x,m{x>1 ?f[x/m,m+1]:x==1}
p f[gets.to_r,1]

This version is pretty straightworward. It divides by successive integers until the number drops at one or below using bignum rational arithmetic, then returns whether it's exactly one, except it uses tail recursion to do so.

If it's allowed to output the condition inverted, use x<1 instead of x==1 for a one-character saving.

The looping version is just 6 characters shorter:

x,m=gets.to_r,1
x/=m+=1 while x>1
p x==1

Also, can I get a 20-point bonus for using a ternary instead of an if statement? If not, can I get it for a pair of short-circuiting boolean operators (53 characters)?

f=->x,m{p x,m;x>1&&f[x/m,m+1]||x==1}

If not, what about an array of functions? This one is too long (even with the bonus) (and unreadable), but it does demonstrate an important point: what does actually count as an if?

f=->x,m{{true=>f,false=>->_,_{x==1}}[x>1][x/m,m+1]}
\$\endgroup\$
1
\$\begingroup\$

Tcl 53 (93-40)

Only int32?

 expr [gets stdin]in{1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800}

Fine.

\$\endgroup\$
0
\$\begingroup\$

Haskell - 49 (or 29 or 9)

This is one bends unwritten rules: It will not halt for non-factorial inputs. In practice it does determine if a number is a factorial or not, but then again theoretically you can never know.

main=getLine>>=print.(`elem`scanl1(*)[1..]).read

Edit: sorry for initially not reading the problem description.

\$\endgroup\$
  • 1
    \$\begingroup\$ The task is not about calculating the n-th factorial but to check if n is a factorial. \$\endgroup\$ – Howard Dec 26 '13 at 21:29
  • \$\begingroup\$ Thanks and sorry @Howard. I guess I thought the bolded text included the important parts. \$\endgroup\$ – shiona Dec 26 '13 at 21:47
0
\$\begingroup\$

Haskell, 31 = (71C - 20 - 20)

No if statements, no recursion.

c n=n`elem`[product[1..n]|n<-[1..n]]
main=do;s<-getLine;print$c$read s
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.