title: The Great API Easter Egg Hunt!

text:
# Question
Title: The Great API Easter Egg Hunt!
# API Easter egg hunt!

There's an API at http://easter\_egg\_hunt.andrewfaraday.com which will provide a special Easter egg hunt, just for you...

You can see the API docs at the above address, or try it from here.

## The API:

All calls to this API are GET requests, which will return a JSON string.

These examples are in a 5x5 garden, for illustration only. The API will actually operate on a 100x100 garden (from indexes 1 to 100)

```
/new_game

```

Internally, the API produces a garden, and hides an egg in it.

In this example the egg is at 4, 4

```
+----------+
|          |
|          |
|          |
|          |
|   E      |
|          |
|          |
|          |
|          |
|          |
+----------+

```

Call

```
/new_game

```

Returns

```
{game_id: 'abcde'}

```

---

```
/guess/:game_id/:x/:y

```

The API looks in the garden and tells you how close you are.

If you guess 2 across and 8 down, the garden looks like this

```
+----------+
|          |
|          |
|          |
|          |
|   E      |
|          |
|          |
| g        |
|          |
|          |
+----------+

```

Call

```
/guess/abcde/2/8

```

Returns

```
{x: 'higher', y: 'lower'}

```

This means: * Your x is too low (the egg position is higher) * Your y is too high (The egg position is lower)

Correct call:

```
/guess/abcde/4/4

```

Returns

```
{x: 'right', y: 'right', turns: 10}

```

---

## The Rules

Write a program to find the Easter egg with an API.

* Use any language.
* Try to write concise, but readable code.
* Your program **MUST** call '/new\_game' every time, and use the game\_id returned in all 'guess' calls. No peeking at the garden!
* Try to consistently finish the game with the smallest number of calls possible.
* This is not code golf.

---

## Competetive answer?

To be in with a chance of winning here's what we need to know:

* What code are you using (In your answer, or a github link if it's bigger than you like to put in an answer).
* Run your code 10 times, and record the game\_id and score each time.

**-game\_id-**: -score-

e.g.

**abbbbbbb**: 10

**abbbbbdd**: 5

(Note: The game\_ids are required to verify a result)

The score will be calculated thus:

* The highest and lowest two results will be ignored.
* The remaining 6 scores will be added together.
* This is your score.
* Lowest score wins.

---

## Addendum

Tl,dr: The app is a little shoddy.

The API was written in the space of about 90 minutes, and is deployed on a Raspberry Pi 2. Please be gentle with my API server. If you DDOS this poor thing you could spoil it for everyone.

Also, it's implemented with NOIP to simulate a static IP address, but sometimes this will drop out for a little while. That's what I get for using for zero-budget web hosting.

Just for giggles, here's a simple statistical analysis of games played... http://easter\_egg\_hunt.andrewfaraday.com/stats

# Answer
> 3 votes
# APL+WIN

Works by starting in the centre and converges on the location by setting the upper or lower limit to the last value and adding or subtracting half the difference to the appropriate limit to the last guess on each iteration.

```
API
id←¯20↑¯2↓GetUrl 'http://easter_egg_hunt.andrewfaraday.com/new_game'
xh←yh←100 ⋄ xl←yl←0 ⋄ x←50 ⋄ y←50 ⋄ c←0
:repeat
    xy←GetUrl 'http://easter_egg_hunt.andrewfaraday.com/guess/',id,'/',(⍕x),'/',⍕y
    xy←(('higher'⍷xy)+(¯1×'lower'⍷xy)+2×'right'⍷xy)~0
    :if xy[1]=1 ⋄ xl←x ⋄ x←x+⌈(xh-x)÷2 ⋄ :endif
    :if xy[1]=¯1 ⋄ xh←x ⋄ x←x-⌈(x-xl)÷2 ⋄ :endif
    :if xy[2]=1 ⋄ yl←y ⋄ y←y+⌈(yh-y)÷2 ⋄ :endif
    :if xy[2]=¯1 ⋄ yh←y ⋄ y←y-⌈(y-yl)÷2 ⋄ :endif
    c←c+1
:until 4=+/2↑xy
'id:',id,' x:',(⍕x),' y:',(⍕y),' count:',⍕c

```

This function uses the following function to do the API calls:

```
r←GetUrl url
⎕wself←'HTTP' ⎕wi 'Create' 'MSXML2.ServerXMLHTTP'
⎕wi 'XOpen' 'GET' url 0
⎕wi 'XSend'
r←⎕wi 'xresponseText'

```

The results for 10 trys were:

```
id:rbgprkxrqzzhwdfsbszn x:36 y:52 count:7
id:nmpcxdqsdzhgrbtlcpbp x:35 y:49 count:6
id:qqnsbpwnlbptxxblywnz x:99 y:22 count:6
id:nsytnvcgnsyrgzvjcysc x:45 y:28 count:6
id:yfkpfhphjpqxtqnwpmhv x:95 y:40 count:7
id:kxhszzrhxqlnvwvwjgnm x:49 y:6 count:6
id:rwnwfgdpzcjpzzfmgcfn x:93 y:34 count:7
id:tcvhtpqlfrwngybsyzqh x:95 y:94 count:6
id:pmlmqnprwcjggjfhttmy x:20 y:41 count:6
id:kpsmmhfhxxrrlvbbgzkv x:9 y:28 count:5

```

# Answer
> 2 votes
# Ruby (+JSON, HTTParty) - Score: 40 (6+7+7+7+7+6)

This was a fun challenge. I used binary search to find the egg and got these results:

```
[{:x=>34, :y=>17, :game_id=>"mgpbmdqbnklcqrdjpyrr", :count=>7},
 {:x=>99, :y=>17, :game_id=>"mhrsqfzmrrlcqxtcfgnw", :count=>7},
 {:x=>23, :y=>86, :game_id=>"zgmsrjpqvdtmqmmglstn", :count=>6},
 {:x=>24, :y=>55, :game_id=>"vkpjffyyltplztwhdsft", :count=>7},
 {:x=>12, :y=>94, :game_id=>"pxrzjvqfjrjsptvtvnfw", :count=>4},
 {:x=>83, :y=>59, :game_id=>"bdxljxkcnqmsqgnvggql", :count=>7},
 {:x=>45, :y=>40, :game_id=>"mqrsbrhbldcqwgbnmymc", :count=>7},
 {:x=>13, :y=> 9, :game_id=>"bphxkdgfcyyrvwxnfvkx", :count=>6},
 {:x=> 8, :y=>80, :game_id=>"qzdstksdwnwrhxqrczpc", :count=>7},
 {:x=>56, :y=>92, :game_id=>"ypqkfvmvwrcvvmjccvxg", :count=>6}]

```

Here's the code:

```
require 'rspec/autorun'
require 'json'
require 'httparty'
require 'pp'

GuessResult = Struct.new :x, :y, :count

class FakeGame
  def initialize(x=random_num, y=random_num)
    @x = x
    @y = y
    @count = 0
  end

  @@results = [:right, :higher, :lower]

  def guess(x, y)
    @count += 1
    GuessResult.new(@@results[@x <=> x], @@results[@y <=> y], @count)
  end

  def id
    :fake
  end

  def random_num
    rand(100) + 1
  end
end

class RealGame
  def initialize
    response = HTTParty.get('http://easter_egg_hunt.andrewfaraday.com/new_game')
    j = JSON.parse(response.body)
    @id = j['game_id']
  end

  def guess(x, y)
    response = HTTParty.get("http://easter_egg_hunt.andrewfaraday.com/guess/#{id}/#{x}/#{y}")
    j = JSON.parse(response.body)
    x_result = j['x'].to_sym
    y_result = j['y'].to_sym
    count = (j['turns']||0).to_i
    GuessResult.new(x_result, y_result, count)
  end

  def id
    @id
  end
end

class BinarySearch
  def initialize(min, max)
    @min = min
    @max = max
    @guessed = false
    update_next_guess
  end

  attr_reader :next_guess, :guessed

  def go(result)
    return if @guessed
    case result
    when :right
      @guessed = true
    when :lower
      @max = @next_guess - 1
      update_next_guess
    when :higher
      @min = @next_guess + 1
      update_next_guess
    end
  end

  private

  def update_next_guess
    @next_guess = (@max + @min) / 2
  end

end

def play(game)
  x_search = BinarySearch.new(1, 100)
  y_search = BinarySearch.new(1, 100)

  until x_search.guessed && y_search.guessed
    puts ?.
    result = game.guess(x_search.next_guess, y_search.next_guess)
    x_search.go(result.x)
    y_search.go(result.y)
  end

  {
    x: x_search.next_guess,
    y: y_search.next_guess,
    game_id: game.id,
    count: result.count
  }
end

def game_controller(game_constructor, game_count)
  (1..game_count).map do |i|
    game = game_constructor.call
    puts "Starting game #{game.id}..."
    play(game)
  end
end

def main
  # pp game_controller(->{ FakeGame.new }, 10)
  pp game_controller(->{ RealGame.new }, 10)
end

main

# tests

describe :FakeGame do

  it "returns right results" do
    game = FakeGame.new 4, 4

    result = game.guess(2, 5)
    expect(result.x).to eql :higher
    expect(result.y).to eql :lower
    expect(result.count).to eql 1

    result = game.guess(5, 3)
    expect(result.x).to eql :lower
    expect(result.y).to eql :higher
    expect(result.count).to eql 2

    result = game.guess(4, 4)
    expect(result.x).to eql :right
    expect(result.y).to eql :right
    expect(result.count).to eql 3

  end

end

describe :binary_search do
  let(:search) { BinarySearch.new 1, 100 }

  it "makes optimal guesses" do
    # aiming for 34
    expect(search.next_guess).to eql 50
    expect(search.guessed).to be_falsey
    search.go(:lower)
    expect(search.next_guess).to eql 25
    search.go(:higher)
    expect(search.next_guess).to eql 37
    search.go(:lower)
    expect(search.next_guess).to eql 31
    search.go(:higher)
    expect(search.next_guess).to eql 34
    search.go(:right)
    expect(search.next_guess).to eql 34
    expect(search.guessed).to be_truthy
  end

end

describe :fake_game do

  it "correctly responds to guesses" do
    game = FakeGame.new(34, 77)
    result = play(game)
    expect(result.y).to eql :lower
    expect(result.count).to eql 1

    result = game.guess(5, 3)
    expect(result.x).to eql :lower
    expect(result.y).to eql :higher
    expect(result.count).to eql 2

    result = game.guess(4, 4)
    expect(result.x).to eql :right
    expect(result.y).to eql :right
    expect(result.count).to eql 3

  end

end

describe '#play' do

  it "guesses correctly" do
    game = FakeGame.new(34, 77)
    result = play(game)
    expect(result[:x]).to eql 34
    expect(result[:y]).to eql 77
    expect(result[:count]).to eql 7
    expect(result[:game_id]).to eql :fake
  end

end

```

# Answer
> 2 votes
# Python 3 (+requests), 39 points

```
http://easter_egg_hunt.andrewfaraday.com/guess/dbxqfgldhryxymljthkx/13/82
{"turns": 7, "url": "http://easter_egg_hunt.andrewfaraday.com/surprise", "x": "right", "y": "right"}
http://easter_egg_hunt.andrewfaraday.com/guess/kfmgrdqlyxfknbgycfwm/6/52
{"turns": 7, "url": "http://easter_egg_hunt.andrewfaraday.com/surprise", "x": "right", "y": "right"}
http://easter_egg_hunt.andrewfaraday.com/guess/gnykwddprlfwwkrybkmc/34/91
{"turns": 6, "url": "http://easter_egg_hunt.andrewfaraday.com/surprise", "x": "right", "y": "right"}
http://easter_egg_hunt.andrewfaraday.com/guess/xhwrqdgtdyrwrvdqqcpk/92/54
{"turns": 7, "url": "http://easter_egg_hunt.andrewfaraday.com/surprise", "x": "right", "y": "right"}
http://easter_egg_hunt.andrewfaraday.com/guess/hmbgrnxjfgqcxhbfkztm/44/48
{"turns": 7, "url": "http://easter_egg_hunt.andrewfaraday.com/surprise", "x": "right", "y": "right"}
http://easter_egg_hunt.andrewfaraday.com/guess/mhbchhbkppqqyxzqvrnb/62/38
{"turns": 7, "url": "http://easter_egg_hunt.andrewfaraday.com/surprise", "x": "right", "y": "right"}
http://easter_egg_hunt.andrewfaraday.com/guess/pbrkghynqybmkmctncmr/73/25
{"turns": 6, "url": "http://easter_egg_hunt.andrewfaraday.com/surprise", "x": "right", "y": "right"}
http://easter_egg_hunt.andrewfaraday.com/guess/sspxcsfblrnmhflgtggn/89/73
{"turns": 6, "url": "http://easter_egg_hunt.andrewfaraday.com/surprise", "x": "right", "y": "right"}
http://easter_egg_hunt.andrewfaraday.com/guess/rlvdstmpsthktzkqbynn/4/71
{"turns": 6, "url": "http://easter_egg_hunt.andrewfaraday.com/surprise", "x": "right", "y": "right"}
http://easter_egg_hunt.andrewfaraday.com/guess/wknwwcrdrmjsqxnqbvhm/50/67
{"turns": 6, "url": "http://easter_egg_hunt.andrewfaraday.com/surprise", "x": "right", "y": "right"}

```

Score 39 (7+7+7+6+6+6 - 7-7-6-6)

Source:

```
import requests
import json
url='http://easter_egg_hunt.andrewfaraday.com/guess/{id}/{x}/{y}'
start='http://easter_egg_hunt.andrewfaraday.com/new_game'
gid = requests.get(start).json()['game_id']
x=y=50
step=25
lx=lr=''
def get_new(old,value):
        if value == 'higher':
                return old+step
        elif value == 'lower':
                return old-step
        else:#right
                return old
while True:
        res = requests.get(url.format(id=gid,x=x,y=y)).json()
        if res['x'] == 'right' and res['y'] == 'right':
                print(url.format(id=gid,x=x,y=y))
                print(json.dumps(res, sort_keys=True))
                break
        x=get_new(x,res['x'])
        y=get_new(y,res['y'])
        step=step // 2 or 1

```

# Answer
> 2 votes
# PHP

```
<?php

error_reporting(E_ALL);

$url = 'http://easter_egg_hunt.andrewfaraday.com';
extract(json_decode(file_get_contents("$url/new_game"), true));

$i = $j = 51;
$step = 50;
$right = false;

while(!$right) {
  extract(json_decode(file_get_contents(sprintf("$url/guess/$game_id/%d/%d", $i, $j)), true));
  $lower = -$higher = $step /= 2;
  $i += $$x;
  $j += $$y;
  $right = !($$x || $$y);
}

printf('{game_id: %s; x: %2d; y: %2d; turns: %d}', $game_id, $i, $j, $turns);

```

Using file\_get\_contents and json\_decode.

As far as I can tell, an optimal strategy needs at most 7 moves, with an average of 5.8 moves on one axis, and an average of 6.4786 moves on two axes.

---

**Sample of 10**

```
{game_id: pfmyldcsltlbtmcfjtqr; x: 76; y: 51; turns: 6}
{game_id: jnmshsfvstcmksdcdrnj; x: 40; y:  5; turns: 7}
{game_id: wsrptrymycxjfxwvdvlh; x: 55; y: 35; turns: 7}
{game_id: fxpxtqwnxstwcxbsqtwc; x: 73; y: 93; turns: 6}
{game_id: zppntvjxnjpnlmpfzcfj; x: 71; y: 76; turns: 6}
{game_id: fzvlxqgrxcvtbbydgrpj; x: 48; y: 51; turns: 6}
{game_id: hqytpzjxkfhqhhwwfryd; x: 23; y: 87; turns: 6}
{game_id: ldsbfgcqbqpxgdhtkxsm; x: 90; y: 81; turns: 5}
{game_id: shypwsmjljyqdvwcwnxv; x: 19; y: 57; turns: 7}
{game_id: bsfrhhrvmpqfvyhjxcwh; x: 82; y: 85; turns: 6}

```

**Score:** 6 + 6 + 6 + 6 + 6 + 7 = **37**

---

**Golfed, 245 bytes**

```
<?$e="extract(json_decode(file_get_contents('http://easter_egg_hunt.andrewfaraday.com";eval("$e/new_game".$f="'),1));");
for($i=$j=$h=50;!$url;$l=-$h/=2)eval("$e/guess/$game_id/".-~($i+=$$x[0]).'/'.-~($j+=$$y[0]).$f);
echo$game_id,~$i,~$j,-$turns;

```

Sample Output

```
$ php egg-hunt.php
hgzqmqyrznglsdwfwcft-9-86-7

```

# Answer
> 2 votes
# JavaScript, 35 points

Posting ungolfed code does *not* sit well with me! :D

```
(async _=>{
    url=`https://crossorigin.me/http://easter_egg_hunt.andrewfaraday.com/`
    promise=await fetch(url+`new_game`)
    json=await promise.json()
    id=json.game_id
    max={x:100,y:100}
    min={x:0,y:0}
    (guess=async (x,y)=>{
        promise=await fetch(url+`guess/${id}/${x|=0}/${y|=0}`)
        json=await promise.json()
        turns=json.turns
        if(turns)
            console.log(`{game:"${id}",turns:${turns},x:${x},y:${y}}`)
        else{
            switch(json.x){
                case`higher`:
                    min.x=x
                    x+=max.x
                    x/=2
                    break
                case`lower`:
                    max.x=x
                    x+=min.x
                    x/=2
            }
            switch(json.y){
                case`higher`:
                    min.y=y
                    y+=max.y
                    y/=2
                    break
                case`lower`:
                    max.y=y
                    y+=min.y
                    y/=2
            }
            guess(x,y)
        }
    })(50,50)
})()

