# $Id: hash.gawk,v 1.3 2001/05/20 06:13:00 doug Exp $
# http://www.bagley.org/~doug/shootout/

# this program modified from:
#   http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
# Timing Trials, or, the Trials of Timing: Experiments with Scripting
# and User-Interface Languages</a> by Brian W. Kernighan and
# Christopher J. Van Wyk.

BEGIN {
    n = (ARGV[1] < 1) ? 1 : ARGV[1];

    for (i = 1; i <= n; i++)
    x[sprintf("%x", i)] = i
    for (i = n; i > 0; i--)
    if (i in x)
        c++
    print c
}

/* -*- mode: c -*-
 * $Id: hash.gcc,v 1.2 2001/01/07 08:33:09 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#define inline
#include "simple_hash.h"

int main(int argc, char *argv[]) {
    int i, c=0, n = ((argc == 2) ? atoi(argv[1]) : 1);
    char buf[32];

    struct ht_ht *ht = ht_create(n);

    for (i=1; i<=n; i++) {
    sprintf(buf, "%x", i);
    (ht_find_new(ht, buf))->val = i;
    }

    for (i=n; i>0; i--) {
    sprintf(buf, "%d", i);
    if (ht_find(ht, buf)) c++;
    }

    ht_destroy(ht);

    printf("%d\n", c);
    return(0);
}

// $Id: hash.csharp,v 1.0 2002/02/14 14:48:00 dada Exp $
// http://dada.perl.it/shootout/

using System;
using System.Collections;

class App {
    public static int Main(String[] args) {        
        int n;
        Hashtable X = new Hashtable();     
        int c = 0;
        
        n = System.Convert.ToInt32(args[0]);
        if(n < 1) n = 1;
        
        for(int i=1; i<=n; i++) {
            X.Add( i.ToString("x"), i);
        }
        
        for(int i=n; i>0; i--) {
            if(X.ContainsKey(i.ToString())) c++;
        }
        Console.WriteLine(c.ToString());
        return(0);
    }
}

#!/usr/local/bin/perl
# $Id: hash.perl,v 1.3 2001/05/16 16:11:41 doug Exp $
# http://www.bagley.org/~doug/shootout/

# this program is modified from:
#   http:#cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
# Timing Trials, or, the Trials of Timing: Experiments with Scripting
# and User-Interface Languages</a> by Brian W. Kernighan and
# Christopher J. Van Wyk.

use strict;

my $n = $ARGV[0] || 1;
my %X = ();
my $c = 0;

for my $i (1..$n) {
    $X{sprintf('%x', $i)} = $i;
}
for my $i (reverse 1..$n) {
    ++$c if exists $X{$i};
}
print "$c\n";

program hash1_2;



uses
  simpleHash in 'simpleHash.pas';

const
  cHexChars: array [0..15] of char = '0123456789abcdef';
  cNullStr: PChar = '00000000';

  function hexStr(i: cardinal): string;
  var n: integer;
  begin
    if i=0 then
      result:='0'
    else begin
      setString(result,cNullStr,8);
      n:=8;
      while (i>0) do begin
        result[n]:=cHexChars[i and $f];
        i:=i shr 4;
        dec(n);
      end;
      for n:=1 to 8 do
        if result[n]<>'0' then begin
          delete(result,1,n-1);
          exit;
        end;
    end;
  end;

var h: TStringHash; n, Count, i: cardinal; code: integer; s: string;
begin
  n :=1;
  if ParamCount=1 then
    Val(ParamStr(1),n,code);

  h:=TStringHash.Create;
  for i:=1 to n do
    h.add(hexStr(i),i);
  count:=0;
  for i:=1 to n do begin
    str(i,s);
    if h.get(s)<>nil then inc(Count);
  end;
  h.Destroy;

  writeln(Count);
end.

// $Id: hash.elastic,v 1.0 2002/05/21 14:38:00 dada Exp $
package xhash;

import basic;
import sys;
import array;
import hash;

private n = 1;
private i;
private c = 0;
private X = %[];

if(array.length(sys.args) > 0) {
    n = basic.int(sys.args[0]);
} else {
    n = 1;
}
for(i=1; i<=n; i++) {
    X[basic.sprintf("%x", i)] = i;
}
for(i=n; i>0; i=i-1) {
     if(hash.has_key(X, basic.sprintf("%d", i))) {
        c = c + 1;
    }
}
basic.print(c);

%%% -*- mode: erlang -*-
%%% $Id: hash.erlang,v 1.3 2001/05/21 01:28:48 doug Exp $
%%% http://www.bagley.org/~doug/shootout/
%%% Tweaked by James Hague.

%% Use ETS tables (Erlang's associative store).

-module(hash).
-export([main/0, main/1]).

main() -> main(['1']).
main([Arg]) ->
    N = list_to_integer(atom_to_list(Arg)),
    H = ets:new(ok, [set]),
    doinserts(0, N, H),
    Count = dolookups(N, 0, H),
    io:format("~w~n", [Count]),
    halt(0).

format_hex(0) -> $0;
format_hex(X) -> format_hex(X, []).
format_hex(0, Hex) -> Hex;
format_hex(X, Hex) ->
    N = X band 16#f,
    if
       N < 10 -> format_hex(X bsr 4, [N+$0 | Hex]);
       true ->   format_hex(X bsr 4, [N+($a-10) | Hex])
    end.

doinserts(N, N, H) -> ok;
doinserts(I, N, H) ->
    Hx = format_hex(I),
    ets:insert(H, {Hx, I}),
    doinserts(I+1, N, H).

dolookups(0, C, H) -> C;
dolookups(I, C, H) ->
    Nx = integer_to_list(I),
    case ets:lookup(H, Nx) of
        []-> dolookups(I-1, C, H);
        _ -> dolookups(I-1, C+1, H)
    end.

Program hash;

uses SysUtils, Classes;


type
   THashEntryPtr = ^THashEntryRec;
   THashEntryRec = record
      name : string;
      number : longint;
      next : THashEntryPtr;
   end;

const
   TABLE_SIZE = 100000;

type THash = class
    private
        hashtable : array[0..TABLE_SIZE - 1] of THashEntryRec;
        function hash(s : string) : longint;
    public
        constructor Create;
        function store(name : string; number : longint; var error : longint) : boolean;
        function fetch(name : string; var number : longint) : boolean;
        function exists(name : string) : boolean;
end;

constructor THash.Create;
var
   i : longint;
begin
   for i := 0 to TABLE_SIZE - 1 do
      hashtable[i].next := nil;
end;


function THash.hash(s : string) : longint;
var
   i, j : longint;
begin
    if length(s) = 0 then Result := 0
    else
    begin
        j := ord(s[1]) mod TABLE_SIZE;
        for i := 2 to length(s) do
            j := (j shl 8 + ord(s[i])) mod TABLE_SIZE;
        Result := j;
    end;
end;

function THash.store(name : string; number : longint; var error : longint) : boolean;
var
   node, prev : THashEntryPtr;
begin
   error := 0;

   prev := @hashtable[hash(name)];
   node := prev^.next;
   
   while (node <> nil) and (node^.name <> name) do
   begin
      prev := node;
      node := node^.next;
   end;

   if node <> nil then error := 1
   else begin
      new(prev^.next);
      node := prev^.next;
      if node = nil then error := -1
      else begin
         node^.name := name;
     node^.number := number;
     node^.next := nil;
      end;
   end;
   
   Result := error = 0;
end;

function THash.fetch(name : string; var number : longint) : boolean;
var
   node : THashEntryPtr;
begin
   node := hashtable[hash(name)].next;
   while (node <> nil) and (node^.name <> name) do
      node := node^.next;
   if node <> nil then number := node^.number;
   Result := node <> nil;
end;

function THash.exists(name : string) : boolean;
var
   node : THashEntryPtr;
begin
   node := hashtable[hash(name)].next;
   while (node <> nil) and (node^.name <> name) do
      node := node^.next;
   Result := node <> nil;
end;
    

var
    n, i, c, err : longint;
    X : THash;
begin
    if ParamCount = 0 then
        n := 1
    else
        n := StrToInt(ParamStr(1));
        
    if n < 1 then n := 1;
    
    X := THash.Create();
    
    For i := 1 To n do
        X.store( Format('%x', [i]), i, err );
    
    c := 0;
    For i:= n downto 1 do
    begin
        if X.exists( IntToStr(i) ) Then Inc(c);
    end;
    
    Writeln (IntToStr(c));
end.

# $Id: hash.gawk,v 1.3 2001/05/20 06:13:00 doug Exp $
# http://www.bagley.org/~doug/shootout/

# this program modified from:
#   http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
# Timing Trials, or, the Trials of Timing: Experiments with Scripting
# and User-Interface Languages</a> by Brian W. Kernighan and
# Christopher J. Van Wyk.

BEGIN {
    n = (ARGV[1] < 1) ? 1 : ARGV[1];

    for (i = 1; i <= n; i++)
    x[sprintf("%x", i)] = i
    for (i = n; i > 0; i--)
    if (i in x)
        c++
    print c
}

/* -*- mode: c -*-
 * $Id: hash.gcc,v 1.2 2001/01/07 08:33:09 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "simple_hash.h"

int main(int argc, char *argv[]) {
    int i, c=0, n = ((argc == 2) ? atoi(argv[1]) : 1);
    char buf[32];

    struct ht_ht *ht = ht_create(n);

    for (i=1; i<=n; i++) {
    sprintf(buf, "%x", i);
    (ht_find_new(ht, buf))->val = i;
    }

    for (i=n; i>0; i--) {
    sprintf(buf, "%d", i);
    if (ht_find(ht, buf)) c++;
    }

    ht_destroy(ht);

    printf("%d\n", c);
    return(0);
}

\ -*- mode: forth -*-
\ $Id: hash.gforth,v 1.1 2001/05/25 21:30:18 doug Exp $
\ http://www.bagley.org/~doug/shootout/
\ from Anton Ertl:


0. argc @ 1- arg >number 2drop drop constant NUM

wordlist constant x

: build 
    get-current x set-current
    base @ hex
    NUM 0 ?do
    i 0 <# #s #> nextname i constant
    loop
    base ! set-current ;

: countdecs 
    0 0 NUM -do
    i 0 <# #s #> x search-wordlist if
        drop 1+
    endif
    1 -loop
;

build countdecs 0 .r cr bye

-- $Id: hash.ghc,v 1.3 2001/06/18 18:17:03 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- from Bryn Keller
-- build with ghc -O2 -package data hash.ghc

import System (getArgs)
import FiniteMap
import Numeric (showInt)

countKeys tbl 0 = 0
countKeys tbl n = case (lookupWithDefaultFM tbl False (show n)) of
                    True -> 1 + countKeys tbl (n - 1)
                    _    -> countKeys tbl (n - 1)

buildTable tbl max num | num <= max = buildTable (addToFM tbl (showHex num "") True) max (num + 1)
                       | otherwise = tbl

showHex n r = let (n',d) = quotRem n 16
                  r'     = toEnum (fromEnum '0' + fromIntegral d) : r
                  in if n' == 0 then r' else showHex n' r'

main = do  args <- getArgs
           case args of
            [number] -> let num = read number
                            tbl = buildTable emptyFM num 1
                    in do putStrLn $ show (countKeys tbl num)
            _        -> fail "You must enter a number."

#!/usr/local/bin/guile \
-e main -s
!#

;;; $Id: hash.guile,v 1.3 2001/06/29 23:12:37 doug Exp $
;;; http://www.bagley.org/~doug/shootout/

(define (main args)
  (use-modules (ice-9 format))
  (let* ((n (or (and (= (length args) 2) (string->;number (cadr args))) 1))
     (last (- n 1))
     (c 0)
     (x (make-hash-table n)))
    (do ((i 1 (+ i 1)))
    ((>; i n))
      (hash-set! x (number->;string i 16) i))
    (do ((i last (- i 1)))
    ((<; i 0))
      (if (hash-ref x (number->;string i 10))
      (set! c (+ c 1))))
    (display (format "~D\n" c))))

// $Id: hash.ici,v 1.0 2003/01/03 11:44:00 dada Exp $
// http://dada.perl.it/shootout
//
// contributed by Tim Long

n = argv[1] ? int(argv[1]) : 1;

x = struct();
for (i = 1; i < n + 1; ++i)
    x[sprintf("%x", i)] = i;

c = 0;
for (i = n; i > 0; --i)
    c += x[string(i)] != NULL;

printf("%d\n", c);

# -*- mode: icon -*-
# $Id: hash.icon,v 1.1 2000/12/18 03:10:54 doug Exp $
# http://www.bagley.org/~doug/shootout/

procedure hexstring(i)
    local s
    if i = 0 then s := "0"
    else {
    s := ""
    while i ~= 0 do {
        s := "0123456789abcdef"[iand(i,15) + 1] || s
        i := ishift(i,-4)
    }
    }
    return s
end

procedure main(argv)
    local n
    local X
    local c
    local i
    n := argv[1] | 1
    X := table(0)
    c := 0
    every i := 1 to n do {
    X[hexstring(i)] := i
    }
    every i := n to 1 by -1 do {
    if (member(X,string(i))) then { c +:= 1 }
    }
    write(c)
end

// $Id: hash.java,v 1.3 2001/03/02 02:17:29 doug Exp $
// http://www.bagley.org/~doug/shootout/

// this program is modified from:
//   http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
// Timing Trials, or, the Trials of Timing: Experiments with Scripting
// and User-Interface Languages</a> by Brian W. Kernighan and
// Christopher J. Van Wyk.

import java.io.*;
import java.util.*;

public class hash {

    public static void main(String args[]) throws IOException {
    int n = Integer.parseInt(args[0]);
    int i, c;
    String s = "";
    Integer ii;
    // the original program used:
    // Hashtable ht = new Hashtable();
    // John Olsson points out that Hashtable is for synchronized access
    // and we should use instead:
    HashMap ht = new HashMap();

    c = 0;
    for (i = 1; i <= n; i++)
        ht.put(Integer.toString(i, 16), new Integer(i));
    for (i = 1; i <= n; i++)
        // The original code converted to decimal string this way:
        // if (ht.containsKey(i+""))
        if (ht.containsKey(Integer.toString(i, 10)))
        c++;

    System.out.println(c);
    }
}

// -*- mode: java -*-
// $Id: hash.njs,v 1.1 2001/07/08 20:20:06 doug Exp $
// http://www.bagley.org/~doug/shootout/
// from: David Hedbor <david@hedbor.org>
// modified by Aldo Calpini <dada@perl.it> for Win32

var i, c = 0;
var n;

ARGS = WScript.Arguments;

if(ARGS.length > 0) {
  n = parseInt(ARGS.Item(0), "10");
  if(n < 1) n = 1;
} else {   
  n = 1;
}
var X = new Object();
for (i=1; i<=n; i++) {
   X[i.toString(16)] = i;
}
for (i=n; i>0; i--) {
  if (X[i.toString()]) c++;
}
WScript.Echo(c);

/* -*- mode: c -*-
 * $Id: hash.gcc,v 1.2 2001/01/07 08:33:09 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include "simple_hash.h"

int main(int argc, char *argv[]) {
    int i, c=0, n = ((argc == 2) ? atoi(argv[1]) : 1);
    char buf[32];

    struct ht_ht *ht = ht_create(n);

    for (i=1; i<=n; i++) {
    sprintf(buf, "%x", i);
    (ht_find_new(ht, buf))->val = i;
    }

    for (i=n; i>0; i--) {
    sprintf(buf, "%d", i);
    if (ht_find(ht, buf)) c++;
    }

    ht_destroy(ht);

    printf("%d\n", c);
    return(0);
}

-- $Id: hash.lua,v 1.1 2000/12/10 00:48:41 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- Author: Roberto Ierusalimschy

local n = tonumber((arg and arg[1]) or 1)

local X={}
for i=1,n do
  X[format("%x", i)] = i
end

local c = 0

for i=n,1,-1 do
  if X[i..''] then c = c+1 end
end

print(c)

-- $Id: hash.lua,v 1.1 2000/12/10 00:48:41 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- contributed by Roberto Ierusalimschy

local n = tonumber((arg and arg[1]) or 1)

local X={}
for i=1,n do
  X[string.format("%x", i)] = i
end

local c = 0

for i=n,1,-1 do
  if X[i..''] then c = c+1 end
end

print(c)

# $Id: hash.mawk,v 1.2 2001/05/20 06:13:00 doug Exp $
# http://www.bagley.org/~doug/shootout/

# this program modified from:
#   http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
# Timing Trials, or, the Trials of Timing: Experiments with Scripting
# and User-Interface Languages</a> by Brian W. Kernighan and
# Christopher J. Van Wyk.

BEGIN {
    n = (ARGV[1] < 1) ? 1 : ARGV[1];

    for (i = 1; i <= n; i++)
    x[sprintf("%x", i)] = i
    for (i = n; i > 0; i--)
    if (i in x)
        c++
    print c
}

%% $Id: hash.mercury,v 1.1 2001/07/28 19:11:22 doug Exp $
%% http://www.bagley.org/~doug/shootout/
%% from Fergus Henderson

:- module mytest.
:- interface.
:- import_module io.

:- pred main(state::di, state::uo) is det.

:- implementation.
:- import_module string, hash_table, list, int.

main -->
    io__command_line_arguments(Args),
    { N = (if Args = [Arg], to_int(Arg, N0) then N0 else 1) },
    { X = insert_values(1, N, hash_table__new(string_double_hash, 18, 0.33)) },
    print(count(N, X, 0)), nl.

:- func insert_values(int, int, hash_table(string, int)) = hash_table(string, int).
:- mode insert_values(in, in, hash_table_di) = hash_table_uo.
insert_values(I, N, X0) =
    (if I > N then X0
    else insert_values(I + 1, N, X0^elem(int_to_base_string(I, 16)) := I)).

:- func count(int, hash_table(string, int), int) = int.
:- mode count(in, hash_table_ui, in) = out.
count(I, X, C0) =
    (if I = 0 then C0
    else count(I - 1, X,
        (if search(X, int_to_string(I), _) then C0 + 1 else C0))).

/* -*- mode: c -*-
 * $Id: hash.gcc,v 1.2 2001/01/07 08:33:09 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "simple_hash.h"

int main(int argc, char *argv[]) {
    int i, c=0, n = ((argc == 2) ? atoi(argv[1]) : 1);
    char buf[32];

    struct ht_ht *ht = ht_create(n);

    for (i=1; i<=n; i++) {
    sprintf(buf, "%x", i);
    (ht_find_new(ht, buf))->val = i;
    }

    for (i=n; i>0; i--) {
    sprintf(buf, "%d", i);
    if (ht_find(ht, buf)) c++;
    }

    ht_destroy(ht);

    printf("%d\n", c);
    return(0);
}

/* The Great Win32 Language Shootout http://dada.perl.it/shootout/ 
   contributed by Isaac Gouy (Nice novice)

To compile:	
   nicec --sourcepath=.. -d=. -a hash.jar hash

To run:
   java -jar hash.jar 80000
*/


