Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Solve using your language of choice

Name: Anonymous 2011-04-13 9:05

http://i56.tinypic.com/9qlh52.png

my solution in Java

import java.io.*;
import java.util.*;

public class ProblemF {
   
    public static void main(String[] args) throws Exception {
        BufferedReader fileIn = new BufferedReader(new FileReader("f.in"));
       
        String line = null;
        while ((line = fileIn.readLine()) != null) {
            int number = Integer.parseInt(line);
            if (number <= 0 || number >= 100000000) {
                break;
            }
            System.out.println(number +" : "+ getOrderedPairs(number));
        }
    }
   
    public static String getOrderedPairs(int number) {
        StringBuffer buff = new StringBuffer();
       
        int pairCount = 0;
        for (int i = 1; i <= number; i++) {
            for (int j = i; j <= number; j++) {
                int sum = getSummation(i, j);
                if (sum == number) {
                    pairCount++;
                    buff.append(" ("+ i +","+ j +")");
                    break;
                } else if (sum > number) {
                    break;
                }
            }
        }
       
        buff.insert(0, pairCount +" :");
       
        return buff.toString();
    }
   
    public static int getSummation(int tempA, int tempB) {
        int a = tempA - 1;
        int b = tempB;
        int sumB = ((b * (b + 1)) / 2);
        int sumA = ((a * (a + 1)) / 2);
        return sumB - sumA;
    }
   
}

Name: Anonymous 2011-04-13 10:01

>>1
Something like:


(defun func (string &optional acc)
  (if lst
    (loop for x from 0 to (1- (length array))
    for i in array do
      (if (eq i ":")
         (func (cdr lst) (cons (aref (1- x) array) acc))))
     acc))

Kinda, that should PROBABLY do it, I haven't tested it though.

Name: Anonymous 2011-04-13 10:21

~:x' : 'x),1>{.),1>\{[.;]+}+/}%{~),>{+}*x=},.,2$@{'('\','*') '}%

Name: Anonymous 2011-04-13 10:21

At first I wrote a naive solution like you, but noticed it was SLOW AS FUCK even when I cranked up the optimization settings:

