www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Algorithms to solve programming contest problems

reply Walter Bright <newshound2 digitalmars.com> writes:
http://www.quora.com/What-are-the-algorithms-required-to-solve-all-problems-using-C++-in-any-competitive-coding-contest

Anyone want to review these and see what we should add to Phobos?
Oct 25 2014
next sibling parent reply "Vic" <vic apakau.com> writes:
On Saturday, 25 October 2014 at 20:51:04 UTC, Walter Bright wrote:
 http://www.quora.com/What-are-the-algorithms-required-to-solve-all-problems-using-C++-in-any-competitive-coding-contest

 Anyone want to review these and see what we should add to 
 Phobos?
I have enormous respect for Walter, this has me betting my company on D. But how I wish this said: hey, anyone know of what we can remove from D or move to downstream? JRE has Oracle and 100 devs, CLR has MS and 100 dec, there are 7 for D, and it should be narrow, like LUA. It should have 7% of their platform. Majority of scared cows must be killed, the sooner leaders realize the better.
Oct 25 2014
next sibling parent reply Martin Nowak <code+news.digitalmars dawg.eu> writes:
On 10/26/2014 02:37 AM, Vic wrote:
 JRE has Oracle and 100 devs, CLR has MS and 100 dec, there are 7
 for D, and it should be narrow, like LUA. It should have 7% of
 their platform. Majority of scared cows must be killed, the
 sooner leaders realize the better.
I'd actually also like to see less things being stuffed into phobos. Now that we have dub and code.dlang.org the benefit of adding something to phobos instead of maintaining it as a separate library is much smaller. And we already have some unmaintained/problematic modules in phobos that would be better as external libraries (std.signals, std.net.curl, std.xml).
Oct 26 2014
next sibling parent reply ketmar via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Sun, 26 Oct 2014 21:58:27 +0100
Martin Nowak via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 I'd actually also like to see less things being stuffed into phobos.
 Now that we have dub and code.dlang.org the benefit of adding
 something to phobos instead of maintaining it as a separate library
 is much smaller. And we already have some unmaintained/problematic
 modules in phobos that would be better as external libraries
 (std.signals, std.net.curl, std.xml).
please, no! ;-) there is alot sense of having many things in phobos. for beginners it's much easier to use just compiler and standard library, for example. it's much easier than "oh, well, compiler. and that strange 'dub' thing. and i have to write 'dubfile' to pull that library. and... uh-oh, internet connection. and... ah, forget it!" and there is rdmd, which is *very* handy for scripting. i found myself writing alot of CLI scripts in D instead of bash/tcl/smth-other. and last, but not least: not everyone wants to switch to dub. let phobos have alot of things. thay may be suboptimal, but at least they are here when someone needs 'em. and i really want libasync to be included too! ;-)
Oct 26 2014
parent reply Martin Nowak <code+news.digitalmars dawg.eu> writes:
On 10/26/2014 10:11 PM, ketmar via Digitalmars-d wrote:
 please, no! ;-) there is alot sense of having many things in phobos.
 for beginners it's much easier to use just compiler and standard
 library, for example.  it's much easier than "oh, well, compiler. and
 that strange 'dub' thing.
Well dmd isn't any simpler than dub.
 and i have to write 'dubfile' to pull that library.
We plan to support single files with dub (https://github.com/D-Programming-Language/dub/issues/103). and... uh-oh, internet connection. and... ah, forget it!" Seriously, internet connection, well you can fetch packages and use them locally.
 and there is rdmd, which is *very* handy for scripting. i found myself
 writing alot of CLI scripts in D instead of bash/tcl/smth-other.
See single file support in dub.
 and last, but not least: not everyone wants to switch to dub.
What's the problem?
 let phobos have alot of things. thay may be suboptimal, but at least
 they are here when someone needs 'em.
No, it means we (a few people) have to maintain all that stuff.
 and i really want libasync to be
 included too! ;-)