import ackermann; // reuse toSingleInt


void main(String[] args){
   let n = toSingleInt(args);
   var count = 0;

   HashMap table = new HashMap();

   for (int i = 1; i <= n; i++) 
      table.put( toString(i, 16), i );
   for (int i = n; i > 0; i--)
      if (table.get( toString(i, 10) ) != null) count++;

   println(count);
}


String toString(int, int) = 
   native String java.lang.Integer.toString(int, int);

(*
 * $Id: hash.ocaml,v 1.4 2001/01/08 03:02:47 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 * with help from Markus Mottl
 *)

let hexdigits =  [| '0'; '1'; '2'; '3'; '4'; '5'; '6'; '7';
                    '8'; '9'; 'a'; 'b'; 'c'; 'd'; 'e'; 'f'; |]

let buf = String.create 32

let rec hexstring_of_int n idx len =
  if n <= 0 then String.sub buf idx len
  else begin
    let new_idx = idx - 1
    and new_len = len + 1 in
    String.set buf new_idx hexdigits.(n land 15);
    hexstring_of_int (n lsr 4) new_idx new_len
  end

let _ =
  let n =
    try int_of_string Sys.argv.(1)
    with Invalid_argument _ -> 1 in
  let hx = Hashtbl.create n in
  for i = 1 to n do
    Hashtbl.add hx (hexstring_of_int i 32 0) true
  done;
  let c = ref 0 in
  for i = n downto 1 do
    if Hashtbl.mem hx (string_of_int i) then incr c
  done;
  Printf.printf "%d\n" !c

