Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. CSES programming problems at https://cses.fi/problemset/
(Julian Ong)
2. Using output of head in data constuctor (Josh Friedlander)
3. Re: Using output of head in data constuctor (Francesco Ariis)
----------------------------------------------------------------------
Message: 1
Date: Sat, 27 Jun 2020 22:41:42 +0000 (UTC)
From: Julian Ong <[email protected]>
To: "[email protected]" <[email protected]>
Subject: [Haskell-beginners] CSES programming problems at
https://cses.fi/problemset/
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
Hi - I'm working through these problems using Haskell and was curious if anyone
else is doing that. I'm currently stuck on the Two Knights problem. I have
implemented a solution using recursion but it's not fast enough to pass the
tests. Has anyone been able to solve this problem using Haskell? Looking for
some optimization tips. I'm not sure if there's a better way to implement the
recursive algorithm - is it doing unnecessary work?
The problem requires that you calculate solutions for 1..n so you need to keep
track of all intermediate values. The program fails the speed test for n=10000
-- it needs to complete in less than a second. I hold out hope that it's doable
in Haskell but I can't figure it out. The algorithm uses the solution for the
(k-1)x(k-1) board and adds the additional possibilities when you add a new left
column and bottom row to make a kxk board.
My current attempt looks like this:---- import Control.Monad
main :: IO ()main = do line <- getLine let n = read line :: Integer
putStr $ unlines $ map show $ reverse $ solveK n
solveK :: Integer -> [Integer]solveK k | k == 1 = [0] | otherwise =
(solveFrameK k + head (solveK (k-1))) : solveK (k-1)
-- Returns list of knight moves in the upper right (k-1) x (k-1) portion of the
board excluding the first column and first rowmoveKnightUR :: Integer ->
(Integer, Integer) -> [(Integer, Integer)]moveKnightUR k (c, r) = do (c',
r') <- [(c-1, r+2), (c+1, r+2), (c+2, r+1), (c+2, r-1), (c+1, r-2), (c-1, r-2),
(c-2, r-1), (c-2, r+1)] guard (c' `elem` [2..k] && r' `elem` [2..k])
return (c', r') -- Returns list of left and bottom border squares for k x k
board in (col, row) format with (1, 1) being the lower left squaregenBorder ::
Integer -> [(Integer, Integer)]genBorder k = [(1, a) | a <- [1..k]] ++ [(a, 1)
| a <- [2..k]]
-- Formula for combinations C(n, r)combinations :: Integer -> Integer ->
Integercombinations n r = product [1..n] `div` (product [1..(n-r)] * product
[1..r])
-- Calculates additional number of two knight placements along the left and
bottom border and from that border into the upper right (k-1) x (k-1)
regionsolveFrameK :: Integer -> IntegersolveFrameK k | k == 1 = 0 | k ==
2 = 6 | otherwise = ((combinations (2*k-1) 2) - 2) + (k-1) * (k-1) * (2*k-1)
- sum (map (toInteger . length) (map (moveKnightUR k) (genBorder k)))----
Julian
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20200627/c9c02b11/attachment-0001.html>
------------------------------
Message: 2
Date: Sun, 28 Jun 2020 14:36:36 +0300
From: Josh Friedlander <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Using output of head in data constuctor
Message-ID:
<cac2wd70+egwrdog4zhxk_z-7axu2uynfs7h3mz9hrqt-fae...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Given the following code:
module Log where
import Control.Applicative
data MessageType = Info
| Warning
| Error Int
type TimeStamp = Int
data LogMessage = LogMessage MessageType TimeStamp String
| Unknown String
I want to create a log parser like this:
module LogAnalysis where
import Log
parseMessage :: String -> LogMessage
parseMessage xs
| length(words(xs)) < 3 = Unknown xs
| notElem(head(words(xs)) ["I", "E", "W"]) = Unknown xs
| otherwise = LogMessage Info 3 head(words(xs))
But GHC gives me "• Couldn't match type ‘[a0] -> a0’ with ‘[Char]’
Expected type: String
Actual type: [a0] -> a0"
So it thinks I am giving it the *function* head, when I would like to give
it the output.
How do I fix this?
Thanks in advance,
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20200628/02251729/attachment-0001.html>
------------------------------
Message: 3
Date: Sun, 28 Jun 2020 13:47:09 +0200
From: Francesco Ariis <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Using output of head in data
constuctor
Message-ID: <20200628114709.GA24819@extensa>
Content-Type: text/plain; charset=utf-8
Hello Josh
Il 28 giugno 2020 alle 14:36 Josh Friedlander ha scritto:
> I want to create a log parser like this:
>
> module LogAnalysis where
> import Log
>
> parseMessage :: String -> LogMessage
> parseMessage xs
> | length(words(xs)) < 3 = Unknown xs
> | notElem(head(words(xs)) ["I", "E", "W"]) = Unknown xs
> | otherwise = LogMessage Info 3 head(words(xs))
>
> But GHC gives me "• Couldn't match type ‘[a0] -> a0’ with ‘[Char]’
> Expected type: String
> Actual type: [a0] -> a0"
I suspect `LogMessage Info 3 head(words(xs))` is the problem. This is
the same as writing
LogMessage Info 3 head (words xs)
keeping in mind how whitespace and parentheses work in Haskell. You
probably want
LogMessage Info 3 (head (words xs))
instead.
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 144, Issue 5
*****************************************
