3n+1 contest (challenge #100 from http://acm.uva.es/problemset)

[rueben26]

GnuVince posted a link to this page with many many contests (almost 1,000).
I decided to take on Challenge #100 (http://acm.uva.es/p/v1/100.html), and did it in perl.

Let me say that the rules of the contest are not written very well. You need to find how many cycles occur for each number between each of two given integers. Print the two integers, and the count of the max number of cycles for any one of the numbers.

My poorly written perl code:

#!/usr/bin/perl

$start_num="$ARGV[0]";
$end_num="$ARGV[1]";
$count=1;

# Check that there are two passed arguments.
if (( $start_num == "") || ($end_num == ""))
{
print "Usage: $0 [starting integer] [ending integer]\n\n";
exit 1;
}

# Verify that the $start_num is smaller than the $end_num
if ( $end_num <= $start_num)
{
print "Usage: $0 [starting integer] [ending integer]\n";
print "Starting integer must be larger than ending integer..\n\n";
exit 1;
}

# Loop thru all of the integers between $start_num and $end_num
for $i ($start_num .. $end_num)
{
$curr_cycle_length=get_cycle_length($i);
if ( $curr_cycle_length > $max_cycle_length)
{
$max_cycle_length = $curr_cycle_length;
}
}

print "$start_num $end_num $max_cycle_length\n";
exit 0;

sub get_cycle_length
{
my (@num_array) = @_;
$num=$num_array[0];

$count=1;

while ( $num != 1 )
{
# If the number modulus is one, then the number is odd.
if ( $num % 2 == 1 )
{
$num=(3 * $num) + 1;
}

# Else the number is even.
else
{
$num=$num / 2;
}

# Increment the counter.
$count++;
}

#print "$count length for the number $num_array[0]\n";
return $count;
}



Anyone else up for it?

[inkedmn]

ooh...

this'd be a fun thing to try to hack out in C++...

my code will be up as soon as i can hack it out :)

[PrBacterio]

In OCaml...
let cycle_length start_num =
let rec cycle accumulator k =
if k == 1 then (* done *)
accumulator
else if (k mod 2) == 0 then (* even *)
cycle (accumulator + 1) (k / 2)
else (* odd *)
cycle (accumulator + 1) (3 * k + 1)
in
cycle 1 start_num

let maximum_cycle_length start_idx end_idx =
let rec iterate accumulator k =
if k > end_idx then
accumulator
else
let len = cycle_length k in
if len > accumulator then
iterate len (k + 1)
else
iterate accumulator (k + 1)
in
iterate (cycle_length start_idx) (start_idx + 1)

let main () =
try while true do
let invals = read_line () in
if not (String.contains invals ' ') then
raise (Failure "illegal_in_fmt");
let nstart = int_of_string
(String.sub invals 0 (String.index invals ' '))
and nend = int_of_string
(String.sub invals (String.rindex invals ' ' + 1)
(String.length invals - String.rindex invals ' ' - 1)) in
if nend < nstart ||
nend <= 0 ||
nstart <= 0 then raise (Failure "illegal_arguments");
let maxcycle = maximum_cycle_length nstart nend in
print_string (string_of_int nstart ^ " " ^ string_of_int nend ^
" " ^ string_of_int maxcycle);
print_newline ()
done with
| End_of_file -> ()
| Failure "illegal_arguments"
| Failure "int_of_string" -> prerr_string "illegal input format"
| Failure "illegal_in_fmt" -> prerr_string "illegal input values"
| _ -> prerr_string "unexpected error"

let _ = main ()

[rueben26]

Originally posted by PrBacterio
In OCaml...

Dang, you guys are good at OCaml.... Looks like an OK language.

I think I might use this challenge as a excuse to learn PHP.

[MJPhill]

Here is my java code, please don't laugh too much ;) :


import java.io.*;