(*
 * $Id: hash.ocaml,v 1.4 2001/01/08 03:02:47 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 * with help from Markus Mottl
 *)

let hexdigits =  [| '0'; '1'; '2'; '3'; '4'; '5'; '6'; '7';
                    '8'; '9'; 'a'; 'b'; 'c'; 'd'; 'e'; 'f'; |]

let buf = String.create 32

let rec hexstring_of_int n idx len =
  if n <= 0 then String.sub buf idx len
  else begin
    let new_idx = idx - 1
    and new_len = len + 1 in
    String.set buf new_idx hexdigits.(n land 15);
    hexstring_of_int (n lsr 4) new_idx new_len
  end

let _ =
  let n =
    try int_of_string Sys.argv.(1)
    with Invalid_argument _ -> 1 in
  let hx = Hashtbl.create n in
  for i = 1 to n do
    Hashtbl.add hx (hexstring_of_int i 32 0) true
  done;
  let c = ref 0 in
  for i = n downto 1 do
    if Hashtbl.mem hx (string_of_int i) then incr c
  done;
  Printf.printf "%d\n" !c

%%% $Id: hash.oz,v 1.0 2002/08/19 16:24:00 dada Exp $
%%% http://dada.perl.it/shootout/
%%% 
%%% contributed by Isaac Gouy

