Loopy Loops
March 18, 2011
The simplest solution that comes to mind uses the range
function from the Standard Prelude:
(define (f n) (range 1 (+ n 1)))
That returns a list, which the REPL prints surrounded by parentheses. If you object to that format, you can print the numbers yourself:
(define (f n)
(for-each (lambda (x) (display x) (newline)) (range 1 (+ n 1))))
If you object to range
because it hides a loop, you can write a recursive function. Recursion can do anything a loop can do, and if you’re clever you can use an and
in place of an if
:
(define (f n)
(and (< 1 n) (f (- n 1)))
(display n) (newline))
That counts down from n, so it has to stack all the recursive calls and produce output as the stack unwinds, which means that if n is too large it will fail when stack space is exhausted. Here’s an alternate version, which uses an auxiliary function (defined inline in a named-let) and an auxiliary variable that counts up as the main variable counts down:
(define (f n)
(let f ((n n) (i 1))
(display i) (newline)
(and (< 1 n) (f (- n 1) (+ i 1)))))
That returns #f
when both arms of the and
statement fail, which is printed by the REPL. This version does the same thing, but eliminates the #f
by calling void
(void
is not R5RS Scheme, but is present in most Scheme systems; the codepad version of the exercise shows an implementation of void
):
(define (f n)
(define (g i)
(display i) (newline)
(and (< i n) (g (+ i 1))))
(g 1) (void))
That solution is probably most in the spirit of the exercise. If you don’t like the use of and
to stop the recursion, you’ll like this even less: stop the recursion by throwing a divide-by-zero error:
(define (f n)
(define (g n i)
(let ((j (/ n)))
(display i) (newline)
(g (- n 1) (+ i 1))))
(g n 1))
I’ll stop now, before I get too silly. You can run the programs shown above at http://programmingpraxis.codepad.org/icuEmmu2.
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):
I feel as though this might be cheating:
A recursive C solution with xor.
A recursive C solution with xor. (This time hopefully correctly formatted.)
Goto considered harmful – not. :-)
Or is goto considered a loop construct?
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.
Call thus. (Tested with ikarus.)
wow, great solution Jussi Piitulainen , never thought of this approach.
cheers
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:
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.
If you’re recursive solution isn’t considered cheating, then these variations shouldn’t be.
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.
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.
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.
(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
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.
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
either
loopy.rkt
/home/fabio/Desktop/loopy.rkt
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
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))
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
Forgot to drop the value on the stack, and also didn’t notice it’s one to 1000. Easily fixed…
In C# using recursion/delegates:
usage: PrintTo1000 (1);