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

2010 Homework No. 3 - findsuss

Name: Anonymous 2010-01-15 22:56

Write a program in the language of your choice that takes a string and inputs "SUSSMAN" for every time those characters appear. In case I'm not being clear, that means output "SUSSMAN" for every 3 's's and 1 'u', 'm', 'a', and 'n' in the string. Inputting "ssssumanssssssssssuman", for example, would print "SUSSMAN" twice. "ssuman", however, would print nothing.

I've written an inelegant solution in C, which I'll post in a second. It tends to crash after execution, however, and I cannot for the life of me figure out what I'm doing wrong. It does everything it's supposed to but refuses to terminate politely. Even stranger, it only happens when there is enough characters for two or more sussmen. I guess the problem is in the susscount loop, but I can't figure out where. Mind giving me a hand, /prog/?

Name: Anonymous 2010-01-16 14:47

>>40
s/1/INT_MAX/

Name: Lisp 2010-01-16 14:52

<?php
$chars = str_split( strtolower($argv[1]) );
foreach($chars as $char)
{
    $char_counts[$char]++;
}

while
(
        $char_counts['s'] >= 3 &&
        $char_counts['u'] &&
        $char_counts['m'] &&
        $char_counts['a'] &&
        $char_counts['n']
)
{
    echo 'SUSSMAN' . "\n";
    $char_counts['s'] = $char_counts['s'] - 3;
    $char_counts['u']--;
    $char_counts['m']--;
    $char_counts['a']--;
    $char_counts['n']--;
}
?>

Name: Anonymous 2010-01-16 14:56

I wonder what Leah Culver's solution would be like.

Name: Anonymous 2010-01-16 14:57


while (<STDIN> =~ m/sussman/ig)
{
  print "sussman\n";
}

i dont realy get what this is about but here it is.

Name: Anonymous 2010-01-16 15:16

>>42
$char_counts['s'] = $char_counts['s'] - 3;
wtf

Name: Anonymous 2010-01-16 15:54

>>45
That's right, she should have used ((char_counts['s']--)--)--.

Name: Anonymous 2010-01-16 16:09

Now making use of PHP FEATURES like variable variables and error suppression !

$s = $u = $m = $a = $n = 0;
foreach (str_split(strtolower($argv[1])) as $c) $$c++;
while (@$_++ < min($s, $u, $m, $a, $n)) print "sussman\n";

Name: Anonymous 2010-01-16 16:23

>>47
Interesting, but suman would incorrectly print one sussman\n.

Name: Anonymous 2010-01-16 16:28

>>47
variable variables
genius!!

Name: Anonymous 2010-01-16 16:33

>>48
Oops !
$s = $u = $m = $a = $n = 0;
foreach (str_split(strtolower($argv[1])) as $c) $$c++;
$s = (int) $s / 3;
while (@$_++ < min($s, $u, $m, $a, $n)) print "sussman\n";

Name: Anonymous 2010-01-16 16:34

>>50
s/$s = (int) $s / 3;/$s = floor($s / 3);/ rather

Name: Anonymous 2010-01-16 16:57

>>38
Array version might be the fastest here. Time to profile!
　　　＿＿＿_　∧ ∧   ／￣￣￣￣￣￣
　～'　＿＿__(,,ﾟДﾟ)＜　OMG OPTIMIZED
　　 ＵU 　 　Ｕ U 　  ＼＿＿＿＿＿＿