%%  Usage: start from command line with
%%     ozc -x hash.oz -o hash.oz.exe
%%     hash.oz.exe 2000

functor
import System Application

define

   fun {IntToHexString I Hex}
      if I =< 0 then Hex else
     local M D in 
        D = I div 16
        M = I mod 16
        if M < 10 then 
           {IntToHexString D M+&0|Hex}
        else
           {IntToHexString D (M-10)+&a|Hex}
        end
     end
      end
   end

   proc {InsertHexKeys H N}
      for I in 0..N-1 do 
    {Dictionary.put H {String.toAtom {IntToHexString I nil}} I}
      end
   end

   proc {CountLookups H I S C}
      if I >= 0 then 
     if {Dictionary.member H {String.toAtom {IntToString I}}} then
        {CountLookups H I-1 S+1 C}
     else 
        {CountLookups H I-1 S C}
     end
      else C = S end
   end

in 
   local Args N H Count in
      [Args] = {Application.getArgs plain}
      N = {String.toInt Args}

      {NewDictionary H}
      {InsertHexKeys H N}
      {CountLookups H N 0 Count}

      {System.showInfo Count}
   end
   {Application.exit 0}
end

# $Id: hash.parrot,v 1.0 2002/08/20 11:14:00 dada Exp $
# http://dada.perl.it/shootout/

    set I1, P0[1]
    new P1, .PerlHash