```

---

## Scoring: 5+6+6+6+6+6=35

Got very lucky, pulling that score of 3 on my last test before posting!

```
{game:"bjzkjzxwmksmbsbxtdzp",turns:3,x:75,y:12}
{game:"bvmhssnmzhlnykgxdkww",turns:5,x:93,y:71}
{game:"mcydbttxhcxwqymksgbg",turns:5,x:71,y:37}
{game:"xdynxrkxgsyltsfrqzll",turns:6,x:54,y:88}
{game:"wjdkclsqksnvdnwbspxq",turns:6,x:90,y:13}
{game:"mgvlssfgjcgtylwqpvhq",turns:6,x:26,y:68}
{game:"rgjvbkrlzqvpdfphqxtq",turns:6,x:19,y:81}
{game:"hgrscvfzgrkzzjvkjjwb",turns:6,x:41,y:19}
{game:"lrfrblmmkggghntshnkj",turns:7,x:86,y:32}
{game:"ldsndvjsbvgvbhbtfckp",turns:7,x:24,y:7}

```

---

## Try it

Using a *somewhat* golfed version of the code above!

```
(async url=>(
    json=await(await fetch(url+`new_game`)).json(),
    id=json.game_id,
    max={x:100,y:100},
    min={x:0,y:0},
    (g=async x=>(
        json=await(await fetch(url+`guess/${id}/${x|=0}/${y|=0}`)).json(),
        x+=json.x==`higher`?(min.x=x,max.x):json.x==`lower`?(max.x=x,min.x):x,x/=2,
        y+=json.y==`higher`?(min.y=y,max.y):json.y==`lower`?(max.y=y,min.y):y,y/=2,
        json.turns?console.log(`{game:"${id}",turns:${json.turns},x:${x},y:${y}}`):g(x)
    ))(y=50)
))`https://crossorigin.me/http://easter_egg_hunt.andrewfaraday.com/`
```

# Answer
> 2 votes
# Haskell, Total Score ~~66~~ 40

(Edit: Missed the part about dropping highest and lowest results in scoring)

I'm just using binary search. Not sure if there's a way to get better than 6.5 per try on average without cheating (I suppose I could just keep running sets of 10 until I get a better score, but where's the fun in that?).

Ah, by the way very fun challenge. The idea is simple enough to be inclusive of everyone, and I don't usually deal with web APIs in my day job and I was just itching for an excuse to try out `servant`, so thanks for that :) Probably not so great if you're hoping for competition, but I think challenges like this could be used to gather code samples for beginners and things like that.

Executable script (runs one game and reports the gameId and score):

```
#!/usr/bin/env stack
{- stack
   --resolver lts-11.2
   script
   --package servant
   --package servant-client
   --package http-client
   --package aeson
   --package text
-}

-- the above comments allow this to be run as a script if haskell-stack is installed.
-- Actual source starts here.
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}

module Main where

import Data.Aeson
import Servant.API
import Servant.Client
import qualified Network.HTTP.Client as HttpClient
import Data.Proxy
import Data.Text(Text)
import Text.Printf
import System.IO(stderr)

newtype GameID = GameID Text deriving (PrintfArg, ToHttpApiData)

instance FromJSON GameID where
  parseJSON = withObject "GameID" $ \o ->
    fmap GameID (o .: "game_id")

data Accuracy = Lower | Higher | Correct

readAccuracy :: Text -> Accuracy
readAccuracy t
  | t == "lower" = Lower
  | t == "higher" = Higher
  | t == "right" = Correct
  | otherwise = error $ printf "Unexpected accuracy text: \"%s\"" t

data GuessResult = GuessResult { xAccuracy :: Accuracy, yAccuracy :: Accuracy, turnCount :: Maybe Int }

instance FromJSON GuessResult where
  parseJSON = withObject "GuessResult" $ \o ->
    GuessResult
      <$> fmap readAccuracy (o .: "x")
      <*> fmap readAccuracy (o .: "y")
      <*> o .:? "turns"

type EggAPI =    "new_game" :> Get '[JSON] GameID
            :<|> "guess"
              :> Capture "game_id" GameID
              :> Capture "x" Int
              :> Capture "y" Int
              :> Get '[JSON] GuessResult

getNewGame :: ClientM GameID
makeGuess :: GameID -> Int -> Int -> ClientM GuessResult
getNewGame :<|> makeGuess = client (Proxy :: Proxy EggAPI)

data CoordinateRange = CoordinateRange { lowerBound :: Int, higherBound :: Int }

middleOfRange :: CoordinateRange -> Int
middleOfRange rng = lowerBound rng + (higherBound rng - lowerBound rng) `div` 2

adjustCoordinateRange :: Accuracy -> CoordinateRange -> CoordinateRange
adjustCoordinateRange Lower rng = CoordinateRange (lowerBound rng) (middleOfRange rng)
adjustCoordinateRange Higher rng = CoordinateRange (middleOfRange rng) (higherBound rng)
adjustCoordinateRange Correct rng = rng

searchForEggs :: ClientM (GameID, Int)
searchForEggs = do
  game <- getNewGame
  let initialRange = CoordinateRange 1 100
  score <- loop game initialRange initialRange
  return (game, score) where
    loop gId xRange yRange = do
      guessResult <- makeGuess gId (middleOfRange xRange) (middleOfRange yRange)
      let newXRange = adjustCoordinateRange (xAccuracy guessResult) xRange
          newYRange = adjustCoordinateRange (yAccuracy guessResult) yRange
      maybe (loop gId newXRange newYRange) return $ turnCount guessResult

main :: IO ()
main = do
  manager' <- HttpClient.newManager HttpClient.defaultManagerSettings
  let clientEnv = mkClientEnv manager' (BaseUrl Http "easter_egg_hunt.andrewfaraday.com" 80 "")
  result <- runClientM searchForEggs clientEnv
  case result of
    Left err -> hPrintf stderr  "Error: %s\n" (show err)
    Right (game, score) -> printf "GameID: %s | Score: %d\n" game score

```

# Results

```
GameID               |  Score
---------------------+-------
fdcbwwxkvhkfskqlpgnh |  7
cdgjnksfnrhgjjsdbnhd |  7
lbjjqgkvfzzprnrxcpsx |  6
rtbngkdlwdfmhdyggnjd |  6
rcphvxzzgblfnzxdqlyh |  6
gyfjbjmplkrfnqjptygl |  7
bkdnbqhsbhwwvgtcfhjb |  6
knjdxdmvttwgltjdpvtv |  7
zqpstnhjgsykkwxnxcbv |  7
rccpmsbfxqvsmzxckhcs |  7

```

# Answer
> 1 votes
# Python 2

**Golfed vesrion - 276 bytes**

```
from requests import*
u='http://easter_egg_hunt.andrewfaraday.com'
i=get('%s/new_game'%u).json()['game_id']
x=y=50;s=25;o={}
while not'turns'in o:o=get('%s/guess/%s/%d/%d'%(u,i,x,y)).json();exec("%s+=s*'rh'.rfind(o['%s'][0]);"*2)%tuple('xxyy');s=s%2+s/2
print i,x,y,o['turns']

```

**More readable version + comments**

```
from requests import*
u='http://easter_egg_hunt.andrewfaraday.com'
i=get('%s/new_game'%u).json()['game_id'] # get game id
x=y=50    # initial central position
s=25      # step of binary search
o={}      # initialize o to further store returns
while not'turns'in o:    # cycle until 'turns' occurs in return
    o=get('%s/guess/%s/%d/%d'%(u,i,x,y)).json()
    exec("%s+=s*'rh'.rfind(o['%s'][0]);"*2)%tuple('xxyy');s=s%2+s/2
    # this exec is used to shorten two similar lines for x and y:
    #  x += s * (... o['x'] ...);
    #  s*'rh'.rfind(o['%s'][0]) - look at first letter of return and use its position in string 'rh' to map multipliers for step:
    #                             -1 for lower, +1 for higher and 0 for right
    #                             rfind() will return -1 for not finding l
    s=s%2+s/2    # divide step in two, rounding up
print i,x,y,o['turns']

```

# Results

```
vjwqvbydwmbvbrhwrxqz 19 95 4
svkdvszghjzfbvqxsprt 5 12 4
dvbpnxjdgrydwffcndnt 81 67 6
qqwgsctqhdcrbywwrcxf 21 49 6
zrgqqtzjjrrsqbgvkbsm 37 12 6
trzjngljbwbwxycxpcbk 91 2 7
kysjwfzsrdjsybrchnzg 76 45 7
kcjtxqfmcgszrwkyhlkm 68 48 7
wykbjvthqmcyzscxnsxt 68 41 7
kldrfccjdphzqnqcmdgz 88 14 7

```

# Summary

Somewhat expected :D
6+6+6+7+7+7 = 39

# Answer
> 1 votes
# Rust

As it happens, Rust has a really nice deserialization library called `serde` which helped a lot with this program. The algorithm itself is a rather straightforward binary search, except ran twice - once for `x` and once for `y`.

The URL macro has a specific case for no format strings because it can be done for pretty much free, and when not formatting the string would be stored in static storage.

## Cargo.toml

```
[package]
name = "easter-egg-hunt"
version = "0.1.0"
authors = ["Konrad Borowski"]

[dependencies]
reqwest = "0.8.5"
serde = "1.0.36"
serde_derive = "1.0.36"

