SamLowry

Members
  • Content count

    913
  • Joined

  • Last visited

Community Reputation

1865 Excellent

About SamLowry

  • Rank
    Advanced Member
  1. data compression

    I see compression as essentially just rearranging bits, or at least their meaning.   'A' is normally (too lazy to check though) encoded by the bitstring '1000001'. What if I choose to represent it by '01010101' instead? It's perfectly possible, I would just have to two swap things around. Is it useful? Not really. But what if I choose to replace the bitstring '10000001' with just '1'? I would need to rearrange a lot more to make it work (ie without introducing ambiguities), but it can be done without too much trouble. This way, I can encode data with a lot of A's much more efficiently: all A's need 8x less bits.   Compression is about remapping the meaning of bits so that a given piece of data turns out be represented with less bits than before.   Of course, you could choose to encode your entire hard drive with a single bit; it is a valid remapping. The problem is that you need to store the remapping somewhere, and that would just amount to having a hash table that maps '1' to <your entire HD data>. So you lose instead of gain. This means that it is important for compression that the remapping itself can be described procedurally.   The part where one says 'you cannot just create information out of nothing' can be found in the remapping: in order to represent 'A' by '1', one has to make a lot of sacrifices. In the case of this example, in order to represent A with one bit, all other characters will require 9 bits. So from this standpoint there is no gain to be made. But since you use the remapping to reencode data, compression is actually possible.
  2. What Are Your Opinions About Various Languages ?

     Never compare C++ any language to Java when referring to line count - C++ looses every time with all of it's tedious class declarations and header files. Java loses due to its maddening verbosity.   I find it strange that C# works against you, as the language is essentially an improved superset of Java. What exactly bothers you? Anyway, IMO, C# is what java should've been: a language with a consistent type system, generics that work, type inference, support for functional programming, a (more) coherent library, ...
  3. Trouble with generic arrays

    My personal solution is to stay away from java as much as possible. I hate the language with a passion, given how it works against me every time I try to implement something nontrivial. The main challenge when using it is to find the least ugly solution.   I wish you luck with your battle against the language. You're a braver person than I am.
  4. Trouble with generic arrays

    It puzzled me for a while, but I've come up with the following explanation for the length-related problem. It seems to make correct predictions.   In order to understand what's going on, you need to know the details of how java works. You probably know this already, but I'm mentioning it for completeness and clear context establishment (i.e. indicating which java 'features' come into play).   First, there's the type erasure (which you mentioned yourself): every type parameter gets replaced by Object (in your code at least, because you didn't specify bounds). Java will put in runtime type checks where it has enough information to do so. In a generic method m<T>, the compiler knows nothing about T, hence it cannot add runtime checks. In a method that uses CmpVec<Integer> however, in knows T = Integer, so runtime checks will be added.   Second, an Object[] cannot be cast to e.g. a String[]. AFAIK, java guarantees that reading from a T[] array yields T objects. If casting Object[] to String[], this would not hold. However, you can cast String[] to Object[], since java makes no guarantees about writes: given a T[] array, it might be that writing a T to the array fails at runtime (while the code passes the compiler type checks). This is because arrays keep track of which type they're supposed to hold at runtime.   Putting these two facts together now. In your code, inside CmpVector, the compiler knows nothing about T, so the array field is really an Object[] at runtime. Your length-printing code contains an explicit type: ParticleTag, which leads the compiler to add a cast to ParticleTag[] for 'safety'. So, the generated code contains a cast of an Object[] to a ParticleTag[], which fails.   If you were to print the length more indirectly, hiding the actual type from the compiler, it would work again: public static <T> void indirect(CmpVector<T> v) { System.out.println( v.array.length ); } indirect( new CmpVector<Whatever>(5) ); // works This does not yet explain why the fill fails though. Probably something similar.     -- Edit The ClassCastException happens where the arrayFill method is called, so it probably means that every time you use the array field directly, a runtime check will occur, which will fail. The arrayFill works if I put it inside a generic method similar to 'indirect' as shown above.   If you're determined to keep the array field public, I'd suggest being 'honest' to the compiler, and just tell it is a Object[] array, not a T[] array. You'll have to suppress unchecked cast warnings at multiple places in your code though (or you could create an auxiliary @SuppressWarnings("unchecked")  T[] arr() { return (T[]) array; } method).
  5.   Thank you.   If you would perhaps extend it to produce Pascal's triangle when feeding it a non-empty source file, it might become a serious contender to PacTri as language to be used in these kinds of contests.
  6. z = concat a = " bottle" e = a ++ "s" y = "o more" b 0 = "n" ++ y ++ e b 1 = "1" ++ a b n = show n ++ e c = " of beer" d = c ++ " on the wall" f 0 = z [ "N", y, e, d, ", ", b 0, c, ".\nGo to the store and buy some more, ", b 99, d, ".\n" ] f n = z [ b n, d, ", ", b n, c, ".\nTake one down and pass it around, ", b $ n-1, d, ".\n\n" ] main = mapM_ (putStr . f) [99,98..0] 260 nonwhitespaces using Haskell.
  7. While your code is certainly correct and written in functional style, I would suggest you try to go one step further. Now, it seems that you are 'inlining' different steps into one big step. Functional programming has the advantage of giving the programmer the possibility to clearly distinguish between different 'levels' of operation, each following a certain pattern.   For example, let's say I have a list of numbers and want to take the sum of the squares of all uneven numbers. The following Haskell-code (I picked Haskell because even if you are not familiar with it, I believe it is more readable than Scheme, as long as I stay away from some of the more arcane notations) does this in a straightforward manner:   bizarreSum :: [Integer] -> Integer ---------------------------------- bizarreSum [] = 0 -- empty list case bizarreSum (x:xs) -- cons case (head = x, tail = xs) | odd x = x * x + bizarreSum xs -- head is odd | otherwise = bizarreSum xs   But one can distinguish three different steps in this algorithm: first, we filter out the even numbers, then we square every number, and finally, we summate. This can be written as bizarreSum' :: [Integer] -> Integer ----------------------------------- bizarreSum' = foldl (+) 0 . map sqr . filter odd       The dot chains the operations together: filtering, mapping, folding. Filter, map and foldl are three well-known patterns, they are in a way higher-level functional loops. In my opinion, it is preferable to try to find these patterns and try to implement your algorithms using them, as you work on a higher level of abstraction.   Permutation can then be implemented as a series of mapping operations. My Haskell implementation looks like this:   split :: [a] -> [([a], a, [a])] ------------------------------- split xs = [ (take n xs, xs !! n, drop (n+1) xs) | n <- [ 0 .. length xs - 1 ] ] permutations :: [a] -> [[a]] ---------------------------- permutations [] = [[]] permutations xs = do (prefix, x, postfix) <- split xs p <- permutations (prefix ++ postfix) return (x : p)   The permutations function first splits a list [a(1), a(2), ..., a(n)] up in three parts: a prefix list [a(1)..a(i-1)], an element x=a(i), and a postfix list [a(i+1)..a(n)], for every possible i (this is a map). Then for all permutations p of prefix++postfix (again a map) it prepends x=a(i) to the front of p. So, this is akin to a nested loop, or in our case, a map within a map. In above Haskell code, you can interpret "x <- xs" as "for each x in xs" (it uses monads, which are  a very powerful concept, and I love to explain people about them, but now it is a bit out of scope of this post).   In your first attempt, insert-everywhere/in-all-words seems to be wrong: (insert-everywhere/in-all-words 1 '((2 3))) '((1 2 3) (1 3 2) (2 1 3) (3 2 1) (3 1 2) (2 3 1)) I don't think it is supposed to generate all permutations of (2 3) in this example. I didn't take the time to inspect your code thoroughly, but I did notice a lot of conds and recursion, which means that you are constantly reimplementing functional building blocks, map in your case.   Final note: it is true that bizarreSum' is less memory-efficient than bizarreSum, as each time a new list must be created in memory (however, this does not apply to Haskell as it is a nonstrict language, but in most other languages, this could be an actual issue). However, would performing your own inlining not be a case of premature optimisation? If it is your intention to practice functional programming, I believe it is more important to focus on learning to think on a higher level than to be efficient.
  8. Switching from Java to C#

    Many little differences. switch statements are fixed. No implicit fall-through. Importing happens on a per-namespace basis (no importing single classes). No static import in C#. No covariant return types in C# (i.e. a method returning object cannot be overridden by a method overriding string, like in java) C# offers structs, i.e. objects with value semantics (copied when passed as argument or return value instead of by reference, etc.) IEnumerable<T> is the central collection class. Generics are not half broken in C#. They don't rely on type erasure: you can create an array of T[]. They work on all types: you can have a list of ints. Contravariance and covariance are supported: an IEnumerable<string> is a subclass of IEnumerable<object>. Overloading is possible: K<T> and K<T, U> can both be defined. Methods are nonvirtual by default. If you want to be able to override them, they need to be declared either abstract or virtual. When an abstract class implements an interface, all methods need to be either implemented or declared as abstract methods. Using 'override' in C# is not optional like @Override. C# has 'yield return', letting you lazily generate IEnumerables. LINQ C# has no "inner classes", only "nested classes". So, declaring a class within a class in C# is like declaring a static class inside another class in java. C# offers properties (replace getters/setters), events (observers), delegates (first class methods), anonymous lambdas (inline functions). There is no final-only limitation on which variables can be captured by closures. Access modifiers work slightly differently. C#'s 'protected' is different from java's. There's also 'internal'. Operator overloading. Extension methods. Keyword parameters. Default argument values. Verbatim strings (which make regexes readable again). ...
  9. Deceptively complex problem...

    You could also actually keep an infinite list, and use laziness. In Haskell, the solution would be quite simple:   generate :: a -> Int -> [[a]] ----------------------------- generate x n = concat $ repeat $ replicate (n - 1) [] ++ [[x]] combine :: [[a]] -> [[a]] -> [[a]] ---------------------------------- combine xs ys = map (uncurry (++)) (zip xs ys) a = generate "a" 5 - "a" is repeated every 5th turn b = generate "b" 3 - "b" is repeated every 3rd turn c = generate "c" 7 - ... result = a `combine` b `combine` c --> [[],[],["b"],[],["a"],["b"],["c"],[],["b"],["a"],[],["b"],[],["c"],["a","b"],[],[],["b"],[],["a"], ...]     Depending on the language you use, it can be easy to simulate this, or it can boil down to solving the same problem you are tackling now.
  10. If your example is representative, I'd think the problem can solved most easily like this:   class OtherClass { public final Func<int> GetX; public OtherClass(Func<int> getX) { GetX = getX; } }   Depending on your exact needs, there might be other solutions available to you. You would need functionality akin to C++'s template specialization; what comes closest in C# is extension methods which you can specialize dependent on type, but there are quite some limitations which I would think make it unusable in your case.   As a general solution, I would keep a Dictionary<Type, Func<int>> which I would create at initialization time using reflection (i.e. it's important I don't have to keep it up-to-date myself). OtherClass would then fetch it GetX from there once in its constructor.
  11. "Functional style" normally refers to "stateless programming", but I've also heard it used to refer to "using higher order functions" (see http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf).   Stateless programming means that you cannot modify existing data, e.g. once a list is created, you cannot add new elements to it. This is not as useless as it sounds, as you can just create a new list which is equal to the old list with the extra elements added to it. This in turn might seem like a waste of memory, but again, it isn't, as you can reuse parts of old data structures in your new ones, since they are guaranteed never to change anyway.   This approach can have many advantages: it makes reasoning about programs easier, it can be more efficient, etc. Functional style can make using multithreading much easier. Formally, a variable in functional setting can be seen as just something with a value, which does never change. A variable in a stateful setting, however, has a value that changes in time, i.e. there's an extra dimension to take into account. Multithreading can be seen as "your code will run, but you can't know when". In that sense, it is easy to see why functional style simplifies multithreading.   Functional and imperative (= non-functional) style can easily coexist. For example, Haskell is a purely functional language (whereas for example O'Caml has ref cells which introduce state). However, Haskell gets translated to imperative code (due to laziness), so underlying a functional layer lies an imperative one. But, using certain syntactic tricks (monads, do-notation, ...) it is possible to introduce state in Haskell programs, so from functional elements one can build an imperative program. Same thing in other languages: in java/C#, strings appear immutable to the user, while internally, they probably use state, but it is abstracted away. These purely functional strings are then used in an imperative setting, etc. etc. You can switch between functional and imperative style at will inside one program.   Also related is the expression problem. This has less to do with stateless vs stateful however, but rather as having functions or classes as building blocks. One can distinguish two "dimensions": functionality and cases. Let's take shapes as an example: one can have circles, squares, etc. as cases, and area, circumference, intersection, ... as functionality. An OO language allows you to easily add new cases (i.e. new shapes) by writing a new subclass, and implementing all necessary methods. This does not require you to make changes to existing code. If however you need new functionality, you would have to modify the superclass (Shape), i.e. add extra methods, and implement these in all subclasses. Functional style can be seen as orthogonal to this. Adding new functionality is trivial: just define a new function, no existing code needs modifications. However, adding a new case requires you to extend the data type definition and adjust all existing functions to deal with this new case.   Technically, it is possible to add extra functionality in OO programs and add new cases in functional programs without modifying existing code, but it can lead to some ugly results, which sometimes bypass the type system (I'm thinking of using instanceof in java, which bypasses some correctness checks (exhaustivity, i.e. making sure that all abstract methods are implemented) done by its type system).
  12. Haskell kicking my Asskell

    (Apologies for the bad formatting, but I lack the patience to correct it once more, it's being screwed up repeatedly)   The error message is probably related to the fact that it can't deduce what the type of the literal 1 is. 1 could be an Int, an Integer, a Float, etc. Haskell knows it must be an instance of the Bits class, but that still leaves open a lot of possibilities. You can solve the problem by giving explicit type annotations. test :: Integer test = fsr 1 1     I'm not 100% certain of your intentions, I'm a bit confused, so I don't know if my answer will make sense to you. Bits is not a type, it is a type class. As far as I know, it is not possible to define a type which requires its constructor arguments to have types belonging to a certain class. For example, newtype Mask = Mask Bits newtype Step = Step Bits   won't work since Bits is not a type. You actually want something like newtype (Bits a) => Mask a = Mask a   i.e. "Mask parameterized in some type a that must be an instance of the class Bits", but this does not exist in Haskell. What you can do however, is this newtype Mask a = Mask a newtype Step a = Step a newtype Lfsr a = Lfsr (Mask a, Step a)   This does not enforce that the type of the Mask and Step are instances of Byte, but it will help you make the distinction between masks and steps. Haskell will give an error message if you put a step in a mask spot, or vice versa. For a PRNG, you only need a part of the state monad's functionality. You can imagine the PRNG as being an infinite list of random numbers. Every time you need a random number, you grab it from the front of this list. This is a more general and would allow you to use different approaches to generating random numbers. The monad would look like this (I believe a similar one already exists in Haskell's standard library): data PRNG r a = PRNG { runPrng :: [r] -> (a, [r]) } instance Monad (PRNG r) where return x = PRNG $ \rs -> (x, rs) PRNG f >>= g = PRNG $ \rs -> let (a, rs') = f rs in runPrng (g a) rs' rand :: PRNG r r ---------------- rand = PRNG (\rs -> (head rs, tail rs))   So, a function needing a source of random numbers is one that takes a list of random numbers and returns some result of arbitrary type a and a remaining list of random numbers, i.e. [r] -> (a, [r]). Combining two such functions is done by giving the rest list returned by the first function to the second function (this is what >>= does). We can define a dumb PRNG as follows: withSillyPRNG :: PRNG Integer a -> a ------------------------------------ withSillyPRNG (PRNG f) = fst $ f [0..] and use it as follows: throwDie :: PRNG Integer Integer -------------------------------- throwDie = do x <- rand return $ x `mod` 6 + 1 throwDice :: Int -> PRNG Integer Integer ---------------------------------------- throwDice 0 = return 0 throwDice n = do x <- throwDie y <- throwDice (n - 1) return $ x + y withSillyPRNG (throwDice 5) 15 generateList :: Int -> PRNG r [r] --------------------------------- generateList 0 = return [] generateList n = do x <- rand xs <- generateList (n - 1) return $ x : xs withSillyPRNG (generateList 10) [0,1,2,3,4,5,6,7,8,9] A PRNG based on your lfsr (probably not as you intend to make it, but hey, it seems to generate numbers) withLFSR :: Bits r => r -> r -> PRNG r a -> a --------------------------------------------- withLFSR seed mask (PRNG f) = fst $ f nums where nums = seed : map (lfsr seed) nums withLFSR 1078 176 (generateList 10) [1078,539,1339,1707,1891,1927,2037,1996,998,499]
  13. Recursive Algorithm Help

    Your first case is wrongly placed: if numbers is empty, the method should still return true if target == 0. Your third case (numbers.size() == 1) is a bit ugly: it is not really necessary, as it should be taken care of by the rest of the code. The last case (else) seems to be wrong: to find a solution, you should both try out picking the last number and skipping it. You only check the skip path if the last number is greater than the target. This would be the code in Haskell; you'll need to translate it into java. My algorithm is not tail recursive, but it is trivial to make it so by just returning a bool instead of the integer selection. [source lang="plain"]sat :: Integer -> [Integer] -> Maybe [Integer] ---------------------------------------------- sat 0 _ = Just [] sat _ [] = Nothing sat n (x:xs) = if n < 0 then Nothing else do solution <- sat (n - x) xs return (x : solution) `mplus` sat n xs[/source] The last case (sat n (x:xs)) should coincide with your last else-branch. My algorithm works on the first item of the list instead of the last as you do. As you can see, first it tries picking the first value (sat (n - x) xs), and if that doesn't work, it tries skipping it (sat n xs).
  14. Chan-wook's vengeance trilogy [url="http://www.imdb.com/title/tt0310775/"]http://www.imdb.com/title/tt0310775/[/url] Sympathy for Mr Vengeance [url="http://www.imdb.com/title/tt0364569/"]http://www.imdb.com/title/tt0364569/[/url] Oldboy [url="http://www.imdb.com/title/tt0451094/"]http://www.imdb.com/title/tt0451094/[/url] Sympathy for Lady Vengeance All Nolan films, my favorite being [url="http://www.imdb.com/title/tt0482571/"]http://www.imdb.com/title/tt0482571/[/url] The Prestige Leone classics [url="http://www.imdb.com/title/tt0060196/"]http://www.imdb.com/title/tt0060196/[/url] The Good, the Bad and the Ugly [url="http://www.imdb.com/title/tt0064116/"]http://www.imdb.com/title/tt0064116/[/url] Once Upon a Time in the West [url="http://www.imdb.com/title/tt0087843/"]http://www.imdb.com/title/tt0087843/[/url] Once Upon a Time in America Coen films, my favorite being [url="http://www.imdb.com/title/tt0100150/"]http://www.imdb.com/title/tt0100150/[/url] Miller's Crossing Scorsese, my favorite being [url="http://www.imdb.com/title/tt0112641/"]http://www.imdb.com/title/tt0112641/[/url] Casino Misc [url="http://www.imdb.com/title/tt0420223/"]http://www.imdb.com/title/tt0420223/[/url] Stranger than Fiction [url="http://www.imdb.com/title/tt0780536/"]http://www.imdb.com/title/tt0780536/[/url] In Bruges [url="http://www.imdb.com/title/tt0083658/"]http://www.imdb.com/title/tt0083658/[/url] Blade Runner [url="http://www.imdb.com/title/tt0455957/"]http://www.imdb.com/title/tt0455957/[/url] Goya's Ghosts and one I cannot leave out [url="http://www.imdb.com/title/tt0088846/"]http://www.imdb.com/title/tt0088846/[/url] Brazil