<html><head></head><body><div class="ydp1b6bf714yahoo-style-wrap" style="font-family:Helvetica Neue, Helvetica, Arial, sans-serif;font-size:13px;"><div></div>
<div dir="ltr" data-setdir="false">I've simplified and optimized it slightly (no need to use a monad for moveKnightUR) but overall it's still not fast enough to pass the CSES test. I'm wondering if the recursion is somehow inefficient because of two instances of solveK (k-1)...?</div><div dir="ltr" data-setdir="false">----</div><div dir="ltr" data-setdir="false"> <div><div>main :: IO ()</div><div>main = do</div><div> line <- getLine</div><div> let n = read line :: Integer</div><div> putStr $ unlines $ map show $ reverse $ solveK n</div><div><br></div><div><br></div><div>solveK :: Integer -> [Integer]</div><div>solveK k</div><div> | k == 1 = [0]</div><div> | otherwise = (solveFrameK k + head (solveK (k-1))) : solveK (k-1)</div><div><br></div><div>-- Returns list of knight moves in the upper right (k-1) x (k-1) portion of the board excluding the first column and first row</div><div>moveKnightUR :: Integer -> (Integer, Integer) -> [(Integer, Integer)]</div><div>moveKnightUR k (c, r) = filter (\(c', r') -> c' `elem` [2..k] && r' `elem` [2..k]) [(c-1, r+2), (c+1, r+2), (c+2, r+1), (c+2, r-1), (c+1, r-2), (c-2, r+1)]</div><div> </div><div>-- Returns list of left and bottom border squares for k x k board in (col, row) format with (1, 1) being the lower left square</div><div>genBorder :: Integer -> [(Integer, Integer)]</div><div>genBorder k = [(1, a) | a <- [1..k]] ++ [(a, 1) | a <- [2..k]]</div><div><br></div><div>-- Formula for combinations C(n, r)</div><div>combinations :: Integer -> Integer -> Integer</div><div>combinations n r = product [1..n] `div` (product [1..(n-r)] * product [1..r])</div><div><br></div><div>-- 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) region</div><div>solveFrameK :: Integer -> Integer</div><div>solveFrameK k</div><div> | k == 1 = 0</div><div> | k == 2 = 6</div><div> | otherwise = ((combinations (2*k-1) 2) - 2) + (k-1) * (k-1) * (2*k-1) - sum (map (toInteger . length) (map (moveKnightUR k) (genBorder k)))</div></div>----</div><div dir="ltr" data-setdir="false"><br></div><div dir="ltr" data-setdir="false">Julian</div><div dir="ltr" data-setdir="false"><br></div>
</div><div id="ydp4fe618aeyahoo_quoted_3401922917" class="ydp4fe618aeyahoo_quoted">
<div style="font-family:'Helvetica Neue', Helvetica, Arial, sans-serif;font-size:13px;color:#26282a;">
<div>
On Sunday, June 28, 2020, 04:27:07 PM PDT, Julian Ong <julian_ong@yahoo.com> wrote:
</div>
<div><br></div>
<div><br></div>
<div><div id="ydp4fe618aeyiv9492847610"><div><div class="ydp4fe618aeyiv9492847610ydpbaedf408yahoo-style-wrap" style="font-family:Helvetica Neue, Helvetica, Arial, sans-serif;font-size:13px;"><div></div>
<div dir="ltr">I realized I did not answer the question Doug posed, but the algorithm as originally presented works correctly and calculates correctly the number of possible knight pairings for each k x k board and generates the correct output requested by the problem.</div><div dir="ltr"><br clear="none"></div><div dir="ltr">The issue is still that, as I have implemented it in Haskell, it doesn't run fast enough to pass the automated CSES testing for n=10000. I am very curious whether it's possible to pass the speed testing for this problem using Haskell and if so how.</div><div><br clear="none"></div>
</div><div class="ydp4fe618aeyiv9492847610ydp6b38afayahoo_quoted" id="ydp4fe618aeyiv9492847610ydp6b38afayahoo_quoted_4139222292">
<div style="font-family:'Helvetica Neue', Helvetica, Arial, sans-serif;font-size:13px;color:#26282a;">
<div class="ydp4fe618aeyiv9492847610yqt2509317737" id="ydp4fe618aeyiv9492847610yqt08964"><div>
On Sunday, June 28, 2020, 09:49:02 AM PDT, Irfon-Kim Ahmad <irfon@ambienautica.com> wrote:
</div>
<div><br clear="none"></div>
<div><br clear="none"></div>
<div><div id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601"><div>
<div class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601moz-cite-prefix">On 2020-06-28 11:26 a.m., Doug McIlroy
wrote:<br clear="none">
</div>
<blockquote type="cite">
<pre class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601moz-quote-pre"></pre>
<blockquote type="cite">
<pre class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601moz-quote-pre">I'm currently stuck on the Two Knights problem.
</pre>
</blockquote>
<pre class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601moz-quote-pre">Having placed one knight on the board, in how many
places can you put the other?
</pre>
</blockquote>
<p>If you check the website indicated, it's a slight variation on
that: <br clear="none">
</p>
<p>"Your task is to count for <span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax_Preview" style="color:inherit;"></span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Element-1-Frame" style="position:relative;"><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601math" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-1" style="width:7.016em;display:inline-block;"><span style="display:inline-block;position:relative;width:6.14em;min-height:0px;font-size:114%;"><span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mrow" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-2"><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mi" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-3" style="font-style:italic;">k</span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mo" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-4" style="padding-left:0.278em;">=</span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mn" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-5" style="padding-left:0.278em;">1</span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mo" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-6">,</span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mn" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-7" style="padding-left:0.167em;">2</span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mo" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-8">,</span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mo" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-9" style="padding-left:0.167em;">…</span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mo" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-10" style="padding-left:0.167em;">,</span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mi" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-11" style="font-style:italic;padding-left:0.167em;">n</span></span><span style="display:inline-block;width:0px;min-height:2.193em;"></span></span></span><span style="display:inline-block;vertical-align:-0.284em;border-left:0px solid;width:0px;min-height:1.137em;"></span></span></span> the
number of ways two knights can be placed on a <span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax_Preview" style="color:inherit;"></span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Element-2-Frame" style="position:relative;"><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601math" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-12" style="width:2.578em;display:inline-block;"><span style="display:inline-block;position:relative;width:2.248em;min-height:0px;font-size:114%;"><span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mrow" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-13"><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mi" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-14" style="font-style:italic;">k</span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mo" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-15" style="padding-left:0.222em;">×</span><span class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601mi" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601MathJax-Span-16" style="font-style:italic;padding-left:0.222em;">k</span></span><span style="display:inline-block;width:0px;min-height:2.193em;"></span></span></span><span style="display:inline-block;vertical-align:-0.075em;border-left:0px solid;width:0px;min-height:0.929em;"></span></span></span>
chessboard so that they do not attack each other."<br clear="none">
</p>
<p>The input is n (an integer that can range from 1 to 10000), the
output is a single integer for each value from 1 to n, one per
line, the memory limit is 512MB, and the maximum runtime is 1.00
seconds. </p><div class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601yqt4596307336" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601yqtfd56774"><br clear="none">
</div><div class="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601yqt4596307336" id="ydp4fe618aeyiv9492847610ydp6b38afayiv2108629601yqtfd45770">
<p><br clear="none">
</p>
</div></div></div>_______________________________________________<br clear="none">Beginners mailing list<br clear="none"><a shape="rect" href="mailto:Beginners@haskell.org" rel="nofollow" target="_blank">Beginners@haskell.org</a><br clear="none"><a shape="rect" href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="nofollow" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><div class="ydp4fe618aeyiv9492847610ydp6b38afayqt4596307336" id="ydp4fe618aeyiv9492847610ydp6b38afayqtfd10315"><br clear="none"></div></div></div>
</div>
</div></div></div></div>
</div>
</div></body></html>