```

## main.rs

```
extern crate reqwest;
extern crate serde;
#[macro_use]
extern crate serde_derive;

use reqwest::Client;

#[derive(Deserialize)]
struct NewGame {
    game_id: String,
}

#[derive(Deserialize)]
struct Guess {
    x: GuessStatus,
    y: GuessStatus,
    turns: Option<u32>,
}

#[derive(Deserialize)]
#[serde(rename_all = "lowercase")]
enum GuessStatus {
    Lower,
    Right,
    Higher,
}

macro_rules! url {
    ($path:expr) => {
        concat!("http://easter_egg_hunt.andrewfaraday.com", $path)
    };
    ($path:expr $(, $part:expr)*) => {
        &format!(url!($path) $(, $part)*)
    };
}

struct BinarySearch {
    low: u8,
    high: u8,
}

impl BinarySearch {
    fn new() -> Self {
        BinarySearch { low: 1, high: 100 }
    }

    fn current_guess(&self) -> u8 {
        (self.low + self.high) / 2
    }

    fn update(&mut self, guess_status: GuessStatus) {
        let current_guess = self.current_guess();
        match guess_status {
            GuessStatus::Lower => self.high = current_guess - 1,
            GuessStatus::Higher => self.low = current_guess + 1,
            GuessStatus::Right => {
                self.high = current_guess;
                self.low = current_guess;
            }
        }
    }
}

fn run_game(client: &Client) -> reqwest::Result<()> {
    let NewGame { game_id } = client.get(url!("/new_game")).send()?.json()?;
    let mut x_search = BinarySearch::new();
    let mut y_search = BinarySearch::new();
    loop {
        let x_guess = x_search.current_guess();
        let y_guess = y_search.current_guess();
        let response = client
            .get(url!("/guess/{}/{}/{}", game_id, x_guess, y_guess))
            .send()?
            .json()?;
        match response {
            Guess { x, y, turns: None } => {
                x_search.update(x);
                y_search.update(y);
            }
            Guess {
                turns: Some(turns), ..
            } => {
                println!("id:{} x:{} y:{} count:{}", game_id, x_guess, y_guess, turns);
                return Ok(());
            }
        }
    }
}

fn main() {
    let client = Client::new();
    for _ in 0..10 {
        run_game(&client).unwrap();
    }
}

```

## Summary

```
id:tlxjnjtslnsnbdxyzlvn x:97 y:22 count:7
id:bbzpyhhflrdjzylwxtbr x:21 y:6 count:5
id:kcjdkfvddgxckmprxwtw x:81 y:99 count:6
id:tnzryxpkblqrqbqrqkby x:30 y:25 count:7
id:pbzkdrmjrvwmkgmlvwcb x:79 y:20 count:7
id:qxvcbcslkdmjxnffsxfb x:36 y:94 count:7
id:hqfgpdmktyfwqtbrvvly x:94 y:71 count:5
id:ytgsnssvlpnhzqzgvygw x:1 y:83 count:7
id:gjhglmkbhvswqwgrynft x:65 y:94 count:5
id:rzghpypysxtwkclgpbkx x:55 y:96 count:7

```

5 + 6 + 7 + 7 + 7 + 7 = 39

---
Tags: code-challenge, internet
---


title: Is the graph acyclic?

text:
# Question
Title: Is the graph acyclic?
A Directed Acyclic Graph (DAG) is a type of graph that has no cycles in it. In other words, if there is a link from node A to node B, there exists no path from B to A (via any nodes).

# Challenge

Determine whether the directed graph given as input is acyclic.

# Input

A list of lists of integers representing the links between nodes, where a node is identified by its index in the list.

# Output

Standard I/O for decision problems; generally a truthy value for acyclic graphs, and a falsy one for cyclic graphs. Additionally, your program may halt/not halt to indicate truthy and falsy, if you wish.

# Test Cases

```
[[1, 2], [3, 4], [5], [], [6], [6], []]

```

Represents the following graph (where all edges are directed downwards):

```
        0
      /   \
     1     2
    / \   /
   3  4  5
      | /
      6

```

This example is acyclic, so the result should be truthy.

```
[[1, 3], [2], [0], [1]]

```

Represents the following graph:

```
 -----<-----<----
/                \
0 --> 3 --> 1 --> 2
 \---->----/

```

This example is cyclic, so the result should be falsey. (Sorry for my terrible drawing; if this is unclear let me know.)

# Constraints

* No input will ever be invalid; i.e. no node will link to a node that does not exist
* Self loops *must* be handled (`[[0]]` is a cyclic graph)

This is , so the fewest bytes in each language wins.

# Answer
> 8 votes
# Mathematica, ~~80~~ ~~44~~ ~~40~~ ~~30~~ 22 bytes

```
#//.x_:>#[[Union@@x]]&

```

Uses 1-based indexing for input. Returns an empty list iff the graph is acyclic.

### Example:

```
In[1]:= #//.x_:>#[[Union@@x]]&[{{2,3},{4,5},{6},{},{7},{7},{}}]

Out[1]= {}

In[2]:= #//.x_:>#[[Union@@x]]&[{{2,4},{3},{1},{2}}]

Out[2]= {{2, 4}, {3}, {1}, {2}}

In[3]:= #//.x_:>#[[Union@@x]]&[{{1}}]

Out[3]= {{1}}

```

# Answer
> 4 votes
# Jelly,  ~~8~~  7 bytes

```
µị³FµL¡

```

A full program, printing no output for an acyclic input; or some output for a cyclic input.

**Try it online!**

### How?

```
µị³FµL¡ - Main link: list of lists of natural numbers, g
µ   µ ¡ - repeat
     L  - length times:
  ³     -   program's 3rd command line argument, 1st program input, g
 ị      -   index into
   F    -   flatten (makes a list of nodes that are reachable, possibly with repeats)
        - implicit print - If cyclic:  it contains integers, and the Jelly representation
                                       is a `[]` enclosed `, ` separated string of them.
                           If acyclic: it contains nothing, anf the Jelly representation
                                       is an empty string (the `[]` is not even printed)

```

# Answer
> 3 votes
# Python 2, 70 bytes

```
f=lambda G,s=0,v=-1:G[s:]and all(f(G,s+1,x)for x in(G+[sum(G,[])])[v])

```

Try it online!

An n-vertex graph is cyclic only if one can take an n-step path. In an acyclic graph, no vertex on the path can repeat so it must hit a dead end.

This recursive function tries all paths in the graph `G`, tracking the current number of steps `s` and current vertex `v`. Once `s` is at least `len(G)`, we the Falsey value of `[]` is returned. To allow the walk to start on any vertex, the initial phantom vertex `v=-1` connects to every (reachable) node of `G`, extracted as `sum(G,[])`.

An iterative version tied in length.

**Python 2, 70 bytes**

```
G=input()
r=sum(G,[])
for _ in G:r=sum([G[v]for v in r],[])
print[]==r

```

Try it online

# Answer
> 3 votes
# Haskell, 28 bytes (halts or doesn’t halt)

```
f g|let s=(>>=s.(g!!))=g>>=s

```

Try it online!

For any list `xs` of nodes, `s xs` = `xs >>= s . (g !!)` = `[y | x <- xs, y <- s (g !! x)]` does a recursive search through all nodes reachable from them. We run this on all nodes in the graph with `g >>= s`.

# Haskell, 36 bytes (returns `True` or `False`)

```
f g=null$foldr(=<<)(id=<<g)$(g!!)<$g

```

Try it online!

For any list `xs` of nodes, `(g!!) =<< xs` = `[y | x <- xs, y <- g !! x]` is the list of endpoints of all edges starting at nodes in `xs`. Now if `g` has length *n*, then

`foldr(=<<)(id=<<g)$(g!!)<$g`
= `foldr (=<<) (id =<< g) [(g!!), (g!!), …, (g!!), (g!!)]` (*n* repetitions)
= `(g!!) =<< (g!!) =<< … =<< (g!!) =<< (g!!) =<< id =<< g`
= `(g!!) =<< (g!!) =<< … =<< (g!!) =<< (g!!) =<< concat g`
= `(g!!) =<< (g!!) =<< … =<< (g!!) =<< (g!!) =<<` \[endpoints of all edges, i.e., paths of length 1\]
= `(g!!) =<< (g!!) =<< … =<< (g!!) =<<` \[endpoints of all paths of length 2\]
= …
= `(g!!) =<<` \[endpoints of all paths of length *n*\]
= \[endpoints of all paths of length *n* \+ 1\],

which is `null` if and only if the graph is acyclic.

# Answer
> 2 votes
# APL (Dyalog Classic), 20 bytes

```
⍳∘≢∨.∊⊂{⍵∪∊⍺[⍵]}⍣≡¨⊢

