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


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


 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


 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


 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