#    new P2, .PerlInt

    set I0, 1
BUILD:
    bsr DEC2HEX
    
#    set P2, I0
#    set P1[S0], P2
    
    set P1[S0], I0

    inc I0
    le I0, I1, BUILD

    set I0, 0
COUNT:
    set S0, I1
#    print "GET hash("
#    print S0
#    print ")="

#    set P2, P1[S0]
#    typeof I2, P2
#    typeof S2, P2

#    print S2
    set I2, P1[S0]
    unless I2, NEXT
#    eq I2, .PerlUndef, NEXT
#    print " ++"
    inc I0
NEXT:
#    print "\n"
    dec I1
    if I1, COUNT
    
    print I0
    print "\n"
    end

DEC2HEX:
    
    set S0, ""
    set I10, I0
DEC2HEX_START:
    mod I11, I10, 16    
    lt I11, 10, DEC2HEX_N    
    eq I11, 15, DEC2HEX_F
    eq I11, 14, DEC2HEX_E
    eq I11, 13, DEC2HEX_D
    eq I11, 12, DEC2HEX_C
    eq I11, 11, DEC2HEX_B
    eq I11, 10, DEC2HEX_A

DEC2HEX_N:
    set S1, I11
    concat S0, S1, S0
    branch DEC2HEX_NEXT
    