public class Challenge100 {
public static void main (String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the first number");
int i = Integer.parseInt(input.readLine());
System.out.println("Enter the second number");
int j = Integer.parseInt(input.readLine());
System.out.println(i+" "+j+" "+max_cycle_length(i,j));
}
public static int max_cycle_length(int i, int j) {
assert ((0 < i) && (0 < j)) : "i and j must be greater than 0";
assert ((i< 1000000) && (j <1000000)) : "i and j must be less than 1000000";
assert (i <= j) : "i must be less than or equal to j";
int cycle = 1;
while (i <= j) {
int temp = 1;
int n = i;
while (n != 1) {
if (n%2 == 1) n = 3*n+1;
else n = n/2;
temp++;
//System.out.println(n);
}
if (temp > cycle) cycle = temp;
i++;
}
return cycle;
}
}

[PrBacterio]

OK I'm bored, here it is in Scheme...
(define (cycle-length k)
(let iterate ((c k) (accum 1))
(cond
((= c 1) accum)
((even? c)
(iterate (/ c 2) (+ 1 accum)))
(else
(iterate (+ 1 (* 3 c)) (+ 1 accum))))))

(define (max-cycle-length start end)
(let iterate ((i (+ 1 start)) (accum (cycle-length start)))
(if (> i end)
accum
(let ((c-len (cycle-length i)))
(if (> c-len accum)
(iterate (+ 1 i) c-len)
(iterate (+ 1 i) accum))))))

