仲玩緊？

[Saren-Arterius]

你地咁有聊既 :joy:

[mingchuno]

@Saren-Arterius 遲下可能會有篇Blog 講 :)

[dng8888]

如果大家都單是找答案，的確已很快就沒意思。但從9－loop開始，已不是這個方向。你有機會可看看Rosetta code，都是做這種比較。題目真不重要，是學習比較不同語言的好方法。好過hello world很多。當然，若在optimise和加base上，將問題genalise，可能會有趣一點。

[gaplo917]

@jackhftang 條 Algo 的確好快 :+1:

[dng8888]

I think there are a few directions that silly question can go. The more robust issue is how to handle change in spec. But if one concentrate on optimisation issues for base and width, the discussion could be divided into hardware, software and implementation (language) one.

For software optimisation, the generative c may be king in reported speed, but perhaps it needs a bit documentation whether it has exhausted all possibilities. In general, I think the approach is to cut the loops (a-b loop effectively with a - b = c then 111 - c then d), faster uniqueness checking logic using bit vector (or generative avoid non-uniqunesness). Any more idea it has used to speed up? Or not (e.g. Inline to avoid function call?)

In particular, not sure why generative (recursive even if tail call i.e. not use stack) is better than loop?

For hardware optimisation, I noted that the loop a = 2000 is independent from, say, a=3000 and ... could we use GPU on top of (or ignore) thread? If so, not sure that is exhaustive in terms of time optimisation yet. Not that adaptive c need any but when you increase the base especially the width ... There is some parallel version I have not dipped into but are they only used parallel threads for multi-core only. Not sure they use GPU though. I guess they are aim at generally available platform.

Another dimension is about what programming language is better. C as a kind of assembler language may compete with the missing x86 and ARM. (For fun, 6502/Z80 and S/370 would be interesting but I guess the target would be either x86 or ARM these days) I guess it might be looking at the generated code and adjust the c is easier than really hardcoding one. What not sure is why FORTRAN not on the Advance competition. Not in that kind of business but it was said many parallel run programming still use FORTRAN. (Do not tell me it is dead. I heard in the my first computer programming lecture in HKU in Oct 1979, "why anyone is using FORTRAN I do not understand, it should be dead by now". It is not.)

The related question in implementation is what is missing and why. Shocking to see BRAINFUCK, but no FORTH/LOGO/APL family. Other than these, not sure what major family is missing other than assembler.

Still back to the basic, if one change the requirement e.g. from -/+ to */log say, can you move the logic easily. The teacher can easily change the question you know :-). Related to this question, can the program be maintained after, say, 1 year. I still think the 9 loop is not that bad in this light. And Minizinc, juila or even common lisp. Just not very optimised for speed, but may be more robust in another angle.

[dng8888]

E.g. one change in user requirement:

https://profile.theguardian.com/save-content?INTCMP=DOTCOM_ARTICLE_SFL&returnUrl=https%3A%2F%2Fwww.theguardian.com%2Fscience%2F2016%2Fapr%2F11%2Fcan-you-solve-it-give-your-grey-cells-a-party-with-the-sweet-16-puzzle%3FCMP%3Dtwt_a-science_b-gdnscience&shortUrl=/p/4t6zm&platform=web:Netscape:mobile

[dng8888]

Thanks for the q&a. I am still tracing your code to understand its logic. For the link, try this

https://www.theguardian.com/science/2016/apr/11/can-you-solve-it-give-your-grey-cells-a-party-with-the-sweet-16-puzzle?CMP=twt_a-science_b-gdnscience#_=_

Or google Sweet-16 puzzles from a guardian report. Similar idea but less silly.

[phiSgr]

Added an OCaml version, surprisingly it is almost as fast as your C version, uses more memory though.

[jackhftang]

I compiled the ocaml code. It is actually faster by ~5% for case b29w4 and for other cases it is >10% slower. And I take a step deeper and run it for case b25w6, it took ~259s and ~1.5GB memory and is around ~4.9 times slower than the c.

I looked into the ocaml code. The main idea is the same. The major difference is that I precompute the values for a and b (in ocaml code g and c) in C and in ocaml you compute the values inside the search. I would guess that the more the base is larger than width, the precomputed table is less useful for speed up, but it always take a constant O(base*base) time for each lkji . BTW, it is surprising that working with linked list could be that close to c speed.

Also, I know that ocaml use a stop-the-world gc and it is likely some time spent on gc for case b25w6.

[phiSgr]

I was surprised by the poor performance and huge memory usage of my code in case b25w6. I cannot identify any source of memory leak and have no idea how much garbage I produced.

[phiSgr]

Added a version totally without lazy lists, uses much less memory but is still very slow for case b25w6.

[KowloonWalledCityCoin]

Try to read the source but a bit hard.

Not sure as it is not documented yet the general optimisation to reach advance, may I ask what is the strategy of optimisation. Why use lazy feature especially the logic require one to go through all the branches to count the result. (If it is the first 50 ...)

I guess your approach is to eliminate branches to avoid execute some branches. What is the elimination strategy?

One major jump from 9 loops to base n loop of n for each digit (as your read me said) to try to do the number calculation I.e. Loop a and b then calculate c = a-b and d=11111...1(n) - c. Then use bit vector to check uniqueness. That is my next Lisp next stage.

I would try to read yours over the weekend.

Ps and also trace more the c generative version.

[phiSgr]

I used lazy list because

• I wanted to try that library
• it fits my way of thinking, i.e., value oriented
• creating the value and transforming the value can be written separately, thus easier

Well I do find my code quite readable, perhaps it is just me. Feel free to tell me where it is not easily understood, I will try to explain.

[dng8888]

Sorry it is just my problem. I do not know your language (!) and hence it is not the horse it is the man.

But after reading your read me I wonder what optimisation strategy you are using and how different it is from the c program I am currently studying.

I would try to read yours again this weekend as I am trying to find way to improve my lisp - I expect 1 to 2 order of magnitude not 6. The reading of the normal c (non advance version) seemed help, after walking through it using x code. The reading of the advance version is much harder. Would try again this weekend in // to yours.

Not sure I will dig your language that deep as I would under c (due to objective c, I knew a bit more that line), but is there any symbolic level tracer and debugger I can use for yours under Mac OS X? An interesting language. Learn ML a bit before. Find its way very interesting. Not sure about ocaml.

[dng8888]

Trying for 2 hours but I think the Mac ports of ocaml has some issues:

ld: symbol(s) not found for architecture x86_64

Download other simple codes rely upon core and all doe not work but ocaml itself work, as some examples compile and run. Move back to c, after post a question to stack overflow : http://stackoverflow.com/questions/36658920/ld-symbols-not-found-for-architecture-x86-64-ocaml

[phiSgr]

No idea with your problem, I used brew to install OCaml and OPAM then used OPAM to install core and core_extended.

[jackhftang]

I used brew to install ocaml too, no problems encountered.