That's 1 approach to asynchronous computation and callbacks have severe drawbacks. I'm happy to see that someone sat down and wrote that epoll/kqueue/IOCP abstraction but I don't think there is a standard async solution.
Oct 26 2014
next sibling parent ketmar via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Sun, 26 Oct 2014 23:42:14 +0100
Martin Nowak via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 and last, but not least: not everyone wants to switch to dub.
What's the problem?
my own build tool can build alot more things than just D sources. for example, build C library with D project. and many more. it is based on 'jam', but i made alot of changes to it. dub will never be able to do the same, at least until it has no scripting language. and if it will get scripting language... well, i don't like to rewrite all my jamfiles for dub. ;-) my jam can work as 'configure', it has module to use D library repository (yes, i have to update that manually and there is no versioning for now, but i just don't need that, it's not hard to add) with dependencies (i.e. doing 'dlang.require derelict.sdl2' will automatically add derelict.util and -ldl to link flags, and so on. please note that i'm not trying to tell that dub is bad or something. dub is great, it just don't fit my needs (and probably never will, 'cause it's architecture is different from what i used to).
 let phobos have alot of things. thay may be suboptimal, but at least
 they are here when someone needs 'em.
No, it means we (a few people) have to maintain all that stuff.
yes, i understand that phobos has alot of code and it's hard to maintain it. i'm just throwing in my $0.02, but i'm in no way forcing someone to do something just because it is useful for me and i don't want to do it myself. ;-)
Oct 26 2014
prev sibling parent reply Russel Winder via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Sun, 2014-10-26 at 23:42 +0100, Martin Nowak via Digitalmars-d wrote:
[=E2=80=A6]
 Seriously, internet connection, well you can fetch packages and use them=
=20
 locally.
[=E2=80=A6] Yes seriously, having to have an Internet connection, to get anything started is a serious problem for many people. When at home it is not a problem, when on the road it is a ####### disaster. As with Maven, Gradle, (anything in the JVM-verse with artefact dependencies) you have to pre-plan having all the artefacts you might want before leaving the Internet. Thus no serendipitous starting of new work. Until the Internet is a high speed resource free for everyone at all times everywhere, please do not hardwire into build tools assumptions that it is there Internet connectivity as Maven originally did. --=20 Russel. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.n= et 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Oct 27 2014
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Monday, 27 October 2014 at 09:10:41 UTC, Russel Winder via 
Digitalmars-d wrote:
 On Sun, 2014-10-26 at 23:42 +0100, Martin Nowak via 
 Digitalmars-d wrote:
 […]
 Seriously, internet connection, well you can fetch packages 
 and use them locally.
[…] Yes seriously, having to have an Internet connection, to get anything started is a serious problem for many people. When at home it is not a problem, when on the road it is a ####### disaster. As with Maven, Gradle, (anything in the JVM-verse with artefact dependencies) you have to pre-plan having all the artefacts you might want before leaving the Internet. Thus no serendipitous starting of new work. Until the Internet is a high speed resource free for everyone at all times everywhere, please do not hardwire into build tools assumptions that it is there Internet connectivity as Maven originally did.
dub functions fine without internet connection. Packages already in ~/.dub (or wherever else you might choose) are used. There isn't anything important to be done to fix this any further: If you want to get code you haven't already decided to download, you're going to have to have an internet connection and download it.
Oct 27 2014
next sibling parent Russel Winder via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Mon, 2014-10-27 at 09:19 +0000, John Colvin via Digitalmars-d wrote:
[=E2=80=A6]
 dub functions fine without internet connection. Packages already=20
 in ~/.dub (or wherever else you might choose) are used.
=20
 There isn't anything important to be done to fix this any=20
 further: If you want to get code you haven't already decided to=20
 download, you're going to have to have an internet connection and=20
 download it.
Indeed, dub currently behaves exactly as Maven and Gradle, and as it should. The workflow for all build systems which handle dependency artefacts stored centrally is fundamentally the same. =20 --=20 Russel. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.n= et 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Oct 27 2014
prev sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Monday, 27 October 2014 at 09:19:26 UTC, John Colvin wrote:
 On Monday, 27 October 2014 at 09:10:41 UTC, Russel Winder via 
 Digitalmars-d wrote:
 On Sun, 2014-10-26 at 23:42 +0100, Martin Nowak via 
 Digitalmars-d wrote:
 […]
 Seriously, internet connection, well you can fetch packages 
 and use them locally.