```

Try it online!

# Answer
> 1 votes
## Mathematica, 82 bytes

```
AcyclicGraphQ[g=Graph[Join@@Thread/@Thread[Range@Length@#->#]]]&&LoopFreeGraphQ@g&

```

# Answer
> 0 votes
# Python 2, 53 bytes

```
f=lambda i:map(f,l[i]);l=input();map(f,range(len(l)))

```

Crashes if and only if the graph is cyclic, due to infinite recursion. Takes input via stdin.

Try it online!

# Answer
> 0 votes
## JavaScript (ES6), 98 bytes

```
f=(a,b=[...a.keys()],c=b.filter(i=>b.some(b=>a[b].some(b=>b==i))))=>1/b[c.length]?f(a,c):!(1/c[0])

```

Returns `true` for acyclic, `false` for cyclic. Explanation: Starting with the set `b` of all the nodes in `a`, the subset of all nodes of `b` which are the target of a link is iterated until it doesn't change. If the resulting subset is empty then the graph is acyclic.

---
Tags: code-golf, decision-problem, graph-theory
---


title: Simulating Crashing Cars

text:
# Question
Title: Simulating Crashing Cars
# Introduction

I have some ASCII cars that have velocity and direction. Their velocity is represented by their number. If a car is `<>` then it has stopped. For example:

```
<>
1>
2>
3>

```

After one second, I get

```
<>
 1>
  2>
   3>

```

After two, I get

```
<>
  1>
    2>
      3>

```

If two cars are too close, they crash.

```
1> <1
1> <2

```

After a second, this becomes

```
 ###
 ##

```

If two cars intersect, they become hashtags were they would be.

If one car is fast enough to 'hop' over the other, it does not result in a crash.

```
3><1   2><1   4><>

```

becomes

```
 <13>   ###     <>4>

```

If a car goes left off-screen, it disappears (unless there's a crash). There is no way for a car to go right off-screen.

```
 <11>
<1  1>
1    1>
      1>

```

# Challenge

Based on the given car physics, you must create a program that can time-step one second into the future. The input will be cars with spaces and a maximum velocity of 5 (matching regex `(<[1-5]|[1-5]>|<>| )+`). The simulation will happen on one line, however that line has no fixed size.

# Test cases

```
<> 1> 2> 3> 4> 5>
<>  1>  2>  3>  4>  5>

1><1   1> <1   1>  <1
 ##     ###     1><1

2><2   2> <2   2>  <2   2>   <2   2>    <2
<22>    ###      ##       ###       2><2

<22>  <1 3>   <2
    ###     ##

<><>     1><>     2><>     3><>     4><>     5><>
<><>      ###       ##       ###      <>4>     <> 5>

<><1 <2 <3 <4 <5
###<2<3<4<5

```

# Scoring

This is , so code with the smallest number of bytes wins!

# Answer
# JavaScript (ES6), 140 bytes

```
s=>[...s.replace(/\S./g,([a,b],i)=>r[r[i+=+b?-b:~~a]=r[i]?C:a,++i]=r[i]?C:b,r=[],C='#')&&r].map((c,i)=>c?r[i-1]==C|r[i+1]==C?C:c:' ').join``

```

Try it online!

### Commented

```
s =>                      // given the input string s
  [ ...s.replace(         // search in s ...
    /\S./g,               //   ... all substrings consisting of 2 non-whitespace characters
    ([a, b], i) =>        //   let a be the 1st character, b the 2nd one and i the position
      r[                  //   update r[]:
        r[i +=            //     apply the car velocity to i:
          +b ? -b         //       if b is a digit, then move b cells backwards
                  : ~~a   //       else: use a to move forwards (or don't move at all)
        ] = r[i] ? C : a, //     if r[i] is set, overwrite it with '#'; otherwise, insert a
        ++i               //     increment i for the 2nd character
      ] = r[i] ? C : b,   //     if r[i] is set, overwrite it with '#'; otherwise, insert b
      r = [],             //   initialize r[] to an empty array
      C = '#'             //   define C as the 'crash' character
  ) && r ]                // end of replace(); return a fully iterable copy of r[]
  .map((c, i) =>          // for each entry c at position i in this array:
    c ?                   //   if c is defined:
      r[i - 1] == C |     //     if either the previous
      r[i + 1] == C ?     //     or the next cell is '#' (in the original array):
        C                 //       replace the current cell with '#'
      :                   //     else:
        c                 //       let c unchanged
    :                     //   else:
      ' '                 //     insert a space
  ).join``                // end of map(); join the result

```
> 3 votes

# Answer
# JavaScript (Node.js), 259 bytes

254 to 259 because i added test case which wasnt in the testcases that complicated my result regex finder

```
s=>{
c=[]
n=[S=""]
s.replace(/<?\d>?|<>/g,([d,D],i)=>d>0?g(i+ +d,d)+g(i-~d,D):g(i-~~D,d)+g(i-~~D+1,D))
for(i of n)S+=i||" "
return S.replace(/1?[2-9]*1?/g,(d,i)=>d>"1".repeat(l=d.length)?"#".repeat(l):c.slice(i,i+l).join``)}
g=(x,p)=>x<0||(n[x]=-~n[x],c[x]=p)

```

Try it online!
> 0 votes

# Answer
# Retina, 178 bytes

```
^\d([^>])
 $1
T`5-1`d`<.
 *(<(\d)|((\d)>|<>))
$2* $#3*5* $4* $.`* $&¶
T`d`5-1`<.
m`^.{0,5}

G`.
N^$`
$.&
{+m`\A( *)  (.*)¶\1(..?)$
$1$3$2
m`^\A( *)( *)..(.*)¶\1(..?)$
$1##$.2*#$3

```

Try it online! Link includes test cases. Explanation:

```
^\d([^>])
 $1

```

Handle the case of a car moving off the left.

```
T`5-1`d`<.

```

Temporarily complement the digits of cars moving to the left.

```
 *(<(\d)|((\d)>|<>))
$2* $#3*5* $4* $.`* $&¶

```

Put each car on its own line (`$.`* $&¶`) and add some indent depending on the speed of the car; left-moving cars get the complemented speed, while non-moving cars get 5 more than the speed.

```
T`d`5-1`<.

```

Uncomplement the left-moving car digits.

```
m`^.{0,5}

```

Move all of the cars 5 to the left. This fixes the indent for all cars.

```
G`.

```

Delete all cars that have moved off the left.

```
N^$`
$.&

```

Sort the remaining cars in reverse horizontal order.

```
{

```

Repeat the remaining stages until all the cars have been processed.

```
+m`\A( *)  (.*)¶\1(..?)$
$1$3$2

```

As long as the next car does not crash, add it to the result.

```
m`^\A( *)( *)..(.*)¶\1(..?)$
$1##$.2*#$3

```

Add a crashing car to the result.
> 0 votes

---
Tags: code-golf, string, simulation
---


# Question
Title: Matrix trace for any matrix through... Bresenham’s line rasterisation
Inspired by this.

Agatha Stephendale, a sophomore who is really into raster graphics, has taken a course in linear algebra. Now she imagines matrices as rectangles, but in her artistic mind, she attaches diagonal lines to those rectangles and tries to compute traces along them. In fact, she wants to compute traces of all matrices, not just square ones.

Since Agatha is an artist, she knows how to draw lines in her favourite image editor, and the latter uses Bresenham’s algorithm to plot lines. She even checked Wikipedia and found the pseudocode:

```
 function line(x0, y0, x1, y1)
     real deltax := x1 - x0
     real deltay := y1 - y0
     real deltaerr := abs(deltay / deltax)    // Assume deltax != 0 (line is not vertical),
           // note that this division needs to be done in a way that preserves the fractional part
     real error := 0.0 // No error at start
     int y := y0
     for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
         while error ≥ 0.5 then
             y := y + sign(deltay) * 1
             error := error - 1.0

```

*(Note that this pseudocode works only for slopes less than 1; for tall grids, a similar treatment should be done, but with a loop over `y`. See this section for the two cases.)*

Agatha imagines a matrix as a rectangle, draws a diagonal line in it, and Bresenham’s algorithm determines which elements of a matrix belong to the diagonal. Then she takes their sum, and this is what she wants to implement in as few bytes as possible because she is a poor student and cannot afford large-capacity HDDs to store her code.

## Task

Given a matrix *A*, return the sum of the elements that lie on the rasterised main diagonal (from top left to bottom right), where the latter is determined by Bresenham’s line algorithm. That is, assuming that the matrix represents a *m×n* grid, draw a line on that grid from A\[1, 1\] to A\[m, n\] using Bresenham’s algorithm, and take the sum of all elements on the line. Note that for *1×N* and *N×1* matrices, the entire matrix becomes its own diagonal (because this is how one would draw a line from the first element of the first row to the last element of the last row).

**Input:** a real matrix (may be a *1×1* matrix, a row matrix, a column matrix, or a rectangular matrix). **Output:** a number.

Note that some sources (e. g. the Wikipedia’s pseudocode above) use the condition check `error≥0.5`, while other sources use `error>0.5`. You should use the originally posted one (`error≥0.5`), but if the alternative `error>0.5` is shorter in your code, then you are allowed to implement it (since this is code golf), but **mention it explicitly**. See test case 4.

## Challenge rules

* I/O formats are flexible. A matrix can be several lines of space-delimited numbers separated by newlines, or an array of row vectors, or an array of column vectors etc.
* This is , so shortest answer in bytes wins.
* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs.
* Default loopholes are forbidden.

## Test cases

1. `[[1,2,3],[4,5,6],[7,8,9]]``1+5+9` → output: `15`.

2. `[[1,2,3,4],[5,6,7,8]]``1+2+7+8` → output: `18`.

3. `[[1,2,3,4,5,6],[7,8,9,10,11,12],[13,14,15,16,17,18],[19,20,21,22,23,24]]``1+8+9+16+17+24` → output: `75`.

4. `[[1,2,3,4,5],[6,7,8,9,10]]``1+2+8+9+10` (using the  error condition) → output: `30`.

However, if it would be shorter to use the strict inequality `>` in your code, then the allowed output is `1+2+3+9+10=25`, but you should mention it separately.

5. `[[1,2,3],[4,5,6],[7,8,9],[10,11,12]]``1+5+8+12` → output: `26`.

6. `[[-0.3,0.5]]` → output: `0.2`.
7. `[[3.1],[2.9]]` → output: `6`.
8. `[[-5]]` → output: `-5`.

## More information on Bresenham’s algorithm

# Answer
# Jelly, 25 bytes

```
ZXL>LƲ¡µLḶ÷’Ɗ×XL’Ɗær0ị"OS

```

Try it online!
> 3 votes

# Answer
# SmileBASIC, ~~101~~ 99 bytes

```
DEF D A,W,H
GCLS
GTRI.,0,0,0,W-1,H-1FOR I=0TO W*H-1=I MOD W
S=S+A[I/W,M]*!!GSPOIT(M,I/W)NEXT?S
END

```

I originally thought of using the GLINE function to draw a line, but it doesn't appear to use the correct algorithm. However, GTRI *does* seem to work,

Test case 4 outputs 30.

Input is a 2D array in \[Y,X\] form, along with the width/height (there's no way to check the dimensions of an array, only the total number of elements).
> 3 votes

# Answer
# JavaScript (ES6), ~~110~~ 103 bytes

Outputs `25` for the 4th test case.

```
a=>(X=a[x=y=0].length-1,Y=1-a.length,g=e=>a[y][x]+(x-X|y+Y&&g(e+(e*2>Y&&++x&&Y)+(e*2<X&&++y&&X))))(X+Y)

```

Try it online!

Or **88 bytes** if taking the dimensions of the matrix as input is allowed.
> 1 votes

# Answer
# Python 3.X, 269 bytes

With input as comma-delimited rows of space-delimited numbers.

`import math;c=math.ceil;a=[[float(k)for k in q.split(" ")]for q in input().split(",")];_=len;m=lambda f,t,x,y,e,d:sum(x[0]for x in a)if 2>_(a[0])else m(*[0]*4,*[(_(a)-1)/(_(a[0])-1)]*2)if f else m(f,t+a[y][x],x+1,y+c(e-0.5),e+d-c(e-0.5),d)if x<_(a[0])else t;m(1,*[0]*5)`

Pre-golfing:

```
def line(a):
   if len(a[0])<2: return sum([x[0] for x in a])
   e = d = abs((len(a)-1)/(len(a[0])-1))
   y=t=0
   for x in range(len(a[0])):
       t += a[y][x]
       f = ceil(e-0.5)
       y += f
       e += d-f
   return t

```
> 1 votes

# Answer
# FMSLogo, 136 bytes

```
make 1 rl
setxy -1+count :1 -1+count last :1
pu home
make 9 0
foreach :1[foreach ?[if
0=last pixel[make 9 :9+?]fd 1]setxy xcor+1 0]pr :9

```

Full program, prompt the user for input (dialog box popup) and then print the output to the screen.

Just draw a line on the screen and calculate the output. Use strict inequality.

---

This only supports matrix size up to FMSLogo's canvas size (about 500×500)

Ungolfed code:

```
Make "input ReadList
SetXY (-1+Count :input) (-1+Count Last :input)
PenUp
Home
Make "sum 0
ForEach :input[
    ForEach ?[
        If 0=Last Pixel[
            Make "sum :sum+?
        ]
        Forward 1
    ]
    SetXY XCor+1 0
]
Print :sum

```
> 1 votes

---
Tags: code-golf, matrix, algorithm
---


title: Not Quite Roman Ternary

text:
# Question
Title: Not Quite Roman Ternary
Given an integer n ≥ 0 , output it in a non-positional base-3 notation, using digits `139ABCDE…` and a 1-character separator. Every digit is a consecutive power of 3 and the digits on the left side of the separator are negated, e.g. **A931|B** → 81−(1+3+9+27) → **41**. A digit may appear only once.

Rigorously, let the value of a digit be:

* its value if the digit is 1, 3 or 9
* 27 if the digit is `A`
* 3 times the value of the digit right before it for `B`..`Z`

Your output should satisfy **sum(value of digits to the right of `|`) - sum(value of digits to the left of `|`) == input** .

### Examples

```
input     output
----------------
0         |
1         |1
7         3|91
730       |D1
9999      FEDC|GA9

```

You may use a different **non-space** character as a separator. You are also allowed to have no separator, in which case the largest digit starts the positive sequence. You don’t need to handle anything larger than 232−1 (`PMIGDCBA9|RQNLH3`).

You may write a full program or function, and input and output may be provided on any of the usual channels.

This is , so the shorter your answer the better!

# Answer
# Java 10, ~~120~~ ~~113~~ ~~112~~ ~~109~~ ~~107~~ ~~102~~ 92 bytes

```
n->{var r="|";for(var c='1';n++>0;c+=c>64?1:c*4%22%9,n/=3)r=n%3<1?c+r:n%3>1?r+c:r;return r;}

```

-3 bytes by using part of the trick of *@Arnauld*'s JavaScript (ES6) answer,
changing `i=0` and `i++<1?49:i<3?51:i<4?57:i+61` to `i=4` and `++i>9?i+55:i>8?57:++i+43`.
-6 bytes thanks to *@Arnauld* directly, by getting rid of `i`.
-10 bytes thanks to *@ceilingcat*.

Order of output: Highest-to-lowest, `|`-delimiter, lowest-to-highest.

**Explanation:**

Try it online.

```
n->{              // Method with integer parameter and String return-type
  var r="|";      //  Result-String, starting at the delimiter "|"
  for(var c='1';  //  Character, starting at '1'
      n++>0       //  Loop as long as `n` is larger than 0
                  //  Increasing it by 1 with `n++` at the start of every iteration
      ;           //    After every iteration:
       c+=        //     Change character `c` to:
          c>64?   //      If the current `c` is an uppercase letter:
               1  //       Simply go to the next letter using `c+=1`
              :   //      Else:
               c*4%22%9,
                  //       Change '1' to '3', '3' to '9', or '9' to 'A'
       n/=3)      //     Integer-divide `n` by 3
     r=           //   Change the result to:
       n%3<1?     //    If `n` modulo-3 is 0:
        c+r       //     Prepend the character to the result
       :n%3>1?    //    Else-if `n` modulo-3 is 2:
        r+c       //     Append the character to the result
       :          //    Else (`n` modulo-3 is 1):
        r;        //     Leave `r` unchanged
   return r;}     //  Return the result-String

```
> 6 votes

# Answer
# Python 3, ~~103~~ ~~99~~ 91 bytes

4 bytes thanks to Lynn.

8 bytes thanks to ovs.

```
def f(n,s="|",b=0):c=('139'+chr(b+62)*b)[b];return n and f(-~n//3,[s,s+c,c+s][n%3],b+1)or s

```

Try it online!

Credits to xnor for the logic.
> 5 votes

# Answer
# JavaScript (ES6), ~~82~~ ~~80~~ 79 bytes

Outputs in lowercase, which should hopefully be fine.

```
f=(n,s=(k=4,'|'),c=++k>8?k.toString(36):++k-5)=>n?f(++n/3|0,[c+s,s,s+c][n%3]):s

```

Try it online!

Similar to Leaky "Ninja Master" Nun's answer and also based on xnor's answer.

### Digit conversion

We start with **k = 4**. While **k** is less than **9**, we increment it twice at each iteration and subtract **5**. After that, we increment it only once and convert it to base-36.

```
  k  | ++k > 8       | k.toString(36) | ++k - 5  | result
-----+---------------+----------------+----------+--------
  4  | k=5  -> false |                | k=6 -> 1 | 1
  6  | k=7  -> false |                | k=8 -> 3 | 3
  8  | k=9  -> true  | '9'            |          | '9'
  9  | k=10 -> true  | 'a'            |          | 'a'
  10 | k=11 -> true  | 'b'            |          | 'b'
 ... | ...           | ...            | ...      | ...

```
> 5 votes

# Answer
# Jelly, 26 bytes

```
‘:3Ɗ⁹Ð¡‘%3ẹÐ€0,2ị139D;ØA¤Y

```

Try it online!

Use a newline as the separator.
> 4 votes

# Answer
# Perl 6, 80 bytes

```
{map({|(1,3,9,|('A'..'Z'))[grep :k,*%3==$^v,($_,-+^*div 3...0)]},1,2).join.flip}

```

Try it online!

No separator. Based on xnor's answer.
> 2 votes

# Answer
# Stax, ~~30~~ 29 bytes

```
£└≤☻╘pÿ╖╡A[ô%æτ⌐}►ºôßHl4⌡π%^

```

Run and debug it

Port of my Stax answer in Balanced Ternary Converter.

## Explanation

Uses the unpacked version to explain.

```
139$VA+cz{;3%+,^3/~;wY1|I@'|ay2|I@L
139$VA+c                               "139AB...Z", make a copy
        z                              Empty array to store the digits
          {         w                  Do the following until 0.
           ;3%+                           Append `b%3` to the digits
                                          Originally, `b` is the input
              ,^3/                        `b=(b+1)/3`
                  ~;                       Make a copy of `b` which is used as the condition for the loop

                     Y                 Save array of digits in `y` for later use
                      1|I              Find index of 1's
                         @             Find the characters in "139AB...Z" corresponding to those indices
                          '|           A bar
                            ay2|I@     Do the same for 2's
                                  L    Join the two strings and the bar and implicit output

```
> 2 votes

# Answer
# , ~~69 64~~  58 bytes

```
('931',~u:90-i.26){~0(>,&I.<)(29$3)((+1&|.-3&*)]-*)^:_@#:]

```

Try it online!
> 2 votes

# Answer
# Ruby, ~~87~~ ~~84~~ 82 bytes

Saved 2 bytes thanks to @benj2240.

```
->n,s=[?1,?3,?9,*?A..?Z],r=[""]*3{r[-m=n%3]+=s.shift
n=n/3+m/2
n>0?redo:r[1,2]*?|}

```

Try it online!
> 1 votes

# Answer
# C# .NET, ~~103~~ 100 bytes

```
n=>{var r="|";for(var c='1';n++>0;c+=(char)(c>64?1:c*4%22%9),n/=3)r=n%3<1?c+r:n%3>1?r+c:r;return r;}

```

-3 bytes thanks to *@ceilingcat*.

Port of my Java 10 answer. If a direct port (except for `n->` to `n=>`) would have been possible, I would have edited my Java answer with this polyglot. Unfortunately however, having `c=49` isn't possible in C#, nor the `c+=` without `(char)` cast, hence this loose ported answer.

Try it online.
> 1 votes

# Answer
# Perl 5 `-p`, ~~71~~ 69 bytes

uses no separator. The negative and positive parts are in "roman order" (largest digit first)

```
#!/usr/bin/perl -p
$n=$_}{s/@{[$n++%3]}\K/]/,$n/=3,y/?-]/>-]/for($_=21)x31;y/>?@12/139/d

```

Try it online!
> 1 votes

# Answer
# , 129 bytes

```
f=:3 :0
a=.'139',u:65+i.26
s=.'|'while.y>0 do.if.1=c=.3|y do.s=.s,{.a end.y=.<.y%3
if.c=2 do.s=.s,~{.a
y=.1+y end.a=.}.a end.s
)

```

Try it online!

Too lengthy, especially for a J program...

## Explanation:

```
f =: 3 : 0
   a =. '139',u:65+i.26   NB. a list '139ABC...Z'
   s =. '|'               NB. initialize the list for the result
   while. y>0 do.         NB. while the number is greater than 0
      c =. 3|y            NB. find the remainder (the number modulo 3)
      y =. <.y%3          NB. divide the number by 3
      if. c = 1 do.       NB. if the remainder equals 1
         s =. s,{.a       NB. Append the current power of 3 to the result
      end.
      if. c = 2 do.       NB. if the remainder equals 2
         s =. s,~{.a      NB. prepends the result with the current power of 3
         y =. 1+y         NB. and increase the number with 1
      end.
      a =. }.a            NB. next power of 3
   end.
   s                      NB. return the result
)

```
> 1 votes

# Answer
# C, `int`: ~~138~~ 123 bytes, `long`: ~~152~~ 131 bytes

I have created two versions of this, as the challenges' limit of a working max input of `0x100000000` seemed a bit odd. One version works with 32 bit integers (which fails the limit for obvious reasons), the other version works with 64 bits (which goes way beyond the given limit, at the cost of ~~14~~ 8 extra bytes).

32 bit version:

```
char b[22],*r=b;f(v,l)char*l;{v%3>1?*r++=*l,v++:0;v&&f(v/3,l+1);v%3?*r++=*l:0;}g(v){f(v,"139ABCDEFGHIJKLMNOPQR");*r=0;r=b;}

```

64 bit version:

```
char b[22],*r=b;f(long v,char*l){v%3>1?*r++=*l,v++:0;v&&f(v/3,l+1);v%3?*r++=*l:0;}g(long v){f(v,"139ABCDEFGHIJKLMNOPQR");*r=0;r=b;}

```

This is identical except that it declares the integer variable to be `long` (which is 64 bits on linux).

The ungolfed `long` version:

```
char buffer[22],*result=buffer;
f(long value,char*letter){
    if(value%3>1){
        *result++=*letter,value++;
    }
    if(value){
        f(value/3,letter+1);
    }
    if(value%3){
        *result++=*letter;
    }
}
g(long value){
    f(value,"139ABCDEFGHIJKLMNOPQR");
    *result=0;
    result=buffer;
}

```

As you can see, this works by recursive decent: If the remainder is 1, the respective character is appended to the output string after the recursive call. If the remainder is 2, the output is performed before the recursing. In this case, I also increment the value by one to handle the negative digit correctly. This has the added benefit of changing the remainder to zero, allowing me to use `value%3` as the condition for the post-recursion if.

The result of the conversion is placed into the global buffer. The `g()` wrapper has the job of zero terminating the resulting string correctly, and to reset the `result` pointer to its start (which is also how `g()` "returns" the result).

Test the `long` version with this code:

```
#include <stdio.h>

char b[22],*r=b;f(long v,char*l){v%3>1?*r++=*l,v++:0;v&&f(v/3,l+1);v%3?*r++=*l:0;}g(long v){f(v,"139ABCDEFGHIJKLMNOPQR");*r=0;r=b;}

void printConversion(long value) {
    g(value);
    printf("%ld: %s\n", value, r);
}

int main() {
    for(long i = 0; i <= 40; i++) {
        printConversion(i);
    }
    printConversion(0x7fffffff);
    printConversion(0xffffffffu);
    printConversion(0x100000000);
}

```

---

Possible further, but destructive golfing:

* -4 bytes: make the function a one-shot by removing the pointer reset in `g()`.
* -5 bytes: force the caller to perform the string termination, returning the string without termination in `buffer`, and the end of the string in `result`.
> 1 votes

# Answer
# Charcoal, 36 bytes

```
ＮθＦ³⊞υ⟦⟧Ｆ⁺139α«⊞§υθι≔÷⊕θ³θ»Ｆ²«×|ι↑⊟υ

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ

```

Input the value.

```
Ｆ³⊞υ⟦⟧

```

Push three empty lists to the predefined empty list.

```
Ｆ⁺139α«

```

Loop through the characters `139` and the uppercase alphabet.

```
⊞§υθι

```

Cyclically index the list of lists with the value and push the current character to it.

```
≔÷⊕θ³θ»

```

Divide the value by 3 but round it by adding 1 first.

```
Ｆ²«×|ι

```

Loop twice. The second time, print a `|`.

```
↑⊟υ

```

Each loop we pop the last entry from the list; the first time this gives us the entries that had a remainder of `2` (which corresponds to a balanced ternary digit of `-1`), while the second time this gives us the entries corresponding to a balanced ternary digit of `1`. The resulting array would normally print vertically, but rotating the print direction upwards cancels that out.
> 1 votes

# Answer
# Perl 5, ~~92~~ 89 bytes

Inspired by the java and python answers.

```
sub n{($n,$r,$c,@a)=(@_,'|',1,3,9,'A'..'Z');$n?n(int++$n/3,($c.$r,$r,$r.$c)[$n%3],@a):$r}

```

Try it online!

With some white space:

```
sub n {
  ($n, $r, $c, @_) = (@_, "|", 1, 3, 9, 'A' .. 'Z');
  $n ? n( int++$n/3, ($c.$r, $r, $r.$c)[$n%3], @_)
     : $r
}

```
> 0 votes

# Answer
# PHP, 73 bytes

```
for(;0|$n=&$argn;$n/=3)${$n++%3}.=_139[++$i]?:chr(61+$i);echo${2},_,${1};

```

## port of xnor´s answer, 53 bytes

```
for(;0|$n=&$argn;$n/=3)$s="0+-"[$n++%3].$s;echo$s??0;

```

Run as pipe with `-nr` or try them online.
> 0 votes

---
Tags: code-golf, integer, base-conversion
---


title: Number sum medley

text:
# Question
Title: Number sum medley
**Winner**

CJam, 74 bytes by Optimizer

**Task**

* Take an input of an integer `n` through the console or a file.
* Find the sum of the `n`th prime, square, triangular number, and cube. Add to that the factorial of the first decimal place of the square root of `n` and the `x`th Fibonacci number, where `x` is the first digit of the square of `n`.
* Print that sum to the console or to a file.

**Rules**

* Entries must complete the task above for all positive integers less than 100.
* Standard loopholes are of course not allowed.
* Any built-in function that finds primes or tests for primes in any way is not allowed.
* This is code golf.

**Summary of numbers to sum**

```
nth prime (where 2 is the first)
square of n
nth triangular number (where 1 is the first)
cube of n
factorial of the first decimal place of the square root of n
xth Fibonacci number, where x is the first digit of the square of n (2 is the third Fibonacci number)

```

**Examples**

Note: The numbers being summed are included here just for clarity.

```
Input: 1
Output: 2 + 1 + 1 + 1 + 1 + 1 = 7

Input: 11
Output: 31 + 121 + 66 + 1331 + 6 + 1 = 1556

Input: 99
Output: 523 + 9801 + 4950 + 970299 + 362880 + 34 = 1348487

```

# Answer
## CJam, ~~83 76 75~~ 74 bytes

This can be golfed more. Will update when I golf it further.

```
T1{_2$+}A*]ri:NN*s1<i={X):Xmf,1=T+:TN<}gXNN*_N*N_)*2/Nmqs_'.#)=~,:)1+:*]:+

```

The online compiler for CJam does not return proper Double numbers(required by mq, root). So try it in the Java version as mentioned on this page
> 2 votes

# Answer
## Java, 323

```
class C {public static void main(String[]s){int n=new java.util.Scanner(System.in).nextInt(),p=2,j,k=1,t=0,a=1,b=0,c;z:for(;t<n;p++){for(j=1;++j<p;)if(p%j<1)continue z;t++;}j=(int)Math.round(Math.sqrt(n)%1*10);for(t=0;t++<j;k*=t);for(c=j=n*n;(j/=10)>9;);for(t=0;++t<j;a+=b,b=a-b);System.out.print(p-1+c+(c+n)/2+c*n+k+a);}}

```

Ungolfed:

```
class C {
    public static void main(String[] args) {
        int n = new java.util.Scanner(System.in).nextInt(),                                                                    p = 2,
            j,
            k = 1,
            t,
            a = 1,
            b = 0,
            c;

        // prime
        z:
        for (t = 0; t < n; p++) {
            for (j = 1; ++j < p; ) {
                if (p % j < 1) {
                    continue z;
                }
            }
            t++;
        }

        // factorial
        j = (int) Math.round(Math.sqrt(n) % 1 * 10);
        for (t = 0; t++ < j; k *= t);

        // fibonacci
        for (c = j = n * n; (j /= 10) > 9;);
        for (t = 0; ++t < j; ) {
             a += b, b = a - b);
        }

        System.out.print(p - 1 + c + (c + n) / 2 + c * n + k + a);
    }
}

```
> 3 votes

# Answer
## Mathematica, ~~152~~ ~~136~~ ~~133~~ 132 bytes

```
For[n=Input[i=m=0],m<n,If[Divisors@++i=={1,i},m++]];#&@@Fibonacci@IntegerDigits[n^2]+i+3n^2/2+n/2+n^3+Floor[-10(Floor[s=Sqrt@n]-s)]!

```

I'm first determining the *n*th prime number in a loop (also avoiding `NextPrime` \- it's not explicitly disallowed but I think it's not intended to be allowed either), and then I'm simply summing all the required numbers in a single expression. There is one simplification: I'm combining *n2* and the triangular number *n(n+1)/2* into *3n2/2* and *n/2*.

Input is taking via prompt, which is the closest thing to STDIN you get in Mathematica.
> 2 votes

# Answer
# JavaScript (Node.js), 159 bytes

```
n=>{
f=a=b=1
for(N=n**.5*10%10|0;N;)
f*=N--
for(N=(n*n+"")[0];--N;)
b=a+(a=b)
f+=a+n*(n*n+n+-~n/2)
for(i=2;n;n-=j<=i++)
for(j=1;++j<i;)
j=i%j?j:i
return f+i-1}

```

Try it online!
> 0 votes

---
Tags: code-golf, number, fibonacci
---


title: Egg hunting in Collatz style

text:
# Question
Title: Egg hunting in Collatz style
*Inspired by The Great API Easter Egg Hunt!*

# Summary

Your task is to search for a predetermined integer in the "Collatz space" (to be explained later) using the fewest step possible.

# Introduction

This challenge is based on the famous Collatz conjecture that hopefully everyone here at least heard of. Here is a recap taken from Print the Super Collatz numbers.

> The Collatz Sequence (also called the 3x + 1 problem) is where you start with any positive integer, for this example we will use 10, and apply this set of steps to it:
>
> ```
> if n is even:
>     Divide it by 2
> if n is odd:
>     Multiply it by 3 and add 1
> repeat until n = 1
>
> ```

The Collatz distance `C(m,n)` between the two numbers `m` and `n`, for the purpose of this challenge, is the distance between two numbers in the Collatz graph(Credits to @tsh for telling me about this concept), which is defined as follows: (using `21` and `13` as examples):

Write down the Collatz sequence for `m` (in this case, `21`):

```
21, 64, 32, 16, 8, 4, 2, 1

```

Write down the Collatz sequence for `n`(in this case, `13`):

```
13, 40, 20, 10, 5, 16, 8, 4, 2, 1

```

Now count how many numbers appear only in one of the sequences. This is defined as the Collatz distance between `m` and `n`. In this case, `8`, namely,

```
21, 64, 32, 13, 40, 20, 10, 5

```

So we have Collatz distance between `21` and `13` as `C(21,13)=8`.

`C(m,n)` have the following nice properties:

```
C(m,n)=C(n,m)
C(m,n)=0 iff. m=n

```

Hopefully the definition of `C(m,n)` is now clear. Let's start doing egg hunting in the Collatz space!

At the beginning of the game, a controller decides the position of an easter egg, which is expressed by its one-dimensional coordinate: An integer in the interval `[p,q]` (in other words, an integer between `p` and `q`, both ends inclusive).

The position of the egg remains constant throughout the game. We'll denote this coordinate as `r`.

You can now make an initial guess a0, and it will be recorded by the controller. This is your 0th round. If you are so lucky that you got it right at the first place (i.e. a0=r), the game ends, and your score is `0`(The lower the score, the better). Otherwise, you enter the 1st round and you make a new guess a1, this goes on until you got it right, i.e. an=r, and your score will be `n`.

For each round after the 0th, the controller gives you one of the following feedbacks so that you can make a better guess based on the information given. Lets assume you are currently at the `n`th round and hence your guess is an

* "You found it!" if an=r, in which case the game ends and you score `n`.
* "You are closer :)" if C(an,r)\<C(an-1,r)
* "You are circling around the egg" if C(an,r)=C(an-1,r)
* "You are farther away :(" if C(an,r)\>C(an-1,r)

To save some bytes, I will call the responses as "Right", "Closer", "Same", "Farther", in the order presented above.

Here is an example game with `p=1,q=15`.

* a0=10
* a1=11, response: "Closer"
* a2=13, response: "Farther"
* a3=4, response: "Farther"
* a4=3, response: "Closer"
* a5=5, response: "Same"
* a6=7, response: "Right"

Score: `6`.

# Challenge

Design a **deterministic** strategy to play the game for `p=51, q=562` with the best score.

Answers should describe the algorithms in detail. You can attach any code that helps to elucidate the algorithm. This is not codegolf so you are encouraged to write legible code.

Answers should include the worst score they may achieve for all possible cases of `r`, and the one with lowest worst score wins. In the case of tie, the algorithms that has a better average score for all possible `r`s (which should also be included in the answers) win. There are no further tie breakers and we may have multiple winners in the end.

# Specs

# Bounty (Added after the first answer is posted)

I may personally offer a bounty to an answer where all the guesses are made within the range `[51,562]` while still having a reasonably low worst score.

# Answer
# Ruby, 196

This was way harder that I initially thought. I had to handle a lot of obscure cases and ended up with a lot of ugly code. But is was a lot of fun! :)

## Strategy

Every Collatz Sequence ends up with a sequence of powers of 2 (ex: \[16, 8, 4, 2, 1\]). As soon as a power of 2 is encountered, we divide by 2 until we reach 1. Let's call the first power of 2 in a sequence *closest pow2* (as this is also the closest power of 2 to our number using Collatz Distance). For the given range (51-562), all the possible *closest pow2* numbers are: \[16, 64, 128, 256, 512, 1024\]

### Short version

The algorithm performs:

* a binary search to figure out the closest power of 2 to the current number
* a linear search to figure out every previous element in the sequence until the target number is discovered.

### Detailed version

Given a game with the target number `r`, the strategy is the following:

1. Use binary search to figure out the power of 2 that is closest to `r` in as few steps as possible.
2. If the closest power of 2 that was found is the solution, stop. Otherwise continue to 3.
3. Since the power of 2 that was found is the first power of 2 occurring in the sequence, if follows that that value was reached by doing a (\* 3 + 1) operation. (If it came after a /2 operation, then the previous number would also have been a power of 2). Compute the previous number in the sequence by doing the reverse operation (-1 and then /3)
4. If that number is the target, stop. Otherwise continue to 5.
5. Given the current number known from the sequence, it is needed to go back and discover the previous number in the sequence. It is not known whether the current number was arrived at by a (/2) or (\*3 +1) operation, so the algorithm tries them both and sees which one yields a number that is closer (as Collatz Distance) from the target.
6. If the newly discovered number is the right one, stop.
7. Using the newly discovered number, go back to step 5.

## The results

Running the algorithm for all the numbers in the 51-562 range takes around a second on a normal PC and the total score is 38665.

## The code

Try it online!

```
require 'set'

# Utility methods
def collatz(n)
  [].tap do |results|
    crt = n
    while true
      results << crt
      break if crt == 1
      crt = crt.even? ? crt / 2 : crt * 3 + 1
    end
  end
end

def collatz_dist(m, n)
  cm = collatz(m).reverse
  cn = collatz(n).reverse
  common_length = cm.zip(cn).count{ |x, y| x == y }
  cm.size + cn.size - common_length * 2
end

GuessResult = Struct.new :response, :score
# Class that can "play" a game, responding
# :right, :closer, :farther or :same when
# presented with a guess
class Game

  def initialize(target_value)
    @r = target_value
    @score = -1
    @dist = nil
    @won = false
  end
  attr_reader :score

  def guess(n)
    # just a logging decorator over the real method
    result = internal_guess(n)
    p [n, result] if LOGGING
    result
  end

  private

  def internal_guess(n)
    raise 'Game already won!' if @won
    @score += 1
    dist = collatz_dist(n, @r)
    if n == @r
      @won = true
      return GuessResult.new(:right, @score)
    end
    response = nil
    if @dist
      response = [:same, :closer, :farther][@dist <=> dist]
    end
    @dist = dist
    GuessResult.new(response)
  end

end

# Main solver code

def solve(game)
  pow2, won = find_closest_power_of_2(game)
  puts "Closest pow2: #{pow2}" if LOGGING

  return pow2 if won
  # Since this is the first power of 2 in the series, it follows that
  # this element must have been arrived at by doing *3+1...
  prev = (pow2 - 1) / 3
  guess = game.guess(prev)
  return prev if guess.response == :right

  solve_backward(game, prev, 300)
end

def solve_backward(game, n, left)
  return 0 if left == 0
  puts "***      Arrived at  ** #{n} **" if LOGGING
  # try to see whether this point was reached by dividing by 2
  double = n * 2
  guess = game.guess(double)
  return double if guess.response == :right

  if guess.response == :farther && (n - 1) % 3 == 0
    # try to see whether this point was reached by *3+1
    third = (n-1) / 3
    guess = game.guess(third)
    return third if guess.response == :right
    if guess.response == :closer
      return solve_backward(game, third, left-1)
    else
      game.guess(n) # reset to n...
    end
  end
  return solve_backward(game, double, left-1)
end

# Every Collatz Sequence ends with a sequence of powers of 2.
# Let's call the first occurring power of 2 in such a sequence
# POW2
#
# Let's iterate through the whole range and find the POW2_CANDIDATES
#
RANGE = [*51..562]
POWERS = Set.new([*0..15].map{ |n| 2 ** n })

POW2_CANDIDATES =
  RANGE.map{ |n| collatz(n).find{ |x| POWERS.include? x} }.uniq.sort
# Turns out that the candidates are [16, 64, 128, 256, 512, 1024]

def find_closest_power_of_2(game)
  min = old_guess = 0
  max = new_guess = POW2_CANDIDATES.size - 1
  guess = game.guess(POW2_CANDIDATES[old_guess])
  return POW2_CANDIDATES[old_guess], true if guess.response == :right
  guess = game.guess(POW2_CANDIDATES[new_guess])
  return POW2_CANDIDATES[new_guess], true if guess.response == :right
  pow2 = nil

  while pow2.nil?

    avg = (old_guess + new_guess) / 2.0

    case guess.response
    when :same
      # at equal distance from the two ends
      pow2 = POW2_CANDIDATES[avg.floor]
      # still need to test if this is correct
      guess = game.guess(pow2)
      return pow2, guess.response == :right
    when :closer
      if old_guess < new_guess
        min = avg.ceil
      else
        max = avg.floor
      end
    when :farther
      if old_guess < new_guess
        max = avg.floor
      else
        min = avg.ceil
      end
    end

    old_guess = new_guess
    new_guess = (min + max) / 2
    new_guess = new_guess + 1 if new_guess == old_guess
    # so we get next result relative to the closer one
    # game.guess(POW2_CANDIDATES[old_guess]) if guess.response == :farther
    guess = game.guess(POW2_CANDIDATES[new_guess])

    if guess.response == :right
      pow2 = POW2_CANDIDATES[new_guess]
      break
    end

    if min == max
      pow2 = POW2_CANDIDATES[min]
      break
    end

  end

  [pow2, guess.response == :right]

end

LOGGING = false

total_score = 0
51.upto(562) do |n|
  game = Game.new(n)
  result = solve(game)
  raise "Incorrect result for #{n} !!!" unless result == n
  total_score += game.score
end
puts "Total score: #{total_score}"

```
> 5 votes

# Answer
# worst score: 11, sum score: 3986

All the guesses are in range `[51,562]`.

My algorithm:

1. First time guess 512, and maintain a set of possible results `vals`, initially the set contains all numbers in range `[51,562]`.
2. At each step, do the following:

1. Find the value of next guess `guess` in range `[51,562]` such that, when the values in `vals` (excluding `guess` itself) is partitioned into 3 sets corresponding to the possible outcomes `Closer`, `Same`, and `Farther`, the maximum size of those 3 sets is minimum.
    If there are multiple possible values of `guess` satisfy the above, choose the smallest.
    2. Guess the value `guess`.
    3. If the answer is "Right", done (exit the program).
    4. Remove all values in the set `vals` such that they cannot possibly give that result.

My reference implementation written in C++ and Bash runs in about 7.6 seconds on my machine and give the worst score/sum score as described in the title.

Trying all possible first guess values will take about 1.5 hours on my machine. I may consider doing that.
> 3 votes

---
Tags: number, optimization, atomic-code-golf
---


title: Asterisk spiral

text:
# Question
Title: Asterisk spiral
Given the spiral of size `S` and the step `N`, output the "square" `S*S` spiral having `N` asterisks, built from the outer to inner radius clockwise.

Test cases (examples) below.

1. Input: `4 3`

Output:

```
***

```
2. Input: `4 6`

Output:

```
****
   *
   *

```
3. Input: `4 11`

Output:

```
****
   *
*  *
****

```
4. Input: `6 18`

Output:

```
******
     *
     *
*    *
*    *
******

```
5. Input: `6 22`

Output:

```
******
***  *
*    *
*    *
*    *
******

```
6. Input: `6 27`

Output:

```
******
******
*   **
*   **
*   **
******

```
7. Input: `1 1`

Output:

```
*

```

It's not necessary to handle the cases when:

* provided `N` asterisks can't "fit" in the spiral of given `S*S` dimensions.
* either `N` or `S` is zero.

The challenge is code-golf, shortest bytes answer wins, any languages can be used.

Your output may have as many trailing (but not leading) spaces/newlines as you wish.

# Answer
> 16 votes
# MATL, ~~17~~ 16 bytes

```
UGlYLGoQ&P->42*c

```

Try it online!

### Explanation (with example)

Consider inputs `4` and `11` as an example.

```
U       % Implicit input: S. Push S^2
        % STACK: 16
G       % Push S again
        % STACK: 16, 4
lYL     % Outward, clockwise, east-first spiral of that size
        % STACK: 16,
                 [ 7  8  9 10;
                   6  1  2 11;
                   5  4  3 12;
                  16 15 14 13]
GoQ     % Push S, compute parity, add 1. Gives 1 for even S, 2 for odd
        % STACK: 16,
                 [ 7  8  9 10;
                   6  1  2 11;
                   5  4  3 12;
                  16 15 14 13],
                 1
&P      % Flip along that dimension (1 is vertical, 2 is horizontal).
        % This corrects for the orientation of the spiral
        % STACK: 16,
                 [16 15 14 13;
                   5  4  3 12;
                   6  1  2 11;
                   7  8  9 10]
-       % Subtract, element-wise. The upper-left corner becomes 0
        % STACK: [ 0  1  2  3
                  11 12 13  4
                  10 15 14  5
                   9  8  7  6]
>       % Implicit input (below): N. Greater than?, element-wise.
        % This transforms the first N entries, starting from
        % upper-left, inward, east-first, into 1, and the rest
        % into 0
        % STACK: [1 1 1 1;
                  0 0 0 1;
                  1 0 0 1;
                  1 1 1 1]
42*     % Multiply each entry by 42
        % STACK: [42 42 42 42;
                   0  0  0 42;
                  42  0  0 42;
                  42 42 42 42]
c       % Convert to char. Char 0 will be displayed as space.
        % Implicit display
        % STACK: ['****';
                  '   *';
                  '*  *';
                  '****']

```

# Answer
> 6 votes
# Stax, 19 bytes

```
±♪☺ÿzMæ¡♠à╣♂7☼V♀§9↓

```

Run and debug it

It starts by building a string that has all the characters in the result with all the asterisks left-aligned. Then it it takes increasingly large slices off the end of the string, and "wraps" them around a grid as it rotates the grid.

Here's the same program, unpacked, ungolfed, and commented.

```
'**     repeat "*" specified number of times
,J(     square the top of the input stack, and right-pad string to that length
z       push an empty array - this is the result grid built up in the loop
{       begin a block to loop
  ~     push grid to the input stack
  ihNv  push -(i / 2) - 1 where i is the 0-based iteration index using integer division
  :/]   split the string at that index and wrap the second half in a singleton array
  ,     pop the grid from the input stack
  rM+   rotate the grid clockwise, then prepend the split string as the new first row
  n     copy what's left of the original string to top of stack for the loop condition
w       while; execute block until condition is truthy
m       display resulting grid

```

Run and debug it

# Answer
> 5 votes
# APL (Dyalog), 65 bytes

```
' *'[1+⎕>⊖∘⌽⍣o(⊖×⍨-,⍨⍴∘(⍋+\)×⍨↑(⌈2÷⍨×⍨),(+⍨⍴1,⊢,¯1,-)(/⍨)2/⍳)o←⎕]

```

Try it online!

The code for the spiral matrix is taken from another answer of mine.

# Answer
> 5 votes
# Python 2, 117 bytes

```
n,k=input()
i=0;d=1
l=(' '*n+'\n')*n
exec"l=l[:i]+'*'+l[i+1:];d=[~n/d*cmp(d*d,2),d][' '<l[i+d:]<'*'];i+=d;"*k
print l

```

Try it online!

# Answer
> 4 votes
# Python 2, 150 bytes

```
S,N=input()
X=y=n=0
Y=x=c=-1
s=eval(`[[' ']*S]*S`)
exec"if n%S<1:S-=c%2<1;X,Y=-Y,X;c+=1;n=0\nx+=X;y+=Y;s[y][x]='*';n+=1\n"*N
for i in s:print`i`[2::5]

```

Try it online!

# Answer
> 4 votes
# Charcoal, 34 bytes

```
ＮθＦＥ⮌Ｅ⊗Ｎ∨ι¹÷⁺ι¬¬κ²«Ｆ‹θι≔θι×ι*≧⁻ιθ↷

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ

```

Input `N`.

```
ＦＥ⮌Ｅ⊗Ｎ∨ι¹÷⁺ι¬¬κ²«

```

The lengths of the spiral arms (excluding corners) are `S-1`, `S-1`, `S-1`, `S-2`, `S-2`, `S-3`, ..., `3`, `2`, `2`, `1`, `1`, `1`. This is formed by starting with the range from `0` up to but excluding `2S`, changing the 0 to 1, reversing it, adding 1 to each element after the first, and finally integer dividing all the elements by 2. This list is then looped over.

```
Ｆ‹θι≔θι

```

If there are fewer stars left to draw than the length of the next arm, reduce the arm to that length.

```
×ι*

```

Draw the appropriate number of stars.

```
≧⁻ιθ

```

Subtract from the number of stars remaining.

Rotate the drawing direction by 90° clockwise.

# Answer
> 4 votes
# PHP, 118 bytes

adjusted and golfed my solution for the Alphabet Spiral.

```
for($w=$n=$argv[$s=1],$r="*";--$argv[2];$r[$p+=$s*$d+$s]="*")if(!$c=++$c%$n)($d^=$w)?$n--:$s=-$s;echo wordwrap($r,$w);

```

Run with `php -nr '<code>' <S> <N>` or try it online.

# Answer
> 3 votes
# J, ~~60~~ 56 Bytes

-4 Bytes by modifying the build proccess for the spiral so that subtracting it from y^2 was unnecessary

```
4 :'''* ''{~x<|."1|.(|:@|.,<:@{:@{:-i.@#)^:(+:<:y),.*:y'

```

Try it online!

Explanation coming ~~soon~~ now.

### Explanation:

```
4 :'''* ''{~x<|."1|.(|:@|.,<:@{:@{:-i.@#)^:(+:<:y),.*:y'  | Explicit dyad definition
                    (|:@|.,<:@{:@{:-i.@#)^:(+:<:y),.*:y   | Generate a y by y inward spiral
                                                  ,.*:y   | The matrix [[y^2]]
                    (                   )^:(+:<:y)        | 2*(y-1) times...
                     |:@|.                                | Rotate
                          ,                               | Append
                                    i.@#                  | [0..len(n)-1]
                           <:@{:@{:-                      | Subtracted from the previous value and decremented
              |."1|.                                      | Flip around antidiagonal
            x>                                            | Test if each entry is less than x
    '' *''{~                                              | ' ' for 0, '*' for 1

```

Examples:

```
   3 :'(|:@|.,<:@{:@{:-i.@#)^:(+:<:y),.*:y' 4
7  8  9 10
6 15 16 11
5 14 13 12
4  3  2  1
   3 :'|."1|.(|:@|.,<:@{:@{:-i.@#)^:(+:<:y),.*:y' 4
1  2  3 4
12 13 14 5
11 16 15 6
10  9  8 7
   11(4 :'x<|."1|.(|:@|.,<:@{:@{:-i.@#)^:(+:<:y),.*:y') 4
0 0 0 0
1 1 1 0
0 1 1 0
0 0 0 0
   11(4 :'''* ''{~x<|."1|.(|:@|.,<:@{:@{:-i.@#)^:(+:<:y),.*:y') 4
****
   *
*  *
****

```

# Answer
> 2 votes
# Java 10, ~~284~~ ~~282~~ ~~281~~ 263 bytes

```
s->n->{var c=new char[s][s];for(var d:c)java.util.Arrays.fill(d,' ');for(int i=0,j=0,y=0,x=1,u=s-1,l=0;n-->0;c[j][i]=42,i+=x,j+=y,l+=i==l&x==0?1:0,u-=i==l&j==l&y<1?1:0)if(x!=0){var b=x>0?i<u:i>l;y=b?0:x;x=b?x:0;}else{var b=y>0?j<u:j>l;x=b?0:-y;y=b?y:0;}return c;}

```

A fun challenge!

Try it online here.

Thanks to Kevin Cruijssen for golfing 18 bytes.

Ungolfed version:

```
s -> n -> { // lambda taking two integer arguments in currying syntax
    var c = new char[s][s]; // the matrix containing the spiral
    for(var d : c) // for every row
        java.util.Arrays.fill(d, ' '); // fill it with spaces
    for(int i = 0, j = 0, // the coordinates of the next '*'
            y = 0, x = 1, // the direction to move in
            u = s-1, l = 0; // the upper and lower bounds
        n-- > 0; // decrecement the length of the spiral and repeat as many times
        c[j][i] = 42, // draw the '*', 42 is ASCII code
        i += x, j += y, // move to the next cell
        l += i == l & x == 0 ? 1 : 0, // adjust lower bound if necessary
        u -= i == l & j == l & y < 1 ? 1 : 0) // adjust upper bound if necessary
        if(x != 0) { // if moving in x direction
            var b = x > 0 ? i < u : i > l; // if we hit the bounds
            y = b ? 0 : x; // flip directions,
            x = b ? x : 0; // turning around
        } else { // if moving in y direction
            var b = y > 0 ? j < u : j > l; // if we hit the bounds
            x = b ? 0 : -y; // flip directions,
            y = b ? y : 0;  // turning around
        }
    return c; // return the matrix
}

```

# Answer
> 2 votes
# Kotlin, ~~361~~ ~~355~~ ~~353~~ 334 bytes

6 bytes saved thanks to Jonathan
2 bytes saved changing to when
19 bytes saved switching to lambda & tracking outer edges

```
{s:Int,n:Int->var a=Array(s,{_->Array(s,{_->' '})})
var r=0
var c=0
var d=0
var e=0
var f=1
var g=s-1
var h=g
for(i in 1..n){a[r][c]='*'
when(d){0->if(c<g)c++
else{d=1
r++
g--}
1->if(r<h)r++
else{d=2
c--
h--}
2->if(c>e)c--
else{d=3
r--
e++}
3->if(r>f)r--
else{d=0
c++
f++}}}
for(i in 0..s-1){for(j in 0..s-1)print(a[i][j])
println()}}

```

Try it online!

# Answer
> 2 votes
# JavaScript (Node.js), 167 164 163 bytes

* thanks to @Erik the Outgolfer and @nicael for spaces (3 bytes)
* thanks to @micha for join\`\`split`,` instead of map (1 byte)

```
(l,s)=>{a=(b=[...Array(l)]).map(x=>b.map(_=>" "))
for(d=1,x=y=D=0;s--;x+=d,y+=D)a[y][x]="*",(a[y+D]||[])[x+d]!=" "?[d,D]=[-D,d]:0
return a.join`
`.split`,`.join``}

```

Try it online!

---
Tags: code-golf, ascii-art
---


title: Quine...but shifted by one

text:
# Question
Title: Quine...but shifted by one
Referring to the printable ASCII character codes in decimal, we know that from 32 to 126 we have the printable characters with 32 being (space). Your challenge is to write a program using only characters from 32 to 125 (excluding 126) which when executed, prints its own source code except that each character in the source code has its ASCII code increased by one.

For example, if the source code was

```
main(){printf("Hello World");}

```

its output would be

```
nbjo)*|qsjoug)#Ifmmp!Xpsme#*<~

```

The following are forbidden:

* Reading/writing/using any external files or storage (including the internet)
* Reading/echoing your own source code
* Source codes with fewer than 2 characters (they are no fun). Must be greater than or equal to 2.

Making it a popularity contest where after waiting for at least two weeks, the answer, in any language, with the highest upvotes wins with the smaller character count being the tie-breaker.

# Answer
> 47 votes
**Python (27 characters)**

In the Python shell, the following script will output the desired result:

```
TzoubyFssps;!jowbmje!tzouby

```

Yes! it outputs:

```
SyntaxError: invalid syntax

```

# Answer
> 14 votes
## huh?, 5 characters

```
Ntbg

```

**Note that the 5th character is a space after `Ntbg`**. This is the same trick as in one of my previous answers. `Ntbg` is an invalid path, so the interpreter will output `Ouch!` You should run it like this:

```
huh.exe Ntbg

```

# Answer
> 8 votes
**PHP (351)**

I'm sure there's a better way to do this, as I am new to codegolfing, but here's my PHP solution:

```
function q(){$q=chr(39);$a=array('function q(){$q=chr(39);$a=array(',');@$r.=$a[0];foreach($a as$b)$r.=$q.$b.$q.",";$r=substr($r,0,-1);$r.=$a[1];for($i=0;$i<strlen($r);$i++)$r{$i}=chr(ord($r{$i})+1);return $r;}');@$r.=$a[0];foreach($a as$b)$r.=$q.$b.$q.",";$r=substr($r,0,-1);$r.=$a[1];for($i=0;$i<strlen($r);$i++)$r{$i}=chr(ord($r{$i})+1);return $r;}

```

Output:

```
gvodujpo!r)*|%r>dis)4:*<%b>bssbz)(gvodujpo!r)*|%r>dis)4:*<%b>bssbz)(-(*<A%s/>%b\1^<gpsfbdi)%b!bt%c*%s/>%r/%c/%r/#-#<%s>tvctus)%s-1-.2*<%s/>%b\2^<gps)%j>1<%j=tusmfo)%s*<%j,,*%s|%j~>dis)pse)%s|%j~*,2*<sfuvso!%s<~(*<A%s/>%b\1^<gpsfbdi)%b!bt%c*%s/>%r/%c/%r/#-#<%s>tvctus)%s-1-.2*<%s/>%b\2^<gps)%j>1<%j=tusmfo)%s*<%j,,*%s|%j~>dis)pse)%s|%j~*,2*<sfuvso!%s<~

```

# Answer
> 6 votes
## GolfScript, 15 chars

```
{`{)}%"/2+"}.1*

```

Output:

```
|a|*~&#03,#~/2+

```

Try it online.

A fairly straightforward solution based on the technique I used for my entry to the "rotating quine" challenge. The one tricky detail is that the character `~` (ASCII 126) is disallowed by the challenge rules, so I can't use it to execute my code block. Fortunately, `1*` can be used as a synonym of it.

**Explanation:**

The code block `{`{)}%"/2+"}` is duplicated by the `.`, and the second copy executed by `1*` (technically, a one-iteration loop), leaving the other copy on the stack. Inside the code block, ``` stringifies the code block, and `{)}%` loops over (the ASCII codes of) its characters, incrementing each by one. Finally, `"/2+"` pushes the literal string `/2+` (which is `.1*` shifted by one) onto the stack. At the end of the program, the GolfScript interpreter then automatically prints everything on the stack.