DEC2HEX_A:
    concat S0, "a", S0
    branch DEC2HEX_NEXT

DEC2HEX_B:
    concat S0, "b", S0
    branch DEC2HEX_NEXT

DEC2HEX_C:
    concat S0, "c", S0
    branch DEC2HEX_NEXT

DEC2HEX_D:
    concat S0, "d", S0
    branch DEC2HEX_NEXT

DEC2HEX_E:
    concat S0, "e", S0
    branch DEC2HEX_NEXT
    
DEC2HEX_F:
    concat S0, "f", S0

DEC2HEX_NEXT:
    div I10, I10, 16
    if I10, DEC2HEX_START
    ret

#!/usr/local/bin/perl
# $Id: hash.perl,v 1.3 2001/05/16 16:11:41 doug Exp $
# http://www.bagley.org/~doug/shootout/

# this program is modified from:
#   http:#cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
# Timing Trials, or, the Trials of Timing: Experiments with Scripting
# and User-Interface Languages</a> by Brian W. Kernighan and
# Christopher J. Van Wyk.

use strict;

my $n = $ARGV[0] || 1;
my %X = ();
my $c = 0;

for my $i (1..$n) {
    $X{sprintf('%x', $i)} = $i;
}
for my $i (reverse 1..$n) {
    ++$c if exists $X{$i};
}
print "$c\n";

<?php
/*
 $Id: hash.php,v 1.2 2001/05/06 05:25:08 doug Exp $
 http://www.bagley.org/~doug/shootout/
*/
$n = ($argc == 2) ? $argv[1] : 1;
for ($i = 1; $i <= $n; $i++) {
    $X[dechex($i)] = $i;
}
for ($i = $n; $i > 0; $i--) {
    if ($X[$i]) { $c++; }
}
print "$c\n";
?>

#!/usr/local/bin/pike// -*- mode: pike -*-
// $Id: hash.pike,v 1.2 2000/12/12 21:28:39 doug Exp $
// http://www.bagley.org/~doug/shootout/
// from: Martin Nilsson

void main(int argc, array(string) argv)
{
    int i, c = 0;
    int n = (int)argv[-1];
    if (n < 1) n = 1;
      
    mapping(string:int) X = ([]);
    
    for (i=1; i<=n; i++) {
    X[sprintf("%x", i)] = i;
    }
    for (i=n; i>0; i--) {
    if (X[(string)i]) c++;
    }
    write("%d\n", c);
}

# $Id: hash.pliant,v 1.0 2002/02/06 16:48:00 dada Exp $
# http://dada.perl.it/shootout/

module "/pliant/language/context.pli"

gvar (Dictionary Str Int) X
gvar Int c
gvar Int i
gvar Str s_n := cast ((pliant_script_args translate Address 1) map CStr) Str
if (s_n parse (gvar Int n))
  c := 0
  for (i) 1 n
    X insert (string i "radix 16") i
  for (i) n 1 step -1
    if (X exists (string i))
      c := c + 1
  console c eol
else
  console "usage: nestedloop.pli <number>" eol

;;; -*- mode: lisp -*-
;;; $Id: hash.poplisp,v 1.0 2002/05/03 13:28:00 dada Exp $

(declaim (optimize (speed 3) (space 0) (safety 0) (debug 0) (compilation-speed 0)))
(defun command-line-argument ()
  (parse-integer (or (car pop11::poparglist) "1")))

(defconstant +digit+ "0123456789ABCDEF")

(defconstant +digits-needed+
  #(    (10 100 1000 10000 100000 10000000 100000000 536870911)
        (16 256 4096 65536 1048576 16777216 268435456 4294967296 536870911)
    )
)

(defun fixnum-to-string (n base)
  (declare (fixnum n base))
  (let* ((size (position-if (lambda (x) (>; (the fixnum x) n))
                (aref +digits-needed+ (ash base -4))))
     (result (make-string (1+ size))))
    (loop for i fixnum from size downto 0 with q fixnum = n and r fixnum = 0
      do (multiple-value-setq (q r) (floor q base))
         (setf (schar result i) (aref +digit+ r)))
    result)
)