[…] Yes seriously, having to have an Internet connection, to get anything started is a serious problem for many people. When at home it is not a problem, when on the road it is a ####### disaster. As with Maven, Gradle, (anything in the JVM-verse with artefact dependencies) you have to pre-plan having all the artefacts you might want before leaving the Internet. Thus no serendipitous starting of new work. Until the Internet is a high speed resource free for everyone at all times everywhere, please do not hardwire into build tools assumptions that it is there Internet connectivity as Maven originally did.
dub functions fine without internet connection. Packages already in ~/.dub (or wherever else you might choose) are used.
And how is it going to get there? It is common for build service (openSUSE's OBS for instance) to disable all internet connectivity. All things that are necessary for building get installed by the build service from prebuilt packages _before_ the system is booted. It cannot download additional files during the build process.
Oct 27 2014
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Monday, 27 October 2014 at 13:24:26 UTC, Marc Schütz wrote:
 On Monday, 27 October 2014 at 09:19:26 UTC, John Colvin wrote:
 On Monday, 27 October 2014 at 09:10:41 UTC, Russel Winder via 
 Digitalmars-d wrote:
 On Sun, 2014-10-26 at 23:42 +0100, Martin Nowak via 
 Digitalmars-d wrote:
 […]
 Seriously, internet connection, well you can fetch packages 
 and use them locally.
[…] Yes seriously, having to have an Internet connection, to get anything started is a serious problem for many people. When at home it is not a problem, when on the road it is a ####### disaster. As with Maven, Gradle, (anything in the JVM-verse with artefact dependencies) you have to pre-plan having all the artefacts you might want before leaving the Internet. Thus no serendipitous starting of new work. Until the Internet is a high speed resource free for everyone at all times everywhere, please do not hardwire into build tools assumptions that it is there Internet connectivity as Maven originally did.
dub functions fine without internet connection. Packages already in ~/.dub (or wherever else you might choose) are used.
And how is it going to get there? It is common for build service (openSUSE's OBS for instance) to disable all internet connectivity. All things that are necessary for building get installed by the build service from prebuilt packages _before_ the system is booted. It cannot download additional files during the build process.
I'm not sure I fully understand, but `dub upgrade` will download all the dependencies for the current package. The --cache=VALUE option can be used to specify where you want them put.
Oct 27 2014
parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Monday, 27 October 2014 at 13:44:23 UTC, John Colvin wrote:
 On Monday, 27 October 2014 at 13:24:26 UTC, Marc Schütz wrote:
 On Monday, 27 October 2014 at 09:19:26 UTC, John Colvin wrote:
 dub functions fine without internet connection. Packages 
 already in ~/.dub (or wherever else you might choose) are 
 used.
And how is it going to get there? It is common for build service (openSUSE's OBS for instance) to disable all internet connectivity. All things that are necessary for building get installed by the build service from prebuilt packages _before_ the system is booted. It cannot download additional files during the build process.
I'm not sure I fully understand, but `dub upgrade` will download all the dependencies for the current package. The --cache=VALUE option can be used to specify where you want them put.
I'm speaking about this: https://build.opensuse.org/ This is for openSUSE, but Redhat/Fedore, Debian and others have similar services. They are used to build software packages (RPM, DEB) for all of a Linux distributions programs and libraries from the source. Each build starts off with a completely freshly installed environment (VM), and during it there is not internet connection. It can only access files from other packages that the build service has preinstalled into this system (as specified in the package's dependencies), or the package's source files. This means that in order to build a DUB based project in such a system, there must not be external dependencies that DUB itself downloads. Instead, these dependencies need to be built separately as *-devel packages and then pulled as build requirements. Thus DUB needs to be told _not_ to download libraries, but use those that are already present in the system.
Oct 27 2014
prev sibling parent "rst256" <ussr.24 yandex.ru> writes:
On Sunday, 26 October 2014 at 20:58:39 UTC, Martin Nowak wrote:
 On 10/26/2014 02:37 AM, Vic wrote:
 JRE has Oracle and 100 devs, CLR has MS and 100 dec, there are 
 7
 for D, and it should be narrow, like LUA. It should have 7% of
 their platform. Majority of scared cows must be killed, the
 sooner leaders realize the better.
I'd actually also like to see less things being stuffed into phobos. Now that we have dub and code.dlang.org the benefit of adding something to phobos instead of maintaining it as a separate library is much smaller. And we already have some
Please tell us more. Separation libraries may accelerate the program's execution, or only compilation speed?
 unmaintained/problematic modules in phobos that would be better 
 as external libraries (std.signals, std.net.curl, std.xml).
Oct 27 2014
prev sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
26-Oct-2014 04:37, Vic пишет:
 On Saturday, 25 October 2014 at 20:51:04 UTC, Walter Bright wrote:
 http://www.quora.com/What-are-the-algorithms-required-to-solve-all-problems-using-C++-in-any-competitive-coding-contest


 Anyone want to review these and see what we should add to Phobos?
I have enormous respect for Walter, this has me betting my company on D. But how I wish this said: hey, anyone know of what we can remove from D or move to downstream?
Me too. I'd rather see a cleanup of both the language and the library. More specifically I believe that std lib should do: 1. Set a canonical standard "interface" for 3rd party libraries to model on - e.g. ranges in large part do that. Same stuff must happen with exception hierarchy, containers, common OS APIs (Memory, VFS, Networking etc.) and a whole lot of more minor things. This is a bare minimum that it must accomplish, it need not have fast implementation but well thought out & easy interface. 2. Next level - be flexible and define standard for extensibility. That is to allow 3rd party libraries to _extend_ the standard interface (by deriving or satisfying similar constraints) rather then re-implement similar interfaces. Again very few modules do that currently: std.range, std.algo, std.digest and maybe one more (upcoming st.logger - might be?). Many, many traits are too narrow to be useful. 3. Even higher - both interfaces & implementations are pluggable, by providing common middle ground as a set of primitives. The idea is to provide a set low-level primitives that any non-std interface may use to get to re-use standard-compliant "backend", including the default one. A major example where (3) is useful would be logging that 9 people do in 13 incompatible ways (esp the interface side). Building on these principles, I should probably fill bugzilla with a bunch of enhancements. A couple of examples of missing good standards: 1. std.zip handles ZIP archives with same bizarre interface that absolutely unlike handling normal file system. 2. DOM-style parsers for XML and JSON are very unlike each other.
 JRE has Oracle and 100 devs, CLR has MS and 100 dec, there are 7
 for D, and it should be narrow, like LUA.
In all fairness the problem of Orcale is different, they mess with tons of legacy code in Java they cannot leave behind. So D can sky rocket with far less dev force (~10-20), especially with the more powerful language. Problem is our devs are pure enthusiasts with a bit of spare time to spent.
 It should have 7% of
 their platform.
We should take the most important 20%, everything else is evolutionary detritus anyway ;)
 Majority of scared cows must be killed, the
 sooner leaders realize the better.
I think now that we have Dub repository, we could just let it grow and look at the fittest designs to boot the standard from. Maybe start labeling the most popular as "featured", and have "new" in the same vane. -- Dmitry Olshansky
Oct 26 2014
prev sibling next sibling parent "rst256" <ussr.24 yandex.ru> writes:
On Saturday, 25 October 2014 at 20:51:04 UTC, Walter Bright wrote:
 http://www.quora.com/What-are-the-algorithms-required-to-solve-all-problems-using-C++-in-any-competitive-coding-contest

 Anyone want to review these and see what we should add to 
 Phobos?
Dear Mr. Bright. Just can not now comment. Please see this code. test code and profililing log. src\phobos\std\stdio.d: lines 361-373 ------------------------------- */ /*file and line in this is demo solve. Just for profilling. I now more safety way. */ this(string name, in char[] stdioOpenmode = "rb", string file = __FILE__, size_t line = __LINE__) safe { import std.conv : text; import std.exception : ErrnoException; /*this(errnoEnforce(.fopen(name, stdioOpenmode), text("Cannot open file `", name, "' in mode `", stdioOpenmode, "'")), name); */ if (!.fopen(name, stdioOpenmode)) throw new ErrnoException(text("Cannot open file `", name, "' in mode `", stdioOpenmode, "'"), file, line); } file.d(test code)----------------------------------------------------------- import std.stdio; void main(string[] args) { /*int i; int a[2]; if(true) i = 3; a[i] = 3;*/ auto fobj = File("hello2.d"); scope(failure) writefln("scope(failure)"); scope(exit) writefln("scope(exit)"); writefln("end"); } profiler log for file.d with old version phobos---------------------- ------------------ 1 _Dmain 7 main _D6object14__T4_dupTxaTaZ4_dupFNaNbAxaZAa 8 89 80 8 _D6object19__T11_doPostblitTaZ11_doPostblitFNaNbNiAaZv ------------------ 8 _D6object14__T4_dupTxaTaZ4_dupFNaNbAxaZAa _D6object19__T11_doPostblitTaZ11_doPostblitFNaNbNiAaZv 8 9 9 ------------------ 1 main _Dmain 1 40831907 40831897 1 _D6object14__T4_dupTxaTaZ4_dupFNaNbAxaZAa ------------------ main 0 0 0 1 _Dmain 7 _D6object14__T4_dupTxaTaZ4_dupFNaNbAxaZAa ======== Timer Is 3579545 Ticks/Sec, Times are in Microsecs ======== Num Tree Func Per Calls Time Time Call 1 11407010 11407007 11407007 _Dmain 8 24 22 2 pure nothrow char[] object._dup!(const(char), char)._dup(const(char)[]) 8 2 2 0 pure nothrow nogc void object._doPostblit!(char)._doPostblit(char[]) 1 0 0 0 main new version------------------------------------------- ------------------ 1 _Dmain 7 main _D6object14__T4_dupTxaTaZ4_dupFNaNbAxaZAa 8 102 88 8 _D6object19__T11_doPostblitTaZ11_doPostblitFNaNbNiAaZv ------------------ 8 _D6object14__T4_dupTxaTaZ4_dupFNaNbAxaZAa _D6object19__T11_doPostblitTaZ11_doPostblitFNaNbNiAaZv 8 14 14 ------------------ 1 main _Dmain 1 2336665 2336654 1 _D6object14__T4_dupTxaTaZ4_dupFNaNbAxaZAa ------------------ main 0 0 0 1 _Dmain 7 _D6object14__T4_dupTxaTaZ4_dupFNaNbAxaZAa ======== Timer Is 3579545 Ticks/Sec, Times are in Microsecs ======== Num Tree Func Per Calls Time Time Call 1 652782 652779 652779 _Dmain 8 28 24 3 pure nothrow char[] object._dup!(const(char), char)._dup(const(char)[]) 8 3 3 0 pure nothrow nogc void object._doPostblit!(char)._doPostblit(char[]) 1 0 0 0 main I not check the other functions, because not sure that this style of coding is enough object oriented. It object only because that here you have objects. if you need it, let's work. Best regards.
Oct 26 2014
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Walter Bright:

 http://www.quora.com/What-are-the-algorithms-required-to-solve-all-problems-using-C++-in-any-competitive-coding-contest

 Anyone want to review these and see what we should add to 
 Phobos?
It's a good idea to help people that want to use D for contests, because contests require to write small programs from scratch and this is a very good situation to try new/uncommon languages as D. Some of those algorithms seem too much large to implement for Phobos (Voronoi), other seem too much specialized, but some of them seem acceptable for Phobos. Regarding simple but very useful things to add to Phobos, I have several Phobos enhancement requests in Bugzilla, that are often more basic than the algorithms in that page. If you want I can list some of them here. Bye, bearophile
Oct 27 2014