(asdf:oos 'asdf:load-op '#:iterate)
(use-package '#:iterate)

(declaim (optimize (speed 3) (safety 0)))

(declaim (inline sum-to))
(defun sum-to (a b)
  (declare (fixnum a b))
  ; (loop for i from a to b sum i) ; naive/slow
  (the fixnum (/ (- (* b (1+ b)) (* a (1- a))) 2))
  ;(the fixnum (/ (* (1+ (- b a)) (+ b a)) 2))
  )

;; too slow O(n*n), starts being unusable at ~10^6, when it takes longer than a minute per number
(defun find-all-sums (x)
  (iter outer (for i from 1 to x)
                   (iter (for j from i to x)
                     (when (= (sum-to i j) x)
                       (in outer (collect (print (list i j))))))))

Name: >>5 2011-04-13 10:23

So I wrote this instead:

;; instead we use some math and make it O(n)
(defun find-all-sums (x)
  (sort
   (remove-duplicates
    (iter (with 2x = (* 2 x))
          (for i from x downto 1)
          (for (values div mod) = (truncate 2x i))
          (when (zerop mod)           
            (let* ((a (/ (1- (+ div i)) 2))
                   (b (- (max div i) a)))
              (collect (list b a)))))
    :key #'first)
   #'< :key #'first))

Let's test it on the highest number:

CL-USER> (time (find-all-sums 99999999))
Evaluation took:
  1.469 seconds of real time
  1.468750 seconds of total run time (1.468750 user, 0.000000 system)
  100.00% CPU
  3,541,887,882 processor cycles
  0 bytes consed
 
((309 14145) (592 14154) (4999 14999) (5002 15000) (6539 15580)
 (9877 17249) (10224 17450) (11669 18334) (18347 23164) (19859 24379)
 (28337 31669) (31672 34685) (39319 41784) (40307 42715) (43894 46115)
 (54097 55914) (61464 63069) (65604 67110) (75447 76760) (80487 81719)
 (89454 90564) (109557 110465) (121244 122065) (124132 124934)
 (151879 152535) (164714 165319) (228092 228529) (243104 243514)
 (329882 330184) (364827 365100) (456512 456730) (494949 495150)
 (504952 505149) (684859 685004) (729859 729995) (990049 990149)
 (1010052 1010150) (1369827 1369899) (1515119 1515184) (3030287 3030319)
 (4545444 4545465) (5555547 5555564) (9090904 9090914) (11111107 11111115)
 (16666664 16666669) (33333332 33333334) (49999999 50000000)
 (99999999 99999999))

Much better!

Formatting and user input is up to you (I'm not doing your homework) as it's easy enough to implement.

Name: Anonymous 2011-04-13 10:37


(struct output (n p c)
  #:property prop:custom-write
  (λ (o p _)
    (fprintf p "~a : ~a : " (output-n o) (output-p o))
    (for-each (λ (x) (display x p) (display #\space p)) (output-c o))))

(define (solve n)
  (let ((l (for/list ((a (in-range 0 (add1 n)))
                      #:when #t
                      (b (in-range 0 (add1 n)))
                      #:when (= (Σ values a b) n)
                      (k #(#f)))
             (cons a b))))
    (output n (length l) l)))

(solve 9)
: 9 : 3 : (2 . 4) (4 . 5) (9 . 9)

Name: >>5 2011-04-13 10:37

And some testing:

(defun test-it (n)
  (every (lambda (x) (= x n)) (mapcar (lambda (list) (apply #'sum-to list)) (find-all-sums n))))

;; will print any number where the sum a to b is not equal to what it should be
(loop for i from 1 to 99999999 unless (test-it i) do (print i))

This revealed a bug when handling even numbers, hence the revised version:

(defun find-all-sums (x &aux (2x (* 2 x)))
  (sort
   (remove-duplicates
    (iter (for i from 2x downto 1)
          (for (values div mod) = (truncate 2x i))
          (and (zerop mod)
               (not (zerop (mod div 2)))
               (let* ((a (/ (1- (+ div i)) 2))
                      (b (- (max div i) a)))
                 (collect (list b a)))))
    :key #'first)
   #'< :key #'first))

Name: Anonymous 2011-04-13 11:08


import Control.Applicative
orderedPair x = [(a,b) | (a,b) <- liftA2 (,) [0..x] [0..x], sum [a..b] == x]

Is that what you mena?

Name: Anonymous 2011-04-13 11:12


import Control.Applicative
orderedPairs x = [(a,b) | (a,b) <- liftA2 (,) [1..x] [1..x], sum [a..b] == x]

Name: Anonymous 2011-04-13 11:43


import Control.Applicative

main = interact (unlines . map (format . orderedPairs . check . read) . lines)

check x
    | x < 0 || x > 100000000 = error "you mena haskal?"
    | otherwise = x

orderedPairs x = (x, [(a,b) | (a,b) <- liftA2 (,) [1..x] [1..x], sum [a..b] == x])

format (x,ps) = show x ++ " : " ++ show (length ps) ++ " : " ++ (unwords . map (\(a,b) -> "(" ++ show a ++ "," ++ show b ++ ")")) ps

improved it to do the whole task

Name: Anonymous 2011-04-13 11:45


import Control.Applicative

main = interact (unlines . map (format . orderedPairs . check . read) . lines)

check x
    | x <= 0 || x > 100000000 = error "you mena haskal?"
    | otherwise = x

orderedPairs x = (x, [(a,b) | (a,b) <- liftA2 (,) [1..x] [1..x], sum [a..b] == x])

format (x,ps) = show x ++ " : " ++ show (length ps) ++ " : " ++ (unwords . map (\(a,b) -> "(" ++ show a ++ "," ++ show b ++ ")")) ps

Name: Anonymous 2011-04-13 11:49


main = interact (unlines . map (format . orderedPairs . check . read) . lines)

check x
    | x <= 0 || x > 100000000 = error "you mena haskal?"
    | otherwise = x

orderedPairs n = (n, [(a,b) | a <- [1..n], b <- [a..n], sum [a..b] == n])

format (x,ps) = show x ++ " : " ++ show (length ps) ++ " : " ++ (unwords . map (\(a,b) -> "(" ++ show a ++ "," ++ show b ++ ")")) ps

Name: Anonymous 2011-04-13 20:23


open System

let orderedPairs x = List.rev [ for b = x downto 1 do
                                    for a = b downto 1 do
                                        if (List.sum [a..b]) = x then yield (a, b) ]
let numbers =
    let rec getNumbers x =
        if (0 < x) && (x < 100000000) then x :: getNumbers(int(Console.ReadLine()))
        else []
    getNumbers(int(Console.ReadLine()))

let rec orderedPairsString orderedPairsX =
    match orderedPairsX with
    | (a, b) :: t -> "(" + string(a) + ", " + string(b) + ") " +  orderedPairsString(t)
    | [] -> ""

numbers
|> List.map (fun x -> (x, orderedPairs x))
|> List.map (fun (x, orderedPairsX) -> (x, List.length orderedPairsX, orderedPairsX))
|> List.map (fun (x, orderedPairsXLength, orderedPairsX) ->
                Console.WriteLine("{0} : {1} : {2}",
                                    x, orderedPairsXLength, orderedPairsString orderedPairsX))
|> ignore

ignore(Console.ReadKey())

Name: Anonymous 2011-04-13 21:15

in brainfuck
++++++++[->++++<]>>>++++++[<++++++>-]<++++[->+>
+>+<<<]>>++++>+>,.<<<<.>>>>>++++++++[-<------>]
<[->+>>>+>>>+<<<<<<<]+>+<[>[->+>+<<]>>>[->+>+<<
]>[-<+<+>>]<<+<[-<+>>>>>-<<<<]>[->>>[-<+>>>+<<]
<[->+<]<<]>>>[-]>[->-->+<<]+>[[-]<[-]>]<[[-]+++
+++++++++[-<<<++++<<<++++>>>>>>]<<<<<<<<<<.>>>>
+.-<<<.>>>>>>.<<<<<.<<<.>>>>>>>>>>>++++++++++++
[-<<<----<<<---->>>>>>][-]]>>[-<<+>>]<<<<<<<<->
+<[->[-]>+<<]>>[-<<+>>]<[[-]>>->+<[->[-]>+<<]>>
[-<<+>>]<[[-]<<<<<[-]>>>>>]<[-<<<+>>>>+<]>[-<+>
]<<<]<<]
http://codepad.org/NdgW7mgP
well, it actually solves for only a single digit but algorithm is correct. It just requires a little extra work for inputting and printing multiple digit numbers

Name: Anonymous 2011-04-13 21:45

What I came up with:

tr :: Int -> Int
tr n = n * (n-1) `div` 2
untr :: Int -> Int
untr n' = let n = fromIntegral n' in ceiling $ sqrt (n*2)

f :: Int -> [(Int, Int)]
f n = [(a,b) | b <- [2..n], let b' = tr (b+1), let a' = (b'-n), let a = untr a', tr a == a']

main = do x <- readLn
          print $ f x
          main

Not as good as some of the solutions here, but it solves the biggest case in half the needed time.

Name: Anonymous 2011-04-14 0:58

>>31

OMGOPTIMISED!


open System

let sumAtoB(a, b) = ((a - b - 1) * (a + b)) / -2

let orderedPairs x =
    [ for b = 1 to x do
        let rec checkFrom(n) =
            if n < 1 then []
            elif sumAtoB(n, b) > x then []
            elif sumAtoB(n, b) = x then (n, b) :: checkFrom(n - 1)
            else checkFrom(n - 1)
        yield checkFrom(b) ] |> List.concat
   
let numbers =
    let rec getNumbers x =
        if (0 < x) && (x < 100000000) then x :: getNumbers(int(Console.ReadLine()))
        else []
    getNumbers(int(Console.ReadLine()))

let rec orderedPairsString orderedPairsX =
    match orderedPairsX with
    | (a, b) :: t -> "(" + string(a) + ", " + string(b) + ") " +  orderedPairsString(t)
    | [] -> ""

numbers
|> List.map (fun x -> (x, orderedPairs x))
|> List.map (fun (x, orderedPairsX) ->
                Console.WriteLine("{0} : {1} : {2}",
                                    x, List.length orderedPairsX, orderedPairsString orderedPairsX))
|> ignore

ignore(Console.ReadKey())

Name: Anonymous 2011-04-14 4:18

use v6;
my @G := [\+] 0 .. *;

sub ranges( $t ) {
    my @S;
   
    for 1 .. $t.sqrt +1 -> $mag {
    my $gval = @G[ $mag ];
    my $x = ( $t - $gval ) / $mag;

    if 0 <= $x && $x.Rat.denominator == 1 {
        @S.unshift: [ $x +1, $x + $mag ];
    }
    }

    return @S;
}

for (open 'f.in').lines -> $t {
    return unless 0 < $t <= 100_000_000;

    my @out = $t.fmt: '%d';
    my @S = ranges $t;
 
    @out.push: @S.elems.fmt: ': %d :';
    for @S { @out.push: sprintf('(%d,%d)', $_[0], $_[1]) };

    @out.join(' ').say;
}
Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -