Send Beginners mailing list submissions to
beginners@haskell.org
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
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: CSES Two Sets problem at
https://cses.fi/problemset/task/1092/ (Irfon-Kim Ahmad)
2. Re: CSES programming problems at https://cses.fi/problemset/
[Two Knights] (Julian Ong)
----------------------------------------------------------------------
Message: 1
Date: Mon, 29 Jun 2020 10:36:11 -0400
From: Irfon-Kim Ahmad <ir...@ambienautica.com>
To: beginners@haskell.org
Subject: Re: [Haskell-beginners] CSES Two Sets problem at
https://cses.fi/problemset/task/1092/
Message-ID: <c8f076e3-450f-4721-cb72-eec5fcb76...@ambienautica.com>
Content-Type: text/plain; charset="utf-8"; Format="flowed"
Without having attempted to code this in any particular language, but
just thinking about the problem, I believe the CSES knights problem is
not a test of language speed or programming acumen but a test of
choosing an efficient choice of algorithm that doesn't generate more
information than the question asks for.
In short, they're asking for the NUMBER of boards, not the actual
boards. Most of the solutions people are proposing in Haskell simulate
the problem instead of calculating it -- in short, they generate the
actual boards, then count them, whereas the solution only requires you
to count them.
The solutions for n = 1 and n = 2 can be calculated by hand and put in
as constants. n = 3 you can calculate or simulate as is your preference.
Knights have a maximum interaction range of three linear squares.
Knights placed more than three squares apart in any one direction cannot
hinder each other. So the number of illegal placements of knights can be
confined to a 3x3 board. After that, all illegal boards of size n x n
are simply one of those 3 x 3 boards shifted to a new position.
The total number of n x n boards with two knights placed on them is
given by (n^2) choose 2, which I'm not going to look up because it's
been over 20 years since I took statistics and I'm happy about that.
Still, it's a calculation. Not a super simple one from a computing
perspective, since it involved factorials, but I'm assuming someone has
figured out how to do factorials quickly in Haskell?
The number of places you can position a 3 x 3 board within an n x n
space is something like (n-3)^2 if I'm not mistaken?
So you can subtract that from the total number of boards to arrive at a
result.
NOTE: This likely requires SOME tweaking for edge cases (For example, Is
the board where k1 is in position x and k2 is in position y considered
the same as the board where their positions reversed, or not? Does the
choosing calculation factor for that properly?) because it's literally a
ten-second-in-the-shower concept, but it seems like this could come up
with a result. Whether it does it in time is mostly down to whether
Haskell can do factorials fast enough at that point.
On 2020-06-28 8:50 p.m., Julian Ong wrote:
> After the Two Knights problem, I went on this next problem which
> requires that you separate 1..n into two sets with the same sum if
> possible. Again my algorithm in Haskell works but is apparently too
> slow. It fails for CSES test inputs >= 26560 where a solution exists.
>
> I'm starting to wonder if Haskell is fundamentally too slow compared
> to other languages. From what I've read that shouldn't be the case
> though. For this problem it looks like it's doable in Python (I
> haven't tried that). Most of the fastest solutions for these problems
> seem to be written in C++. If there's anyone who's trying to solve
> these problems in Haskell (they're really fun by the way if you've
> never checked them out) and has solved this one (or Two Knights) and
> passed all the tests, I'd love to hear how you did it. Thanks.
>
> ---
>
> -- CSES - Two Sets
> -- Given 1..n, separate into two sets of equal sums and if possible
> list the elements of each set of a possible solution or output NO if
> not possible
>
> main :: IO ()
> main = do
> line <- getLine
> let n = read line :: Integer
> putStrLn $ solveN n
> -- Observe that sum [1..n] = n*(n+1)/2 so each set sum must be
> n*(n+1)/4 and so the set sum must be divisible by 4 for the separation
> to be possible
> -- Then the algorithm starts adding numbers from n down to 1 until the
> next number would make the sum exceed the required set sum
> -- At this point you add one more number, which will be the lowest
> number, to fill in the gap to complete set1. Set2 is then the other
> numbers.
> solveN :: Integer -> String
> solveN n
> | (n * (n+1) `mod` 4 /= 0) = "NO"
> | otherwise = "YES\n" ++ show set1_count ++ "\n" ++ (unwords $ map
> show set1_list) ++ "\n" ++ show set2_count ++ "\n" ++ (unwords $ map
> show set2_list)
> where
> set_sum = (n * (n+1)) `div` 4
> set1_part1 = takeWhile (\x -> x*(n+1-x) + sum [0..(n-x)] <
> (n * (n+1)) `div` 4) [n, n-1..1]
> set1_part2 = set_sum - sum set1_part1
> set1_list = set1_part1 ++ [set1_part2]
> set1_count = (toInteger . length) set1_list
> set2_list = [x | x <- [1..n], not (x `elem` set1_list)]
> set2_count = (toInteger . length) set2_list
> ----
>
> Julian
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20200629/74e5c9fe/attachment-0001.html>
------------------------------
Message: 2
Date: Tue, 30 Jun 2020 05:59:09 +0000 (UTC)
From: Julian Ong <julian_...@yahoo.com>
To: "beginners@haskell.org" <beginners@haskell.org>
Subject: Re: [Haskell-beginners] CSES programming problems at
https://cses.fi/problemset/ [Two Knights]
Message-ID: <590680425.128466.1593496749...@mail.yahoo.com>
Content-Type: text/plain; charset="utf-8"
Update: Doug showed me a fast algorithm that does the trick. It doesn't use
recursion. For an nxn board, the algorithm counts the possibilities given a
knight in each of these regions:
1. The central (n-4)x(n-4) sub-board2. The squares bordering this central
sub-board but excluding the four "corners" where the row and column squares
intersect3. The edge squares adjacent to the ones in #24. The four
"corners" excluded in #2 that are one square diagonal from each of the four
corners of the nxn board5. The eight edge squares adjacent to the four
corners of the nxn board6. The four corners of the nxn board
Sum these and divide by two (because the two knights are interchangeable) and
you can calculate the solution very quickly for any nxn. Mapping this over
[1..n] will provide the required output. My takeaway from this is that using
the solution to case n-1 in order to solve case n may not be the most efficient
way to do things. Sometimes just solving for case n from scratch is faster.
Thanks Doug.
Julian
On Sunday, June 28, 2020, 09:00:53 AM PDT, Julian Ong
<julian_...@yahoo.com> wrote:
There are 8 possibilities and then you can filter them by column and row
values depending on the region of the board you’re interested in.
Julian
On Jun 28, 2020, at 8:26 AM, Doug McIlroy <d...@cs.dartmouth.edu> wrote:
> I'm currently stuck on the Two Knights problem.
Having placed one knight on the board, in how many
places can you put the other?
Doug McIlroy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20200630/b3fa6da9/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 144, Issue 9
*****************************************
