[MN-dev] [mndiff]: r157 - in trunk/ffvotetov: . beatpairtest.txt ffvotetov.c input.txt minimax-fail.txt
michael
subversion at mplayerhq.hu
Tue Dec 15 17:53:52 CET 2009
Author: michael
Date: Tue Dec 15 17:53:52 2009
New Revision: 157
Log:
Initial commit of my vote counting software.
Added:
trunk/ffvotetov/
trunk/ffvotetov/beatpairtest.txt
trunk/ffvotetov/ffvotetov.c
trunk/ffvotetov/input.txt
trunk/ffvotetov/minimax-fail.txt
Added: trunk/ffvotetov/beatpairtest.txt
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/ffvotetov/beatpairtest.txt Tue Dec 15 17:53:52 2009 (r157)
@@ -0,0 +1,128 @@
+1 B
+2 A
+3 C
+4 D
+
+1 B
+2 A
+3 C
+4 D
+1 B
+2 A
+3 C
+4 D
+1 B
+2 A
+3 C
+4 D
+1 B
+2 A
+3 C
+4 D
+1 B
+2 A
+3 C
+4 D
+1 B
+2 A
+3 C
+4 D
+--
+1 C
+2 D
+3 A
+4 B
+1 C
+2 D
+3 A
+4 B
+1 C
+2 D
+3 A
+4 B
+1 C
+2 D
+3 A
+4 B
+1 C
+2 D
+3 A
+4 B
+--
+1 D
+2 B
+3 A
+4 C
+1 D
+2 B
+3 A
+4 C
+1 D
+2 B
+3 A
+4 C
+1 D
+2 B
+3 A
+4 C
+1 D
+2 B
+3 A
+4 C
+--
+1 C
+2 A
+3 D
+4 B
+1 C
+2 A
+3 D
+4 B
+1 C
+2 A
+3 D
+4 B
+1 C
+2 A
+3 D
+4 B
+--
+1 B
+2 C
+3 A
+4 D
+1 B
+2 C
+3 A
+4 D
+1 B
+2 C
+3 A
+4 D
+1 B
+2 C
+3 A
+4 D
+--
+1 D
+2 A
+3 B
+4 C
+1 D
+2 A
+3 B
+4 C
+--
+1 A
+2 D
+3 B
+4 C
+1 A
+2 D
+3 B
+4 C
+--
+1 A
+2 C
+3 D
+4 B
\ No newline at end of file
Added: trunk/ffvotetov/ffvotetov.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/ffvotetov/ffvotetov.c Tue Dec 15 17:53:52 2009 (r157)
@@ -0,0 +1,251 @@
+/*
+ * copyright (c) 2009 Michael Niedermayer <michaelni at gmx.at>
+ *
+ * ffvotetov is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * ffvotetov is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with ffvotetov; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
+#include <inttypes.h>
+
+#undef NDEBUG
+#include <assert.h>
+
+
+#define CANDIDATES_MAX 100
+#define CANDIDATE_LEN 100
+
+char canditates[CANDIDATES_MAX][CANDIDATE_LEN];
+int canditate_count;
+
+int sums[CANDIDATES_MAX], subs[CANDIDATES_MAX];
+int pair_matrix[CANDIDATES_MAX][CANDIDATES_MAX];
+int pair_ranking_matrix[CANDIDATES_MAX][CANDIDATES_MAX];
+
+int cssd_beats[CANDIDATES_MAX][CANDIDATES_MAX];;
+
+int contains_loop(const int matrix[CANDIDATES_MAX][CANDIDATES_MAX]){
+ int m[CANDIDATES_MAX][CANDIDATES_MAX];
+ int s[CANDIDATES_MAX]={0};
+ int i,j,changed,ret;
+
+ for(j=0; j<canditate_count; j++){
+ for(i=0; i<canditate_count; i++){
+ m[i][j] = matrix[i][j] - matrix[j][i];
+ s[i] += m[i][j] < 0;
+ }
+ }
+
+ do{
+ changed=0;
+ ret=0;
+ for(i=0; i<canditate_count; i++){
+ if(!s[i]){
+ s[i]--;
+ changed=1;
+ for(j=0; j<canditate_count; j++){
+ s[j] -= (m[i][j] < 0) + (m[j][i] < 0);
+ m[i][j]= m[j][i]=0;
+ }
+ }else if(s[i]>0)
+ ret=1;
+ }
+ }while(changed);
+
+ return ret;
+}
+
+void print_condorcet_winners(const int matrix[CANDIDATES_MAX][CANDIDATES_MAX], int limit){
+ int j,k;
+
+ for(j=0; j<canditate_count; j++){
+ for(k=0; k<canditate_count; k++){
+ if(matrix[j][k] < matrix[k][j] - limit)
+ break;
+ }
+ if(k==canditate_count)
+ printf(" %s\n", canditates[j]);
+ }
+}
+
+void beatpath(int strength[CANDIDATES_MAX], const int matrix[CANDIDATES_MAX][CANDIDATES_MAX], int a){
+ int i, j, changed;
+
+ for(i=0; i<canditate_count; i++)
+ strength[i]= matrix[a][i] - matrix[i][a];
+
+ do{
+ changed=0;
+ for(i=0; i<canditate_count; i++){
+ for(j=0; j<canditate_count; j++){
+ int diff= matrix[i][j] - matrix[j][i];
+ if(strength[i] < diff)
+ diff= strength[i];
+ if(strength[j] < diff){
+ strength[j]= diff;
+ changed=1;
+ }
+ }
+ }
+ }while(changed);
+}
+
+void add_vote(int vote[CANDIDATES_MAX]){
+ int j,k;
+
+ for(j=0; j<CANDIDATES_MAX; j++){
+ if(vote[j]){
+ sums[j] -= vote[j];
+ subs[j] ++;
+ }
+ for(k=j+1; k<CANDIDATES_MAX; k++){
+ int score_j= vote[j] ? vote[j] : CANDIDATES_MAX;
+ int score_k= vote[k] ? vote[k] : CANDIDATES_MAX;
+ if(score_j < score_k)
+ pair_matrix[j][k]++;
+ if(score_j > score_k)
+ pair_matrix[k][j]++;
+ }
+ }
+
+ for(j=0; j<CANDIDATES_MAX; j++)
+ vote[j]=0;
+}
+
+int main(){
+ int i,j, k, num, cand_idx, limit;
+ int64_t max;
+ char line[1000], *p;
+ int last_num=-1;
+ int vote[CANDIDATES_MAX]={0};
+
+ //very lame parser below, this is not robust nor tamper proof,only use with manually checked input!
+ while(!feof(stdin)){
+ scanf("%999[^\n]\n", line);
+ num= strtol(line, &p, 0);
+ if(num>0){
+ if(last_num >= num)
+ add_vote(vote);
+ p+= strspn(p, " .:,;()[]{}=-_#~|");
+ for(cand_idx=0; cand_idx<canditate_count; cand_idx++)
+ if(!strcasecmp(canditates[cand_idx], p))
+ break;
+ if(cand_idx==canditate_count){
+ if(canditate_count==CANDIDATES_MAX){
+ fprintf(stderr, "Remove cadidate (try russian roulette if you have no fanatasy) or increase CANDIDATES_MAX\n");
+ exit(1);
+ }
+ strncpy(canditates[canditate_count++], p, CANDIDATE_LEN-1);
+ }
+ vote[cand_idx]= num;
+ last_num=num;
+ printf("Parsed as:%d %s\n", num, p);
+ }
+ }
+ add_vote(vote);
+ for(j=0; j<canditate_count; j++)
+ sums[j] += subs[j]*7; //canditate_count;
+
+ printf("Candidates:\n");
+ for(cand_idx=0; cand_idx<canditate_count; cand_idx++)
+ printf(" Borda:%3d \"%s\"\n", sums[cand_idx], canditates[cand_idx]);
+
+ printf("Pair table:\n");
+ for(j=0; j<canditate_count; j++){
+ for(k=0; k<canditate_count; k++){
+ printf(" [%4d%4d]", pair_matrix[j][k], pair_matrix[j][k] - pair_matrix[k][j]);
+ }
+ printf("\n");
+ }
+
+ printf("Condorcet winner(s):\n");
+ print_condorcet_winners(pair_matrix, 0);
+
+ printf("minimax winner(s):\n");
+ max= INT_MIN;
+ for(j=0; j<canditate_count; j++){
+ int min= INT_MAX;
+ for(k=0; k<canditate_count; k++){
+ int diff= pair_matrix[j][k] - pair_matrix[k][j];
+ if(diff < min) min=diff;
+ }
+ if(min>max) max= min;
+ }
+ print_condorcet_winners(pair_matrix, -max);
+
+ printf("nameless? sum:\n");
+ max= INT64_MIN;
+ for(i=0; i<2; i++){
+ for(j=0; j<canditate_count; j++){
+ int64_t sum=0;
+ for(k=0; k<canditate_count; k++){
+ int64_t diff= pair_matrix[j][k] - pair_matrix[k][j];
+ if(diff < 0) sum+=diff<<24;
+ else sum+=diff;
+ }
+ if(sum>max) max= sum;
+ if(sum == max && i)
+ printf(" %s\n", canditates[j]);
+ }
+ }
+
+ for(limit=INT_MAX; limit>1; ){
+ int max=1;
+ for(j=0; j<canditate_count; j++){
+ for(k=0; k<canditate_count; k++){
+ int diff= pair_matrix[j][k] - pair_matrix[k][j];
+ if(diff > max && diff < limit) max=diff;
+ }
+ }
+ limit=max;
+ for(j=0; j<canditate_count; j++){
+ for(k=0; k<canditate_count; k++){
+ int diff= pair_matrix[j][k] - pair_matrix[k][j];
+ if(diff==max){
+ pair_ranking_matrix[j][k] = pair_matrix[j][k];
+ pair_ranking_matrix[k][j] = pair_matrix[k][j];
+ }
+ }
+ }
+ if(contains_loop(pair_ranking_matrix)){
+ for(j=0; j<canditate_count; j++){
+ for(k=0; k<canditate_count; k++){
+ int diff= pair_matrix[j][k] - pair_matrix[k][j];
+ if(diff==max){
+ printf("Cycle, ignoring pair %d %d with score of %d\n", j, k, max);
+ pair_ranking_matrix[j][k] =
+ pair_ranking_matrix[k][j] = 0;
+ }
+ }
+ }
+ }
+ }
+ printf("Ranked pairs winner(s):\n");
+ print_condorcet_winners(pair_ranking_matrix, 0);
+
+ printf("Cloneproof schwartz sequential droping / beatpath winner(s):\n");
+ for(i=0; i<canditate_count; i++)
+ beatpath(cssd_beats[i], pair_matrix, i);
+ for(i=0; i<canditate_count; i++){
+ for(j=0; j<canditate_count; j++){
+ if(cssd_beats[i][j] < cssd_beats[j][i])
+ break;
+ }
+ if(j==canditate_count)
+ printf(" %s\n", canditates[i]);
+ }
+}
\ No newline at end of file
Added: trunk/ffvotetov/input.txt
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/ffvotetov/input.txt Tue Dec 15 17:53:52 2009 (r157)
@@ -0,0 +1,88 @@
+From: Vitor Sessak <vitor1001 at gmail.com>
+
+1. Free Multimedia Tech / freemediatech.org
+2. FFMTech (Foundation for Free Multimedia Technologies)
+3. FFmpeg Foundation
+4. FFmedia (Foundation for Free MultimEDIA)
+5. FFm.org (Foundation for Free Multimedia)
+6. FFMF (Fast Forward Multimedia Foundation)
+
+From: Thilo Borgmann <thilo.borgmann at googlemail.com>
+1 FFmedia (Foundation for Free MultimEDIA)
+2 Free Multimedia Tech / freemediatech.org
+3 FFMTech (Foundation for Free Multimedia Technologies)
+
+From: Ivo <ivop at euronet.nl>
+
+1. FFmedia (Foundation for Free MultimEDIA)
+
+From: Alex Converse <alex.converse at gmail.com>
+
+1 FFm.org (Foundation for Free Multimedia)
+2 FFmedia (Foundation for Free MultimEDIA)
+3 OMF (Open Multimedia Foundation)
+4 FFmpeg Foundation
+5 FFMF (Fast Forward Multimedia Foundation)
+6 FFMTech (Foundation for Free Multimedia Technologies)
+
+From: Guillaume POIRIER <poirierg at gmail.com>
+
+ 1. Free Multimedia Tech / freemediatech.org
+ 2. FFmedia (Foundation for Free MultimEDIA)
+ 3. FFMTech (Foundation for Free Multimedia Technologies)
+ 4.
+ 5. FFmpeg Foundation
+ 6. OMF (Open Multimedia Foundation)
+ 7. FFm.org (Foundation for Free Multimedia)
+ 8. FFMF (Fast Forward Multimedia Foundation)
+
+From: "Ronald S. Bultje" <rsbultje at gmail.com>
+My vote (bit late):
+1) FFmpeg Foundation
+2) FFMTech (Foundation for Free Multimedia Technologies)
+3) Free Multimedia Tech / freemediatech.org
+4) FFmedia (Foundation for Free MultimEDIA)
+5) FFMF (Fast Forward Multimedia Foundation)
+6) FFm.org (Foundation for Free Multimedia)
+
+From: Stefano Sabatini <stefano.sabatini-lala at poste.it>
+1. Free Multimedia Tech / freemediatech.org
+2. FFMTech (Foundation for Free Multimedia Technologies)
+3. FFMF (Fast Forward Multimedia Foundation)
+4. FFmpeg Foundation
+5. FFmedia (Foundation for Free MultimEDIA)
+
+From: Zuxy Meng <zuxy.meng at gmail.com>
+1 Free Multimedia Tech / freemediatech.org
+2 FFmpeg Foundation
+3 FFmedia (Foundation for Free MultimEDIA)
+4 FFMTech (Foundation for Free Multimedia Technologies)
+
+From: Justin Ruggles <justin.ruggles at gmail.com>
+
+1. Free Multimedia Tech / freemediatech.org
+2. FFmpeg Foundation
+3. FFMTech (Foundation for Free Multimedia Technologies)
+4. FFm.org (Foundation for Free Multimedia)
+5. FFmedia (Foundation for Free MultimEDIA)
+
+From: Benjamin Larsson <banan at ludd.ltu.se>
+
+1. FFMTech (Foundation for Free Multimedia Technologies)
+2. Free Multimedia Tech / freemediatech.org
+
+From: Luca Abeni <lucabe72 at email.it>
+
+1) FFmpeg Foundation
+2) FFmedia (Foundation for Free MultimEDIA)
+3) FFMTech (Foundation for Free Multimedia Technologies)
+
+From: Attila Kinali <attila at kinali.ch>
+
+1) FFmedia (Foundation for Free MultimEDIA)
+2) FFMTech (Foundation for Free Multimedia Technologies)
+3) Free Multimedia Tech / freemediatech.org
+4) FFm.org (Foundation for Free Multimedia)
+5) FFMF (Fast Forward Multimedia Foundation)
+6) FFmpeg Foundation
+7) OMF (Open Multimedia Foundation)
\ No newline at end of file
Added: trunk/ffvotetov/minimax-fail.txt
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/ffvotetov/minimax-fail.txt Tue Dec 15 17:53:52 2009 (r157)
@@ -0,0 +1,179 @@
+1 A
+2 B
+3 C
+4 D
+
+1 A
+2 B
+3 C
+4 D
+
+1 A
+2 B
+3 C
+4 D
+
+1 A
+2 B
+3 C
+4 D
+
+1 A
+2 B
+3 C
+4 D
+
+1 A
+2 B
+3 C
+4 D
+--
+1 D
+2 C
+3 A
+4 B
+
+1 D
+2 C
+3 A
+4 B
+
+1 D
+2 C
+3 A
+4 B
+
+1 D
+2 C
+3 A
+4 B
+
+1 D
+2 C
+3 A
+4 B
+
+1 D
+2 C
+3 A
+4 B
+--
+1 B
+2 C
+3 A
+4 D
+
+1 B
+2 C
+3 A
+4 D
+
+1 B
+2 C
+3 A
+4 D
+
+1 B
+2 C
+3 A
+4 D
+
+1 B
+2 C
+3 A
+4 D
+
+1 B
+2 C
+3 A
+4 D
+--
+1 D
+2 A
+3 B
+4 C
+
+1 D
+2 A
+3 B
+4 C
+
+1 D
+2 A
+3 B
+4 C
+
+1 D
+2 A
+3 B
+4 C
+
+1 D
+2 A
+3 B
+4 C
+--
+1 C
+2 A
+3 B
+4 D
+
+1 C
+2 A
+3 B
+4 D
+
+1 C
+2 A
+3 B
+4 D
+
+1 C
+2 A
+3 B
+4 D
+-
+1 D
+2 B
+3 C
+4 A
+
+1 D
+2 B
+3 C
+4 A
+
+1 D
+2 B
+3 C
+4 A
+
+1 D
+2 B
+3 C
+4 A
+--
+1 B
+2 C
+3 D
+4 A
+
+1 B
+2 C
+3 D
+4 A
+--
+1 A
+2 C
+3 B
+4 D
+
+1 A
+2 C
+3 B
+4 D
+--
+1 A
+2 C
+3 D
+4 B
More information about the Mndiff-dev
mailing list