(define (main)
(let loop ()
(let* ((i (read))
(j (read))
(n (max-cycle-length i j)))
(if (not (or (eof-object? i)
(eof-object? j)))
(begin
(display i) (display #\space)
(display j) (display #\space)
(display n) (display #\newline)
(loop))))))

[_underdog]

I have not really used assertions too much in Java, but I think this would not be a case where you would want to. According to Sun http://java.sun.com/j2se/1.4.1/docs/guide/lang/assert.html#usage Do not use assertions for argument checking in public methods.
Argument checking is typically part of the published specifications (or contract) of a method, and these specifications must be obeyed whether assertions are enabled or disabled. Another problem with using assertions for argument checking is that erroneous arguments should result in an appropriate runtime exception (such as IllegalArgumentException, IndexOutOfBoundsException, or NullPointerException). An assertion failure will not throw an appropriate exception.

[MJPhill]

I think I understand what you are saying. However, without the assertion, if a negative number is input for i, the result is an infinite loop. Also, for the case where i > j, the result returned without the assertion is one, which is often inaccurate. Assertions seemed the best way to avoid these situations, but maybe there is a better way to do it?

[_underdog]

I would just test for those conditions with an if statement and display an error message or throw an approriate exception. If you used assertions to verify user input what happens if someone runs your program with assertions disabled, which is the default mode.

[MJPhill]

Ok, I got it, thanks for your input.

[rueben26]

Does anyone see any value in me posting more of the contests to this forum? Anyone else have any good ideas for more competitions?

I forgot how much fun it is to program for fun....

[inkedmn]

C++ :



#include <iostream>
#include <stdlib.h>
#include <string>

using namespace std;

bool validInput(int i, int j) {
if (i <= 0 || i > 1000000) {
return false;
}
if (j <= 0 || j > 1000000) {
return false;
}
if (i > j) {
return false;
}
return true;
}

int maxCycleLength(int i) {
int counter = 0;
while (i != 1) {
if (i % 2 != 0)
i = (3 * i) + 1;
else
i = i / 2;
counter++;
}
return counter;
}

int main() {
int i, j, cycleLength;

int maxLength = 0;
cout << "Enter the first integer: ";
cin >> i;
cout << "Enter the second integer: ";
cin >> j;
if (!validInput(i, j)) {
cout << "Invalid input" << endl;
return 0;
}
for (int n = i; n <= j; n++) {
cycleLength = maxCycleLength(n);
if (cycleLength > maxLength)
maxLength = cycleLength;
}
cout << i
<< " "
<< j
<< " "
<< maxLength
<< endl;
}


:)

[inkedmn]

python:


# 3n + 1 challenge for cf
# coded by inkedmn

import sys

def validData(first, second):
if first > second:
print "First integer must be the smaller of the two"
return False
elif first < 1 or first > 1000000:
print "First integer isn't valid"
return False
elif second < 1 or second > 1000000:
print "Second integer isn't valid"
return False
return True

def getCycleLength(num):
counter = 0
while num != 1:
if num % 2 != 0:
num = (num * 3) + 1
else:
num = num / 2
counter += 1
return counter


try:
first = int(raw_input("First integer "))
second = int(raw_input("Second integer "))
except ValueError:
print "enter integers, tardmo..."
sys.exit(1)

temp = first
maxCycle = 0

if not validData(first, second):
sys.exit(1)
while temp < second:
cycle = getCycleLength(temp)
if cycle > maxCycle:
maxCycle = cycle
temp += 1
print first, second, maxCycle

[madMoney]

my own java version
using recursion of all things!


public class contest
{
static contest c;

public static void main(String[] args)
{

if (args.length == 2)
{
int a1 = Integer.parseInt(args[0]);
int a2 = Integer.parseInt(args[1]);
if (a1 < a2)
{
c = new contest();
System.out.println(a1 + " " + a2 + " " + c.max_len(a1, a2));
}
else
{
System.out.println("Usage: java contest <start integer> <end integer>\n" +
"The start integer must be less than the end");
}
}
else
{
System.out.println("Usage: java contest <start integer> <end integer>");
}
}

public int max_len(int start, int end)
{
int max = 0;
for (int i=start; i<end; i++)
{
//System.out.println(i);
int a = get_len(i, 1);
if (a > max) max = a;
}
return max;
}

public int get_len(int n, int c)
{
//System.out.println("\t"+n);
return ( n == 1 ? c : ((n % 2 == 1) ? get_len(3 * n + 1, ++c) : get_len(n / 2, ++c)) );
}
}

[inkedmn]

8-space tabs!!

/me holds up cross and slowly backs away ;)

[madMoney]

and /me rolls eyes

sorry guys, i prefer it!

[iDxMan]

Anyone else up for it?

I must have missed your post, but I hacked up a very similar perl version last night. (...its going to be very similar in any language -- not much to it)


Although mine reads a file for input.


#!/usr/bin/perl

die "Usage $0 file \n" if (!@ARGV);

$DEBUG = 0;

while(<>)
{
chomp;
s/\r//g;
next if (/^\s*$/);
next if (/^\s*#/);
($i, $j) = split(/\s+/);


$end = $j;
$start = $i;
$len = 0;
for ($start; $start <= $end; $start++)
{
print "PRE: start=$start, len=$len\n" if $DEBUG;
$tmp = get_count($start);
$len = $tmp if ($tmp > $len);
print "POST: start=$start, len=$len\n" if $DEBUG;
}


print "$i - $j\tMax Cycle Length = $len\n";

}




# {{{ get_count()
sub get_count($)
{
$n = $_[0];
$n =~ tr/0-9//cd;
$count = 0;

while ($n)
{

++$count;
if ($n eq 1) {
last;
}

## non-zero = odd
if ($n % 2) {
$n = (3 * $n) + 1;
}
else {
$n = $n / 2;
}

}

return ($count);
}
# }}}

[iDxMan]

Originally posted by rueben26
I think I might use this challenge as a excuse to learn PHP.


Just about to do that myself, but I'm off for vacation tomorrow.. (hooray beach!) It would almost be identical to the perl versions though..

-r

[jamessan]

Here's my perl version:#!/usr/bin/perl

my $output = "";
while (<STDIN>) {
last if /^$/;
my @nums = split " ";
my $res = "";
if ($#nums != 1 || ! is_valid($nums[1]) || ! is_valid($nums[2])) { next; }
$output .= (($res = compute($nums[1],$nums[2])) ne undef) ? "$res\n" :
"";
}
print "$output";

sub is_valid {
my $test = shift;
return ($test <= 1000000 && $test > 0);
}

sub compute {
my $start = shift;
my $end = shift;
if ($start > $end) { return undef; }
my $res = "$start $end ";
$res .= max_count($start, $end);
return $res;
}

sub max_count {
my $start = shift;
my $end = shift;
my $count = 0;
for (;$start <= $end;++$start) {
my $num = count($start);
unless ($num < $count) { $count = $num; }
}
return $count;
}

sub count {
my $num = shift;
my $iter = 1;
while ($num != 1) {
++$iter;
if ($num % 2 == 0) { $num = $num/2; }
else { $num = 3*$num + 1; }
}
return $iter;
}*Note: I only did this in perl because I am using perl for work and was bored.

[slidewinder]

Here's a stab at it in Haskell:

import IO
import Char

check f = check' f 1 where
check' g i | g == 1 = i
| g `mod` 2 > 0 = check' (3 * g + 1) (i + 1)
| otherwise = check' (g `div` 2) (i + 1)

results x = putStrLn (min ++ " " ++ max ++ " " ++ high)
where
(min:max:_) = words x
high = show (maximum (map check [(read min)..(read max)]))

main = do
inp <- hGetContents stdin
mapM_ results (lines inp)

[php_brian]

The problem coded in PHP:


<?php

function calculateCycleLength($num) {
/* an array to store the cycles */
$cycles[] = $num;

while($num != 1) {
if(($num % 2) == 1) $num = (3 * $num) + 1;
else $num = $num / 2;

$cycles[] = $num;
}

return count($cycles);
}

/* read the file of numbers */
$numberSets = file("./numbers.txt");
$countNumberSets = count($numberSets);

for($i = 0; $i < $countNumberSets; $i++) {
/* retrieve the min and max for this set */
list($min,$max) = explode(" ",$numberSets[$i]);

/* convert form string to int */
$min = (int)$min;
$max = (int)$max;

/* get all cycle lengths of numbers */
for($j = $min; $j <= $max; $j++) {
$cycleLengths[] = calculateCycleLength($j);
}

/* get the max cycle length */
sort($cycleLengths);
$maxCycleLength = array_pop($cycleLengths);

/* display answer for set */
echo $min . " " . $max . " " . $maxCycleLength . "
\n";

/* reset the cycles for next set */
unset($cycleLengths);
}

?>

[woodwind]

I like this problem because it's so simple. It involves recursion and finding the maximum value.


def is_even(n): return n%2==0

def f(n):
if n==1: return 1

if is_even(n): return 1 + f(n/2)
else: return 1 + f(3*n+1)

print str(f(22))

i = 900
j = 1000
max = 0
for val in range(i,j+1):
cur = f(val)
if cur > max: max = cur

print str(max)

[skidooer]

Let the golf begin.
My current score: 134


sub r{($_,$x)=@_;$x++;return$x if($_==1);if($_%2){r(3*$_+1,$x)}else{
r($_/2,$x)}};for(shift..shift){$t=r($_,0);$m=$t if($t>$m)}print$m;

[skidooer]

Originally posted by inkedmn
C++

#include <iostream>

class Cycle
{
public:
Cycle(int n)
{
_count = 0;
calculateCycles(n);
}

int getNumberOfCycles()
{
return _count;
}

private:
void calculateCycles(int n) {
_count++;
if(n == 1)
return;

if(n % 2)
calculateCycles(3 * n + 1);
else
calculateCycles(n / 2);
}

int _count;
};

inline int max(int x, int y)
{
return x > y ? x : y;
}

int main()
{
int i, j, r = 0;

std::cin >> i;
std::cin >> j;
for(i; i < j; i++) {
Cycle c(i);
r = max(c.getNumberOfCycles(), r);
}

std::cout << r << std::endl;
}

[Ohara]

I'm afraid that Python appears nearly as good for golfing as Perl <urgh> ;-). Here's a 3 liner that conforms (more or less) to the VPC spec, using woodwind's functional version as a base.

Skidooer, your version looks like it only takes a single pair of numbers - is this correct??


## http://acm.uva.es/p/v1/100.html
##
## Input:
## 1 10
## 100 200
## 201 210
## 900 1000
##
## Output:
## 1 10 20
## 100 200 125
## 201 210 89
## 900 1000 174

f=lambda n:n==1or 1+(n%2and f(3*n+1)or f(n/2))
def x((i,j)):print i,j,max(map(f,range(i,j+1)))
def m(d):a=map(int,d.split());map(x,zip(a,a[1:])[::2])

if __name__ == "__main__":
indata = '''
1 10
100 200
201 210
900 1000
'''

m(indata)