Loopy Loops
March 18, 2011
I don’t like this silly question. But it has appeared recently on Hacker News and Stack Overflow (C/C++ and Java, and probably other languages but I quit searching), and generated lots of comments on both, and it’s apparently a popular interview question, so we may as well do it here, too:
Print the numbers from 1 to 1000 without using any loop or conditional statements. Don’t just write the printf() or cout statement 1000 times.
Your task is to write the program in your favorite language. Have fun — think of as many solutions as you can, or the wackiest, or the fewest characters in the source file, or some other best-in-category. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Using C++ templates and recursion:
#include
template
void print_num ()
{
std::cout << NUM << std::endl;
print_num ();
}
template
void print_num ()
{
std::cout << 0 << std::endl;
}
int main (int, char**)
{
print_num ();
}
Sorry, new here, this time with correct formatting (hopefully)
Using C++ templates and recursion:
[/sourcecode lang="c++"]
#include
template
void print_num ()
{
std::cout << NUM << std::endl;
print_num ();
}
template
void print_num ()
{
std::cout << 0 << std::endl;
}
int main (int, char**)
{
print_num ();
}
[/sourcecode]
Okay, it’s getting silly, please delete 2 previous messages. (I could really use a preview before my message is actually posted)
#include <iostream>
template <int NUM>
void print_num ()
{
std::cout << NUM << std::endl;
print_num<NUM-1> ();
}
template <>
void print_num<0> ()
{
std::cout << 0 << std::endl;
}
int main (int, char**)
{
print_num<1000> ();
}
[…] today’s Programming Praxis, our goal is to print the numbers 1 through 1000 without using loops or […]
My Haskell solution (see http://bonsaicode.wordpress.com/2011/03/18/programming-praxis-loopy-loops/ for a version with comments):
import Control.Exception import Control.Monad.State loopy1 :: IO () loopy1 = mapM_ print [1..1000] loopy2 :: IO () loopy2 = f 1 where f 1000 = print 1000 f n = print n >> f (n + 1) loopy3 :: IO () loopy3 = handle (\DivideByZero -> return ()) $ f 1 where f n = seq (div n (1001 - n)) print n >> f (n + 1) loopy4 :: IO () loopy4 = evalStateT (do10 . do10 . do10 $ next) 1 where next = (liftIO . print =<< get) >> modify succ do10 f = f >> f >> f >> f >> f >> f >> f >> f >> f >> fI feel as though this might be cheating:
A recursive C solution with xor.
#include int func(int i,int m) { fprintf(stdout,"%d\n",i); return((!(i^m))||func(i+1,m));} int main(int argc,const char** argv){func(1,1000); return(1);}A recursive C solution with xor. (This time hopefully correctly formatted.)
#include <stdio.h> int func(int i,int m){ fprintf(stdout,"%d\n",i); return((!(i^m))||func(i+1,m));} int main(int argc,const char** argv){func(1,1000); return(1);}Goto considered harmful – not. :-)
Or is goto considered a loop construct?
#include <stdio.h> #include <stdlib.h> int doexit(){ exit(0); return(1);} int main(int argc,const char** argv) { int i=1; start: fprintf(stdout,"%d\n",i); (!(i^1000)) && doexit(); ++i; goto start; return(0); }My silly solution :)
Prints 1 to 20 numbers.
#lang racket
(require web-server/private/timer)
(define num 1)
(define timer1 -1)
(define (action)
(display num)
(display " ")
(set! num (+ num 1))
(set! timer1 (start-timer 1 action))
)
(define (stop-action)
(cancel-timer! timer1))
(start-timer-manager)
(action)
(start-timer 20 stop-action)
Codepad doesn’t seem to be working for me today, so I used github instead.
I had a hard time telling exactly what counted and what was cheating on this one :-)
Graham: The definition of cheating is probably up to the interviewer. You keep writing different solutions until he tells you to stop.
I’m hoping a wily Perl hacker comes along with a seriously code golfed version.
Fair enough!
I’m afraid a wily Perl hacker comes along with a seriously code golfed version.
No recursion, no exceptions, no short-circuiting.
Just 1000 is 10 times 10 times 10.
And 10 is 2 times 5.
And a counter thunk.
(define (compose f g) (lambda (a) (f (g a)))) (define (five* o) (lambda () (o) (o) (o) (o) (o))) (define (two* o) (lambda () (o) (o))) (define (three-deep f a) (f (f (f a)))) (define (n) (let ((n 1)) (lambda () (display n) (newline) (set! n (+ n 1)))))Call thus. (Tested with ikarus.)
wow, great solution Jussi Piitulainen , never thought of this approach.
cheers
import sys _ = map(sys.stdout.write,map('{}\n'.format,range(1,1000)))Let’s start the Perl ball rolling:
perl -e “print join(‘, ‘, 1 .. 1000)”
Best I can do without resorting to the optional “say”
Shaved one character off the above:
This is sort of like Jussi Piitulainen’s solution:
(define ten (lambda (f) (lambda (start increment) (let ((new-inc (quotient increment 10))) (f start new-inc) (f (+ start (* increment 2)) new-inc) (f (+ start (* increment 3)) new-inc) (f (+ start (* increment 4)) new-inc) (f (+ start (* increment 5)) new-inc) (f (+ start (* increment 6)) new-inc) (f (+ start (* increment 7)) new-inc) (f (+ start (* increment 8)) new-inc) (f (+ start (* increment 9)) new-inc)))))Now call it as ((ten (ten (ten (lambda (n . not-used) (format #t “~a ” n))))) 1 100)
Oops. I just noticed that I dropped a line. Insert
(f (+ start increment) new-inc)
between lines 5 and 6.
;;; In Common Lisp
;Termination of count – just print it out.
(defmethod mcount ((n (eql 1000)))
(format t “~&~A~%” 1000))
; Generic counting – start at n and recurse to count up from there.
(defmethod mcount ((n t))
(format t “~&~A~%” n)
(mcount (1+ n)))
; Start counting from 1.
(mcount 1)
In Clojure the following does the trick at the REPL (because of the implied print):
(range 1 1001)
But if you also disallow the built-in range function, then the following is a nice functional way to actually generate the sequence:
(take 1000 (iterate inc 1))
For fun, here are a few more.
from __future__ import print_function # 1 y = lambda n: (n-1 and y(n-1)) or print(n) y(1000) # 2 print('\n'.join(reduce(lambda a,b: a + [str(len(a)+1)],[0]*1000,[]))) # 3 - This works up to 100, but exceeds the stack limit when I try to do it up to 1000. (What do I expect for # recursive regular expression substitutions.) I've not tried changing the stack limit. (To go up to 1000, # change the {1,2} in the regex pattern to {1,3} import re pat = re.compile(r'(?<!\d)\d{1,2}$') f = lambda o: pat.sub(f, o.group() + '\n' + str(int(o.group()) + 1) ) print(f(re.search('.', '1')))If you’re recursive solution isn’t considered cheating, then these variations shouldn’t be.
(define (display-line n) (display n) (newline) n) (define (f n) ;; call/cc loop (let* ((restart #f) (answer (display-line (call/cc (lambda (k) (set! restart k) 1))))) (if (not (= n answer)) (restart (+ answer 1))))) (f 1000) (define (g n) ;; cps loop (define (h n done) (if (zero? n) (done) (h (- n 1) (lambda () (display-line n) (done))))) (h n (lambda () 'done))) (g 1000)Erm, that should be “your”
Thanks, guys. I have now worked out a general system for
making any fixed number of repetitions of a transformation
(here, successor, with output) from zero, one, addition
and multiplication. The zero is a bit redundant. Here are
the building blocks.
(define (o m n) ;addition (lambda (f) (lambda (a) (call-with-values (lambda () ((n f) a)) (lambda (f a) ((m f) a)))))) (define (x m n) ;multiplication (lambda (f) (lambda (a) (call-with-values (lambda () ((m (lambda (a) (call-with-values (lambda () ((n f) a)) (lambda (_ a) a)))) a)) (lambda (_ a) (values f a)))))) (define (zero f) (lambda (a) (values f a))) (define (one f) (lambda (a) (values f (f a))))Here are some auxiliaries that double as examples of the
use of the system.
Here is the answer to the interview question.
And here is a demonstration of the generality, 314 being
2224 in base five.
(define three-hundred-and-fourteen ;in base five (o (x two (cube five)) (o (x two (square five)) (o (x two five) four)))) ((three-hundred-and-thirteen out) 1)The system passes on and finally returns the transformation
procedure and the next value. This was a bit tricky in the
multiplication procedure, and is a bit spurious in the end.
Er, -fourteen in the last line, of course, not -thirteen.
Jussi: You’re hired.
def do2 yield;yield end def do5 yield;yield;yield;yield;yield end x=0 do2{do5{do2{do5{do2{do5{x+=1;puts x}}}}}}def do10 yield;yield;yield;yield;yield;yield;yield;yield;yield;yield end x=0 do10{do10{do10{x+=1;puts x}}}(define (one->1000 n)(/ n (- 1001 n))
(display n)
(newline)
(one->1000 (+ 1 n)))
Feels like cheating.
praxis.ss
In F#, tail call in continuation style
let rec loopy n cont = match n with | 1 -> cont 1 | _ -> loopy (n-1) (fun x -> printfn "%A" x cont n ) loopy 1000 (fun x -> printfn "%A" x x )To paraphrase a well-known programming quote, there are two ways of solving this exercise: write or program that obviously has no loops or conditionals, or write a program that has no obvious loops or conditionals. In the example below, I’ve chosen the latter :)
It’s based on lambda calculus and is written in Coffeescript rather than plain Javascript to keeps things slightly readable. It takes about 40 seconds to run in Chrome.
And of course the quote should start with ‘write a program’ rather than ‘write or program’. I wish there was an edit option on these comments.
Here is my solution in python3, I’m not sure if the conditions are kept in the background.
list_of_ints = list(range(1,1001))
print(*list_of_ints)http://dev.mysql.com/doc/world-setup/en/world-setup.html
Java version:
import java.util.Arrays;
public class LoopyPrint {
public static void printNumbers(final int current, final int target) {
int index = (current – 1) / target;
Arrays.asList(new Runnable() {
@Override
public void run() {
System.out.println(current);
printNumbers(current + 1, target);
}
}, new Runnable() {
@Override
public void run() {
}
}).get(index).run();
}
public static void main(String[] args) {
printNumbers(1, 1000);
}
}
#include
#include
#include
jmp_buf place;
void again(int i) {
longjmp(place,i);
}
int main(int argc, char** argv) {
int i=1+setjmp(place);
printf(“%4d “,i);
(*(&again+(&exit-&again)*(i/1000)))(i);
return 0;
}
With church numerals:
((λ (m)
((λ (t)
((λ (o)
((o (λ (x) (display x) (+ x 1))) 1))
(m (m t t) t)))
(m (λ (f) (λ (x) (f (f x))))
(λ (f) (λ (x) (f (f (f (f (f x))))))))))
(λ (n m)
(λ (f) (λ (x) ((m (n f)) x)))))
Here’s a solution in erlang:
-module(loopy).
-export([loopy/0]).
loopy()->
loopy(1).
loopy(1000)->
io:format(“1000\n”);
loopy(N)->
io:format(“~B\n”,[N]),
loopy(N+1).
You could get away without the extra noargs loopy function and simply call loopy/1 yourself (after exporting it, of course).
C#:
static void Main(string[] args)
{
Enumerable.Range(1, 1000).Select(x => { Console.Write(x); return x; }).ToArray();
}
public Integer count(Integer i){
System.out.println(i);
return i < 1000 ? count(i++) : null;
}
public static void main(String[] args){
count(1);
}
Apologies … i totally did *not* read the HOWTO: Posting Source Code section. Don’t hate me … too much.
‘PHP!
print_r((array_fill(1, 1001, ”)));
in ML:
fun count(0) = Int.toString(0)
| count(n) = Int.toString(n) ^ ” ” ^ count(n-1);
print (count 1000);
The solution is in php
function f_0($x) {
$res = (int)($x/1000);
print $x.”\n”;
$res = “f_”.$res;
$res(++$x);
}
function f_1($y) {
print $x.”\n”;
}
f_0(1);
No arrays, no maps, no recursion:
echo H4sIAFS6jE0AA+3Tuw1AMQhD0Z5pyD/Zf7Es4Db3SU8+lTsjBJnvFUAFNEAHDMAELMAGHECod1Snrc5ErVyN7w53uOPbjshSWx9z7ePk5PTXFBf4WqqcuwsAAA== | base64 -d | gunzip
//using C#
class Program
{
static void Main(string[] args)
{
try
{
int i = 1, j = 1000;
Print(ref i, ref j);
}
catch (Exception ex){//do nothing}
static void Print(ref int i, ref int j)
{
int x = i / j;
Console.WriteLine(i.ToString());
i++;
j–;
Print(ref i, ref j);
}
}
# include
using namespace std;
struct acc{
static int a;
acc()
{
cout<<a++<<endl;
}
};
int acc::a=1;
int main()
{
acc b[1000];
return 0;
}
#include
int myexit() {
exit(0);
}
void foo(int i) {
(1000 – i) || myexit();
printf(“%d\n”, ++i);
foo(i);
}
int main() {
foo(0);
return 0;
}
you have used recursion
yes
In C. No loops, conditionals, recursion, global variables or assignments; printf only called once (statically) and only 19 lines. (It’s actually shorter if you leave the macro out…) Undoubtedly the formatting will be screwy, but I see no ‘preview’ button here.
#include <stdio.h> int do1(int n){ printf("%d\n", n+1); return n+1; } #define twice(name, call) int name(int n){ return call(call(n)); } twice(do2, do1) twice(do4, do2) twice(do8, do4) twice(do16, do8) twice(do32, do16) twice(do64, do32) twice(do128, do64) twice(do256, do128) twice(do512, do256) int main(void){ do512(do256(do128(do64(do32(do8(0)))))); /* 1000[10]=1111101000[2] */ return 0; }public static void main(String[] args) {
// TODO Auto-generated method stub
printFromUpto(1,1000);
}
public static void printFromUpto(int start,int last){
System.out.println(start);
try{
int x = 1/(last-start);
printFromUpto(start+1, last);
}catch(Exception e){
return;
}
Solution in Javascript:
var F = [loop, exit];
function exit() { return; }
function loop(n) {
console.log(n);
F[Math.floor(n / 1000)](n + 1);
}
f(1);
print (1..1000);
Any kind of recursion require a condition to stop. So let’s be trivial:
Loopy.java
/home/fabio/Desktop/Loopy.java
1 /** 2 Loopy Loops 3 4 Print the numbers from 1 to 1000 without using 5 any loop or conditional statements. 6 */ 7 public class Loopy 8 { 9 public static void main(String args[]) { 10 loopy(); 11 } 12 13 private static void loopy() { 14 lloopy(0); 15 lloopy(1); 16 lloopy(2); 17 lloopy(3); 18 lloopy(4); 19 lloopy(5); 20 lloopy(6); 21 lloopy(7); 22 lloopy(8); 23 lloopy(9); 24 } 25 26 private static void lloopy(int i) { 27 llloopy(10 * i + 0); 28 llloopy(10 * i + 1); 29 llloopy(10 * i + 2); 30 llloopy(10 * i + 3); 31 llloopy(10 * i + 4); 32 llloopy(10 * i + 5); 33 llloopy(10 * i + 6); 34 llloopy(10 * i + 7); 35 llloopy(10 * i + 8); 36 llloopy(10 * i + 9); 37 } 38 39 private static void llloopy(int i) { 40 lllloopy(10 * i + 0); 41 lllloopy(10 * i + 1); 42 lllloopy(10 * i + 2); 43 lllloopy(10 * i + 3); 44 lllloopy(10 * i + 4); 45 lllloopy(10 * i + 5); 46 lllloopy(10 * i + 6); 47 lllloopy(10 * i + 7); 48 lllloopy(10 * i + 8); 49 lllloopy(10 * i + 9); 50 } 51 52 private static void lllloopy(int i) { 53 System.out.println(1 + i); 54 } 55 } 56 57 58either
loopy.rkt
/home/fabio/Desktop/loopy.rkt
#include <iostream> using namespace std; int p1(int n); int p(int n) { if(n>=1001) return 0; cout<<n<<endl; p1(++n); return 0; } int p1(int n) { if(n>=1001) return 0; cout<<n<<endl; p(++n); return 0; } int main() { int n=1; p(n); return 0; }public static void main(String[] args) {
printnum(1000);
}
private static void printnum(int num) {
if(num > 1){
printnum(num -1);
}
System.out.println(num);
}
good old c :
#include
int main(){
static int i = 1;
static int j = 1001;
printf(“%d\n”,i++);
return (j-i && main());
}
did mine in java, no loops or conditional statements!! :D
class NoLoops { static int i =1; public static void main(String[] args) { m04(); } public static void m01() { System.out.println(i++); } public static void m02() { m01(); m01(); m01(); m01(); m01(); m01(); m01(); m01(); m01(); m01(); } public static void m03() { m02(); m02(); m02(); m02(); m02(); m02(); m02(); m02(); m02(); m02(); } public static void m04() { m03(); m03(); m03(); m03(); m03(); m03(); m03(); m03(); m03(); m03(); } }R5RS SCHEME
R5RS SCHEME
R5RS SCHEME
codepad
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
(define (print function argument)
(display (function argument 1))
(display (function argument 2))
(display (function argument 3))
(display (function argument 4))
(display (function argument 5))
(display (function argument 6))
(display (function argument 7))
(display (function argument 8))
(display (function argument 9))
(display (function argument 10)))
(define (hundred start)
(begin (print + (+ 0 start))
(print + (+ 10 start))
(print + (+ 20 start))
(print + (+ 30 start))
(print + (+ 40 start))
(print + (+ 50 start))
(print + (+ 60 start))
(print + (+ 70 start))
(print + (+ 80 start))
(print + (+ 90 start))))
(begin (hundred 0)
(hundred 100)
(hundred 200)
(hundred 300)
(hundred 400)
(hundred 500)
(hundred 600)
(hundred 700)
(hundred 800)
(hundred 900))
(define (print function argument) (display (function argument 1)) (display (function argument 2)) (display (function argument 3)) (display (function argument 4)) (display (function argument 5)) (display (function argument 6)) (display (function argument 7)) (display (function argument 8)) (display (function argument 9)) (display (function argument 10))) (define (hundred start) (begin (print + (+ 0 start)) (print + (+ 10 start)) (print + (+ 20 start)) (print + (+ 30 start)) (print + (+ 40 start)) (print + (+ 50 start)) (print + (+ 60 start)) (print + (+ 70 start)) (print + (+ 80 start)) (print + (+ 90 start)))) (begin (hundred 0) (hundred 100) (hundred 200) (hundred 300) (hundred 400) (hundred 500) (hundred 600) (hundred 700) (hundred 800) (hundred 900))run the code here
C++, using recursion, no logic operators, no exceptions, using function pointers and the global initialization convention (and a little too much space).
#include
using namespace std;
typedef void (*func_type)(int);
int offsets[1002];
func_type funcs[2];
void print(int a) {
cout << a++ << endl;
funcs[offsets[a]](a); // call the function determined by the value of a.
}
void nullfunc(int a) {} // A do-nothing function to terminate the recursion.
int main (int argc, const char * argv[])
{
// Initialize the jump table.
funcs[0] = print;
funcs[1] = nullfunc;
offsets[1001] = 1; // set the last one to nullfunc. and the rest of the array is ZERO since it's a global variable.
print(1);
return 0;
}
FORTH version
: 1.n 1+ dup . ; : 2.n 1.n 1.n ; : 4.n 2.n 2.n ; : 8.n 4.n 4.n ; : 16.n 8.n 8.n ; : 32.n 16.n 16.n ; : 64.n 32.n 32.n ; : loopy-loop 0 64.n 32.n 4.n ;Forgot to drop the value on the stack, and also didn’t notice it’s one to 1000. Easily fixed…
: 1.n 1+ dup . ; : 2.n 1.n 1.n ; : 4.n 2.n 2.n ; : 8.n 4.n 4.n ; : 16.n 8.n 8.n ; : 32.n 16.n 16.n ; : 64.n 32.n 32.n ; : 128.n 64.n 64.n ; : 256.n 128.n 128.n ; : 512.n 256.n 256.n ; : loopy-loop 0 512.n 256.n 128.n 64.n 32.n 8.n drop ;In C# using recursion/delegates:
private static readonly Action<int>[] actions = new Action<int>[] { PrintTo1000, n => {} }; public static void PrintTo1000(int n) { Console.WriteLine (n); actions [(int)(((float)n) / 1000.0)] (n + 1); }usage: PrintTo1000 (1);