**Ps.** Yes, I know this is a rather than strict , but what else am I going to do with GolfScript — ASCII art? ;-)

# Answer
> 6 votes
## TI-BASIC, 10

For your TI-83/84 calculator!

```
DQQ9RXMS@W

```

Outputs:

```
ERR:SYNTAX

```

# Answer
> 3 votes
# JavaScript, 117 characters

I know it's not code golf but I golfed it anyway.

```
function f(){alert((f+';f()').split('').map(function(x){return String.fromCharCode(x.charCodeAt()+1)}).join(''))};f()

```

(I'm not reading my own source code; I'm simply using the `Function` object's `toString` function.)

# Answer
> 2 votes
# Java - 1331 bytes, 618 bytes and 504 bytes

Here it is in java. The cool thing is that it is pretty legible and flexible. You may experiment to change the `SHIFT` variable to 0 and it will be a quine. You may change it to whatever value you want, including negative values and it will shift the code accordingly.

```
public class Quinex {

    private static final int SHIFT = 1;

    private static String next(String now, boolean mangles) {
        String sb = "";
        for (char c : now.toCharArray()) {
            if (!mangles && c == 87) {
                sb += next(String.valueOf(SHIFT), true);
            } else {
                sb += (char) ((mangles ? c : c == 94 ? 10 : c == 64 ? 34 : c) + SHIFT);
            }
        }
        return sb;
    }

    public static void main(String... args) {
        System.out.println(next(TEXT, false) + next(TEXT, true) + new String(new char[] { 34, 59, 10, 125 }));
    }

    private static final String TEXT = "public class Quinex {^^    private static final int SHIFT = W;^^    private static String next(String now, boolean mangles) {^        String sb = @@;^        for (char c : now.toCharArray()) {^            if (!mangles && c == 87) {^                sb += next(String.valueOf(SHIFT), true);^            } else {^                sb += (char) ((mangles ? c : c == 94 ? 10 : c == 64 ? 34 : c) + SHIFT);^            }^        }^        return sb;^    }^^    public static void main(String... args) {^        System.out.println(next(TEXT, false) + next(TEXT, true) + new String(new char[] { 34, 59, 10, 125 }));^    }^^    private static final String TEXT = @";
}

```

However, the only drawback in the previous class are the line breaks, which are not permited in the question spec (are outside the range 32 to 125). So I give here a golfed version that is free of line breaks (and free of the quirks to handle them). You may edit the value of the `S` variable to change the shift. This has 618 bytes:

```
class Q{static String g(String p,int m){int S=1;String u="";for(char c:p.toCharArray()){if(m==0&&c==87){u+=g(String.valueOf(S),1);}else{u+=(char)((m>0?c:c==64?34:c)+S);}}return u;}public static void main(String[]y){System.out.println(g(T,0)+g(T,1)+new String(new char[]{34,59,125}));}static final String T="class Q{static String g(String p,int m){int S=W;String u=@@;for(char c:p.toCharArray()){if(m==0&&c==87){u+=g(String.valueOf(S),1);}else{u+=(char)((m>0?c:c==64?34:c)+S);}}return u;}public static void main(String[]y){System.out.println(g(T,0)+g(T,1)+new String(new char[]{34,59,125}));}static final String T=@";}

```

Surely, if we drop the fine adjustment of the offset and hardcode the value of the shift, we can do a completely golfed version with 504 bytes:

```
class Q{static String g(String p,int m){String u="";for(char c:p.toCharArray()){u+=(char)((m>0?c:c==64?34:c)+1);}return u;}public static void main(String[]y){System.out.println(g(T,0)+g(T,1)+new String(new char[]{34,59,125}));}static final String T="class Q{static String g(String p,int m){String u=@@;for(char c:p.toCharArray()){u+=(char)((m>0?c:c==64?34:c)+1);}return u;}public static void main(String[]y){System.out.println(g(T,0)+g(T,1)+new String(new char[]{34,59,125}));}static final String T=@";}

```

# Answer
> 1 votes
### Perl 5, 284 characters include the linefeeds

Not being allowed to use ~ made it a bit more tricky.

```
#!/usr/bin/perl
$_=<<X;
#!/usr/bin/perl
Y
\$a=\$_;
s/\\\\/\\\\\\\\/g;
s/\\\$/\\\\\\\$/g;
\$b=\$_;
\$_=\$a;
s/Y/\\\$\\_\\=\\<\\<X\\;\\n\${b}X/;
s/(.)/chr(ord(\$1)+1)/ge;
print;
X
$a=$_;
s/\\/\\\\/g;
s/\$/\\\$/g;
$b=$_;
$_=$a;
s/Y/\$\_\=\<\<X\;\n${b}X/;
s/(.)/chr(ord($1)+1)/ge;
print;

```

# Answer
> 1 votes
## Python, 99

```
s='import sys;sys.stdout.write("".join(chr(ord(c)+1)for c in a%(s,a)))';a='s=%r;a=%r;exec s';exec s

```

Output:

```
t>(jnqpsu!tzt<tzt/tuepvu/xsjuf)##/kpjo)dis)pse)d*,2*gps!d!jo!b&)t-b***(<b>(t>&s<b>&s<fyfd!t(<fyfd!t

```

This can be shortened to **75 chars**, but it will print a new line character after the output, technically breaking the rules:

```
s='print"".join(chr(ord(c)+1)for c in a%(s,a))';a='s=%r;a=%r;exec s';exec s

```

# Answer
> 1 votes
# Stax, 16 bytes

```
"{^m'#bL"{^m'#bL

```

Run and debug it

Adaption of the `"34bL"34bL` quine. Since now `"` becomes `#` which does not need to be escaped we can just include it in the string.

# Answer
> 0 votes
# Lua - 192

Pretty straightforward,

```
s=[[print((('s=['..'['..s..']'..']'..s):gsub('.',function(x)return string.char(x:byte()+1)end)))]]print((('s=['..'['..s..']'..'];'..s):gsub('.',function(x)return string.char(x:byte()+1)end)))

```

# Answer
> 0 votes
# C - 156

```
char*f="char*f=%c%s%c,q[200];i;main(){sprintf(q,f,34,f,34);while(q[i])q[i++]++;puts(q);}",q[200];i;main(){sprintf(q,f,34,f,34);while(q[i])q[i++]++;puts(q);}

```

Just the classic C quine with required modifications

P.S, apparently `sprintf(f,...,f,...)` is a segfault.

# Answer
> 0 votes
**JavaScript (276)**

Without using `.toString()`:

```
function q(){x=String.fromCharCode;y=x(39);a=['function q(){x=String.fromCharCode;y=x(39);a=[','];r=a[0]+y+a[0]+y+","+y+a[1]+y+a[1];q="";for(c in r)q+=x(r[c].charCodeAt(0)+1);return q;}'];r=a[0]+y+a[0]+y+","+y+a[1]+y+a[1];q="";for(c in r)q+=x(r[c].charCodeAt(0)+1);return q;}

```

# Answer
> 0 votes
## Ruby, 63

Darn, can't use a heredoc on this one.

```
s="s=%p;(s%%s).chars{|c|$><<c.succ}";(s%s).chars{|c|$><<c.succ}

```

Ruby has a native method `.succ` that does this on a character, and printing without a newline is shorter than printing with, so this works out pretty neatly.

# Answer
> 0 votes
# C, 153

```
main(a){char b[999];sprintf(b,a="main(a){char b[999];printf(a=%c%s%c,34,a,34);for(a=0;b[a];)b[a++]++;puts(b);}",34,a,34);for(a=0;b[a];)b[a++]++;puts(b);}

```

Another modification of the classic quine in c...

# Answer
> 0 votes
## \>\<\>, 16 bytes

```
" r:2+l?!;1+o50.

```

Try it here!

This is more-or-less just a standard quine in \>\<\> (without using the `g` instruction). The only differences are it doesn't read its own source-code and increments each character by 1 before outputting it.

**Outputs**

```
#!s;3,m@"<2,p61/

```

---

### \*\>\<\>, 15 bytes (non-competing)

```
" r:2+Ol?!;1+ou

```

Try it here!

# Answer
> 0 votes
# Tcl, 89 bytes

```
puts [join [lmap c [split [read [open $argv0]] ""] {format %c [expr [scan $c %c]+1]}] ""]

```

Try it online!

---

# Tcl, 89 bytes

```
puts [join [lmap c [split [read [open $argv0]] ""] {scan $c %c s;format %c [incr s]}] ""]

```

Try it online!

---

Two approaches; the same byte length!

# Answer
> 0 votes
# Haskell, 64 bytes

```
main=putStr$succ<$>s++show s;s="main=putStr$succ<$>s++show s;s="

```

Try it online!

# Answer
> 0 votes
## Perl 5, 55 bytes

```
$_=q{print chr(1+ord)for split//,"\$_=q{$_};eval"};eval

```

Try it online!

# Answer
> 0 votes
# J, 42 Bytes

```
(>:&.(u:inv)@,quote)'(>:&.(u:inv)@,quote)'

```

---
Tags: popularity-contest, quine
---


# Question
Title: Calculate the p-adic norm of a rational number
# Calculate the p-adic norm of a rational number

Write a function or a program, that takes 3 integers `m,n,p` (where `p` is a positive prime) as input, that outputs the p-adic norm (denoted by `|m/n|_p`) as a (completely reduced) fraction. Fermat is known to have only very small margins, but what is rather unknown is that he only had a very small computer screen. So try to make the code as short as possible for it to fit on Fermat's screen!

## Definition

Given a prime `p`, every fraction `m/n` can uniquely be written (ignoring the signs) as `(a/b)* p^e` such that `e` is a integer and `p` divides neither `a` nor `b`. The *p-adic norm* of `m/n` is `p^-e`. There is a special case, if the fraction is 0: `|0|_p = 0`.

The output format must be `x/y` (e.g. `1/3`; for integers both `10` or equivalently `10/1` is allowed, for negative numbers there must be a leading minus e.g. `-1/3`)

## Details

The program must use stdin/stdout, or just consist of a function that returns the rational number or string. You have to assume that the input `m/n` is not fully reduced. You can assume that `p` is a prime. The program has to be able to process integers between `-2^28` up to `2^28`, and should not take more than 10 seconds.

Built in factorization and prime checking functionalities are not allowed, as well as built in base conversatio, and built in function that calculate the p-adic valuation or norm.

# Examples (stolen from wikipedia):

```
x = m/n = 63/550 = 2^-1 * 3^2 * 5^-2 * 7 * 11^-1
|x|_2 = 2
|x|_3 = 1/9
|x|_5 = 25
|x|_7 = 1/7
|x|_11 = 11
|x|_13 = 1

```

# Interesting *trivia*

(Not necessary to know/read for this challenge, but perhaps nice to read as a motivation.)

(Please correct me if I use the wrong words, or something else is wrong, I am not used to talking about this in english.)

If you consider the rational numbers as a field, then the p-adic norm induces the p-adic metric `d_p(a,b) = |a-b|_p`. Then you can *complete* this field with regard to this metric, that means you can construct a new field where all cauchy sequences converge, which is a nice topological property to have. (Which e.g. the rational numbers do not have, but the reals do.) These *p-adic numbers* are as you might have guessed, used a lot in number theory.

Another interesting result is Ostrowski's theorem which basically says, any absolut value (as defined below) on the rational numbers is one of the following three:

* The trivial: `|x|=0 iff x=0, |x|=1 otherwise`
* The standard (real): `|x| = x if x>=0, |x| = -x if x<0`
* The p-adic (as we defined it).

An absolute value / a metric is just the generalization of what we consider a *distance*. A absolute value `|.|` satisfies following conditions:

* `|x| >= 0 and |x|=0 if x=0`
* `|xy| = |x| |y|`
* `|x+y| <= |x|+|y|`

Note that you can easily construct metrics from absolute values and vice versa: `|x| := d(0,x)` or `d(x,y) := |x-y|`, so they are almost the same if you can *add*/*substract*/*multiply* (that is in integral domains). You can of course define a metric on more general sets, without this structure.

# Answer
# Julia, ~~94~~ ~~80~~ 75 bytes

```
f(m,n,p)=(k=gcd(m,n)
g(m)=m%p>0?g(m÷p)p:1
m!=0?print(g(n÷k),/,g(m÷k)):0)

```

Note: using linefeeds in place of semicolons for readability - will work same either way.

This is quite simple - the `g(m,n)` function uses recursion and remainder (`%`) to extract the `p^n` factor from input `m`, with `n=1` as default and then multiplied by `p` on each step of the recursion, so that the output will be `p^n`. The code applies that to `n/gcd(m,n)`, and then to `m/gcd(m,n)` to obtain the appropriate expression. `k=gcd(m,n)` is used to avoid calculating the `gcd(m,n)` twice, to save characters. `m!=0` is a test to handle the case where `x=0`.

The output is of the form `N/1` or `1/N` as appropriate, where `N` is `p^e`.
> 3 votes

# Answer
## J, ~~35~~ 34 bytes

```
(,'/'&,)&":/@(%+./)@(]<.^+.|.@])x:

```

This is a binary verb that takes the prime `p` as its left argument, and the array `m n` as its right argument. It always prints the slash `/`, and returns `0/1` if `m = 0`. Use it like this:

```
  f =: (,'/'&,)&":/@(%+./)@(]<.^+.|.@])x:
  5 f 63 550
25/1

```

## Explanation

The `x:` turns on extended precision, since we're handling very large numbers. The rest of the code works as follows:

```
(,'/'&,)&":/@(%+./)@(]<.^+.|.@])
                        ^         Power: this gives the array p^n p^m
                         +.       Take element-wise GCD with
                           |.@]   the rotated array n m; this gives
                                  the largest powers of p that divide n and m
                      <.          Take element-wise minimum with
                     [            The array m n to handle the m=0 case correctly
              %+./                Divide this array by its GCD to get it to lowest terms
        &":/                      Convert both elements to strings
 ,'/'&,                           Insert the slash '/' between them

```
> 1 votes

# Answer
# CJam, 42 bytes

```
q~)\_:*g_sW<o@*28#f{{{_@\%}h;}:G~}_~Gf/'/*

```

THis finishes with an error (after printing 0) for input 0. Try it online in the CJam interpreter.
> 0 votes

# Answer
# Stax, 32 bytes

```
éE▌ΦΔΘao£╙)ΩuÅI~AAε3∞xC█&½╤%╩▌ïö

```

Run and debug it

Should be able to make it shorter. The native support for fraction by Stax is quite neat.

ASCII equivalent:

```
hY{y:+y|aEGsG-ys|**}0?}0{^scxHY%Cy/sWd

```
> 0 votes

---
Tags: code-golf, math, primes, rational-numbers
---