L'algorithme de cette semaine: calculez l'itinéraire le plus court! (Itérateur de permutation en Ruby / Python / C # / VB / Go)

Problème https://codeiq.jp/ace/thisweek_masuipeo/q608 Permission Granted as https://twitter.com/masuipeo/status/410915846987345920 Résumé https://github.com/cielavenir/procon/commit/9eab68d94840331618eb8e4c07b84fb0c0adb8b0

Go et JavaScript sont de loin les langages les plus rapides qui ne nécessitent pas de compilation. Ruby fait également de son mieux. Comme rdmd est compilé en interne, il est rapide après la deuxième fois. Boo semble être un peu plus rapide, mais Boo est difficile à taper. C # est meilleur. C'est rapide. Même ainsi, R est lent ...

[140104 postscript] Perl6 est trop mauvais ... w

Puisque je peux utiliser des langues, je dois écrire sur next_permutation, donc j'avais l'intention d'écrire next_permutation en 20 langues (rires) Tout a commencé avec Ruby

#!/usr/bin/ruby
class Array
	def unique_permutation(n=self.size)
		return to_enum(:permutation2,n) unless block_given?
		return if n<0||self.size<n
		a=self.sort
		yield a[0,n]
		while true
			a=a[0,n]+a[n..-1].reverse
			k=(a.size-2).downto(0).find{|i|a[i]<a[i+1]}
			break if !k
			l=(a.size-1).downto(k+1).find{|i|a[k]<a[i]}
			a[k],a[l]=a[l],a[k]
			a=a[0,k+1]+a[k+1..-1].reverse
			yield a[0,n]
		end
	end
	def partial_sum
=begin
		s=[0]
		0.step(self.size-1){|i|s<<s[i]+self[i]}
		s
=end
		self.reduce([0]){|s,e|s<<s.last+e}
	end
end

N=6
P=([0]*N+[1]*N).unique_permutation.to_a # N=Quand 5, permutation.to_a.70 fois plus rapide que uniq
#Chaque P représente une route. 1 est vertical et 0 est horizontal.
r=0
i=0
e=[0]*(N*2+1)
f=[0]*(N*2+1)
P.each{|e0|
	(N*2).times{|i|e[i+1]=e[i]+e0[i]}
	#En supposant que la partie inférieure gauche est A et la partie supérieure droite est B comme dans le système de coordonnées mathématiques, la coordonnée x est i à chaque indice i de e.-e[i], La coordonnée Y est e[i]Sera.
	P.each{|f0|
		r+=1 if (N*2).times.none?{|i|
			f[i+1]=f[i]+f0[i]
			#i-ème coordonnée et i+Si les premières coordonnées sont égales, on peut considérer qu'il y a un chevauchement dans la route.
			e[i]==f[i] && e[i+1]==f[i+1]
		}
	}
}
p r # 100360

C'est parce qu'il était beaucoup plus rapide que la permutation Array #. En fait, permutation.to_a.uniq n'a pas pu être exécuté en raison d'un manque de mémoire en premier lieu. Donc, j'ai écrit une permutation qui élimine la duplication.

Python

#!/usr/bin/python
#coding:utf-8
import sys
if sys.version_info[0]>=3: from functools import reduce

def find(cond,a):
	for e in a:
		if cond(e): return e
	return None
def permutation(x,n=None):
	if n==None: n=len(x)
	if n<0 or len(x)<n: return
	a=sorted(x)
	yield tuple(a[0:n])
	while True:
		a=a[0:n]+a[len(a)-1:n-1:-1]
		k=find(lambda i: a[i]<a[i+1], range(len(a)-2,-1,-1))
		if k==None: break
		l=find(lambda i: a[k]<a[i], range(len(a)-1,k,-1))
		a[k],a[l]=a[l],a[k]
		a=a[0:k+1]+a[len(a)-1:k:-1]
		yield tuple(a[0:n])

N=6
e0=[0]*N+[1]*N
f0=[0]*N+[1]*N
#Chaque P représente une route. 1 est vertical et 0 est horizontal.
r=0
i=0
e=[0]*(N*2+1)
f=[0]*(N*2+1)
for _e in permutation(e0):
	for i in range(N*2): e[i+1]=e[i]+_e[i]
	#e=reduce(lambda s,_: (s.append(s[-1:][0]+_),s)[1],e0,[0])
	#En supposant que la partie inférieure gauche est A et la partie supérieure droite est B comme dans le système de coordonnées mathématiques, la coordonnée x est i à chaque indice i de e.-e[i], La coordonnée Y est e[i]Sera.
	for _f in permutation(f0):
		for i in range(N*2): f[i+1]=f[i]+_f[i]
		#f=reduce(lambda s,_: (s.append(s[-1:][0]+_),s)[1],f0,[0])
		if all(e[i]!=f[i] or e[i+1]!=f[i+1] for i in range(N*2)): r+=1
		#i-ème coordonnée et i+Si les premières coordonnées sont égales, on peut considérer qu'il y a un chevauchement dans la route.
print(r) # 100360

C#

using System;
using System.Collections.Generic;
class CodeIQRoute{
	static IEnumerable<List<T>> Permutation<T>(List<T> x,int? _n=null) where T : IComparable<T>{
		int n=_n ?? x.Count;
		if(n<0||x.Count<n)yield break;
		List<T> a=new List<T>(x);
		a.Sort();
		yield return a.GetRange(0,n);
		for(;;){
			int i;
			a.Reverse(n,a.Count-n);
			for(i=a.Count-2;i>=0;i--)if(a[i].CompareTo(a[i+1])<0)break;
			if(i<0){
				//a.Reverse(0,a.Count);
				/*yield*/ break;
			}
			int k=i;
			for(i=a.Count-1;i>=k+1;i--)if(a[k].CompareTo(a[i])<0)break;
			int l=i;
			T z=a[k];a[k]=a[l];a[l]=z;
			a.Reverse(k+1,a.Count-(k+1));
			yield return a.GetRange(0,n);
		}
	}
	const int N=6;
	public static void Main(){
		int r=0,i;
		List<int>e0=new List<int>(),f0=new List<int>();
		for(i=0;i<N;i++){e0.Add(0);f0.Add(0);}
		for(i=0;i<N;i++){e0.Add(1);f0.Add(1);}
		int[] e=new int[N*2+1];
		int[] f=new int[N*2+1];
		foreach(List<int> _e in Permutation(e0)){
			for(i=0;i<N*2;i++)e[i+1]=e[i]+_e[i];
			foreach(List<int> _f in Permutation(f0)){
				for(i=0;i<N*2;i++){
					f[i+1]=f[i]+_f[i];
					if(e[i]==f[i]&&e[i+1]==f[i+1])break;
				}
				if(i==N*2)r++;
			}
		}
		Console.WriteLine(r);
	}
}

VB.Net

imports System
imports System.Collections.Generic
module CodeIQRoute
	iterator function permutation(of T as IComparable)(ByVal x as List(of T),optional ByVal _n as integer?=Nothing) as IEnumerable(of List(of T))
		dim n as integer=if(_n.HasValue,_n,x.Count)
		if n<0 orelse x.Count<n
			return
		end If
		dim a as List(of T)=new List(of T)(x)
		a.Sort()
		dim i as integer
		yield a.GetRange(0,n)
		while true
			a.Reverse(n,a.Count-n)
			for i=a.Count-2 to 0 step -1
				if a(i).CompareTo(a(i+1))<0
					exit for
				end if
			next
			if i<0
				a.Reverse(0,a.Count)
				return
			end if
			dim k as integer=i
			for i=a.Count-1 to k+1 step -1
				if a(k).CompareTo(a(i))<0
					exit for
				end if
			next
			dim l as integer=i
			dim z as T=a(k):a(k)=a(l):a(l)=z
			a.Reverse(k+1,a.Count-(k+1))
			yield a.GetRange(0,n)
		end while
	end function

	const N=6
	sub Main(ByVal args() as String)
		dim r,i as integer
		dim e0 as List(of integer)=new List(of integer)()
		dim f0 as List(of integer)=new List(of integer)()
		for i=0 to N-1
			e0.Add(0)
			f0.Add(0)
		next
		for i=0 to N-1
			e0.Add(1)
			f0.Add(1)
		next
		dim e as integer()=new integer(N*2){}
		dim f as integer()=new integer(N*2){}
		for each _e as List(of integer) in permutation(e0)
			for i=0 to N*2-1
				e(i+1)=e(i)+_e(i)
			next
			for each _f as List(of integer) in permutation(f0)
				for i=0 to N*2-1
					f(i+1)=f(i)+_f(i)
					if e(i)=f(i) andalso e(i+1)=f(i+1)
						exit for
					end if
				next
				if i=N*2
					r+=1
				end if
			next
		next
		Console.WriteLine(r)
	end sub
end module

Go C'est un peu sale car il n'y a pas de génériques. J'ai aussi essayé de revoir la réflexion.

package main
import (
	"fmt"
	"sort"
	"reflect"
)

/*
func compare(a interface{},b interface{}) int{ // a and b must have the same type. If different, runtime error will be triggered. will be fixed after generics is introduced.
	switch reflect.ValueOf(a).Kind() {
		case reflect.Int:
			n1:=reflect.ValueOf(a).Int()
			n2:=reflect.ValueOf(b).Int()
			if n1<n2 {return -1} else if n1>n2 {return 1} else {return 0}
		case reflect.Float32: case reflect.Float64:
			n1:=reflect.ValueOf(a).Float()
			n2:=reflect.ValueOf(b).Float()
			if n1<n2 {return -1} else if n1>n2 {return 1} else {return 0}
		case reflect.String:
			n1:=reflect.ValueOf(a).String()
			n2:=reflect.ValueOf(b).String()
			if n1<n2 {return -1} else if n1>n2 {return 1} else {return 0}
	}
	return 0 //lol
}
func reflect_reverse(a reflect.Value,start int,size int){
	for end:=start+size-1;start<end;start++ {
		z:=a.Index(start).Interface()
		a.Index(start).Set(a.Index(end))
		a.Index(end).Set(reflect.ValueOf(z))
		end--
	}
}
func permutation(x interface{}, n int) <- chan reflect.Value{
	ch := make(chan reflect.Value)
	go func(){
		if 0<=n&&n<=reflect.ValueOf(x).Len() {
			a:=reflect.MakeSlice(reflect.TypeOf(x),reflect.ValueOf(x).Len(),reflect.ValueOf(x).Len())
			reflect.Copy(a,reflect.ValueOf(x))
			//sort.Sort(sort.IntSlice(a)); //interface{} cannot be sorted, so you must sort the array prior.
			ch <- a
			for {
				reflect_reverse(a,n,a.Len()-n)
				i:=0
				for i=a.Len()-2;i>=0;i-- {if compare(a.Index(i).Interface(),a.Index(i+1).Interface())<0 {break}}
				if i<0 {
					//reflect_reverse(a,0,a.Len())
					break
				}
				k:=i
				for i=a.Len()-1;i>=k+1;i-- {if compare(a.Index(k).Interface(),a.Index(i).Interface())<0 {break}}
				l:=i
				z:=a.Index(k).Interface()
				a.Index(k).Set(a.Index(l))
				a.Index(l).Set(reflect.ValueOf(z))
				reflect_reverse(a,k+1,a.Len()-(k+1))
				ch <- a
			}
		}
		close(ch)
	}()
	return ch
}
*/
func reverse(a sort.Interface,start int,size int){
	for end:=start+size-1;start<end;start++ {
		a.Swap(start,end)
		end--
	}
}
func permutation(a sort.Interface, n int) <- chan reflect.Value{
	ch := make(chan reflect.Value)
	go func(){
		if 0<=n&&n<=a.Len() {
			sort.Sort(a); // a is modified directly, so never write to it within the block
			ch <- reflect.ValueOf(a)
			for {
				reverse(a,n,a.Len()-n)
				i:=0
				for i=a.Len()-2;i>=0;i-- {if a.Less(i,i+1) {break}}
				if i<0 {
					reverse(a,0,a.Len())
					break
				}
				k:=i
				for i=a.Len()-1;i>=k+1;i-- {if a.Less(k,i) {break}}
				l:=i
				a.Swap(k,l)
				reverse(a,k+1,a.Len()-(k+1))
				ch <- reflect.ValueOf(a)
			}
		}
		close(ch)
	}()
	return ch
}

func main(){
	N:=6
	e0:=make([]int,N*2)
	f0:=make([]int,N*2)
	i:=0
	r:=0
	for i=0;i<N;i++ {e0[N+i]=1;f0[N+i]=1}
	e:=make([]int,N*2+1);
	f:=make([]int,N*2+1);
	for _e:=range permutation(sort.IntSlice(e0),len(e0)) {
		for i=0;i<N*2;i++ {e[i+1]=e[i]+_e.Index(i).Interface().(int)}
		for _f:=range permutation(sort.IntSlice(f0),len(f0)) {
			for i=0;i<N*2;i++ {
				f[i+1]=f[i]+_f.Index(i).Interface().(int)
				if e[i]==f[i]&&e[i+1]==f[i+1] {break}
			}
			if i==N*2 {r++}
		}
	}
	fmt.Println(r)
}