　　 　  ∧ ∧　 ／￣￣￣￣
　　　 (,,ﾟДﾟ)＜　VROOM VROOM
　　  　⊂　　⊃　＼＿＿＿＿
　　 　～|　 |
　　  　 し`J

Name: Anonymous 2010-01-16 17:09

>>52
Premature optimizations are the root of all evil.
    -Some fag nobody cares about

Name: Anonymous 2010-01-16 17:14

>>53
Premature optimizations are the root of all evil.
the guy specifically mentions that he is going to profile
IHBT

Name: Anonymous 2010-01-16 17:19

import Control.Monad
import List

findSuss text =
   when (intersect "sussman" text == "sussman")
        (putStrLn "sussman" >> findSuss (text \\ "sussman"))

Name: >>55 2010-01-16 17:34

I fucked up on the last one.

import Control.Monad
import List

findSuss text =
   when (length text - length next == length "sussman") (putStrLn "sussman" >> findSuss next)
   where next = text \\ "sussman"

Name: Anonymous 2010-01-16 17:46

>>56
So when's a while?

Name: EXPERT PROFILER 2010-01-16 17:47

HASKAL RESULTS ARE OUT
My array-based code (>>10) wins for now. Extra points to >>38 who gets very close using elegant arrows.

Everything run with a 91KB text file containing "sussman sussman"... repeated until the file was big enough.
Compiled with ghc --make -02 -auto-all -fforce-recomp -prof findsuss.hs and ran with findsuss findt +RTS -p -sstderr -hd > findtout (on Windows, so the > pipes the output to a file in order to save my emacs console from death). I have the memory allocation profiles (in PDF) for all posts, will post if there's interest.


Run time in seconds (Core 2 Duo laptop)
>>10   >>38   >>35    >>56   >>55  
0.30   0.50   32.07   32.68  44.93

>>35
  22,532,708,420 bytes allocated in the heap
   2,509,842,544 bytes copied during GC
       1,849,172 bytes maximum residency (1725 sample(s))
          86,004 bytes maximum slop
               6 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0: 41396 collections,     0 parallel,  2.61s,  2.65s elapsed
  Generation 1:  1725 collections,     0 parallel,  2.31s,  2.08s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time   26.79s  ( 27.46s elapsed)
  GC    time    4.91s  (  4.73s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.37s  (  0.36s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   32.07s  ( 32.55s elapsed)

  %GC time      15.3%  (14.5% elapsed)

  Alloc rate    841,231,738 bytes per MUT second

  Productivity  83.5% of total user, 82.3% of total elapsed

>>55
  22,534,919,924 bytes allocated in the heap
   1,712,117,048 bytes copied during GC
         243,460 bytes maximum residency (1639 sample(s))
          39,136 bytes maximum slop
               2 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0: 41552 collections,     0 parallel,  2.62s,  2.97s elapsed
  Generation 1:  1639 collections,     0 parallel,  0.36s,  0.49s elapsed

  INIT  time    0.02s  (  0.00s elapsed)
  MUT   time   40.92s  ( 41.43s elapsed)
  GC    time    2.98s  (  3.46s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.02s  (  0.04s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   43.93s  ( 44.93s elapsed)

  %GC time       6.8%  (7.7% elapsed)

  Alloc rate    550,509,504 bytes per MUT second

  Productivity  93.1% of total user, 91.1% of total elapsed

>>38
     109,663,904 bytes allocated in the heap
      77,659,004 bytes copied during GC
       4,606,460 bytes maximum residency (19 sample(s))
          29,116 bytes maximum slop
              13 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:   191 collections,     0 parallel,  0.19s,  0.15s elapsed
  Generation 1:    19 collections,     0 parallel,  0.14s,  0.11s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    0.16s  (  0.18s elapsed)
  GC    time    0.33s  (  0.26s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.02s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    0.50s  (  0.44s elapsed)

  %GC time      65.6%  (58.1% elapsed)

  Alloc rate    702,973,743 bytes per MUT second

  Productivity  31.2% of total user, 35.3% of total elapsed

>>10
      31,085,184 bytes allocated in the heap
       7,515,104 bytes copied during GC
       4,689,640 bytes maximum residency (3 sample(s))
         842,360 bytes maximum slop
              12 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:    43 collections,     0 parallel,  0.23s,  0.23s elapsed
  Generation 1:     3 collections,     0 parallel,  0.02s,  0.03s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    0.05s  (  0.07s elapsed)
  GC    time    0.25s  (  0.26s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    0.30s  (  0.34s elapsed)

  %GC time      84.2%  (77.8% elapsed)

  Alloc rate    664,199,141 bytes per MUT second

  Productivity  15.8% of total user, 13.8% of total elapsed

>>56
  22,530,904,044 bytes allocated in the heap
   2,630,688,952 bytes copied during GC
       1,851,628 bytes maximum residency (1709 sample(s))
          87,692 bytes maximum slop
               6 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0: 41401 collections,     0 parallel,  3.03s,  2.91s elapsed
  Generation 1:  1709 collections,     0 parallel,  1.68s,  1.93s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time   27.66s  ( 27.57s elapsed)
  GC    time    4.71s  (  4.84s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.31s  (  0.38s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   32.68s  ( 32.79s elapsed)

  %GC time      14.4%  (14.8% elapsed)

  Alloc rate    814,596,463 bytes per MUT second

  Productivity  84.6% of total user, 84.3% of total elapsed

Name: Anonymous 2010-01-16 17:50

>>58
Oh, and
> ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.10.4

Of course we could try bytestrings or the new GHC version if we wanted true VROOM VROOM performance.

Name: Anonymous 2010-01-16 17:54

import Control.Monad
import List

findSuss text =
   when (null ("sussman" \\ text))
        (putStrLn "sussman" >> findSuss (text \\ "sussman"))

Name: Anonymous 2010-01-16 17:58

>>57
Nope, there's a recursion in that when's second argument.

Name: Anonymous 2010-01-16 18:00

By the way, I didn't check for correctness, but some outputs were of a different size than expected. Watch for case sensitivity, whether you put spaces in the output, etc.

>>60
Are you a ruby programmer?
  57,146,166,712 bytes allocated in the heap
  19,402,948,040 bytes copied during GC
       1,858,492 bytes maximum residency (7076 sample(s))
          82,776 bytes maximum slop
               6 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0: 102215 collections,     0 parallel, 27.52s, 28.74s elapsed
  Generation 1:  7076 collections,     0 parallel, 12.03s, 11.98s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time   62.17s  ( 63.40s elapsed)
  GC    time   39.55s  ( 40.72s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.92s  (  0.95s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time  102.63s  (105.07s elapsed)

  %GC time      38.5%  (38.8% elapsed)

  Alloc rate    919,245,230 bytes per MUT second

  Productivity  60.6% of total user, 59.2% of total elapsed

My test suite is dirty but here it is:
import Control.Arrow ((&&&))
import Data.List (group, sort, lookup)
import Data.Maybe (fromMaybe)
import Data.Char (toLower,toUpper)
import Array

count = map (head &&& length) . group . sort . map toLower

find38 = (fromMaybe 0 .) . flip lookup

a /// b = minimum $ map (uncurry $ (quot . find38 a)) b

rearrange src pat = unwords . take n $ repeat pat
  where n = count src /// count pat

findSuss38 = putStrLn . flip rearrange "SUSSMAN"

findSuss10 xs = putStrLn . unwords $ take sussmen (repeat "SUSSMAN")
    where counts = assocs . accumArray (+) 0 (minBound,maxBound) . (map (\x -> (toUpper x,1))) $ xs
          sussmen = minimum $ [floor . (/3) . fromIntegral $ count 'S'] ++ map count "UMAN"
          count c = fromMaybe 0 $ lookup c counts

findSuss35 s =
    mapM_ (const $ putStrLn "sussman") $ takeWhile (== length "sussman")
              $ zipWith (subtract `on` length) =<< tail
              $ iterate (\\ "sussman") s
findSuss55 text =
   when (intersect "sussman" text == "sussman")
        (putStrLn "sussman" >> findSuss55 (text \\ "sussman"))

findSuss56 text =
   when (length text - length next == length "sussman") (putStrLn "sussman" >> findSuss56 next)
   where next = text \\ "sussman"

findSuss60 text =
   when (null ("sussman" \\ text))
        (putStrLn "sussman" >> findSuss60 (text \\ "sussman"))

main = testsuss
testsuss = do [f] <- getArgs
              putStrLn $ "Reading sussfile: " ++  f
              text <- readFile f
              findSuss60 text

gen = do args <- getArgs
         writeFile (head args) (writeSuss 100000000)

writeSuss = unwords . flip take (repeat "sussman")

Name: Anonymous 2010-01-16 18:01

Missed some imports
import Control.Monad
import Control.Monad.Instances
import Data.Function
import List
import System.Environment

Name: Anonymous 2010-01-16 18:52

>>62
Are you a ruby programmer?
No, i'm just Lazy.

Name: Anonymous 2010-01-16 19:25

>>62
Here, speedy, try this one:

import Control.Monad
import Data.Function
import Data.Map

findSuss text =
   flip replicateM_ (putStrLn "sussman") $ minimum $ elems $
      (intersectionWith div `on` (fromListWith (+) . flip zip (repeat 1))) text "sussman"

Name: Anonymous 2010-01-16 19:47

inelegant as fuck

sussmen = sussmen' (0,0,0,0,0)
  where sussmen' (s,u,m,a,n) str
          | and [s>2,u>0,m>0,a>0,n>0] = 1 + sussmen' (s-3,u-1,m-1,a-1,n-1) str
          | null str = 0
        sussmen' z@(s,u,m,a,n) (c:cs) = case toLower c of
          's' -> sussmen' (s+1,u,m,a,n) cs
          'u' -> sussmen' (s,u+1,m,a,n) cs
          'm' -> sussmen' (s,u,m+1,a,n) cs
          'a' -> sussmen' (s,u,m,a+1,n) cs
          'n' -> sussmen' (s,u,m,a,n+1) cs
          _   -> sussmen' z cs

main = putStrLn . unwords . flip replicate "SUSSMAN" . sussmen =<< getLine

Name: Anonymous 2010-01-16 19:56

>>65
Much better.
      35,261,328 bytes allocated in the heap
      10,478,824 bytes copied during GC
       2,554,132 bytes maximum residency (4 sample(s))
         421,348 bytes maximum slop
               7 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:    60 collections,     0 parallel,  0.02s,  0.02s elapsed
  Generation 1:     4 collections,     0 parallel,  0.02s,  0.01s elapsed

  INIT  time    0.02s  (  0.00s elapsed)
  MUT   time    0.08s  (  0.07s elapsed)
  GC    time    0.03s  (  0.04s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    0.12s  (  0.11s elapsed)

  %GC time      25.0%  (33.3% elapsed)

  Alloc rate    376,723,589 bytes per MUT second

  Productivity  62.5% of total user, 74.3% of total elapsed

Name: Anonymous 2010-01-16 19:58

>>66
Indeed, that was my first implementation idea too but it was so ugly I went back to an array. Very good performance though.
      15,028,916 bytes allocated in the heap
         364,968 bytes copied during GC
         527,856 bytes maximum residency (2 sample(s))
          16,680 bytes maximum slop
               2 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:    25 collections,     0 parallel,  0.00s,  0.00s elapsed
  Generation 1:     2 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    0.09s  (  0.08s elapsed)
  GC    time    0.00s  (  0.00s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    0.09s  (  0.08s elapsed)

  %GC time       0.0%  (4.8% elapsed)

  Alloc rate    160,565,341 bytes per MUT second

  Productivity 100.0% of total user, 111.4% of total elapsed

Name: Anonymous 2010-01-16 20:04

Jesus, who invited all the Haskell weenies?

Name: Anonymous 2010-01-16 20:07

>>68
And here is an improvement on it, makes it stricter and removes the explicit recursion, and uses the simpler way to count the sussmen. Run time about 0.08s. Using foldl makes it take 0.11s.
findSuss66b = count . foldl' sussmen (0,0,0,0,0)
    where sussmen z@(s,u,m,a,n) c = case toLower c of
                                      's' -> (s+1,u,m,a,n)
                                      'u' -> (s,u+1,m,a,n)
                                      'm' -> (s,u,m+1,a,n)
                                      'a' -> (s,u,m,a+1,n)
                                      'n' -> (s,u,m,a,n+1)
                                      _   -> z
          count (s,u,m,a,n) = minimum [floor $ fromIntegral s / 3,u,m,a,n]

findSuss66 = putStrLn . unwords . flip replicate "SUSSMAN" . findSuss66b

Name: Anonymous 2010-01-16 20:12

>>68
Sure it was, buddy.

Name: Anonymous 2010-01-16 20:14

>>69
What's the matter, jealous?

Name: PHP > Haskell 2010-01-16 20:15

If Haskell was readable ...

>>66
>>42

>>70
>>50

Name: Anonymous 2010-01-16 20:54

>>73
Read >>38 and tell me the code isn't ELEGANT AS FUCK.

Name: Anonymous 2010-01-16 21:02

>>74
Haskell is just like English except it isn't readable.

Name: Anonymous 2010-01-16 21:13

>>74
I prefer >>65, personally. Arrows are obscure as fuck.

Name: Anonymous 2010-01-16 21:17

>>76
The only part in which I am using Control.Arrow is &&&, and how is that obscure?

Name: xiagox 2010-01-16 21:51

/* sussmanChallenge.c
 * write a program that takes a string and outputs "SUSSMAN" for every time
 * those character appear. Example, "ssssumanssssssssssuman" would print
 * "SUSSMAN" twice
 */

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

main(){
int i, s=0, u=0, m=0, a=0, n=0;

printf("Enter string to be processed.\n");

while(i = getchar()){
if(i == '\n')
    break;
else{
    if(i == 115) // 's' = 115
        s++;
    else if(i == 117) // 'u' = 117
        u++;
    else if(i == 109) // 'm' = 109
        m++;
    else if(i == 97) // 'a' = 97
        a++;
    else if(i == 110) // 'n' = 110
        n++;
    }
}

/* printing code */
while(1 == 1){
if(s>2 && u>0 && m>0 && a>0 && n>0){
    printf("SUSSMAN\n");
    s-3; u--; m--; a--; n--;
}
if(s<3 || u<1 || m<1 || a<1 || n<1)
    break;
}
return 0;
}
only handles lower case versions of 's', 'u', 'm', 'a' and 'n'.
For uppercase put more cases :P

Name: Anonymous 2010-01-16 22:07

>>78
That while() loop is bad and you should feel bad.

Name: Anonymous 2010-01-16 22:09

>>78
s-3

wut
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 -