(defun main (&optional (n (command-line-argument)))
  (let ((hash (make-hash-table :test 'equal :size n)))
    (macrolet ((hash (i base) `(gethash (fixnum-to-string ,i ,base) hash)))
      (loop for i fixnum from 1 to n do (setf (hash i 16) i))
      (format t "~a~%" (loop for i fixnum from n downto 1 count (hash i 10))))))

(main)

#!/usr/local/bin/python
# $Id: hash.python,v 1.4 2001/06/10 03:33:57 doug Exp $
# http://www.bagley.org/~doug/shootout/
# with help from from Gustavo Niemeyer

import sys
#sys.setcheckinterval(10000)

def main():
    n = int(sys.argv[1])
    X = {}
    myhex = hex
    for i in xrange(1,n+1):
        X[myhex(i)[2:]] = i
    c = 0
    has_key = X.has_key
    for i in xrange(n, 0, -1):
        c += has_key(`i`)
    print c

main()

REBOL [
    Title:   "Hash"
    Author:  "Aldo Calpini"
    Date:    05-Jul-2001
    File:    %hash.r
]

NUM: to-integer to-string system/script/args
NUM: either NUM < 1 [ 1 ] [ NUM ]

myhex: func [ N /local k flag c r ] [
    k: to-hex N
    k: to-string k
    flag: 0
    r: copy ""
    forall k [
        c: first k
        if (c <> #"0") or (flag = 1) [
            append r c
            flag: 1
        ]
    ]
    return r
]

X: make hash! []
c: 0
for i 1 NUM 1 [
    append X myhex i
    append X i
]

for i NUM 1 -1 [
    s: to-string i
    if select/skip X s 2 [
        c: c + 1
    ]
]
print c

write %output.rebol c

parse arg n
If n < 1 Then Do
    n = 1
End

Do i = 1 To n
    xx = d2x(i)
    X.xx = i
End

c = 0

Do i = n To 1 By -1
    if X.i <> "X."i Then Do
        c = c + 1
    End
End
Say c

#!/usr/local/bin/ruby
# -*- mode: ruby -*-
# $Id: hash.ruby,v 1.2 2001/05/16 15:54:34 doug Exp $
# http://www.bagley.org/~doug/shootout/

n = Integer(ARGV.shift || 1)

X = {}
for i in 1 .. n
    X[sprintf("%x", i)] = 1
end

c = 0
(n).step(1,-1) do |i|
    if (X.has_key?(i.to_s)) then
    c += 1
    end
end

puts c

-- -*- mode: eiffel -*-
-- $Id: hash.se,v 1.3 2001/01/18 20:57:05 doug Exp $
-- http://www.bagley.org/~doug/shootout/

class HASH
   
creation make
   
feature -- Initialization
   
   make is
      local
     n : INTEGER
     i, j, c : INTEGER
     s : STRING
     ht : DICTIONARY[INTEGER, STRING]
     
     arg: ARGUMENTS
      do
     n := argument(1).to_integer

     !!ht.with_capacity(n);
     
     from  i := 1
     until i > n
     loop
        s := i.to_hexadecimal
        from  j := 1
        until s @ j /= '0'
        loop  j := j + 1
        end
        ht.put (i, s.substring(j,s.count))
        i := i+1
     end
     
     from  i := n
     until i = 0
     loop
        s := i.to_string
         if ht.has (s) then
           c := c + 1
        end
        i := i - 1
     end
     
     print (c.out + "%N")

      end

end -- class HASH

% $Id: hash.slang,v 1.0 2003/01/03 14:09:00 dada Exp $
% http://dada.perl.it/shootout/
%
% contributed by John E. Davis

define main ()
{
   variable n = integer (__argv[1]);
   variable X = Assoc_Type[Int_Type];
   _for (1, n, 1)
     {
    variable i = ();
    X[sprintf("%x", i)] = i;
     }
   variable c = 0;
   _for (n, 1, -1)
     {
    i = ();
    if (assoc_key_exists (X, string(i)))
      c++;
     }
   vmessage ("%d", c);
}

main();

(* -*- mode: sml -*-
 * $Id: hash.smlnj,v 1.3 2001/07/09 00:25:28 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 *)

structure Test : sig
    val main : (string * string list) -> OS.Process.status
end = struct

open HashTable;

fun hashtest n =
    let
    val hx = mkTable (HashString.hashString, op =) (n, (Fail "not found"))
    fun doinserts i n =
        if i < n then (
        insert hx ((Int.fmt StringCvt.HEX i), i);
        doinserts (i+1) n
        ) else ()
    fun dolookups i c =
        if i > 0 then
        case find hx (Int.toString i) of
            SOME key => dolookups (i-1) (c+1)
          | _ => dolookups (i-1) c
        else c
    in (
    doinserts 0 n;
    dolookups n 0
    ) end;

fun atoi s = case Int.fromString s of SOME num => num | NONE => 0;

fun main(name, args) = 
    let
    val arg = hd(args @ ["1"])
    val num = atoi arg
    val result = hashtest num
    in
    print (Int.toString result) ; print "\n" ;
    OS.Process.success
    end
end

val _ = SMLofNJ.exportFn("hash", Test.main);

#!/usr/local/bin/tclsh
# $Id: hash.tcl,v 1.4 2001/05/02 05:32:39 doug Exp $
# http://www.bagley.org/~doug/shootout/

# this program is modified from:
#   http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
# Timing Trials, or, the Trials of Timing: Experiments with Scripting
# and User-Interface Languages</a> by Brian W. Kernighan and
# Christopher J. Van Wyk.

proc main {} {
    global argv
    set n [lindex $argv 0]
    for {set i 1} {$i <= $n} {incr i} {
        set x([format {%x} $i]) $i
    }
    set c 0
    for {set i $n} {$i > 0} {incr i -1} {
    if {[info exists x($i)]} {
        incr c
    }
    }
    puts $c
}

main

n = WScript.Arguments(0)
If n < 1 Then n = 1

Set X = CreateObject("Scripting.Dictionary")
c = 0
For i = 1 To N
    X.Add Hex(i), i
Next

For i = n To 1 step -1
    If X.Exists(CStr(i)) Then c = c + 1
Next
WScript.Echo c

/* -*- mode: c -*-
 * $Id: hash.gcc,v 1.2 2001/01/07 08:33:09 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include "simple_hash.vc.h"

int main(int argc, char *argv[]) {
    int i, c=0, n = ((argc == 2) ? atoi(argv[1]) : 1);
    char buf[32];

    struct ht_ht *ht = ht_create(n);

    for (i=1; i<=n; i++) {
    sprintf(buf, "%x", i);
    (ht_find_new(ht, buf))->val = i;
    }

    for (i=n; i>0; i--) {
    sprintf(buf, "%d", i);
    if (ht_find(ht, buf)) c++;
    }

    ht_destroy(ht);

    printf("%d\n", c);
    return(0);
}

// -*- mode: c++ -*-
// $Id: hash.g++,v 1.2 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <stdio.h>
#include <iostream>
#include <hash_map.h>

using namespace std;

struct eqstr {
    bool operator()(const char* s1, const char* s2) const {
    return strcmp(s1, s2) == 0;
    }
};

int
main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 1);
    char buf[16];
    typedef hash_map<const char*, int, hash<const char*>, eqstr> HM;
    HM X;

    for (int i=1; i<=n; i++) {
    sprintf(buf, "%x", i);
    X[strdup(buf)] = i;
    }

    int c = 0;
    for (int i=n; i>0; i--) {
    sprintf(buf, "%d", i);
    if (X[strdup(buf)]) c++;
    }

    cout << c << endl;
}

Program hash;
uses SysUtils, Classes;

type
   THashEntryPtr = ^THashEntryRec;
   THashEntryRec = record
      name : string;
      number : longint;
      next : THashEntryPtr;
   end;

const
   TABLE_SIZE = 100000;

type THash = class
    private
        hashtable : array[0..TABLE_SIZE - 1] of THashEntryRec;
        function hash(s : string) : longint;
    public
        constructor Create;
        function store(name : string; number : longint; var error : longint) : boolean;
        function fetch(name : string; var number : longint) : boolean;
        function exists(name : string) : boolean;
end;

constructor THash.Create;
var
   i : longint;
begin
   for i := 0 to TABLE_SIZE - 1 do
      hashtable[i].next := nil;
end;


function THash.hash(s : string) : longint;
var
   i, j : longint;
begin
    if length(s) = 0 then Result := 0
    else
    begin
        j := ord(s[1]) mod TABLE_SIZE;
        for i := 2 to length(s) do
            j := (j shl 8 + ord(s[i])) mod TABLE_SIZE;
        Result := j;
    end;
end;

function THash.store(name : string; number : longint; var error : longint) : boolean;
var
   node, prev : THashEntryPtr;
begin
   error := 0;

   prev := @hashtable[hash(name)];
   node := prev^.next;
   
   while (node <> nil) and (node^.name <> name) do
   begin
      prev := node;
      node := node^.next;
   end;

   if node <> nil then error := 1
   else begin
      new(prev^.next);
      node := prev^.next;
      if node = nil then error := -1
      else begin
         node^.name := name;
     node^.number := number;
     node^.next := nil;
      end;
   end;
   
   Result := error = 0;
end;

function THash.fetch(name : string; var number : longint) : boolean;
var
   node : THashEntryPtr;
begin
   node := hashtable[hash(name)].next;
   while (node <> nil) and (node^.name <> name) do
      node := node^.next;
   if node <> nil then number := node^.number;
   Result := node <> nil;
end;

function THash.exists(name : string) : boolean;
var
   node : THashEntryPtr;
begin
   node := hashtable[hash(name)].next;
   while (node <> nil) and (node^.name <> name) do
      node := node^.next;
   Result := node <> nil;
end;
    

var
    n, i, c, err : longint;
    X : THash;
begin
    if ParamCount = 0 then
        n := 1
    else
        n := StrToInt(ParamStr(1));
        
    if n < 1 then n := 1;
    
    X := THash.Create;
    
    For i := 1 To n do
        X.store( Format('%x', [i]), i, err );
    
    c := 0;
    For i:= n downto 1 do
    begin
        if X.exists( IntToStr(i) ) Then Inc(c);
    end;
    
    Writeln (IntToStr(c));
end.